Engineering Optimization: Theory and Practice, Fourth Edition

210 Linear Programming II: Additional Topics and Extensions

SOLUTION Letx 1 , x 2 , x 3 , andx 4 denote the number of units of productsA, B, C,

andDproduced per day. Then the problem can be stated in standard form as follows:

Minimizef= − 45 x 1 − 001 x 2 − 03 x 3 − 05 x 4

subject to

7 x 1 + 01 x 2 + 4 x 3 + 9 x 4 ≤ 2001

3 x 1 + 04 x 2 +x 3 +x 4 ≤ 008

xi≥ 0 , i=1 to 4

By introducing the slack variablesx 5 ≥ and 0 x 6 ≥ , the problem can be stated in 0

canonical form and the simplex method can be applied. The computations are shown

in tableau form below:

Basic Variables Ratiobi/ais

variables x 1 x 2 x 3 x 4 x 5 x 6 −f bi forais> 0

x 5 7 10 4 9 1 0 0 1200 120

x 6 3 40 1 1 0 1 0 800 20←Smaller

one,x 6 leaves

Pivot element the basis

−f − 45 − 100 − 30 − 50 0 0 1 0

↑

Minimumcj< 0 ;x 2 enters the next basis

Result of pivot operation:

x 5 254 0 154 354 1 − 41 0 1000^400035 ←Smaller

one,x 5 leaves

Pivot element the basis

x 2 403 1 401 401 0 401 0 20 800

−f −^7520 −^552 −^9520 −^52 1 2000

↑

Minimumcj<0,x 4 enters the basis

Result of pivot operation:

x 4 57 0 37 1 354 − 351 0 4 , 35000 8003 ←Smaller

one,x 4 leaves

Pivot element the basis

x 2 352 1 701 0 − 3501 3509 0 1207 1200

−f −^2570 −^507038787152 , 7000

↑

Minimumcj<0,x 3 enters the basis