Engineering Optimization: Theory and Practice, Fourth Edition

192 Linear Programming II: Additional Topics and Extensions

4.3 Duality in Linear Programming

Associated with every linear programming problem, called theprimal, there is another

linear programming problem called itsdual. These two problems possess very inter-

esting and closely related properties. If the optimal solution to any one is known, the

optimal solution to the other can readily be obtained. In fact, it is immaterial which

problem is designated the primal since the dual of a dual is the primal. Because of

these properties, the solution of a linear programming problem can be obtained by

solving either the primal or the dual, whichever is easier. This section deals with

the primal–dual relations and their application in solving a given linear programming

problem.

4.3.1 Symmetric Primal–Dual Relations

A nearly symmetric relation between a primal problem and its dual problem can be

seen by considering the following system of linear inequalities (rather than equations).

Primal Problem.

a 11 x 1 +a 12 x 2 + · · · +a 1 nxn≥b 1

a 21 x 1 +a 22 x 2 + · · · +a 2 nxn≥b 2

..

. (4.17)
am 1 x 1 +am 2 x 2 + · · · +amnxn≥bm

c 1 x 1 +c 2 x 2 + · · · +cnxn=f

(xi≥ 0 ,i=1 ton,andf is to be minimized)

Dual Problem. As a definition, the dual problem can be formulated by transposing

the rows and columns of Eq. (4.17) including the right-hand side and the objective

function, reversing the inequalities and maximizing instead of minimizing. Thus by

denoting the dual variables asy 1 , y 2 ,... , ym, the dual problem becomes

a 11 y 1 +a 21 y 2 + · · · +am 1 ym≤c 1

a 12 y 1 +a 22 y 2 + · · · +am 2 xm≤c 2

..

. (4.18)

a 1 ny 1 +a 2 ny 2 + · · · +amnym≤cn

b 1 y 1 +b 2 y 2 + · · · +bmym=v

(yi≥ 0 ,i=1 tom,andvis to be maximized)

Equations (4.17) and (4.18) are calledsymmetric primal– dual pairsand it is easy to

see from these relations that the dual of the dual is the primal.