Math 340 Practice Midterm Time 45min
This is a closed-book examination. ONLY pen/pencil/eraser are allowed.
1. (4 points) You are given an LP problem and are also given a feasible solution to it and a feasible solution to its dual. Explain (referring to relevant theorems) why both problems must have optimal solutions.
Solution:
• The fundamental theorem of LP tells us that an LP problem is either infeasible, unbounded or has an optimal solution.
• Since the primal problem and the dual problem have feasible solutions they must be either unbounded or have optimal solutions.
• Weak duality implies that the optimal value of the primal problem is bounded above by the optimal value of the dual problem. Alternatively The strong duality theorem tells us that the optimal value of the primal problem is equal to that of the dual problem.
• Hence if the primal problem were unbounded, then there could not be a feasible solution to the dual. And if the dual problem were unbounded, then there cannot be a solution to the primal problem.
• Hence both problems have optimal solutions.
Math340 Practice Midterm
2. A colleague hands you the following LP problem
x1, x2, x3, x4 ≥ 0
and tells you that they used the simplex method to get to the following dictionary:
x2 = 20 −2×1 −4×3 −4×5 +1×6 3333
x4 = 4 +1×3 +1×5 −1×6 3333
x7 = 1 +4×1 +6×3 +10×5 −3×6 z = 52 −3×1 −6×3 −5×5 −x6
(a) (2 points) Find the optimal solution.
Maximize 9×1 +6×2 Subject to 2×1 +x2 2×1 +x2
+x3 +9×4 +x3 +x4 +4×4 10×1 +7×2 +4×3 −2×4
≤ 8 ≤ 12 ≤ 45
Solution:
• Since all coefficients in z are negative this is an optimal dictionary. • The optimal solution is therefore
x1 = 0 x2 = 20 x3 = 0 x4 = 4 33
x5 = 0 x6 = 0 x7 = 1 z = 52
(b) (3 points) Write down the dual of the original problem.
Math340 Practice Midterm
Solution:
• The dual is
Minimize Subject to
8y1 +12y2 +45y3 2y1 +2y2 +10y3 y1 +y2 +7y3 y1 +4y3 y1 +4y2 −2y3
≥ 9 ≥ 6 ≥ 1 ≥ 9
y1, y2, y3≥0
(c) (2 points) Find the optimal solution to the dual problem.
Solution:
• Strong duality tells us we can read off the optimal solution of the dual problem from the coefficients of optimal dictionary.
• In particular y∗ = −c ̄
i n+i
• Hence the optimal solution of the dual is
y 1∗ = 5 y 2∗ = 1 y 3∗ = 0
• Thisgivesobjectivefunctionvalue8×5+12×1+0=52
• Substitute into dual constraints to check feasibility
10 + 2 + 0 > 9 5+1+0>6 5+0>1 5+4−0>9
So all are satisfied and all yi∗ ≥ 0.
Math340 Practice Midterm
3. (6 points) Use the two-phase simplex method (and Anstee’s rule) to solve the following linear programming problem:
Maximize Subject to
5×1 +3×2
2×1 +4×2 ≤ 4 −x1 −x2 ≤ −6
x1, x2 ≥0
Solution:
• Write in dictionary form
x3 = 4 −2×1 −4×2 x4 = −6 +x1 +x2 z = 0 +5×1 +3×2
• This is not a feasible dictionary, so we must use the two-phase method.
• Form the auxiliary problem. We add x0 to each row and replace the objective
function w = −x0:
x3 = 4 −2×1 −4×2 +x0 x4 = −6 +x1 +x2 +x0 w= −x0
• The most negative row is x4 so we do a “fake pivot to feasibility” where x0 enters and x4 leaves:
x0 = 6 −x1 −x2 +x4 x3 = 10 −3×1 −5×2 +x4 w = −6 +x1 +x2 −x4
• By Anstee’s rule — x1 enters and x3 leaves
x0 = (8/3) +(2/3)x2 +(1/3)x3 +(2/3)x4 x1 = (10/3) −(5/3)x2 −(1/3)x3 +(1/3)x4 w = −(8/3) −(2/3)x2 −(1/3)x3 −(2/3)x4
• There are no entering variables because all the coefficients in the objective function are negative.
• Hence the optimal value of auxiliary problem is −8/3. Hence the minimum value of x0 = 8/3.
• Since the optimal value of x0 ̸= 0 we conclude that the original problem is not feasible.
Math340 Practice Midterm
Extra work space for Question 3
Math340 Practice Midterm
4. (8 points) Check whether each of the following statements is correct or not. Circle True or False, and you do not need to explain your answer. Each correct answer will earn 1 mark.
(a)
i. True / False. If a standard form linear programming problem is feasible but unbounded, then its dual problem is infeasible.
ii. True / False. Given a linear programming problem, it is possible to have no optimal solution, while there is an optimal solution to its dual problem.
iii. True / False. There is a linear programming problem for which both primal and dual problems are not feasible simulataneously.
iv. True / False. For each vector ⃗y ∈ Rn, it holds that max [⃗y · ⃗x] = +∞. ⃗x∈Rn
Solution:
a. True by weak duality b. False by strong duality
c. True.
d. False. If⃗y=⃗0,thenmax[⃗y·⃗x]=0. ⃗x∈Rn
(b) (Read carefully.) Suppose that Prof. Anstee is following his rule to perform the simplex method to solve an LP problem. At a certain step he gets a feasible dictio- nary D1, and by continuing iterations (”pivotings”), he gets subsequent dictionaries D2, D3, D4, D5, D6, and D7.
i. True / False. The dictionaries D2, D3, D4, D5, D6, D7 must be feasible.
ii. True / False. In some cases, it is possible to have an optimal basic solution
to D1 but, non-optimal basic solution to D3.
iii. True / False. If D7 is identical to D1, then this LP problem has no optimal
solution.
iv. True / False. If D7 is not identical to D1, then the dictionaries D1, D2, D3,
D4, D5, D6, and D7 all have different basic solutions from each other.
Solution:
Math340 Practice Midterm
a. True. If started from a feasible dictionary, the simplex methods gives only feasible dictionaries.
b. False. Each pivot from a feasible dictionary only improves the objective function value. Once optimal, it stays to be optimal, as you cannot im- proved the optimal value.
c. False. Cycling does not imply that there is no optimal solution.
d. False. It is possible to be degenerate without cycling, thus having the same basic solutions between two consecutive dictionaries.
Math340 Practice Midterm
5. A colleague hands you the following LP problem
Maximize z = 2×1 +x2 +2×3 Subject to x1 +x2 +2×3 3×1 +6×2 +3×3 4×1 +2×2 +2×3 x1, x2, x3
≤6 ≤ 18 ≤ 12 ≥ 0
and tells you that they found the following optimal solution.
x∗1 =2 x∗2 =0 x∗3 =2 z=8
(a) (2 points) Check that their solution is feasible.
Solution:
• All are non-negative.
• Substitute into the inequalities
2+4=6 6 + 6 < 18 8 + 4 = 12
(b) (6 points) Check that their solution is optimal using complementary slackness.
Solution:
• Write down the dual problem:
Minimise 6y1 +18y2 +12y3 subject to y1 +3y2 +4y3 ≥ 2 y1 +6y2 +2y3 ≥ 1 2y1 +3y2 +2y3 ≥ 2 y1, y2, y3≥0
Math340 Practice Midterm
• Since x∗1,x∗3 > 0 it follows that the first and third dual constraints are equalities:
y1 +3y2 +4y3 =2 2y1 +3y2 +2y3 =2
• The second primal constraint is a strict inequality, so y2∗ = 0.
• Hence
y1 + 4y3 = 2 2y1 + 2y3 = 2
whichsolvetogivey∗ =2 andy =1. 13 33
• This gives objective function 12/3 + 12/3 = 8
• These are all non-negative, and substituting into the dual constraints gives
2/3 + 4/3 = 2 2/3+2/3 > 1 4/3 + 2/3 = 2
• The dual solution implied by complementary slackness is feasible and gives the same objective function. Hence the original solution is optimal.
Math340 Practice Midterm
Extra Page 1
Math340 Practice Midterm
Extra Page 2
Math340 Practice Midterm
Extra Page 3
Math340 Practice Midterm