Engineering Optimization: Theory and Practice, Fourth Edition

4.3 Duality in Linear Programming 199

Step 2Sincea 22 is the only negative coefficient, it is taken as the pivot element.
Step 3The result of pivot operation ona 22 in the preceding table is as follows:

Basic Variables

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

x 3 0 0 1 12 −^12003

x 2 0 1 0 − 1 0 0 0 6

x 1 1 0 0 12 −^1200112

x 6 0 0 0 −^12 −^1210 −^12 ←Minimum,

pivot row

Pivot element

−f 0 0 0 6 10 0 1 − 206

Step 4Since allbiare not ≥ 0 , the present solution is not optimum. Hence we go to
the next iteration.
Step 1The pivot row (corresponding to minimumbi≤ ) can be seen to be the fourth 0
row.
Step 2Since
c 4
−a 44

= 2 and 1

c 5

−a 45

= 02

the pivot column is selected ass=4.
Step 3The pivot operation is carried ona 44 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 0 1 0 − (^11052)
x 2 0 1 0 0 1 − 2 0 7
x 1 1 0 0 0 − 1 1 0 5
x 4 0 0 0 1 1 − 2 0 1
−f 0 0 0 0 4 12 1 − 212
Step 4Since allbiare ≥ 0 , the present solution is dual optimal and primal feasible.
The solution is
x 1 = 5 , x 2 = 7 , x 3 =^52 , x 4 = 1 (dual basic variables)
x 5 =x 6 = 0 (dual nonbasic variables)
fmin= 122