Lecture 9
Duality
09-13-2009
Duality
Every LP has its Dual.
Primal(Ex 4.1-1)
max z = 5x1 + 12x2 + 4x3
s.t. x1 + 2x2 + x3 10
2x1 x2 + 3x3 =8
x1 , x2 , x3 0.
Dual
min w = 10y1 + 8y2
s.t. y1 + 2y2 5
2y1 y2 12
y1 + 3y2 4
y1 0
Primal Optimal Solution
Primal
max z = 5x1 + 12x2 + 4x3
s.t. x1 + 2x2 + x3 10
2x1 x2 + 3x3 =8
x1 , x2 , x3 0.
(x1 , x2 , x3 ) = (5.2, 2.4, 0).
z = 54.8.
Dual Optimal Solution
Dual
min w = 10y1 + 8y2
s.t. y1 + 2y2 5
2y1 y2 12
y1 + 3y2 4
y1 0
(y1 , y2 ) = (5.8, 0.4).
w = 54.8.
Duality
Dual can be constructed from its primal.
Primal(Ex 4.1-1)
max z = 5x1 + 12x2 + 4x3
s.t. x1 + 2x2 + x3 10
2x1 x2 + 3x3 =8
x1 , x2 , x3 0.
Dual
min w = 10y1 + 8y2
s.t. y1 + 2y2 5
2y1 y2 12
y1 + 3y2 4
y1 0
Strong Duality
Economic Interpretation
Economic Interpretation
Ex 4.3-2
TOYCO assembles three types of toys: trains, trucks, and cars
using three operations. Available assembly times for the three
operations are 430, 460 and 420 minutes per day, respectively, and
the revenues per toy train, truck, and car are $3, $2 and $5,
respectively. The assembly times per train for the three operations
are 1, 3 and 1 minutes, respectively. The corresponding times per
truck and per car are (2, 0, 4) and (1, 2, 0) minutes (a zero time
indicates that the operations is not used).
Economic Interpretation
Primal
max z = 3x1 + 2x2 + 5x3
s.t. x1 + 2x2 + x3 430
3x1 + 2x3 460
x1 + 4x2 420
x1 , x2 , x3 0.
Optimal solution:
z = $1350
x = (0, 100, 230).
Economic Interpretation
Dual side of the story
TOYCOs available assembly times for the three operations are
430, 460 and 420 minutes per day. You want to buy all assembly
times from TOYCO, by paying prices y1 , y2 , y3 per minute,
respectively. You must pay enough for the assembly times because
otherwise TOYCO would choose not to sell to you, they would
produce on their own and profit from it.
TOYCOs revenues per toy train, truck, and car are $3, $2 and $5,
respectively. The assembly times per train for the three operations
are 1, 3 and 1 minutes, respectively. The corresponding times per
truck and per car are (2, 0, 4) and (1, 2, 0) minutes.
Economic Interpretation
Dual
max w = 430y1 + 460y2 + 420y3
s.t. y1 + 3y2 + y3 3
2y1 + 4y3 2
y1 + 2y2 5
y1 , y2 , y3 0.
Optimal solution:
w = $1350
y = (1, 2, 0).
Economic Interpretation
Primal Dual
max z = 3x1 + 2x2 + 5x3 min w = 430y1 + 460y2 + 420y3
s.t. x1 + 2x2 + x3 430 s.t. y1 + 3y2 + y3 3
3x1 + 2x3 460 2y1 + 4y3 2
x1 + 4x2 420 y1 + 2y2 5
x1 , x2 , x3 0. y1 , y2 , y3 0.
z = $1350 w = $1350
x = (0, 100, 230). y = (1, 2, 0).
Constructing Dual LP
Constructing Dual LP
I Transpose all coefficients.
I Flip max/min.
Primal Dual
max z = 3x1 + 2x2 + 5x3 min w = 430y1 + 460y2 + 420y3
s.t. x1 + 2x2 + x3 430 s.t. y1 + 3y2 + y3 (?) 3
3x1 + 2x3 460 2y1 + 4y3 (?) 2
x1 + 4x2 420 y1 + 2y2 (?) 5
x1 , x2 , x3 0. y1 , y2 , y3 (?) 0.
Constructing Dual LP
Constraints Variables
max min
0
0
= Unrestricted
min max
0
0
= Unrestricted
Constructing Dual LP
TOYCOs example: primal
max z = 3x1 + 2x2 + 5x3
s.t. x1 + 2x2 + x3 430
3x1 + 2x3 460
x1 + 4x2 420
x1 , x2 , x3 0.
Constructing Dual LP
TOYCOs example: dual
max w = 430y1 + 460y2 + 420y3
s.t. y1 + 3y2 + y3 3
2y1 + 4y3 2
y1 + 2y2 5
y1 , y2 , y3 0.
Quiz
Maximization, all variables nonnegative.
Basic x1 x2 x3 x4 x5 x6 Solution
z 7 0 a 0 0 0 210
x5 2 0 c 3 1 0 9
x2 3 1 d 1 0 0 b
x6 1 0 e 2 0 1 8
I (a) Assume b 0. What are the basic variables? What is the
current objective value? What is the current solution?
I (b) Given a = 2, b = 3, is the tableau optimal?
I (c) Given a = 2, b = 3, find another optimal solution.
I (d) For what values of a, b, c, d, e is the current table optimal?
I (e) If a = 1, b 0, c, d, e 0, what can you conclude
about the optimal value?
I (f) Give a possible value of (a, b, c, d, e) so that x3 would
replace x2 in the basis.
You can Obtain an optimal tableau by simply knowing two things:
I Initial table.
I Optimal basic variables.
Example: Initial Table
Basic x1 x2 s1 s2 s3 s4 RHS
z 5 4 0 0 0 0 0
s1 6 4 1 0 0 0 24
s2 1 2 0 1 0 0 6
s3 1 1 0 0 1 0 1
s4 0 1 0 0 0 1 2
Example: Intermediate Table
Basic x1 x2 s1 s2 s3 s4 RHS
z 0 2/3 5/6 0 0 0 20
x1 1 2/3 1/6 0 0 0 4
s2 0 4/3 1/6 1 0 0 2
s3 0 5/3 1/6 0 1 0 5
s4 0 1 0 0 0 1 2
There can be many intermediate tables.
Example: Final(Optimal) Table
Basic x1 x2 s1 s2 s3 s4 RHS
z 0 0 3/4 1/2 0 0 21
x1 1 0 1/4 1/2 0 0 3
x2 0 1 1/8 3/4 0 0 3/2
s3 0 0 3/8 5/4 1 0 5/2
s4 0 0 1/8 3/4 0 1 1/2
Constructing Dual LP
Constructing Dual LP
Constraints Variables
max min
0
0
= Unrestricted
min max
0
0
= Unrestricted
Constructing Dual LP
Primal(Ex 4.1-1)
max z = 5x1 + 12x2 + 4x3
s.t. x1 + 2x2 + x3 10
2x1 x2 + 3x3 =8
x1 , x2 , x3 0.
Constructing Dual LP
Dual(Ex 4.1-1)
min w = 10y1 + 8y2
s.t. y1 + 2y2 5
2y1 y2 12
y1 + 3y2 4
y1 0
Constructing Dual LP from standard form
Standard form:
I Constraints: =.
I Variables: 0.
Dual of standard form:
I Dual variables: unrestricted.
I Dual Constraints:
I 0 if dual is min.
I 0 if dual is max.
Constructing Dual LP from standard form
Ex 4.1-1
max z = 5x1 + 12x2 + 4x3
s.t. x1 + 2x2 + x3 10
2x1 x2 + 3x3 =8
x1 , x2 , x3 0.
Constructing Dual LP from standard form
Ex 4.1-1, standard form
max z = 5x1 + 12x2 + 4x3
s.t. x1 + 2x2 + x3 + x4 = 10
2x1 x2 + 3x3 =8
x1 , , x4 0.
Constructing Dual LP from standard form
Dual of Ex 4.1-1
min w = 10y1 + 8y2
s.t. y1 + 2y2 5
2y1 y2 12
y1 + 3y2 4
y1 0
Constructing Dual LP from standard form
Primal of Ex 4.1-2
min z = 15x1 + 12x2
s.t. x1 + 2x2 3
2x1 4x2 5
x1 , x2 0.
Constructing Dual LP from standard form
Ex 4.1-2, standard form
min z = 15x1 + 12x2
s.t. x1 + 2x2 x3 =3
2x1 4x2 + x4 =5
x1 , , x4 0.
Constructing Dual LP from standard form
Dual of Ex 4.1-2
min w = 3y1 + 5y2
s.t. y1 + 2y2 15
2y1 4y2 12
y1 0
y2 0.
Constructing Dual LP from standard form
Primal of Ex 4.1-3
max z = 5x1 + 6x2
s.t. x1 + 2x2 =5
x1 + 5x2 3
4x1 + 7x2 8
x1 unrestricted
x2 0.
Constructing Dual LP from standard form
Substitute x1 = x1+ x1 :
Ex 4.1-3, standard form
max z = 5x1+ 5x1 + 6x2
s.t. x1+ x1 + 2x2 =5
x1+ + x1 + 5x2 x3 =3
4x1+ 4x1 + 7x2 + x4 =8
x1+ , x1 , x2 , x3 , x4 0.
Constructing Dual LP from standard form
Dual of Ex 4.1-3
min w = 5y1 + 3y2 + 8y3
s.t. y1 y2 + 4y3 =5
2y1 + 5y2 + 7y3 6
y1 unrestricted
y2 0
y3 0.
Optimal Dual Solution
Primal and Dual solution meet at optimality. How do you
determine the optimal dual variables when you solved the primal?
Ex 4.2-1
max z = 5x1 + 12x2 + 4x3
s.t. x1 + 2x2 + x3 10
2x1 x2 + 3x3 =8
x1 , x2 , x3 0.
Optimal Dual Solution
Primal Dual
max z = 5x1 + 12x2 + 4x3 MR min w = 10y1 + 8y2
s.t. x1 + 2x2 + x3 + x4 = 10 s.t. y1 + 2y2 5
2x1 x2 + 3x3 + R = 8 2y1 y2 12
x1 , , x4 , R 0 y1 + 3y2 4
y1 0
y2 M.
Optimal Dual Solution
Initial Table
Basic x1 x2 x3 x4 R RHS
z 5 12 4 0 M 0
x4 1 2 1 1 0 10
R 2 1 3 0 1 8
Optimal Table
Basic x1 x2 x3 x4 R RHS
3 29
z 0 0 5 5 25 + M 54 45
x2 0 1 15 2
5 51 12
5
7 1 2 26
x1 1 0 5 5 5 5
Method 1
Optimal value of dual variable yi =
Optimal primal z-coefficient of starting basic variable xi
+
Original objective coefficient of xi .
! ! ! !
y1 29/5 0 29/5
= + =
y2 2/5 + M M 2/5
I Distinguish between starting basis and optimal basis.
I Distinguish between z-coefficient and objective coefficient.
Method 2
Optimal value of dual variables =
Row vectors of !
Optimal primal
original objective coefficients
inverse
of optimal primal basic variables
!1
2 1
y1 y2 = 12 5
1 2
!
2/5 1/5
= 12 5
1/5 2/5
= 29/5 2/5
I ()1 means matrix inversion.
