Engineering Optimization: Theory and Practice, Fourth Edition

4.2 Revised Simplex Method 189

Table 4.8 Relative Cost Factorscj

Variablexj

Cycle number x 1 x 2 x 3 x 4 x 5 x 6

Phase II

Cycle 0 − 1 − 2 − 1 0 0 0

Cycle 1 3 0 − 3 2 0 0

Cycle 2 6 0 0 114 34 0

Step 4Find whether allcj≥ for optimality. The present basic feasible solution is 0
not optimal since somecj are negative. Hence select a variablexsto enter
the basic set in the next cycle such thatcs= inm (cj< 0 )=c 2 in this case.
Therefore,x 2 enters the basic set.
Step 5Compute the elements of thexscolumn as

As=[βij]As

where [βij] is available in Table 4.7 andAsin Table 4.6.

A 2 = AI 2 =







1

− 1

1







These elements, along with the value ofc 2 , are entered in the last column of
Table 4.7.
Step 6Select a variable (xr) o be dropped from the current basic set ast

br

ars

= min

ais> 0

(

bi

ais

)

In this case,

b 4

a 42

=

2

1

= 2

b 6

a 62

=

6

1

= 6

Therefore, xr=x 4.

Step 7To bringx 2 into the basic set in place ofx 4 , pivot onars=a 42 in Table 4.7.
Enterthe result as shown in Table 4.9, keeping its last column blank. Since a
new cycle has to be started, we go to step 3.
Step 3The relative cost factors are calculated as

cj=cj −(π 1 a 1 j+π 2 a 2 j+π 3 a 3 j)