Engineering Optimization: Theory and Practice, Fourth Edition

4.3 Duality in Linear Programming 197

2.We can see that the primal will not have a feasible solution when allarj are

nonnegativefrom the following reasoning. Let (x 1 , x 2 ,... , xm) be the set of

basic variables. Then therth basic variable,xr, can be expressed as

xr=br−

∑n

j=m+ 1

arjxj

It can be seen that ifbr< and 0 arj≥ for all 0 j, xrcannot be made non-

negative for any nonnegative value ofxj. Thus the primal problem contains

an equation (therth one) that cannot be satisfied by any set of nonnegative

variables and hence will not have any feasible solution.

The following example is considered to illustrate the dual simplex method.

Example 4.3
Minimizef= 20 x 1 + 61 x 2

subject to

x 1 ≥ 2. 5

x 2 ≥ 6

2 x 1 +x 2 ≥ 71

x 1 +x 2 ≥ 21

x 1 ≥ 0 ,x 2 ≥ 0

SOLUTION By introducing the surplus variablesx 3 , x 4 , x 5 , andx 6 , the problem can
be stated in canonical form as
Minimizef
with

−x 1 +x 3 = − 2. 5

−x 2 +x 4 = − 6

− 2 x 1 −x 2 +x 5 = − 17

−x 1 −x 2 +x 6 = − 12

20 x 1 + 61 x 2 −f = 0

xi≥ 0 , i=1 to 6

(E 1 )

The basic solution corresponding to (E 1 ) is infeasible since x 3 = − 2. 5 ,x 4 =
− 6 ,x 5 = − 17,and x 6 = − 1 2. However, the objective equation shows optimality
since the cost coefficients corresponding to the nonbasic variables are nonnegative
(c 1 = 02 ,c 2 = 6). This shows that the solution is infeasible to the primal but feasible 1
to the dual. Hence the dual simplex method can be applied to solve this problem as
follows.