11.4. FINDING A BASIC FEASIBLE SOLUTION 239

are nonnegative. Suppose also that it can be done in such a way that x8 and x7 happento be 0. Then it will follow that x1, · · · ,x6 is a feasible solution for 11.18. Conversely, ifyou can find a feasible solution for 11.18, then letting x7 and x8 both equal zero, you haveobtained a feasible solution to 11.19. Since all variables are nonnegative, x7 and x8 bothequalling zero is equivalent to saying the minimum of z = x7 +x8 subject to the constraintsrepresented by the above augmented matrix equals zero. This has proved the followingsimple observation.

Observation 11.4.2 There exists a feasible solution to the constraints represented by theaugmented matrix of 11.18 and x≥ 0 if and only if the minimum of x7 + x8 subject to theconstraints of 11.19 and x≥ 0 exists and equals 0.

Of course a similar observation would hold in other similar situations. Now the pointof all this is that it is trivial to see a feasible solution to 11.19, namely x6 = 7,x7 = 3,x8 = 2and all the other variables may be set to equal zero. Therefore, it is easy to find an initialsimplex tableau for the minimization problem just described. First add the column and rowfor z 

2 1 −1 −1 0 0 1 0 0 31 1 1 0 −1 0 0 1 0 21 1 1 0 0 1 0 0 0 70 0 0 0 0 0 −1 −1 1 0

Next it is necessary to make the last two columns on the bottom left row into simplecolumns. Performing the row operation, this yields an initial simplex tableau,

2 1 −1 −1 0 0 1 0 0 31 1 1 0 −1 0 0 1 0 21 1 1 0 0 1 0 0 0 73 2 0 −1 −1 0 0 0 1 5

Now the algorithm involves getting rid of the positive entries on the left bottom row. Beginwith the first column. The pivot is the 2. An application of the simplex algorithm yieldsthe new tableau 

1 12 − 1

2 − 12 0 0 1

2 0 0 32

0 12

32

12 −1 0 − 1

2 1 0 12

0 12

32

12 0 1 − 1

2 0 0 112

0 12

32

12 −1 0 − 3

2 0 1 12

Now go to the third column. The pivot is the 3/2 in the second row. An application of thesimplex algorithm yields

1 23 0 − 1

3 − 13 0 1

313 0 5

30 1

3 1 13 − 2

3 0 − 13

23 0 1

30 0 0 0 1 1 0 −1 0 50 0 0 0 0 0 −1 −1 1 0

 (11.20)

and you see there are only nonpositive numbers on the bottom left column so the processstops and yields 0 for the minimum of z = x7+x8. As for the other variables, x1 = 5/3,x2 =