Mathematics 340 Section 202 Homework 5 Due Friday, March 5th Only part of the problems may be graded. But, you have to submit all required
problems. (Do not submit optional problems.)
Submit only pdf files. Remember to use
Anstee’s rule:
– Choose the entering variable with the largest positive coefficient.
– If there is a tie, then choose the one with the smaller subscript.
– If there is a choice of leaving variable, then choose the one with the smallest subscript.
1. Solve the linear programming problem
minimize w = 40y1 + 30y2 + 20y3 + 10y4 + 10y5
y1 +2y3 +y4
subject to y1 +y2 +2y5
2y2 +2y4 +y5 y1,…,y5 ≥0
≥ 300 ≥ 400 ≥ 1000
by solving the dual problem and then using Complementary Slackness.
Solution: The dual problem is
subject to non-negativity and
x1 2×1
x1
+x2
+x2 +2×3
+2×3 2×2 +x3
≤40 ≤ 30 ≤20 ≤ 10 ≤10
Write in dictionary form:
x4=40−x1 −x2
x5 = 30
x6 = 20
x7 = 10
x8 = 10
z = 0
−x2 −2×3
−2×1
−x1 −2×3
−2×2 −x3 +300×1 +400×2 +1000×3
maximise z = 300×1 + 400×2 + 1000×3
Page 1 of 8
Mathematics 340 Section 202 Homework 5 Due Friday, March 5th
So x3 enters and x7 leaves
x3 = 5
x4 = 40
x5 = 20
x6 = 20
x8 = 5 z = 5000
So x2 enters and x8 leaves
x2 = (5/2)
x3 = 5
x4 = (75/2)
x5 = (35/2)
x6 = 20
z = 6000
Hence the solution is z = 6000 and
(x4,…,x8) = (75/2,35/2,20,0,0)
We need to map this back to the original problem. We use complementary slackness to do so. It tells us that
x∗j >0 =⇒ aijyi∗ =cj aijx∗j
y1∗ +y2∗ +2y5∗ =400 2y2∗ + 2y4∗ + y5∗ = 1000
Subsituting the x∗j into the inequalities we see (in order)
2.5 < 40 12.5 < 30 0 < 20 10 = 10 10 = 10
Hence y1∗ = y2∗ = y3∗ = 0. The two equations above then imply y5∗ = 200 and y4∗ = 400. We can check that this does also give w = 6000.
−(1/2)x1 −x1 +x1 −2x1 +(1/2)x1 −200x1
+(1/4)x1 −(1/2)x1 −(5/4)x1 +(3/4)x1
−(1/2)x7 −x2
−x2 +x7 −2x2 +(1/2)x7
−2x1 −100x1
+400x2
+(1/4)x7 −(1/2)x7 −(1/4)x7 +(3/4)x7
−500x7 −(1/2)x8
+(1/2)x8 +(1/2)x8
−200x8
−400x7 (x1, x2, x3) = (0, 5/2, 5)
Page 2 of 8
Mathematics 340 Section 202 Homework 5
Due Friday, March 5th
2. The optimal solution to the linear program: Maximize 10x1 +14x2 +20x3
2x1 4x1 x1
+3x2 +2x2
+4x3 −x3 +4x3
≤ 220 ≤ 385 ≤ 160
x1,x2,x3 ≥0
is x1 = 60, x2 = 0, x3 = 25. Write down the dual problem. Use this information above to find an optimal solution to the dual (don’t use the simplex algorithm) explaining your work (name theorems used). Explain how this confirms that the optimal solution to the primal I claimed is in fact an optimal solution.
Solution:
Minimize 220y1 +385y2 +160y3
Dual: 2y1 +4y2 +y3 ≥10 y1,y2,y3 ≥0
3y1 +2y2 ≥ 14 4y1 −y2 +4y3 ≥ 20
Now x1 = 60 > 0 implies 2y1∗ + 4y2∗ + y3∗ = 10 by Complementary Slackness.
Also x3 = 25 > 0 implies 4y1∗ − y2∗ + 4y3∗ = 20 by Complementary Slackness.
Also 4×1 + 2×2 − x3 = 215 < 385 implies y2∗ = 0 by Complementary Slackness.
The optimal solution to the dual can be determined by solving three equations in 3 unknowns to obtain
y 1∗ = 5 , y 2∗ = 0 , y 3∗ = 0
We check feasibilty of our primal and dual solutions and then, since Complementary Slackness is satisfied, the Theorem of Complementary Slackness shows that the pri- mal (and dual) solution is optimal. An alternate way is to note you have a feasible solution to the primal (60, 0, 25) with objective function value 10 × 60 + 14 × 0 + 20 × 25 = 1100 and a feasible solution to the dual (5,0,0) with objective function value 220×5+385×0+160×0 = 1100 and so by Weak Duality, both must be optimal.
Comment: It is somewhat lucky that the three equations determine an optimal dual solution but that is how the question was chosen. The value of the question is in testing your hands on understanding of Complementary Slackness.
3. Prove the following:
Theorem Let A and ⃗b be given. Then either
thereexistsan⃗xsuchthat⃗x≥0andA⃗x≤⃗b,or
thereexistsa⃗ysuchthatATy≥0,⃗y≥0and⃗b·⃗y<0,
Page 3 of 8
Mathematics 340 Section 202 Homework 5 Due Friday, March 5th but not both. Note the strict inequality in the second.
Hint: Use both weak and strong duality theorems. You will also need the fundamental theorem of linear programming.
Solution:
We write this as an LP problem and use duality. Now we have constraints, but no objective function, so let us just use Z = ⃗0 · ⃗x.
max ⃗0 · ⃗x A ⃗x ≤ ⃗b
⃗x ≥ 0
min ⃗b · ⃗y
A T ⃗y ≥ 0
⃗y ≥ 0
Since the primal problem is bounded (the objective function is zero), the fundamental theorem of linear programming tells us that the primal problem either has an optimal solution or is infeasible.
If the primal has an optimal solution (option 1), ⃗x∗ then the objective function is 0. Weak duality tells us that any feasible solution of the dual problem must give 0 ≤ ⃗bT ⃗y. Hence option 2 cannot happen if option 1 does happen.
Assume the primal is infeasible. We see that the dual is always feasible since ⃗y = 0 is always a solution. Again, the fundamental theorem of LP tells that the dual is either has an optimal solution or unbounded.
– If the dual has an optimal solution, ⃗y∗ then strong duality implies that there is an optimal and so feasible solution to the primal — which we have assumed does not exist.
– Hence the dual must be unbounded. Since it is unbounded, then there exists a feasible solution of the dual, ⃗y′ with objective function ⃗b · ⃗y′ = −1. Hence there exists a ⃗y such that ⃗b · ⃗y < 0.
The fundamental theorem of linear programming tells us that either the primal has an optimal solution or is infeasible. If optimal, then option 1 happens but not option 2. If the primal is infeasible, option 1 cannot happen, but option 2 must.
ALTERNATIVE (starting with the dual problem):
If option 2, then there is ⃗y that is feasible with⃗b·⃗y < 0. For any t ≥ 0, t⃗y is also feasible with objective function t (⃗b · ⃗y) and considering t very large we see the dual problem is unbounded. Weak duality implies that the primal problem is infeasible so we cannot have option a.
Page 4 of 8
Mathematics 340 Section 202 Homework 5 Due Friday, March 5th
We must also show that at least one of the options hold. If not option 2, then ⃗y = ⃗0 is an optimal solution to the dual problem because there is no feasible solution with ⃗b · ⃗y < 0. The strong duality theorem states that the dual of the dual (the primal)
also has an optimal solution. This implies option 1.
Page 5 of 8
Mathematics 340 Section 202 Homework 5 Due Friday, March 5th The following two problems are OPTIONAL for your practice with comple-
mentary slackness. Do not hand in.
4. Question 5.3(a) from Chvatal. Maximise 7x1
subjectto x1 4x1 2x1 3x1
Is (0, 4/3, 2/3, 5/3, 0) optimal?
+6x2 +5x3 +3x2 +5x3 +2x2 −2x3 +4x2 +4x3
+x2 +2x3
−2x4 +3x5 −2x4 +2x5 +x4 +x5 −2x4 +5x5 −x4 −2x5
≤ 4 ≤3 ≤ 5 ≤1
x1,x2,x3,x4,x5 ≥ 0
Solution:
subject to
The dual problem is
minimise 4y1
+3y2 +5y3 +y4 y1 +4y2 +2y3 +3y4 3y1 +2y2 +4y3 +y4 5y1 −2y2 +4y3 +2y4 −2y1 +y2 −2y3 −y4 2y1 +y2 +5y3 −2y4
≥7 ≥6 ≥5 ≥ −2 ≥3
y1,y2,y3,y4 ≥ 0
Since x∗2, x∗3, x∗4 > 0 it follows that the corresponding dual constraints are equal-
ities:
3y1 +2y2 +4y3 +y4 = 6 5y1 −2y2 +4y3 +2y4 = 5
−2y1 +y2 −2y3 −y4 =−2
Substitute x∗ into the primal constraints gives
4 + 10/3 − 10/3 = 4
8/3 − 4/3 + 5/3 = 3
16/3 + 8/3 − 10/3 = 14/3 < 5
4/3 + 4/3 − 5/3 = 1
Since the third constraint is a strict inequality, y3∗ = 0.
Page 6 of 8
Mathematics 340 Section 202 Homework 5 Due Friday, March 5th
So we have to solve the following 3 equations
3y1 +2y2 +4y3 +y4 = 6 5y1 −2y2 +4y3 +2y4 = 5
−2y1 +y2 −2y3 −y4 =−2 These have solution y1∗ = y2∗ = y3∗ = 1.
So complementary slackness implies the dual optimal solution is (1, 1, 0, 1).
This gives optimal value 4 + 3 + 1 = 8. The optimal value of the primal was
24/3 + 10/3 − 10/3 = 8.
All the yi∗ > 0, sub into the constraints gives
1+4+3=8>7
3+2+1=6
−2 + 4 + 2 = 4 < 5 problem1 + 5 − 2 = 4 > 3
The dual solution implied by complementary slackness is not feasible. Hence the orginal values of x∗ is not optimal.
5. Question 5.3(b) from Chvatal.
maximise 4×1 +5×2 +x3 +3×4 −5×5 +8×6 stnon-negand 1 0 −4 3 1 1≤1 5 3 1 0 −5 3≤4 4 5 −3 3 −4 1 ≤ 4 0 −1 0 2 1 −5≤5 −2 1 1 1 2 2≤7 2 −3 2 −1 4 5≤5
Is (0, 0, 5/2, 7/2, 0, 1/2) optimal?
Solution:
Since x3, x4, x6 > 0 the corresponding dual constraints are equalities:
−4y1 +y2 −3y3 +y5 +2y6 = 1 3y1 +3y3 +2y4 +y5 −y6 = 3 y1 +3y2 +y3 −5y4 +2y5 +5y6 = 8
Page 7 of 8
Mathematics 340 Section 202 Homework 5 Due Friday, March 5th
Sub the x∗ into the constraints to get
−20/2 + 21/2 + 1/2 = 1 5/2 + 3/2 = 4
−15/2 + 21/2 + 1/2 = 7/2 < 4 14/2 − 5/2 = 9/2 < 5
5/2 + 7/2 + 2/2 = 7 10/2 − 7/2 + 5/2 = 4 < 5
Since the third, fourth and sixth constraints are strict inequalities, it follows that y3∗, y4∗, y6∗ = 0.
Hence we need to solve
−4y1 +y2 +y5 =1 3y1 + y5 = 3 y1 +3y2 +2y5 =8
This solve to give y1∗ = 1/2, y2∗ = 3/2, y5∗ = 3/2.
The dual objective function is z = 1/2 + 12/2 + 21/2 = 17. The primal is
5/2 + 21/2 + 8/2 = 17.
The dual variables are all non-negative. Need to check dual constraints.
[1,5,4,0,−2,2][1/2,3/2,0,0,3/2,0]T =1/2+15/2−6/2=5>4 [0,3,5,−1,1,−3][1/2,3/2,0,0,3/2,0]T =9/2+3/2=12/2>1 [−4,1,−3,0,1,2][1/2,3/2,0,0,3/2,0]T =−4/2+3/2+3/2=1
[3,0,3,2,1,−1][1/2,3/2,0,0,3/2,0]T =3/2+3/2=3 [1,−5,−4,1,2,4][1/2,3/2,0,0,3/2,0]T =1/2−15/2+6/2=−8/2>−5
[1,3,1,−5,2,5][1/2,3/2,0,0,3/2,0]T =1/2+9/2+6/2=8
So the dual solution is feasible and gives same objective function.
Hence the original solution is optimal.
Page 8 of 8