Duality and Post Optimal Analysis
Rajesh P Mishra
1228A
[email protected]
Rajesh P Mishra lect 17
Mute ur call
Plz add
Engineering Optimization
group of facebook
(Rajesh Mishra)
Rajesh P Mishra lect 17
Dual Problem of an LPP
1. Given a LPP (called the primal problem), we shall
associate another LPP called the dual problem of the
original (primal) problem.
2. We shall see that the Optimal values of the primal and
dual are the same provided both have finite feasible
solutions.
3. This topic is further used to develop another method of
solving LPPs and is also used in the sensitivity (or
post-optimal) analysis.
Rajesh P Mishra lect 17
Definition of the dual problem
Given the primal problem (in standard form)
z c1 x1 c2 x2 ... cn xn
Maximize
subject to
a11 x1 a12 x2 ... a1n xn b1
a21 x1 a22 x2 ... a2 n xn b2
.
.
am1 x1 am 2 x2 ... amn xn bm
x1 , x2 ,..., xn 0, b1 , b2 ,..., bm 0
Rajesh P Mishra lect 17
the dual problem is the LPP
Minimize
subject to
w b1 y1 b2 y2 ... bm ym
a11 y1 a21 y2 ... am1 ym c1
a12 y1 a22 y2 ... am 2 ym c2
.
.
a1n y1 a2 n y2 ... amn ym cn
y1 , y2 ,..., yn unrestricted in sign
Rajesh P Mishra lect 17
If the primal problem (in standard form) is
Minimize z c1 x1 c2 x2 ... cn xn
subject to
a11 x1 a12 x2 ... a1n xn b1
a21 x1 a22 x2 ... a2 n xn b2
.
.
am1 x1 am 2 x2 ... amn xn bm
x1 , x2 ,..., xn 0, b1 , b2 ,..., bm 0
Rajesh P Mishra lect 17
Then the dual problem is the LPP
Maximize w b1 y1 b2 y2 ... bm ym
subject to
a11 y1 a21 y2 ... am1 ym c1
a12 y1 a22 y2 ... am 2 ym c2
.
.
a1n y1 a2 n y2 ... amn ym cn
y1 , y2 ,..., yn unrestricted in sign
Rajesh P Mishra lect 17
We thus note the following:
1. In the dual, there are as many (decision)
variables as there are constraints in the
primal.
We usually say yi is the dual variable
associated with the ith constraint of the
primal.
2. There are as many constraints in the dual
as there are variables in the primal.
Rajesh P Mishra lect 17
3. If the primal is maximization then the
dual is minimization and all constraints
are
If the primal is minimization then the dual
is maximization and all constraints are
4. In the primal, all variables are 0 while
in the dual all the variables are
unrestricted in sign.
Rajesh P Mishra lect 17
5. The objective function coefficients cj of
the primal are the RHS constants of the
dual constraints.
6. The RHS constants bi of the primal
constraints are the objective function
coefficients of the dual.
7. The coefficient matrix of the constraints
of the dual is the transpose of the
coefficient matrix of the constraints of
the primal.
Rajesh P Mishra lect 17
10
Write the dual of the LPP
Maximize
subject to
z 5x1 2 x2
x1 x2 2
2 x1 3 x2 5
x1 , x2 0
Rajesh P Mishra lect 17
11
Thus the primal in the standard form is:
Maximize z 5x1 2 x2 0 x3 0 x4
subject to
x1 x2 x3
2 x1 3x2
2
x4 5
x1 , x2 , x3 , x4 0
Rajesh P Mishra lect 17
12
Hence the dual is:
Minimize
w 2 y1 5 y2
subject to
y1 2 y2 5
y1 3 y2
y1
y2
y1 0, y2 0
y1 , y2 unrestricted in sign
Rajesh P Mishra lect 17
13
Write the dual of the LPP
Minimize z 6 x1 3x2
subject to
6 x1 3x2 x3 2
3x1 4 x2 x3 5
x1 , x2 , x3 0
Rajesh P Mishra lect 17
14
Thus the primal in the standard form is:
Minimize z 6 x1 3x2 0 x3 0 x4 0 x5
subject to
6 x1 3x2 x3 x4
3x1 4 x2 x3
2
x5 5
x1 , x2 , x3 , x4 , x5 0
Rajesh P Mishra lect 17
15
Hence the dual is:
Maximize w 2 y1 5 y2
subject to
6 y1 3 y2 6
3 y1 4 y2 3
y1
y1
y2 0
0
y2 0
y1 , y2 0
y1 , y2 unrestricted in sign
Rajesh P Mishra lect 17
16
Write the dual of the LPP
Maximize
subject to
z x1 x2
2 x1 x2 5
3x1 x2 6
x1 , x2 unrestricted in sign
Rajesh P Mishra lect 17
17
Thus the primal in the standard form is:
Maximize
z x x x x
subject to
2x 2x x x 5
3x 3x x x 6
x ,x ,x ,x 0
Rajesh P Mishra lect 17
18
Hence the dual is:
w 5 y1 6 y2
Minimize
subject to
2 y1 3 y2 1
2 y1 3 y2 1
2 y1 3 y2 1
y1
y2 1
y1
y2 1
y1 y2 1
y1 , y2 unrestricted in sign
Rajesh P Mishra lect 17
19
From the above examples we get the
following SOB rules for writing the dual:
Label
Sensible
Odd
Bizarre
Sensible
Odd
Bizarre
Maximization
Constraints
form
= form
form
Variables
0
unrestricted
0
Rajesh P Mishra lect 17
Minimization
Variables
0
unrestricted
0
Constraints
form
= form
form
20
Theorem: The dual of the dual is the primal
(original problem).
Proof. Consider the primal problem (in standard
form)
z c1 x1 c2 x2 ... cn xn
Maximize
subject to
a11 x1 a12 x2 ... a1n xn b1
a21 x1 a22 x2 ... a2 n xn b2
.
.
am1 x1 am 2 x2 ... amn xn bm
x1 , x2 ,..., xn 0
Rajesh P Mishra lect 17
21
The dual problem is the LPP
Minimize w b1 y1 b2 y2 ... bm ym
subject to
a11 y1 a21 y2 ... am1 ym c1
a12 y1 a22 y2 ... am 2 ym c2
.
.
a1n y1 a2 n y2 ... amn ym cn
y1 , y2 ,..., yn unrestricted in sign
Rajesh P Mishra lect 17
22
Case (i): All cj 0. Then the dual problem in
the standard form is the LPP
Minimize
w b1 y1 b1 y1 ... bm ym
bm ym
0t1 0t 2 ... 0t n
subject to
11 1
11 1
a y a y ... am1 y am1 y t1 c1
a12 y1 a12 y1 ... am 2 ym am 2 ym t 2 c2
.
.
a1n y1 a1n y1 ... amn ym amn ym t n cn
y1 , y1 ,..., ym , ym , t1 , t 2 ,..., t n 0
Rajesh P Mishra lect 17
23
Hence its dual is the LPP
Maximize z c1 x1 c2 x2
subject to
... cn xn
a11 x1 a12 x2 ... a1n xn b1
a11 x1 a12 x2 ... a1n xn b1
.
am1 x1 am 2 x2 ... amn xn bm
am1 x1 am 2 x2 ... amn xn bm
x1 0, x2 0,..., xn 0
x1 , x2 ,..., xn unrestricted in sign
Rajesh P Mishra lect 17
24
Which is nothing but the LPP
Maximize z c1 x1 c2 x2 ... cn xn
subject to
a11x1 a12 x2 ... a1n xn b1
a21x1 a22 x2 ... a2 n xn b2
.
.
am1 x1 am 2 x2 ... amn xn bm
x1 , x2 ,..., xn 0
This is the primal problem.
Rajesh P Mishra lect 17
25
Case (ii): All cj 0 except c1. Then the dual
problem in the standard form is the LPP
w b1 y1 b1 y1 ... bm ym
bm ym
Minimize
0t1 0t 2 ... 0t n
Subj
ect a11 y1 a11 y1 ... am1 ym am1 ym t1 c1
a12 y1 a12 y1 ... am 2 ym am 2 ym t 2 c2
to
.
.
1n 1
1n 1
a y a y ... amn y amn y t n cn
Rajesh P Mishra lect 17
m
m 1 2
y , y ,..., y , y , t , t ,..., t n 0
26
Hence its dual is the LPP
Maximize z c1v1 c2 x2 ... cn xn
subject to
a11v1 a12 x2 ... a1n xn b1
a11v1 a12 x2 ... a1n xn b1
.
am1v1 am 2 x2 ... amn xn bm
am1v1 am 2 x2 ... amn xn bm
v1 0, x2 0,..., xn 0
v1 , x2 ,..., xn unrestricted in sign
Rajesh P Mishra lect 17
27
Which is nothing but the LPP
z c1v1 c2 x2 ... cn xn
Maximize
subject to
a11v1 a12 x2 ... a1n xn b1
a21v1 a22 x2 ... a2 n xn b2
.
.
am1v1 am 2 x2 ... amn xn bm
v1 0, x2 ,..., xn 0
Putting x1 v1
Rajesh P Mishra lect 17
28
This is nothing but the LPP
Maximize
subject to
z c1 x1 c2 x2 ... cn xn
a11 x1 a12 x2 ... a1n xn b1
a21 x1 a22 x2 ... a2 n xn b2
.
.
am1 x1 am 2 x2 ... amn xn bm
x1 , x2 ,..., xn 0
This is the primal problem. Cases where
other cj are 0 are similarly treated.
Rajesh P Mishra lect 17
29
Duality theorems
Finding the dual optimal solution from the
primal optimal tableau
Dual problem in Matrix form
In this lecture we shall present the primal
and dual problems in matrix form and
prove certain results on the feasible and
optimal solutions of the primal and dual
problems.
Dual problem in Matrix form
Suppose the primal in (Matrix and ) standard
form is
Maximize
subject to
z cX
A X b,
X 0, b 0
where
C c1
c2
a11
a
21
A .
.
am1
. . cn ,
x1
x
2
X .
.
xn
a12
a22
.
.
.
.
am 2
a1n
a2 n
amn
b1
b
2
b .
.
bm
Letting
Y y1 y2 . . ym
the dual LPP in matrix form becomes
Minimize w Y b
subject to
Y A c,
Y unrestricted in sign
If the primal LPP is a minimization problem
Minimize
z cX
subject to A X b,
X 0, b 0
the dual LPP in matrix form becomes
Maximize
w Yb
subject to Y A c,
Y unrestricted in sign
Rajesh P Mishra lect 17
36
Optimal Dual Solution
The primal and dual solutions are so closely
related that the optimal solution of either
problem directly yields (with little additional
computation) the optimal solution to the
other.
Thus, in an LP model in which the number of
variables is considerably smaller than the
number of constraints, computational savings
may be realized by solving the dual, from
which the primal solution is determined
automatically
Rajesh P Mishra lect 17
37
Rajesh P Mishra lect 17
38
Rajesh P Mishra lect 17
39
Rajesh P Mishra lect 17
40
Rajesh P Mishra lect 17
41
