Engineering Optimization: Theory and Practice, Fourth Edition

198 Linear Programming II: Additional Topics and Extensions

Step 1Write the system of equations (E 1 ) in tableau form:

Basic Variables

variables x 1 x 2 x 3 x 4 x 5 x 6 −f bi

x 3 − 1 0 1 0 0 0 0 − 2. 5

x 4 0 −1 0 1 0 0 0 − 6

x 5 − 2 −1 0 0 1 0 0 − 17 ←Minimum,

pivot row

Pivot element

x 6 − 1 −1 0 0 0 1 0 − 12

−f 20 16 0 0 0 0 1 0

Select the pivotal rowrsuch that

br= inm (bi< 0 )=b 3 = − 17

in this case. Hencer=3.

Step 2Select the pivotal columnsas

cs

−ars

= min

arj< 0

(

cj

−arj

)

Since

c 1

−a 31

=

20

2

= 10 ,

c 2

−a 32

=

16

1

= 16 , and s= 1

Step 3The pivot operation is carried ona 31 in the preceding table, and the result is

as follows:

Basic Variables

variables x 1 x 2 x 3 x 4 x 5 x 6 −f bi

x 3 0 12 1 0 −^12006

x 4 0 − 1 0 1 0 0 0 − 6 ←Minimum,

pivot row

Pivot element

x 1 1 12 0 0 −^1200172

x 6 0 −^1200 −^1210 −^72

−f 0 6 0 0 10 0 1 − 170

Step 4Since some of thebiare < 0 , the present solution is not optimum. Hence we

proceed to the next iteration.

Step 1The pivot row corresponding to minimum (bi< ) can be seen to be 2 in the 0

preceding table.