230 CHAPTER 11. LINEAR PROGRAMMING

Now stop. The maximum value is 10. This is an easy enough problem to do geometricallyand so you can easily verify that this is the right answer. It occurs when x4 = x5 = 0,x1 =2,x2 = 2,x3 = 3.

11.3.2 MinimumsHow does it differ if you are finding a minimum? From a basic feasible solution, a simplextableau of the following form has been obtained in which the simple columns for the basicvariables, xB are listed first and b≥ 0.(

I F 0 b0 c 1 z0

)(11.14)

Let x0i = bi for i = 1, · · · ,m and x0

i = 0 for i > m. Then(x0,z0

)is a solution to the above

system and since b≥ 0, it follows(x0,z0

)is a basic feasible solution. So far, there is no

change.Suppose first that some ci > 0 and Fji ≤ 0 for each j. Then let x′F consist of changing xi

by making it positive but leaving the other entries of xF equal to 0. Then from the bottomrow,

z =−cixi + z0

and you let x′B = b− Fx′F ≥ 0. Thus the constraints continue to hold when xi is madeincreasingly positive and it follows from the above equation that there is no minimum forz. You stop when this happens.

Next suppose c≤ 0. Then in this case, z = z0− cxF and from the constraints, xF ≥ 0and so −cxF ≥ 0 and so z0 is the minimum value and you stop since this is what you arelooking for.

What do you do in the case where some ci > 0 and some Fji > 0? In this case, you usethe simplex algorithm as in the case of maximums to obtain a new simplex tableau in whichz0′ is smaller. You choose Fji the same way to be the positive entry of the ith column suchthat bp/Fpi ≥ b j/Fji for all positive entries, Fpi and do the same row operations. Now thistime,

z0′ = z0− ci

(b j

Fji

)< z0

As in the case of maximums no problem can occur and the process will converge unlessyou have the degenerate case in which some b j = 0. As in the earlier case, this is mostunfortunate when it occurs. You see what happens of course. z0 does not change and thealgorithm just delivers different values of the variables forever with no improvement.

To summarize the geometrical significance of the simplex algorithm, it takes you fromone corner of the feasible region to another. You go in one direction to find the maximumand in another to find the minimum. For the maximum you try to get rid of negative entriesof c and for minimums you try to eliminate positive entries of c, where the method ofelimination involves the auspicious use of an appropriate pivot element and row operations.

Now return to Example 11.2.2. It will be modified to be a maximization problem.

Example 11.3.2 Maximize z = x1− x2 subject to the constraints,

x1 +2x2 ≤ 10,x1 +2x2 ≥ 2,

and 2x1 + x2 ≤ 6,xi ≥ 0.