3.9 Simplex Algorithm 149
Result of pivoting:
x 3 8 0 1 −^1200 1,500
x 2 104 1 0 101 0 0 200
x 5 108 0 0 − 103 1 0 300
−f 0 0 0 10 0 1 20,000
Since all c′′i≥ , the present solution is optimum. The optimum values are 0
given by
x 2 = 002 , x 3 = 5001 , x 5 = 003 (basic variables)
x 1 =x 4 = 0 (nonbasic variables)
fmin= − 20 , 000
Important note:It can be observed from the last row of the preceding tableau that
the cost coefficient corresponding to the nonbasic variablex 1 (c′′ 1 ) s zero. This is ani
indication that an alternative solution exists. Herex 1 can be brought into the basis and
the resulting new solution will also be an optimal basic feasible solution. For example,
introducingx 1 into the basis in place ofx 3 (i.e., by pivoting ona′′ 13 ) we obtain the,
new canonical system of equations as shown in the following tableau:
Basic Variables b
′′
i/a
′′
isfor
variables x 1 x 2 x 3 x 4 x 5 −f bi′′ ais′′> 0
x 1 1 0 18 − 161 0 0 15008
x 2 0 1 − 201 18 0 0 125
x 5 0 0 − 101 −^1410150
−f 0 0 0 10 0 1 20,000
The solution corresponding to this canonical form is given by
x 1 =^15008 , x 2 = 251 , x 5 = 501 (basic variables)
x 3 =x 4 = 0 (nonbasic variables)
fmin= − 20 , 000
Thus the value off has not changed compared to the preceding value sincex 1 has a
zero cost coefficient in the last row of the preceding tableau. Once two basic (optimal)
feasible solutions, namely,
X 1 =
0
200
1500
0
300
and X 2 =
1500
8
125
0
0
150