The system of constraints (29.59)–(29.61) has 3 equations and 6 variables. Any
setting of the variables x1, x2, and x3 defines values for x4, x5, and x6; therefore,
we have an infinite number of solutions to this system of equations. A solution is
feasible if all of x1; x2; : : : ; x6 are nonnegative, and there can be an infinite number
of feasible solutions as well. The infinite number of possible solutions to a
system such as this one will be useful in later proofs. We focus on the basic solution:
set all the (nonbasic) variables on the right-hand side to 0 and then compute
the values of the (basic) variables on the left-hand side. In this example, the basic
solution is .xN1; xN2; : : : ; xN6/ D .0; 0; 0; 30; 24; 36/ and it has objective value
´ D .3 0/ C .1 0/ C .2 0/ D 0. Observe that this basic solution sets N xi D bi
for each i 2 B. An iteration of the simplex algorithm rewrites the set of equations
and the objective function so as to put a different set of variables on the righthand
side. Thus, a different basic solution is associated with the rewritten problem.
We emphasize that the rewrite does not in any way change the underlying linearprogramming
problem; the problem at one iteration has the identical set of feasible
solutions as the problem at the previous iteration. The problem does, however,
have a different basic solution than that of the previous iteration.