Duality in Linear
Programming
By
Dr. Babita Mishra
Assistant Professor,
Department of Mathematics,
School of Physical Sciences.
Mahatma Gandhi Central University,
Motihari, Bihar.
Duality in Linear Programming
Problem
There is always a corresponding
Linear Programming Problem (LPP)
associated to every LPP, which is
called as dual problem of the original
LPP(Primal Problem).
Let the primal problem in standard form be
max/min 𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 +. . . +𝑐𝑛 𝑥𝑛
𝑠. 𝑡. 𝑎11 𝑥1 + 𝑎12 𝑥2 + . . . +𝑎1𝑛 𝑥𝑛 =𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + . . . +𝑎2𝑛 𝑥𝑛 =𝑏2
.
.
.
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + . . . +𝑎𝑚𝑛 𝑥𝑛 =𝑏𝑚
and 𝑥1 , 𝑥2 , . . . , 𝑥𝑛 ≥0
Associated dual problem is
min/𝑚𝑎𝑥 𝑍 ∗ = 𝑏1 𝑤1 + 𝑏2 𝑤2 +. . . +𝑏𝑚 𝑤𝑚
𝑠. 𝑡. 𝑎11 𝑤1 + 𝑎21 𝑤2 + . . . +𝑎𝑚1 𝑤𝑚 ≥/≤ 𝑐1
𝑎12 𝑤1 + 𝑎22 𝑤2 + . . . +𝑎𝑚2 𝑤𝑚 ≥/≤ 𝑐2
.
.
.
𝑎1𝑛 𝑤1 + 𝑎2𝑛 𝑤2 + . . . +𝑎𝑚𝑛 𝑤𝑚 ≥/≤ 𝑐𝑛
and 𝑤1 , 𝑤2 , . . . , 𝑤𝑚 are unrestricted in
sign.
Formulating a Dual Problem
Steps for formulation are summarised as
Step 1: write the given LPP in its standard form.
Step 2: identify the variables of dual problem
which are same as the number of constraints
equation.
Step 3: write the objective function of the dual
problem by using the constants of the right had
side of the constraints.
Step 4: if primal is max/min type than dual is
min/max type and the constraints are ≥/≤ type.
Step 5: dual variables are unrestricted in sign.
Primal-dual pair in matrix
form
Standard Primal Problem:
Find 𝑥 ∈ ℝ𝑛 so as to
maximize/minimize z = c𝑥, 𝑐 ∈ ℝ𝑛
Subject to constraints
𝐴𝑥 = 𝑏 𝑎𝑛𝑑 𝑥 ≥ 0, 𝑏 ∈ ℝ𝑚
where 𝐴 𝑖𝑠 𝑚 × 𝑛 real matrix.
Associated Dual Problem:
Find w∈ ℝ𝑚 so as to
minimize/maximize 𝑧 ∗ = 𝑏 𝑇 𝑤, 𝑏 ∈ ℝ𝑚
Subject to constraints
𝐴𝑇 𝑤 ≥/≤ 𝑐 𝑇 , c ∈ ℝ𝑛
where 𝐴 𝑖𝑠 𝑛 × 𝑚 real matrix and 𝑤 is
unrestricted in sign.
Some Important
characteristics of Duality
➢ Dual of dual is primal.
➢ If either the primal or dual problem has a solution
then the other also has a solution and their
optimum values are equal.
➢ If any of the two problems has an infeasible
solution, then the value of the objective function
of the other is unbounded.
➢ The value of the objective function for any feasible
solution of the primal is less than the value of the
objective function for any feasible solution of the
dual.
➢ If either the primal or dual has an unbounded
solution, then the solution to the other problem
is infeasible.
➢ If the primal has a feasible solution, but the dual
does not have then the primal will not have a
finite optimum solution and vice versa.
Duality and Simplex method
Since any LPP can be solved by using simplex
method, so we can solve primal as well as dual,
and as there is relation between the two we can
solve one and give the solution for the
associated other problem by using some rule as
given
Primal problem is in form of maximization,
then
Rule 1: Corresponding net evaluation of the
starting primal variables=difference between
the left and right sides of the dual constraints
associated with the starting primal variables.
(by using optimal solution of the primal get the
optimal solution for dual.)
Rule 2: negative of the Corresponding net
evaluation of the starting dual
variables=difference between the left and
right sides of the primal constraints
associated with the starting dual variables.
(by using optimal solution of the dual get the
optimal solution for primal.)
Rule 3: if the primal (dual) is unbounded
then the dual (primal) does not have any
feasible solution.
Advantages and
Applications of Duality
➢Sometimes dual problem solution may be
easier than primal solution, particularly
when the number of decision variables is
considerably less than slack / surplus
variables.
➢In the areas like economics, it is highly
helpful in obtaining future decision in the
activities being programmed.
➢In physics, it is used in parallel circuit and
series circuit theory.
➢In game theory, dual is employed by
column player who wishes to minimize
his maximum loss while his opponent
i.e. Row player applies primal to
maximize his minimum gains. However,
if one problem is solved, the solution for
other also can be obtained from the
simplex tableau.
➢When a problem does not yield any
solution in primal, it can be verified with
dual.
➢Economic interpretations can be made
and shadow prices can be determined
enabling the managers to take further
decisions.
Some Examples
Write the dual of following LPP
1. 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑧 = 20𝑥1 + 40𝑥2
𝑠. 𝑡. 36 𝑥1 + 6𝑥2 ≥ 108,
3𝑥1 + 12𝑥2 ≥ 36,
20 𝑥1 + 10𝑥2 ≥ 100 𝑎𝑛𝑑
𝑥1 ≥ 0, 𝑥2 ≥ 0
Solution: first we have to write the given
LPP in standard form.
introducing surplus variables 𝑠1 , 𝑠2 , 𝑠3 ≥ 0,
the primal problem in standard form can be
written as
𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑧 = 20𝑥1 + 40𝑥2 + 0. 𝑠1 + 0. 𝑠2 + 0. 𝑠3
𝑠. 𝑡. 36 𝑥1 + 6𝑥2 − 𝑠1 = 108,
3𝑥1 + 12𝑥2 − 𝑠2 = 36,
20 𝑥1 + 10𝑥2 − 𝑠3 = 100 𝑎𝑛𝑑
𝑥1 , 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0.
Associated dual is
𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑧 ∗ = 108𝑤1 + 36𝑤2 + 100𝑤3
𝑠. 𝑡. 36𝑤1 + 3𝑤2 + 20𝑤3 ≤ 20,
6𝑤1 + 12𝑤2 + 10𝑤3 ≤ 40,
-𝑤1 ≤ 0, -𝑤2 ≤ 0, −𝑤3 ≤0
Where 𝑤1 , 𝑤2 , 𝑤3 are unrestricted in sign
dominated by 𝑤1 ≥ 0, 𝑤2 ≥ 0, 𝑤3 ≥0
𝟐. 𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑧 = 𝑥1 + 3𝑥2
𝑠. 𝑡. 𝑥1 + 𝑥2 ≤ 3,
2𝑥1 − 𝑥2 ≥ −1,
𝑥1 + 2𝑥2 = 5, 𝑎𝑛𝑑
𝑥1 ≥ 0, 𝑥2 unrestricted in sign.
Solution: first we have to write the given
LPP in standard form.
let 𝑥2 = 𝑥2′ − 𝑥2′′ (where 𝑥2′ 𝑎𝑛𝑑 𝑥2′′ ≥ 0)
introducing slack variables 𝑠1 , 𝑠2 ≥ 0,
the primal problem in standard form can be
written as
𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑧 = 𝑥1 + 3𝑥2′ − 3𝑥2′′ + 0. 𝑠1 + 0. 𝑠2
𝑠. 𝑡. 𝑥1 + 𝑥2′ − 𝑥2′′ + 𝑠1 = 3,
−2𝑥1 + 𝑥2′ − 𝑥2′′ + 𝑠2 = 1,
𝑥1 + 2𝑥2′ − 2𝑥2′′ = 5, 𝑎𝑛𝑑
𝑥1 , 𝑥2 ′, 𝑥2 ′′, 𝑠1 , 𝑠2 ≥ 0.
Associated dual is
𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑧 ∗ = 3𝑤1 + 𝑤2 + 5𝑤3
𝑠. 𝑡. 𝑤1 − 2𝑤2 + 𝑤3 ≥ 1,
𝑤1 + 𝑤2 + 2𝑤3 ≥ 3,
ൠ ⇒ 𝑤1 + 𝑤2 + 2𝑤3 = 3
−𝑤1 − 𝑤2 − 2𝑤3 ≥ −3,
𝑤1 ≥ 0, 𝑤2 ≥ 0, 𝑤3 unrestricted.
Thank you!
