ISL 323E Operations Research

Fall 2024

Assoc. Prof. Dr. Fuat Kosanoğlu

ISL 323E Operations Research
Week VII
26 November 2024
Duality: Introduction
 Consider the following LP:
maximize Z = 30x1 + 20x2

s.t. x1 + 2x2 ≤6 (1)

2x1 + x2 ≤8 (2)
x2 ≤2 (3)
−x1 + x2 ≤1 (4)
x1 , x2 ≥ 0
 Here is a feasible solution: (x1, x2) = (2, 1) with Z = 80.
 Is it optimal? If not, How far from optimal is it?
 We could answer by solving the LP using simplex.
 Is there another way?

2/68
 Lower and Upper Bounds
 Since (2, 1) is a feasible solution with Z = 80, 80 is a lower bound
on the optimal objective value.
◼ Why?
10 4 380
 ( , )is also a feasible solution, with 𝑍 = = 126.67 is another
3 3 3
feasible solution.
◼ So 126.67 is also a LB.
 What if I told you that 160 is an upper bound on the optimal
objective value?
10 4
◼ Then ( 3 , 3) is no more than 160 − 126.67 = 33.33 units away from optimal.
10 4
 If I could prove that 126.67 is also an upper bound, then ( , )
3 3
must be optimal.
◼ Why?
3/68
An Upper Bound
maximize Z = 30x1 + 20x2

s.t. x1 + 2x2 ≤6 (1)

2x1 + x2 ≤8 (2)
x2 ≤2 (3)
−x1 + x2 ≤1 (4)
x1 , x2 ≥0

 If we multiply (2) by 20, we get 40x1 + 20x2 ≤ 160.

 So any feasible solution satisfies 40x1 + 20x2 ≤ 160
 The objective function is 30x1 + 20x2
 So any feasible solution must satisfy 30x1 + 20x2 ≤ 160 .
◼ Therefore 160 is an upper bound on the optimal objective value.

4/68
Another Upper Bound
maximize Z = 30x1 + 20x2

s.t. x1 + 2x2 ≤6 (1)

2x1 + x2 ≤8 (2)
x2 ≤2 (3)
−x1 + x2 ≤1 (4)
x1 , x2 ≥0

 Multiply (1) and (2) by 10 and add them:

◼ 30x1 + 30x2 ≤ 140.
 Since 30x1 + 20x2 ≤ 30x1 + 30x2 ≤ 140
◼ 140 is another (even better) upper bound.
◼ Why?
 How can we find the best (i.e., smallest) upper bound?

5/68
Finding the Best Upper Bound
maximize Z = 30x1 + 20x2

s.t. x1 + 2x2 ≤6 (1)

2x1 + x2 ≤8 (2)
x2 ≤2 (3)
−x1 + x2 ≤1 (4)
x1 , x2 ≥ 0
 We want multipliers for each constraint.
◼ Call them y1, y2, y3, y4 .
 The multipliers must be chosen such that:
◼ σ multipliers times 𝑥1 ’s constraint coefficients ≥ 30
◼ σ multipliers times 𝑥2 ’s constraint coefficients ≥ 20
 We also want the sum of the multipliers times the RHSs to be as small as
possible.
◼ Also, the multipliers have to be nonnegative.
6/68
Finding the Best Upper Bound
maximize Z = 30x1 + 20x2

s.t. x1 + 2x2 ≤6 (1)

2x1 + x2 ≤8 (2)
x2 ≤2 (3)
−x1 + x2 ≤1 (4)
x1 , x2 ≥0

 In other words, we want to.

Minimize W = 6y1 + 8y2 + 2y3 + y4

s.t y1 + 2y2 − y4 ≥ 30
2y1 + y2 + y3 + y4 ≥ 20

y1 , y2 , y3 , y4 ≥ 0

7/68
The Dual Problem
 This new problem is called the dual problem.
 The original problem is called the primal problem.
 The optimal objective function value for the dual
problem gives an upper bound on the optimal
objective function value for the primal problem:
Z∗ ≤ W ∗
 How close is the UB?
 We’ll answer this shortly.

8/68
 Formulating the Dual
 In standard form, the primal and dual problems look like this:
𝑛

𝑚𝑎𝑥 𝑍 = ෍ 𝑐𝑗 𝑥𝑗
𝑗=1
𝑛 Primal
𝑠. 𝑡 ෍ 𝑎𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖 ∀𝑖 = 1,2. . 𝑚
𝑗=1
𝑥𝑗 ≥ 0 ∀𝑗 = 1,2. . 𝑛
𝑚

