Engineering Optimization: Theory and Practice, Fourth Edition

194 Linear Programming II: Additional Topics and Extensions

Table 4.13 Primal–Dual Relations Wherem∗=mandn∗=n

Primal problem Corresponding dual problem

Minimizef=

∑n

i= 1

cixi Maximizeν=

∑m

i= 1

biyi

subject to subject to

∑n

j= 1

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

∑m

i= 1

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

where where

xi≥ 0 , i= 1 , 2 ,... , n yiis unrestricted in sign,i= 1 , 2 ,· · ·, m

In matrix form In matrix form

Minimizef=cTX Maximizeν=YTb

subject to subject to

AX=b ATY≤c

where where

X≥ 0 Yis unrestricted in sign

Example 4.2 Write the dual of the following linear programming problem:

Maximizef= 50 x 1 + 001 x 2

subject to

2 x 1 +x 2 ≤ 2501

2 x 1 + 5 x 2 ≤ 0001

2 x 1 + 3 x 2 ≤ 009

x 2 ≤ 501















n= 2 , m= 4

where

x 1 ≥ 0 and x 2 ≥ 0

SOLUTION Lety 1 , y 2 , y 3 , andy 4 be the dual variables. Then the dual problem can

be stated as

Minimizeν= 1250 y 1 + 0001 y 2 + 009 y 3 + 501 y 4

subject to

2 y 1 + 2 y 2 + 2 y 3 ≥ 05

y 1 + 5 y 2 + 3 y 3 +y 4 ≥ 001

wherey 1 ≥ 0 , y 2 ≥ 0 , y 3 ≥ 0 ,andy 4 ≥ 0.

Notice that the dual problem has a lesser number of constraints compared to the

primal problem in this case. Since, in general, an additional constraint requires more

computational effort than an additional variable in a linear programming problem, it

is evident that it is computationally more efficient to solve the dual problem in the

present case. This is one of the advantages of the dual problem.