228 CHAPTER 11. LINEAR PROGRAMMING

variable.) Now permuting the columns and variables, yields(I F ′ 0 b′

0 c′ 1 z0′

)

where z0′ ≥ z0 because z0′ = z0−ci

(b jFji

)and ci < 0. If b′ ≥ 0, you are in the same position

you were at the beginning but now z0 is larger. Now here is the important thing. Youdon’t pick just any Fji when you do these row operations. You pick the positive one forwhich the row operation results in b′ ≥ 0. Otherwise the obvious basic feasible solutionobtained by letting x′F = 0 will fail to satisfy the constraint that x≥ 0.

How is this done? You need

b′k ≡ bk−Fkib j

Fji≥ 0 (11.12)

for each k = 1, · · · ,m or equivalently,

bk ≥Fkib j

Fji. (11.13)

Now if Fki ≤ 0 the above holds. Therefore, you only need to check Fpi for Fpi > 0. Thepivot, Fji is the one which makes the quotients of the form

bp

Fpi

for all positive Fpi the smallest. This will work because for Fki > 0,

bp

Fpi≤ bk

Fki⇒ bk ≥

Fkibp

Fpi

Having gotten a new simplex tableau, you do the same thing to it which was just done andcontinue. As long as b > 0, so you don’t encounter the degenerate case, the values for zassociated with setting xF = 0 keep getting strictly larger every time the process is repeated.You keep going until you find c≥ 0. Then you stop. You are at a maximum. Problems canoccur in the process in the so called degenerate case when at some stage of the processsome b j = 0. In this case you can cycle through different values for x with no improvementin z. This case will not be discussed here.

Example 11.3.1 Maximize 2x1 + 3x2 subject to the constraints x1 + x2 ≥ 1,2x1 + x2 ≤6,x1 +2x2 ≤ 6, x1,x2 ≥ 0.

The constraints are of the form

x1 + x2− x3 = 12x1 + x2 + x4 = 6x1 +2x2 + x5 = 6

where the x3,x4,x5 are the slack variables. An augmented matrix for these equations is ofthe form  1 1 −1 0 0 1

2 1 0 1 0 61 2 0 0 1 6

