Engineering Optimization: Theory and Practice, Fourth Edition

144 Linear Programming I: Simplex Method

Example 3.4

MaximizeF=x 1 + 2 x 2 +x 3

subject to

2 x 1 +x 2 −x 3 ≤ 2

− 2 x 1 +x 2 − 5 x 3 ≥ − 6

4 x 1 +x 2 +x 3 ≤ 6

xi≥ 0 , i= 1 , 2 , 3

SOLUTION We first change the sign of the objective function to convert it to a

minimization problem and the signs of the inequalities (where necessary) so as to

obtain nonnegative values ofbi (to see whether an initial basic feasible solution can

be obtained readily). The resulting problem can be stated as

Minimizef= −x 1 − 2 x 2 −x 3

subject to

2 x 1 +x 2 −x 3 ≤ 2

2 x 1 −x 2 + 5 x 3 ≤ 6

4 x 1 +x 2 +x 3 ≤ 6

xi≥ 0 , i=1 to 3

By introducing the slack variablesx 4 ≥ , 0 x 5 ≥ , and 0 x 6 ≥ , the system of equations 0

can be stated in canonical form as

2 x 1 + x 2 − x 3 + x 4 = 2

2 x 1 − x 2 + 5 x 3 + x 5 = 6

4 x 1 + x 2 + x 3 + x 6 = 6

−x 1 − 2 x 2 − x 3 −f = 0

(E 1 )

wherex 4 ,x 5 ,x 6 , and −f can be treated as basic variables. The basic solution corre-

sponding to Eqs.(E 1 ) s given byi

x 4 = 2 , x 5 = 6 , x 6 = 6 (basic variables)

x 1 =x 2 =x 3 = 0 (nonbasic variables) (E 2 )

f= 0

which can be seen to be feasible.

Since the cost coefficients corresponding to nonbasic variables in Eqs.(E 1 ) rea

negative (c 1 ′′= − 1 ,c′′ 2 = − 2 ,c′′ 3 = − 1 ), the present solution given by Eqs.(E 2 ) s noti

optimum. To improve the present basic feasible solution, we first decide the variable

(xs) to be brought into the basis as

c′′s= inm (c′′j< 0 )=c′′ 2 = − 2