APM236 HW5
Due date: Sat, Apr 6 (before 9pm) on Crowdmark.
(1) Let a > 0 be a positive number and consider the LPP from Q5 on the midterm project:
maximize z = 2x1+ 0x2+ 2x3+ 4x4
subject to x1 , x2 , x3 , x4 ≤ a
x1 , x2 , x3 , x4 ≥ 0
(a) Find the dual of this problem.
(b) Use complementary slackness and the solution to Q5 on the midterm project to find solution(s) to the dual LPP.
(2) Consider the following LPP from Q2 on the midterm project:
maximize y
subject to a1x1 + ··· + anxn+ y − t = b
x1 , ··· , xn,y, t ≥ 0,
here a1 , ··· , an, b > 0. Note that the variables in this problem are x1 , ··· , xn , y, and t.
(a) Find the dual of this problem and solve it (in any way you like).
(b) Use complementary slackness or the Strong Duality Theorem to conclude something about the solution(s) to the primal LPP. Do you get the same answer you found on Q2 of the midterm project?
(3) Let a ≥ 0 and consider the following LPP:
maximize x1 + ax2
subject to 4x1 − 3x2 ≥ 12
x1 ≥ 0
x2 free
(a) Find the dual of this problem. Does the dual have optimal solutions?
(b) Are you able to use complementary slackness and your answer to part (a) to find so- lution(s) to the primal LPP? Why or why not?
(4) Consider the following LPP where all the constants ci are positive:
maximize ：cixi
subject to xi ≤ i for i = 1,..., n − 1
xi ≥ 0 for i = 1,...,n.
Note that there is no upper bound on xn.
(a) Find a formula for the optimal cost. Hint: consider the cases when n is even and then the cases when it is odd.
(b) Write the dual and find an optimal solution to the dual.
(c) Use complementary slackness and the solution(s) you found in part (b) to find primal optimal solution(s). Do you get the same answer you found in part (a)?
(5) Let a, b, c E R2 be three fixed vectors, where a and b are linearly independent and c ≠ 0. Let d be a positive number. Suppose the following primal LPP has a maximizer x* E R2:
maximize: cTx
subject to: bTx ≤ d
aTx = 1
(a) Find all BFS and the maximal value. Hint: how many constraints are active at the BFS?
(b) Find and solve the dual problem.
(c) Use complementary slackness and the solution to part (b) to find solution(s) to the primal LPP above. Do you get the same solution you got in part (a)?
(6) Let (a1 , b1 ), . . . , (an, bn) be n points in the plane R2 . Supopse we are trying to find a line L with equation y = αx + β, such that the sum of the vertical distances from the points (ai, bi) to L is minimized. We set up the following piecewise linear convex problem:
α(m) |αai+ β - bi|
Note that here α,β are the variables and that they are free variables.
(a) Write this problem as a linear programming problem. Hint: you should have (free) variables: α,β, and z1 ,...,zn.
(b) Find the dual of your LPP from part (a).
(c) If you need to solve the piecewise linear convex problem above, would you choose to solve the primal problem (part a) or the dual problem (part b)? Explain.