APM236 HW51
Due: Sat Mar 26 (before 9pm) on Crowdmark
(1) Use the two-phase method to solve the LPP in Q.7 on HW2.
(2) Consider the following LPP where a, b ∈ R:
maximize ax1 + bx2
subject to x1 3×2 = 6
x1, x2 ≥ 0
(a) Solve this LPP graphically. Hint: you should consider 3 cases which have to do with
the possibile directions of the vector (a, b).
(b) Use the two phase method to find solution(s) to this LPP when b is positive and a = 1.
Do you get the same solutions you found in part (a)
(3) Consider the following LPP where a, b ∈ R:
maximize ax1 + bx2
subject to x1 + 2×2 ≥ 6
x1, x2 ≥ 0
(a) Solve this LPP graphically. Hint: you should consider 4 cases which have to do with
the possibile directions of the vector (a, b).
(b) Use the two phase method to find solution(s) to this LPP when a = 1, b = 2. Do you
get the same solutions you found in part (a)
(4) Read KB sec 2.2 example 2 (pp.127-128) where following the Simplex algorithm results in
cycling. Now, starting with the LPP in Q.4 on HW4 apply the Simplex algorithm using
the modified lexicographical pivoting rule2 to solve the problem. Show all your work.
(5) Consider the primal LPP in Q2 above where a is negative:
maximize ax1 x2
subject to x1 3×2 = 6
x1, x2 ≥ 0
(a) Find the dual of this problem and solve it graphically.
(b) Use complementary slackness and the solution(s) you found in part (a) to find solu-
tion(s) to the primal LPP. Do you get the same answer you found in Q2
(6) Consider the following primal LPP:
maximize z = 2×1 +
x2
3
subject to x1 + 2×2 ≥ 0
x1 x2 ≤ 3
x1, x2 ≥ 0
1Copyright c 2022 J. Korman. Sharing or selling this material without permission of author is a copyright violation.
2see Announcement about “Anticycling rule” on Quercus.
1
(a) Solve this problem graphically.
(b) Find the dual of this problem and solve it graphically.
(c) Use complementary slackness and the solution(s) you found in part (b) to find solu-
tion(s) to the primal LPP. Do you get the same answer you found in part (a)
