Some practice problems for Math 340
1 (10 points). Use a graphical method to find the optimal solution to
maximize 3×1 + 4×2 subjectto x1 + 2×2 2×1 + x2 −x1 + x2 x1, x2
≤ 60 ≤ 80 ≤ 20 ≥ 0
2 (15 points). Consider the dictionary below. x1 = (4 − 2α) −
x2= β+ s3= 4− z = γ +
s1
s1 2s1 (α − 3)s1
+ s2 + 2s2 − 3s2 + δs2
This dictionary is repeated overleaf for your convenience.
(a) (4 points) Find the range of values for each of α,β,γ,δ such that the dictionary is feasible.
(b) (4 points) Find the range of values for each of α,β,γ,δ such that the dictionary is dual feasible.
(c) (7 points) Find the range of values for each of α,β,γ,δ such that the dictionary is dual feasible but not feasible.
3 (15 points). (a) (5 points) State the Weak Duality Theorem.
(b) (10 points) Consider a primal LP problem with a feasible solution x∗ that yields z∗ when substituted into the objective function z. Let its dual LP problem have a feasible solution y∗ that yields w∗ when substituted into its objective function w.
Prove that if z∗ = w∗ = α then α is the optimal value for both problems.
4 (15 points). Consider the problem
Maximize 10×1 +18×2 +10×3 subject to 2×1 +2×2 +x3 ≤ 7 x1 +3×2 +2×3 ≤ 5 x1, x2, x3≥0.
(a) (5 points) A friend claims she solved it using the simplex method and got optimal value 43. Prove she is wrong without using the simplex method or complimentary slackness.
(b) (10 points) Another friend says
“I got optimal solution 11 , 0, 3 and optimal value 41.”
44
Use complimentary slackness to answer the following.
Is x1 = 11 , x2 = 0, x3 = 3 the optimal solution? Is 41 the optimal value? 44
5 (20 points). Consider the problem Maximize
subject to
2×1 +3×2 +3×3
3×1 +x2
−x1 +x2 +4×3
2×1 −2×2 +5×3 x1, x2, x3
≤60 ≤ 10 ≤ 15 ≥ 0.
Solve this problem using the revised simplex method and eta factorization. Use the largest coefficient rule to select your entering and leaving variables. (You should find you are stopped during the third iteration.)
6 (25 points). We run a small smoothie company with four flavours: Apple-Acai, Banana- Berry, Citrus Cooler, and Durian Delight. To make a carton of Apple-Acai we require 1 kg mixed fruit and 1 kg yogurt. To make a carton of Banana-Berry we require 2 kg mixed fruit and 1 kg yogurt. To make a carton of Citrus Cooler we require 3 kg mixed fruit and 2 kg yogurt. To make a carton of Durian Delight we require 1 kg mixed fruit and 3 kg yogurt. On each carton of Apple-Acai we make $ 5 profit, each carton of Banana-Berry $ 6 profit, each carton of Citrus Cooler $ 9 profit, each carton of Durian Delight $ 8.
We can afford 50 kg mixed fruit, and 30 kg yogurt per day. If x1, x2, x3 are the 10’s of cartons we sell per day we get the following Linear Program.
maximise5x1 +6×2 +9×3 +8×4 subjecttox1,x2,x3,x4 ≥0and x1+2×2+3×3+x4 ≤ 5
x1+x2+2×3+3×4 ≤ 3 After applying the simplex method we get the final dictionary
x1 = 1 −x3 −5×4 +s1 −2s2 x2 = 2 −x3 +2×4 −s1 +s2 z = 17 −2×3 −5×4 −s1 −4s2
(a) (5 points) Compute B for the revised simplex method for this final dictionary and label your columns appropriately. Calculate B−1.
(b) (5 points) A carton of Mango Madness can be made from 1 kg mixed fruit and 2 kg yogurt at a profit of $ 7. Is it profitable to produce it?
(c) (5 points) Determine the range on b2 (yogurt) so that the basis {x1,x2} remains opti- mal.
(d) (5 points) Determine the range on c1 (profit on Apple-Acai) so that the basis {x1,x2} remains optimal.
(e) (5 points) If we can afford 70 kg of yogurt per day what is the new optimal value, and optimal solution?
Mathematics 340 more detailed!)
(x1,x2) z (0,0) 0
(0, 20) 80 (62,262) 1262
(331,131) 1531 333
Very Brief Solutions (Your actual solutions should be much
1.
2.
333
(40, 0) 120
(a) α ≤ 2, 0 ≤ β, γ anything, δ anything.
(b) α ≤ 3, β anything, γ anything, δ ≤ 0.
(c) α≤2,β<0OR2<α≤3,βanything,THENγanything,δ≤0.
3. (a) See the notes.
(b)BytheWDTiftheprimaloptimalvalueisZthenα=z∗ ≤Z≤w∗ =α. Bythe
WDT if the dual optimal value is W then α = z∗ ≤ W ≤ w∗ = α. So Z = W = α. 4. (a) Add 3 times the first and 4 times the second constraint to get
10x1 +18x2 +10x3 ≤ 10x1 +18x2 +11x3 ≤ 41 so 41 is an upper bound, and the answer can’t be 43.
(b) NO: The 1st and 2nd constraint aren’t maximized, so y1 = y2 = 0. Since x1,x3 > 0 this means 2y1 + y2 = 10 = y1 + 2y2 so y1, y2 ̸= 0. So this isn’t the optimal solution.
YES: Letting x1 = 11,×2 = 0,×3 = 3 we get y1 = 3,y2 = 4, the constraints are satisfied 44
and in both cases z = 41. 5. First iteration:
Form matrices.
60 60 s1 x1
b=10 x∗B =10 xB =s2 xN =x2 cB =0 0 0 cN =2 3 3
15 15 s3 x3
s1 s2 s3 x1 x2 x3 100 310 B0=I=0 1 0AN=−1 1 4
0 0 1 2 −2 5
Solve yB = cB to get y = 0 0 0. Then cN − yAN = 2 3 3. Hence x2 enters
1
and d = 1 . So t = 10. Since the second component = 0, it follows that s2 leaves. −2
Update things
50 s1 x1
x∗B=10 xB=x2 xN=s2 cB=0 3 0 cN=2 0 3
Second iteration:
Third iteration:
35 s3 x3
x1 s2 x3
3 0 0 1 1 0
AN=−1 1 4 E1=0 1 0 2 0 5 0 −2 1
SolveyE1 =cB togety=0 3 0. ThencN−yAN =5 −3 −9.Hencex1 enters 4
and d = −1. So t = 25/2. Since the first component = 0, it follows that s1 leaves. 0
Update things
25/2 x1 s1
x∗B =45/2 xB =x2 xN =s2cB =2 3 0 cN =0 0 3
35 s3 x3
s1 s2 x3
1 0 0 1 1 0 4 0 0
AN = 0 1 4 E1 = 0 1 0 E2 = −1 1 0
0 0 5 0 −2 1
0 0 1
=⇒ u=5/4 3 0 =⇒ y=5/4 7/4 0
Solve yE1E2 = cB.
u1 u2 u3−1 1 0=2 3 0
4 0 0 001
1 1 0
y1 y2 y30 1 0=5/4 3 0
0 −2 1 Choose entering variable.
cN−yAN=003−5/47/40 0 1 4=−5/4−7/4−4
005
Since all are negative, there are no entering columns. The current BFS is optimal.
s1 s2 x3 100
The solution is
xB =x2=x∗B =45/2 xN =s2=0 z=185/2.
x1 25/2 s1 0 s3 35 x3 0
x1 x2
1 2 −1 −1 2
6. (a)B= 1 1 ,B = 1 −1 (b) 1.1+2.4=9>7sono.
(c) 5 ≤α≤5. 2
(d) 4≤β≤6.
(e) Dual pivot to get dictionary
x1 = 4 −5×2 −7×3 −3s1 −9s2 2222
x4 = 1 +1×2 +1×3 +1s1 −1s2 2222
x4 = 28 −5×2 −9×3 −3s1 −3s2 2222
and solution x1 = 4,×2 = 0,×3 = 0,×4 = 1,s1 = s2 = 0 and optimal value 28.