Dual
Linear Programming Problem
Anil Kumar, Mathematics 1
Dual Linear Programming Problem
v With every linear programming problem, another linear
programming problem is associated, called the dual of the
original (or the primal) problem.
v The dual problem is defined systematically from the primal
(or original) LP model.
The two problems are so closely related that the optimal
solution of one yields the optimal solution of the other
problem.
Anil Kumar, Mathematics 2
Rules for constructing the Dual Problem
The following are the key ideas for constructing the dual from
the primal:
Let xi be the primal variable and yj be the dual variable
1. Number of dual variables ( yj )
= Number of constraints in the primal.
2. Number of variables ( xi ) in the primal
= Number of constraints in the dual
Anil Kumar, Mathematics 3
Rules for constructing the Dual Problem
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.
Anil Kumar, Mathematics 4
Rules for constructing the Dual Problem
5. The objective function coefficients ci of the primal are the
RHS constants of the dual constraints.
6. The RHS constants bj 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.
Anil Kumar, Mathematics 5
Construction of the Dual from Primal
Primal Variables
!!!!!!!!!!!!!!!!
&! & " & # ''' & $ ''' & %
!!!!!!!!!!!!!!!!
Dual Variables $! $" $# ''' $ ! ''' $" Right-hand side
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
%! &!! &!" &!# ''' &! ! ''' &!" '!
%" &"! &"" &"# ''' &" ! ''' &" " '"
! ! ! ! ! ! !
%# &#! &# " &# # ''' &#! ''' &#" '#
jth dual Dual objective
constraints coefficients
Anil Kumar, Mathematics 6
Rules for constructing the Dual Problem
Dual problem
Primal problem
objective
Objective Constraints type Variables sign
Maximization Minimization ≥ unrestricted
Minimization Maximization ≤ Unrestricted
Anil Kumar, Mathematics 7
Dual Problems
Primal (Original) LP P (in standard form)
Maximize $ = ## "# + #" "" + !!! + #! "!
subject to
#!! $! + #!" $" + ### + #!! $! = %!
#"! $! + #"" $" + ### + #" ! $! = %"
!
#"! $! + #" " $" + ### + #"! $! = %"
$! $ $" $###$ $! ! %
Anil Kumar, Mathematics 8
The dual problem is the LP:
Minimize $ = ## "# + #" "" + !!! + #! "!
subject to
#!! $! + #"! $" + ### + #!! $! ! %!
#!" $! + #"" $" + ### + #! " $! ! %"
!
#!" $! + #" " $" + ### + #!" $! ! %"
$! $ $" $###$ $! %&'()*'+,*(- +& )+.&
Anil Kumar, Mathematics 9
Matrix Form
Primal Problem (in the Standard Form):
!"# ! = "#
$%&'()* *+
A# = %
# !,
Anil Kumar, Mathematics 10
Where
" = [#! #" # # #! ]
! "! " ! #!! #!" # # #!! "
! "! "
#" $ #" $ ## #"" # # #" ! $$
# "$ # "$ # "!
# = # # $$ " = # # $$ A=# # $
# $ # $ # $
##$ # # $ # # $
#% "! $& #%"! $& #% #"! #" " # # #"! $&
Anil Kumar, Mathematics 11
Dual Problem:
#$% # = A! %
&'()*+, ,-
C! % ! ' !
% ! '%.*&,.$+,*/ $% &$0%
12*.* % = 3 (! 4 (" 4" 4 (" 5!
Anil Kumar, Mathematics 12
If the primal problem (in standard form) is
Minimize $ = ## "# + #" "" + !!! + #! "!
subject to
#!! $! + #!" $" + ### + #!! $! = %!
#"! $! + #"" $" + ### + #" ! $! = %"
!
#"! $! + #" " $" + ### + #"! $! = %"
$! $ $" $###$ $! ! %
Anil Kumar, Mathematics 13
Then the dual problem is the LP
Maximize $ = ## "# + #" "" + !!! + #! "!
subject to # $ + # $ + ### + # $ ! %
!! ! "! " !! ! !
#!" $! + #"" $" + ### + #! " $! ! %"
!
#!" $! + #" " $" + ### + #!" $! ! %"
$! $ $" $###$ $" %&' ()&'*+&,-+'. ,) *,/)
Anil Kumar, Mathematics 14
Primal Problem (in the Standard Form):
!"# ! = "#
$%&'()* *+
A# = %
# !,
Anil Kumar, Mathematics 15
Dual Problem:
#$% # = A! %
&'()*+, ,-
C! % ! ' !
% './*&,/0+,*1 0. &02.
34*/* % = 5 (! 6 (" 6! 6 (" 7!
Anil Kumar, Mathematics 16
Example 1: Write the dual of the following LPP
Maximize " = !#!" + !!!
subject to
!! ! !" ""
" !! + # !" # $
!! % !" " &
Anil Kumar, Mathematics 17
Thus, the primal in the standard form is:
Maximize ! = !#"! + " "" + $#! + $#"
subject to !! ! !" ! "! ="
" !! + #!" + "" = $
!! % !" % "! % "" " &
Anil Kumar, Mathematics 18
Hence the dual is:
Minimize " = ! !" + # !!
subject to
!! + " !" ! "#
" !! + $ !" ! "
" !! ! %
!" ! % !! ! #$ !" " #
!! & !" '()*+,)-.,*/ -( +-0(
Anil Kumar, Mathematics 19
Example 2: Write the dual of the following LPP
Minimize " = $!" + #!!
subject to
$ !! ! #!" + !# " "
#!! + % !" + !# " &
!! ' !" ' !# " (
Anil Kumar, Mathematics 20
Thus, the primal in the standard form is:
Minimize ! = $ "! + #"" + % "# + %#! + %#"
subject to
$ !! ! #!" + !# ! "! ="
#!! + % !" + !# ! "" = &
!! ' !" ' !# ' "! ' "" " (
Anil Kumar, Mathematics 21
Hence the dual is:
Maximize " = ! !" + # !!
subject to
# !! + $ !" ! #
"$ !! + % !" ! $
!! + !" ! &
" !! !&
" !" ! & !! # !" ! $
!! ' !" ()*+,-*./-+01.)1,.2)
Anil Kumar, Mathematics 22
Example 3: Write the dual of the following LPP
Maximize " = !" + !!
subject to
" !! + !" = #
$!! ! !" = %
!! & !" '()*+,)-.,*/ -( +-0(
Anil Kumar, Mathematics 23
Thus, the primal in the standard form is:
Maximize " = !"+ ! !"! + !!+ ! !!!
subject to
& !'+ " & !'" + !&+ " !&" = %
$!'+ " $!'" " !&+ + !&" = #
!'+ " !'" " !&+ " !&" ! !
Anil Kumar, Mathematics 24
Hence the dual is:
Minimize " = $ !" + # !!
subject to
" !! + # !" ! ! # !! + " !# = !
" " !! " # !" ! "!
!! " !" ! !
!! ! !" = !
" !! + !" ! " !
!! $ !" %&'()*'+,*(- +& )+.&
Remark: if an LPP contains any variable !! of unrestricted in
sign, then the kth dual constraint will be written as equality
constraint.
Anil Kumar, Mathematics 25
Example 4: Write the dual of the following LPP
$%& " = # !! ! " !" + * !#
'()( # !! + + !" + * !# " ,
- !! + !" + #!# " *
, !! ! " !" ! !# # !.
!! ! " !" + + !# " #
* !! + , !" ! " !# " "
!! / !" / !# " .
Anil Kumar, Mathematics 26
Example 5:
Write the dual of the following LPP
max % = 2!" − 3!#
subject to
!" + 2!# ≤ 4
3!" − !# = 5
!" , !# ≥ 0.
Remark: If the primal contains some equality constraint,
then the dual variable corresponding to that constraint will
be unrestricted in sign.
Anil Kumar, Mathematics 27
Example 6: Write the dual of the LP
/01 " = $ !! + # !"
+3,3 !! + " !" = $
! !! + $ !" " %
!! &'()*+,)-.,*2 0(2 !" # 4
Anil Kumar, Mathematics 28
Theorem: The dual of the dual is the primal
Proof: Consider the primal problem (in standard form)
Maximize $ = ## "# + #" "" + !!! + #! "!
subject to #!! $! + #!" $" + ### + #!! $! = %!
#"! $! + #"" $" + ### + #" ! $! = %"
!
#"! $! + #" " $" + ### + #"! $! = %"
$! $ $" $###$ $! ! %
Anil Kumar, Mathematics 29
Weak Duality Theorem
For any pair of feasible primal and dual solutions (X, Y), the
value of the objective function in the minimization problem is
an upper bound for the value of the objective function in the
maximization problem.
Anil Kumar, Mathematics 38
Proof : Let the Primal be a Maximization problem
!"# ! = " #
and
! " = #! " ! "! # ! "
Then the dual problem
!"# " = #! $
"! # ! A! ! # "#$%&'$()'%* (# &(+#
Given X is a feasible solution of the Primal problem,
! " = #! " ! "
Anil Kumar, Mathematics 39
!
Pre-multiplying the first part of the equation by "
(feasible solution of dual), we get
" ! #! A = " ! % = %! " = & … (1)
Given Y is a feasible solution of the dual problem, i.e.,
"! # ! A ! ! # "#$%&'$()'%* (# &(+#
"! # ! A ! " ! #! A
Post-multiplying the inequality by the vector X ! ! "#, we
get
"! # A ! % A = C … (2)
Combining equations (1) and (2), we get ! ! "!
The proof when the primal is a minimization problem is
similar. Anil Kumar, Mathematics 40
Corollary-1
If X* is a feasible solution of the primal and Y* is a feasible
solution of the dual, such that
"! = # $ ! = %! & !!=! ! !
then X* is an optimal solution of the primal and Y* is an
optimal solution of the dual.
Anil Kumar, Mathematics 41
Unboundedness and infeasibility
Corollary 2. If the objective value of one of the two problems
is unbounded, then the other problem must be infeasible.
n if it is not, then both problems have feasible solutions, and the
relationship " ! ! must hold, impossible as by assumption
either ! = + ! !" " = " !
42
Remark:
n The converse of this corollary is NOT true.
n Example:
#$%&'( &') ! = "! + "" * "! ! "" " !!+ ! "! + "" " !!+ "! + "" # ,-
#$%&DD ()* ! = ! "! ! "" + "! ! "" " !, ! "! + "" " !, "! , "" " -.
If one of the problems has an infeasible solution, then
the other problem either has an unbounded solution or
an infeasible one.
Anil Kumar, Mathematics 43
The following shows which outcome pairs are possible for a
primal linear program and its dual:
Dual
Primal
Optimal Infeasible Unbounded
Optimal Possible Never Never
Infeasible Never Possible Possible
Unbounded Never Possible Never
Anil Kumar, Mathematics 44
The following theorem tells us how we can find the optimal
solution of the dual from the optimal table of the primal :
Theorem: Given the optimal primal basis B and its
associated objective coefficient vector CB, the optimal
solution to the dual problem is
# ! = $" " !"
Anil Kumar, Mathematics 45
Proof: Let the primal be a maximization problem. Then
" ! ! # ! " ! "#$ %&& !
That is, ! " ! ! !! # ! " " "
! "! # ! A
! "! # ! A ! ⇒ Y is feasible.
The optimal solution of the primal is
# " = $" B " = $" " !! C = ' ! C = C ! ' = (#
Hence, by the corollary of the weak duality theorem, Y is
the optimal solution of the dual.
Anil Kumar, Mathematics 46
Example 1: Consider the following LP:
Maximize " = # !$ + ! !# + ! !" ! "!!
Subject to
!! + !" + !# =$
!! + $ !" + !$ = %
!! & !" & !# & !$ ! '(
(a) Verify that B = (A2, A3) is optimal.
(b) Write the dual.
(c) Find the associated optimal dual solution.
Anil Kumar, Mathematics 47
Example 2: Consider the following problem
$%& ! = "! + ' "" + #"#
()*+,-. ./
"! + " "" + "# =#
" "! ! "" =0
"! 1 "" 1 "# " 2
1. Verify that B= (P1, P3) is optimal.
2. Write the dual.
3. Find the associated optimal dual solution.
Anil Kumar, Mathematics 52