Mathematics 340 Practice Midterm Questions Page 1 of 5
Practice midterm questions — do not hand in
1. Use the two-phase method to solve the following LP problem
Maximise Subject to
x1 +3×2 −6×3
x1 −x2 −x1
−x3 ≤ 2
+x3 ≤ −1 x2 −x3 ≤ 2
x1, x2 ≥0
Solution:
• Axillary problem
• Solve it to get
x4 = 2−x1
x5 = −1 +x1
x6 = 2
w= −x0
x1 =1 −x0 x4 = 1 +2×0 x6 =2 +x0 w= −x0
+x3 +x5 +x2 −x5
−x2 +x3
• Hence original problem is feasible. Second phase dictionary is therefore
+x2 +x3 +x0 −x3 +x0
−x2 +x3
• Solve this to get
x1 = 1 x4 = 1 x6 = 2 z = 1
x1 = 4 x2 = 2 x5 = 3 z = 10
+x3 +x5 +x2 −x5
−x2 +x3
+3×2 −5×3 +x5
+2×3 −x4 −x6 +x3 −x6
+x3 −x4 −x6 −x3 −x4 −4×6
• So optimal value is z = 10 and optimal solution is
x1 = 4 x2 = 2 x3 = 0 x4 = 0 x5 = 3 x6 = 0
Page 1 of 5
Mathematics 340 Practice Midterm Questions 2. Consider the following LP problem:
Maximise 7×1 +5×2 +2×3 Subject to x1 +x2 +x3 x1 +3×2 +x3 3×1 +x2 +x3 x1, x2, x3
Page 2 of 5
≥0
Use complementary slackness to see if (x∗1, x∗2, x∗3) = (1, 3, 0) is an optimal solution.
≤ 5 ≤ 10 ≤ 6
Solution:
• The primal objective function is 7 + 15 = 22.
• Subsituting (x∗1, x∗2, x∗3) = (1, 3, 0) into the primal constraints gives
4<5 10 = 10 6=6
So complementary slackness implies that y1∗ = 0.
• The dual problem is
Minimise 5y1 +10y2 +6y3
ST y1 +y2 +3y3 ≥ 7 y1 +3y2 +y3 ≥ 5 y1 +y2 +y3 ≥ 2
• Since x∗1,x∗2 > 0, Complementary slackness implies that the first and second dual constraints are equalities:
y1 + y2 + 3y3 = 7 y1 + 3y2 + y3 = 5
• Since y1∗ = 0 we have two equations to solve y 2∗ + 3 y 3∗ = 7
3 y 2∗ + y 3∗ = 5 These have solution y2∗ = 1, y3∗ = 2.
Page 2 of 5
Mathematics 340 Practice Midterm Questions Page 3 of 5
• Check that (y1∗, y2∗, y3∗) = (0, 1, 2) is feasible and gives same objective function value:
0 + 10 + 12 = z = 22 0+1+6=7 0+6+1>5 0+2+1>2
• Since this is feasible and gives same objective function value, we conclude that (1, 3, 0) is indeed an optimal solution.
3. (a) State the fundamental theorem of linear programming.
Solution: Every linear programming problem in standard form has the follow- ing three properties:
• If it has no optimal solution then it is either infeasible or unbounded. • If it has a feasible solution then it has a basic feasible solution.
• If it has an optimal solution then it has a basic optimal solution.
(b) Explain (referring to relevant theorems) why if a primal problem is unbounded then the corresponding dual problem must be infeasible.
Solution:
• The weak duality theorem says that if ⃗x∗ is any feasible solution to the primal problem and ⃗y∗ is any feasible solution to the corresponding dual problem then
⃗c.⃗x∗ ≤⃗b.⃗y∗
ie the value of the objective function of the primal problem at ⃗x∗ is less
than or equal to the objective function of the dual problem at ⃗y∗.
• Say that the primal problem is unbounded but that the dual problem has
a feasible solution ⃗y∗.
• The objective function of the dual problem at ⃗y∗ takes some value — call it M.
Page 3 of 5
Mathematics 340 Practice Midterm Questions Page 4 of 5
• The weak duality theorem implies that for any feasible solution ⃗x∗ of the primal problem we have
⃗c.⃗x∗ ≤ M
• Hence the objective function of the primal problem is bounded above by
M.
• This contradicts the assumption that the primal problem is unbounded.
• Hence no feasible solution to the dual problem can exist. ie the dual problem is infeasible.
4. At Caf ́e Sunfrancs a cappuccino is made from one shot of espresso, three ounces of milk, and six ounces of foam. A latt ́e is made from one shot of espresso, seven ounces of milk, and two ounces of foam. A caf ́e sells only cappucinos and latt ́es, and makes one dollar profit on each drink it sells. Today the caf ́e has materials to produce 50 shots of espresso, 20 ounces of milk, and 30 ounces of foam.
Write down a linear program to maximize the profit the caf ́e will make. Write down the dual LP. For all variables involved (objective, decision, and slack, both in the primal and dual), state in what units they are given.
Solution:
• Let x1 =# cappucinos made, and x2 =# latt ́es made.
• Let z = dollars of profit.
• The primal problem is
maximise x1 subject to x1
+x2
+x2≤50 3×1 +7×2 ≤ 20 6×1 +2×2 ≤ 30 x1, x2,≥0
(espresso bound) (milk bound) (foam bound) non-negativity
• Since the right-hand side of the constraints
foam (respectively), it follows that the slack variables x3,x4,x5 are in units of espressos, milk and foam (respectively).
are units of espresso, milk and
Page 4 of 5
Mathematics 340 Practice Midterm Questions Page 5 of 5
• The dual problem is
minimise 50y1 subject to y1
+20y2 +30y3
+3y2 +6y3 y1 +7y2 +2y3
≥ 1 ≥ 1 ≥ 0
(dollars per cappucino) (dollars per latt ́e) non-negativity
y1, y2, y3
• The objective function is measured in dollars.
• y1 is dollars per espresso, y2 is dollars per unit of milk and y3 is dollars per unit of foam.
• Since the right-hand side of the dual constraints are dollars per cappucino and dollars per latt ́e, it follows that the dual slack variables, y4 and y5 are in units of dollars per cappucino and dollars per latt ́e (respectively).
Page 5 of 5