Engineering Optimization: Theory and Practice, Fourth Edition

214 Linear Programming II: Additional Topics and Extensions

Example 4.7 Find the effect of changingc 3 from − 3 0 to−24 in Example 4.5.

SOLUTION Herec 3 = and Eq. (4.43) gives that 6

c′ 1 =c 1 +c 1 − c 3 [a 21 β 32 +a 31 β 33 ]=^253 + 0 − 6 [3(− 151 )+ 7 ( 154 ) ]=−^53

c′ 4 =c 4 + c 4 −c 3 [a 24 β 32 +a 34 β 33 ]=^503 + 0 − 6 [1(− 151 )+ 9 ( 154 )]=^83

c′ 5 =c 5 + c 5 −c 3 [a 25 β 32 +a 35 β 33 ]=^223 + 0 − 6 [0(− 151 )+ 1 ( 154 )]=^8615

c′ 6 =c 6 + c 6 −c 3 [a 26 β 32 +a 36 β 33 ]=^23 + 0 − 6 [1(− 151 )+ 0 ( 154 )]=^1615

The change in the value of the objective function is given by Eq. (4.45) as

f=c 3 x 3 =

4800

3

so thatf= −

28 , 000

3

+

4800

3

= −

23 , 200

3

Sincec′ 1 is negative, we can bringx 1 into the basis. Thus we start with the optimal

tableau of the original problem with the new values of relative cost coefficients and

improve the solution according to the regular procedure.

Variables Ratiobi/aij

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

x 3 53 0 1^73154 − 151 0 8003 160 ←

Pivot element

x 2 301 1 0 − 301 − 1501 752 0 403 400

−f −^53 0 0^8386151615123 , 3200

↑

x 1 1 0 35 75 254 − 251 0 160

x 2 0 1 − 501 − 252 − 2503 2507 0 8

−f 0 0 1 5 6 1 1 8000

Since all the relative cost coefficients are nonnegative, the present solution is optimum

with

x 1 = 601 , x 2 = 8 (basic variables)

x 3 =x 4 =x 5 =x 6 = 0 (nonbasic variables)

fmin= − 8 000 and maximum profit=$8000

4.5.3 Addition of New Variables

Suppose that the optimum solution of a LP problem withnvariablesx 1 , x 2 ,... , xn

has been found and we want to examine the effect of adding some more variables

xn+k, k = 1 , 2 ,.. ., on the optimum solution. Let the constraint coefficients and the