Engineering Optimization: Theory and Practice, Fourth Edition

234 Linear Programming II: Additional Topics and Extensions

According to the regular procedure of simplex method,λ 1 enters the next basis since

the cost coefficient ofλ 1 is most negative andz 2 leaves the basis since the ratiobi/ais

is smaller forz 2. However,λ 1 cannot enter the basis, asY 1 is already in the basis [to

satisfy Eqs. (E 4 )]. Hence we selectx 2 for entering the next basis. According to this

choice,z 2 leaves the basis. By carrying out the required pivot operation, we obtain the

following tableau:

Basic Variables bi/ais

variables x 1 x 2 λ 1 λ 2 θ 1 θ 2 Y 1 Y 2 z 1 z 2 w bi forais> 0

Y 1 52 0 −^14 1 0^14 1 0 0 −^14 0 6^125 ←Smaller

one

Y 2 −1 0 1 −4 0 −1 0 1 0 1 0 0

z 1 1 0^52 − 1 − 1 −^12 0 0 1^12 0 4 4

x 2 −^12114 −1 0 −^14 0 0 0^14 0 0

−w −1 0 −^52 1 1^12 0 0 0^121 − 4

↑ ↑

x 1 selected to Most negative

enter the basis

This tableau shows thatλ 1 has to enter the basis andY 2 orx 2 has to leave the basis.

However,λ 1 cannot enter the basis sinceY 1 is already in the basis [to satisfy the

requirement of Eqs. (E 4 )]. Hencex 1 is selected to enter the basis and this givesY 1 as

the variable that leaves the basis. The pivot operation on the element^52 results in the

following tableau:

Basic Variables bi/ais

variables x 1 x 2 λ 1 λ 2 θ 1 θ 2 Y 1 Y 2 z 1 z 2 w bi forais> 0

x 1 1 0 − 101 25 0 101 25 0 0 − 101 0 125

Y 2 0 0 109 −^1850 − 109 52 1 0 109 0 125 83

z 1 0 0^135 −^75 − 1 −^35 −^25 0 1^35085138 ←Smaller

one

x 2 0 1^15 −^450 −^1515 0 0^150656

−w 0 0 −^1357513525 0 0^251 −^85

↑

Most negative

From this tableau we find thatλ 1 enters the basis (this can be permitted this time since

Y 1 is not in the basis) andz 1 leaves the basis. The necessary pivot operation gives the

following tableau: