首页 > > 详细

辅导 APM236 HW5讲解 Java语言

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 abc 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.






联系我们
  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp
热点标签

联系我们 - QQ: 99515681 微信:codinghelp
程序辅导网!