Engineering Optimization: Theory and Practice, Fourth Edition

4.3 Duality in Linear Programming 193

4.3.2 General Primal–Dual Relations

Although the primal–dual relations of Section 4.3.1 are derived by considering a system

of inequalities in nonnegative variables, it is always possible to obtain the primal–dual

relations for a general system consisting of a mixture of equations, less than or greater

than type of inequalities, nonnegative variables or variables unrestricted in sign by

reducing the system to an equivalent inequality system of Eqs. (4.17). The correspon-

dence rules that are to be applied in deriving the general primal–dual relations are

given in Table 4.11 and the primal–dual relations are shown in Table 4.12.

4.3.3 Primal–Dual Relations When the Primal Is in Standard Form

Ifm∗= mandn∗= n,primal problem shown in Table 4.12 reduces to the standard

form and the general primal–dual relations take the special form shown in Table 4.13.

It is to be noted that the symmetric primal–dual relations, discussed in Section 4.3.1,

can also be obtained as a special case of the general relations by settingm∗= and 0

n∗= nin the relations of Table 4.12.

Table 4.11 Correspondence Rules for Primal–Dual Relations

Primal quantity Corresponding dual quantity

Objective function: MinimizecTX MaximizeYTb

Variablexi≥ 0 ith constraintYTAi≤ci(inequality)

Variablexiunrestricted in sign ith constraintYTAi=ci(equality)

jth constraint,AjX=bj(equality) jth variableyjunrestricted in sign

jth constraint,AjX≥bj(inequality) jth variableyj≥ 0

Coefficient matrixA≡[A 1.. .Am] Coefficient matrixAT≡[A 1 ,... ,Am]T

Right-hand-side vectorb Right-hand-side vectorc

Cost coefficientsc Cost coefficientsb

Table 4.12 Primal–Dual Relations

Primal problem Corresponding dual problem

Minimizef=

∑n

i= 1

cixisubject to Maximizev=

∑m

i= 1

yibisubject to

∑n

j= 1

aijxj=bi, i= 1 , 2 ,... , m∗

∑m

i= 1

yiaij=cj, j=n∗+ 1 , n∗+2,

∑n

j= 1

aijxj≥bi, i=m∗+ 1 , m∗+2,... , n

... , m

∑m

i= 1

yiaij≤cj, j= 1 , 2 ,... , n∗

where where

xi≥ 0 , i= 1 , 2 ,... , n∗; yi≥ 0 , i=m∗+ 1 , m∗+ 2 ,... , m;

and and

xiunrestricted in sign,i=n∗+ 1 , yiunrestricted in sign,i= 1 , 2 ,... , m∗

n∗+ 2 ,... , n