Engineering Optimization: Theory and Practice, Fourth Edition

190 Linear Programming II: Additional Topics and Extensions

Table 4.9 Tableau at the Beginning of Cycle 1

Columns of the original canonical form

Basic variables x 4 x 5 x 6 −f

Value of the basic

variable x 3 a

x 2 1 0 0 0 2 a 23 = − 1

x 5 1 1 0 0 8 a 53 = 4

Pivot element

x 6 − 1 0 1 1 4 a 63 = 2

←Inverse of the basis=[βij]→

−f 2 = −π 1 0 = −π 2 0 = −π 3 1 4 c 3 = − 3

aThis column is entered at the end of step 5.

where the negative values ofπ 1 , π 2 , andπ 3 are given by the row of−f in

Table 4.9, andaij andciare given in Table 4.6. Hereπ 1 = − 2 ,π 2 = , and 0

π 3 =. 0

c 1 =c 1 −π 1 a 11 = − 1 −(− 2 )( 2 )= 3

c 2 =c 2 −π 1 a 12 = − 2 −(− 2 )( 1 )= 0

c 3 =c 3 −π 1 a 13 = − 1 −(− 2 )(− 1 )= − 3

c 4 =c 4 −π 1 a 14 = 0 −(− 2 )( 1 )= 2

c 5 =c 5 −π 1 a 15 = 0 −(− 2 )( 0 )= 0

c 6 =c 6 −π 1 a 16 = 0 −(− 2 )( 0 )= 0

Enter these values in the second row of Table 4.8.

Step 4Since all cj are not ≥ 0 , the current solution is not optimum. Hence

select a variable (xs) to enter the basic set in the next cycle such that

cs= inm (cj< 0 )=c 3 in this case. Therefore,xs=x 3.

Step 5Compute the elements of thexscolumn as

As=[βij]As

where [βij] is available in Table 4.9 andAsin Table 4.6:

A 3 =







a 23

a 53

a 63







=





1 0 0

1 1 0

−1 0 1











− 1

5

1







=







− 1

4

2







Enter these elements and the value ofcs=c 3 = − 3 in the last column of

Table 4.9.

Step 6Find the variable (xr) to be dropped from the basic set in the next cycle as

br

ars

= min

ais> 0

(

bi

ais

)