Kenneth Kuttler

11.3. THE SIMPLEX ALGORITHM 227

11.3 The Simplex Algorithm11.3.1 MaximumsThe simplex algorithm takes you from one basic feasible solution to another while maxi-mizing or minimizing the function you are trying to maximize or minimize. Algebraically,it takes you from one simplex tableau to another in which the lower right corner eitherincreases in the case of maximization or decreases in the case of minimization.

I will continue writing the simplex tableau in such a way that the simple columns havingonly one entry nonzero are on the left. As explained above, this amounts to permuting thevariables. I will do this because it is possible to describe what is going on without onerousnotation. However, in the examples, I won’t worry so much about it. Thus, from a basicfeasible solution, a simplex tableau of the following form has been obtained in which thecolumns for the basic variables, xB are listed first and b≥ 0.(

I F 0 b0 c 1 z0

)(11.10)

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.

If ci < 0 for some i, and if Fji ≤ 0 so that a whole column of

(Fc

)is ≤ 0 with the

bottom entry < 0, then letting xi be the variable corresponding to that column, you couldleave all the other entries of xF equal to zero but change xi to be positive. Let the newvector be denoted by x′F and letting x′B = b−Fx′F it follows(

x′B)

k = bk−∑j

Fk j (xF) j

= bk−Fkixi ≥ 0

Now this shows (x′B,x′F) is feasible whenever xi > 0 and so you could let xi become arbi-trarily large and positive and conclude there is no maximum for z because

z = (−ci)xi + z0 (11.11)

If this happens in a simplex tableau, you can say there is no maximum and stop.What if c≥ 0? Then z = z0 − cxF and to satisfy the constraints, you need xF ≥ 0.

Therefore, in this case, z0 is the largest possible value of z and so the maximum has beenfound. You stop when this occurs. Next I explain what to do if neither of the above stoppingconditions hold.

The only case which remains is that some ci < 0 and some Fji > 0. You pick a column

(Fc

)in which ci < 0, usually the one for which ci is the largest in absolute value. You

pick Fji > 0 as a pivot element, divide the jth row by Fji and then use to obtain zeros aboveFji and below Fji, thus obtaining a new simple column. This row operation also makesexactly one of the other simple columns into a nonsimple column. (In terms of variables,it is said that a free variable becomes a basic variable and a basic variable becomes a free

11.3. THE SIMPLEX ALGORITHM 22711.3. The Simplex Algorithm11.3.1 MaximumsThe simplex algorithm takes you from one basic feasible solution to another while maxi-mizing or minimizing the function you are trying to maximize or minimize. Algebraically,it takes you from one simplex tableau to another in which the lower right corner eitherincreases in the case of maximization or decreases in the case of minimization.I will continue writing the simplex tableau in such a way that the simple columns havingonly one entry nonzero are on the left. As explained above, this amounts to permuting thevariables. I will do this because it is possible to describe what is going on without onerousnotation. However, in the examples, I won’t worry so much about it. Thus, from a basicfeasible solution, a simplex tableau of the following form has been obtained in which thecolumns for the basic variables, xz are listed first and b > 0.I F 0b(; 4 | (11.10)Let x? = b; for i= 1,---,m and x? = 0 fori > m. Then (x°, 2°) is a solution to the abovesystem and since b > 0, it follows (x?, 2°) is a basic feasible solution.FIf c; < 0 for some i, and if Fj; < 0 so that a whole column of is < 0 with thecbottom entry < 0, then letting x; be the variable corresponding to that column, you couldleave all the other entries of xp equal to zero but change x; to be positive. Let the newvector be denoted by x’, and letting x, = b — Fx’, it follows(xz), = be — Voi (xr);J= by — Fux; = 0Now this shows (x},,x/,) is feasible whenever x; > 0 and so you could let x; become arbi-trarily large and positive and conclude there is no maximum for z becausez= (—ci)xi+2° (11.11)If this happens in a simplex tableau, you can say there is no maximum and stop.What if c > 0? Then z = 2° — exp and to satisfy the constraints, you need xr > 0.Therefore, in this case, z° is the largest possible value of z and so the maximum has beenfound. You stop when this occurs. Next I explain what to do if neither of the above stoppingconditions hold.The only case which remains is that some c; < 0 and some Fj; > 0. You pick a columnFin ( in which c; < 0, usually the one for which c; is the largest in absolute value. Youcpick F;; > 0 as a pivot element, divide the j'" row by F ji and then use to obtain zeros aboveFj; and below F;;, thus obtaining a new simple column. This row operation also makesexactly one of the other simple columns into a nonsimple column. (In terms of variables,it is said that a free variable becomes a basic variable and a basic variable becomes a free