𝑚𝑖𝑛 𝑊 = ෍ 𝑏𝑖 𝑦𝑖
𝑖=1
𝑚
Dual
𝑠. 𝑡 ෍ 𝑎𝑖𝑗 𝑦𝑖 ≥ 𝑐𝑗 ∀𝑗 = 1,2. . 𝑛
𝑖=1
𝑦𝑖 ≥ 0 ∀𝑖 = 1,2. . 𝑚
9/68
 Formulating the Dual
𝑛
𝑚𝑎𝑥 𝑍 = ෍ 𝑐𝑗 𝑥𝑗 ❑(P) is a maximization
𝑗=1
𝑛
problem, (D) is a
𝑠. 𝑡 ෍ 𝑎𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖 ∀𝑖 = 1,2. . 𝑚 P minimization problem.
𝑗=1 ❑For every variable in (P), there
𝑥𝑗 ≥ 0 ∀𝑗 = 1,2. . 𝑛
is a constraint in (D).
𝑚 ❑For every constraint in (P),
𝑚𝑖𝑛 𝑊 = ෍ 𝑏𝑖 𝑦𝑖 there is a variable in (D).
𝑖=1 ❑The objective function
𝑠. 𝑡
𝑚
෍ 𝑎𝑖𝑗 𝑦𝑖 ≥ 𝑐𝑗 ∀𝑗 = 1,2. . 𝑛
D coefficients in (P) are the
𝑖=1 RHSs in (D).
𝑦𝑖 ≥ 0 ∀𝑖 = 1,2. . 𝑚
❑The RHSs in (P) are the
objective function coefficients
in (D).

10/68
Primal and Dual in Matrix Form
𝑚𝑎𝑥 𝑍 = 𝑐𝑥 ❑c and y are row vectors.
❑b and x are column vectors.
𝑠. 𝑡 𝐴𝑥 ≤ 𝑏 P ❑0 is a column vector in (P) and
𝑥≥0 a row vector in (D).
❑A is m*n matrix

𝑚𝑖𝑛 𝑊 = 𝑦𝑏
𝑠. 𝑡 𝑦𝐴 ≥ c D
𝑦 ≥0

11/68
Example
𝑚𝑎𝑥 𝑍 = 3𝑥1 +5𝑥2
𝑠. 𝑡 𝑥1 ≤4
2𝑥2 ≤ 12 P
3𝑥1 + 2𝑥2 ≤ 18
𝑥1 , 𝑥2 ≥ 0

𝑚𝑖𝑛 𝑊 = 4𝑦1 +12𝑦2 + 18𝑦3

𝑠. 𝑡 𝑦1 + 3𝑦3 ≥3
2𝑦2 + 2𝑦3 ≥ 5 D
𝑦1 , 𝑦2 , 𝑦3 ≥ 0
12/68
Example 2:
 Consider the following LP:
Max Z = 10x1 + 20x2

s.t. −x1 + 2x2 ≤ 15

x1 + x2 ≤ 12
5x1 + 3x2 ≤ 45

x1 , x2 ≥ 0

 Write the primal in matrix form.

 Write the dual in algebraic form.
 Write the dual in matrix form.
13/68
Primal in Matrix Form

𝑥1
𝑚𝑎𝑥 𝑍 = 10 20 𝑥
max Z = 10x1 + 20x2 2
−1 2 𝑥 15
1
s.t. −x1 + 2x2 ≤ 15 𝑠. 𝑡. 1 1 𝑥 ≤ 12
2
5 3 45
x1 + x2 ≤ 12 𝑥1 0
𝑥2 ≥
0
5x1 + 3x2 ≤ 45

x1 , x2 ≥ 0

14/68
Dual in Algebraic Form

P max Z = 10x1 + 20x2 D 𝑚𝑖𝑛 𝑊 = 15𝑦1 + 12𝑦2 + 45𝑦3

𝑠. 𝑡 − 𝑦1 + 𝑦2 + 5𝑦3 ≥ 10
s.t. −x1 + 2x2 ≤ 15 2𝑦1 + 𝑦2 + 3𝑦3 ≥ 20
x1 + x2 ≤ 12 𝑦1, 𝑦2, 𝑦3 ≥ 0

5x1 + 3x2 ≤ 45

x1 , x2 ≥ 0

15/68
Dual in Matrix Form

15
𝑚𝑖𝑛 𝑊 = 𝑦1 𝑦2 𝑦3 12
𝑚𝑖𝑛 𝑊 = 15𝑦1 + 12𝑦2 + 45𝑦3
45
𝑠. 𝑡 − 𝑦1 + 𝑦2 + 5𝑦3 ≥ 10 −1 2
2𝑦1 + 𝑦2 + 3𝑦3 ≥ 20 s. 𝑡. [𝑦1 𝑦2 𝑦3] 1 1 ≥ 10 20
𝑦1 , 𝑦2 , 𝑦3 ≥ 0 5 3
[𝑦1 𝑦2 𝑦3 ] ≥ 0 0 0

16/68
The Weak Duality Property
 If x is a feasible solution for the primal problem
and y is a feasible solution for the dual
problem, then cx ≤ yb
Proof: cx ≤ (yA)x since c ≤ yA and x ≥ 0
= y(Ax)
≤ yb since Ax ≤ b and y ≥ 0

17/68
The Strong Duality Property
 If x* is an optimal solution for the primal
problem and y* is an optimal solution for the
dual problem, then
cx* = y*b
 So: If I have a solution to the primal (x) and a
solution to the dual (y), they are both optimal if
their objective values are equal.
 Otherwise, at least one is not optimal.

18/68
Obtaining Dual Solutions from the Tableau
 At any iteration of the simplex method, the tableau
gives information about the dual problem.
 In particular, the coefficients of the slack variables in
row (0) provide a dual solution y.
 It has the same objective value as x:
cx = yb.
 For most iterations of the simplex method, y is
infeasible for(D).
 At the final iteration, y is feasible for (D).

19/68
Dual Solutions from Tableau: Example
 Row (0) of the tableau for the 3 iterations of
simplex for Wyndor Glass:
 Iteration 0:
y = 0 0 0 ve
4
yb = 0 0 0 12 = 0
18
 y is infeasible for (D) since
𝑦1 + 3𝑦3 = 0 + 3 ∗ 0 ≱ 3
20/68
Dual Solutions from Tableau: Example
 Row (0) of the tableau for the 3 iterations of
simplex for Wyndor Glass:
5
 Iteration 1: y = 0 2
0 and
4
5
yb = 0 2 0 12 = 30
18
 y is infeasible for (D) since:
𝑦1 + 3𝑦3 = 0 + 3 ∗ 0 ≱ 3

21/68
Dual Solutions from Tableau: Example
3
 Iteration 2: y = 0 2
1 ve
4
3
yb = 0 2 1 12 = 36
18
 y is feasible for (D) since
𝑦1 + 3𝑦3 = 0 + 3 ∗ 1 = 3 ≥ 3
3
2𝑦2 + 2𝑦3 = 2 ∗ + 2 ∗ 1 = 5 ≥ 5
2

22/68
Complementary Solutions Property
 At each iteration, the simplex method
simultaneously identifies a CPF solution x for the
primal problem and a complementary solution y
for the dual problem (the coefficients of the slack
variables in row (0)) such that
cx = yb.
 But: The dual solution y may be infeasible

23/68
Complementary Optimal Solutions Property
 At the final iteration, the simplex method
simultaneously identifies a optimal solution x*
for the primal problem and a complementary
optimal solution y*for the dual problem (the
coefficients of the slack variables in row (0))
such that
cx*=y*b
 So the simplex method finds an optimal
solution for the primal and the dual problem!

24/68
 Symmetry Property:
 For any primal problem and its dual problem, all
relationships between them must be symmetric because
the dual of the dual is the primal.
 Therefore, all of the duality relationships hold
regardless of which problem we label as “primal.”
 Except: the inequality in weak duality is reversed if the
primal is a minimization problem.
 Simplex can be applied to either problem, and it will
find optimal solutions for both.

25/68
Infeasible and Unbounded Problems
 We have assumed that the primal is feasible and has an
optimal solution.
 What about other cases?
 Duality Theorem:
1. If (P) is feasible and bounded, then so is (D). Both weak and
strong duality apply.
2. If (P) is feasible and unbounded, then (D) is infeasible.
3. If (P) is infeasible, then (D) is either infeasible or unbounded.
 If you switch (P) and (D) in the Duality Theorem, all
three results still hold.

26/68
 Applications of Duality
 The dual may be easier to solve than the primal.
◼ Origin may be feasible.
◼ The primal may have m>>n.
 And solving the dual gives an optimal solution to the
primal.
 You might “guess” at primal and dual solutions x and y.
◼ If cx = yb, they are optimal.
◼ If not, they still provide bounds for one another.
 Economic interpretation and sensitivity analysis

27/68
Economic interpretation : Shadow Prices
 Dual objective function:
𝑊 = 𝑏1 𝑦1 + 𝑏2 𝑦2 + ⋯ + 𝑏𝑚 𝑦𝑚
 Suppose y* is the optimal dual solution
 If 𝑏𝑖 increased by 1 unit, how much would W*
increase?
 How much would Z* increase?
 𝑦𝑖∗ gives the increase in Z* for each unit increase in
𝑏𝑖 , assuming the optimal solution stays optimal
∗′
 The 𝑦𝑖 𝑠 are also called shadow prices.
28/68
 Example:
