Engineering Optimization: Theory and Practice, Fourth Edition

3.10 Two Phases of the Simplex Method 155

This array can be rewritten as a canonical system with basic variables asy 1 ,

y 2 , −f,and−wby subtracting the sum of the first two equations of(E 2 ) romf

the last equation of(E 2 ) Thus the last equation of. (E 2 ) ecomesb

− 4 x 1 + 2 x 2 − 5 x 3 − 5 x 4 + 0 x 5 − w=− 2 (E 3 )

Since this canonical system [first three equations of(E 2 ) and, (E 3 ) provides]

an initial basic feasible solution, phase I of the simplex method can be started.

The phase I computations are shown below in tableau form.

Artificial Value of
Basic Admissible variables variables b′′i/a′′isfor
variables x 1 x 2 x 3 x 4 x 5 y 1 y 2 b′′i ais′′> 0

y 1 3 − 3 4 2

Pivot

element

− 1 1 0 0 0 ←Smaller value

(y 1 drops from

next basis)

y 2 1 1 1 3 1 0 1 (^223)
−f 2 3 2 − 1 1 0 0 0
−w − 4 2 − 5 − 5 0 0 0 − 2
↑ ↑
Most negative
Since there is a tie between d 3 ′′ andd 4 ′′, d 4 ′′is selected arbitrarily as the most
negatived′′ifor pivoting (x 4 enters the next basis).
Result of pivoting:
x 4 32 −^3221 −^121200
y 2 −^72112
Pivot
element
− 5 0 52 −^3212111 ←y 2 drops
from next
basis
−f^723240121200
−w^72 −^11250 −^52520 − 2
↑
Most negativedi′′(x 2 enters next basis)
Result of pivoting (since y 1 and y 2 are dropped from basis, the columns cor-
responding to them need not be filled):
x 4 116 0 117 1 112 Dropped 116 62
x 2 − 117 1 −^1011011511445
−f^98220118220 − 224 − 116
−w 0 0 0 0 0 0