Engineering Optimization: Theory and Practice, Fourth Edition

4.2 Revised Simplex Method 185

Table 4.3 Relative Cost Factordjorcj

Variablexj
Cycle number x 1 x 2 · · · xn xn+ 1 xn+ 2 · · · xn+m

Phase I













0

1

..

.

l

d 1 d 2 · · · dn 0 0 · · · 0

Use the values ofσi(if phase I) orπi(if phase II) of the

current cycle and compute

dj=dj−(σ 1 a 1 j+σ 2 a 2 j+ · · · +σmamj)

or

Phase II









l+ 1

l+ 2

..

.

cj=cj−(π 1 a 1 j+π 2 a 2 j+ · · · +πmamj)

Enterdjorcjin the row corresponding to the current cycle

and choose the pivot columnssuch thatds=mindj

(if phase I) orcs=mincj(if phase II)

Table 4.4 Tableau at the Beginning of Cyclek

Columns of the original canonical form

Basic variable xn+ 1 · · ·xn+m −f −w

Value of the basic

variable xsa

[βij]=[ai,n+j]

←Inverse of the basis→

xj 1 β 11 · · ·β 1 m b 1 a 1 s=

∑m

i= 1

β 1 iais

..

.

..

.

..

.

..

.

xj r βr 1 · · ·βrm br ars=

∑m

i= 1

βriais

..

.

..

.

..

.

..

.

xj m βm 1 · · ·βmm bm ams=

∑m

i= 1

βmiais

−f −π 1 · · · −πm 1 −f 0 cs=cs−

∑m

i= 1

πiais

(−πj= +cn+j)

−w −σ 1 · · · −σm 1 −w 0 ds=ds−

∑m

i= 1

σiais

(−σj= +dn+j)

aThis column is blank at the start of cyclekand is filled up only at the end of cyclek.

If somedj< , choose 0 xsas the variable to enter the basis in the next

cycle in place of the presentrth basic variable (rwill be determined later) such

that

ds= inm (dj< 0 )

On the other hand, if the current cycle corresponds to phase II, find whether

allcj≥. If all 0 cj≥ , the current basic feasible solution is also an optimal 0

solution and hence terminate the process. If somecj< , choose 0 xsto enter