𝑚𝑎𝑘𝑠 𝑍 = 3𝑥1 +5𝑥2
❑ Optimum solution:
𝑠. 𝑡 𝑥1 ≤4 ❑ (𝑥1∗ , 𝑥2∗ ) = (2,6) ve Z*=36
2𝑥2 ≤ 12 P 3
❑ (𝑦1∗ , 𝑦2∗ , 𝑦3∗ ) = (0, , 1) and W*=36
2
3𝑥1 + 2𝑥2 ≤ 18 ❑ If increase 𝑏2 = 13 :
𝑥1 , 𝑥2 ≥ 0 ❑ (𝑥1∗ , 𝑥2∗ ) = (1.67, 6.5) and Z*=37.5
❑ The optimum objective value is
increased by 1.5
𝑚𝑖𝑛 𝑊 = 4𝑦1 +12𝑦2 + 18𝑦3 ❑ If we increase 𝑏1 = 5 (and 𝑏2 = 12 ):
❑ (𝑥1∗ , 𝑥2∗ ) = (2, 6) and Z*=36
𝑠. 𝑡 𝑦1 + 3𝑦3 ≥3 ❑ OpThe optimum value doesn’t change.
2𝑦2 + 2𝑦3 ≥ 5 D Why?
𝑦1 , 𝑦2 , 𝑦3 ≥ 0 ❑ Because the first constraint is not
binding.

29/68
Economic interpretation : Shadow Prices
 So: constraint i is not binding in (P) ⇒ 𝑦𝑖∗ = 0 in
(D)
 In other words, constraint i has slack in (P) ⇒
𝑦𝑖∗ = 0 in (D)
 By the symmetry property, we can also say:
constraint j has slack in (D) ⇒ 𝑥𝑗∗ = 0 in (P).
 These are called complementary slackness
properties.

30/68
Adapting to Other Primal Forms
 Our discussion of duality assumes standard form:
 Maximization
◼ ≤ functional constraints

◼ ≥ decision variables

 But every LP has a dual, even if not in standard form.

 Could convert a nonstandard LP to standard form, then
take dual.
 But there is an easier way.

31/68
Objective Function
 If the primal is a maximization problem, then
the dual is a minimization problem.
 And vice-versa.

max 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 (P)
min 𝑏1 𝑦1 + 𝑏2 𝑦2 + ⋯ + 𝑏𝑚 𝑦𝑚 (D)

32/68
 Form of Constraints
 The sense of the functional constraints in the primal affects the
sense of the nonnegativity constraints in the dual.
◼ If the primal constraint is ≤ , the dual variable is ≥ 0.
◼ If the primal constraint is ≥, the dual variable is ≤0.
◼ If the primal constraint is =, the dual variable is unrestricted.
◼ And vice-versa for a minimization problem.
𝑛
෍ 𝑎𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖 ⟷ 𝑦𝑖 ≥ 0
𝑗=1
𝑛
෍ 𝑎𝑖𝑗 𝑥𝑗 ≥ 𝑏𝑖 ⟷ 𝑦𝑖 ≤ 0
𝑗=1
𝑛
෍ 𝑎𝑖𝑗 𝑥𝑗 = 𝑏𝑖 ⟷ 𝑦𝑖 𝑢𝑛𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑒𝑑 𝑖𝑛 𝑠𝑖𝑔𝑛
𝑗=1
33/68
 Nonnegativity
 The sense of the nonnegativity constraints in the primal affects the
sense of the functional constraints in the dual.
◼ If the primal variable is ≥ 0, the dual constraint is ≥.
◼ If the primal variable is ≤ 0, the dual constraint is ≤.
◼ If the primal variable is unrestricted, the dual constraint is =.
◼ And vice-versa for a minimization problem.
𝑚
𝑥𝑗 ≥ 0 ⟷ ෍ 𝑎𝑖𝑗 𝑦𝑖 ≥ 𝑐𝑗
𝑖=1
𝑚
𝑥𝑗 ≤ 0 ⟷ ෍ 𝑎𝑖𝑗 𝑦𝑖 ≤ 𝑐𝑗
𝑖=1
𝑚
𝑥𝑗 unrestricted ⟷ ෍ 𝑎𝑖𝑗 𝑦𝑖 = 𝑐𝑗
𝑖=1

34/68
Summary :
Primal Dual
Objective Function: Maks Z Objective Function: Min W
Constraint i: ≤ Variable i: 𝑦𝑖 ≥ 0
≥ 𝑦𝑖 ≤ 0
= 𝑦𝑖 unrestricted
Variable j: 𝑥𝑗 ≥ 0 Constraint j: ≥
𝑥𝑗 ≤ 0 ≤
𝑥𝑗 unrestricted =

If the primal is a minimization problem, swap the two columns and

swap x’s and y’s.

35/68