(a) The dual is as follows: max - cy s.t. My c, y 0. Since M...

 

Transcribed Image Text:

(a) The dual is as follows: max - cy s.t. My c, y 0. Since M = MT, MTy c is equivalent to My 2-c. Therefore, we can reformulate the dual problem as a minimization problem as follows: min s.t. cy My 2-c, y 0. Therefore, the dual problem is equivalent to the primal problem. 7 (b) First, it is obvious that if the problem has optimal solution, then it must have a feasible solution. Now we prove the other direction. If the problem has a feasible solution, then y = r is also feasible to the dual problem. Therefore, both the primal and dual problems are feasible. According to the weak duality theorem, they both have finite optimal solution. (a) The dual is as follows: max - cy s.t. My c, y 0. Since M = MT, MTy c is equivalent to My 2-c. Therefore, we can reformulate the dual problem as a minimization problem as follows: min s.t. cy My 2-c, y 0. Therefore, the dual problem is equivalent to the primal problem. 7 (b) First, it is obvious that if the problem has optimal solution, then it must have a feasible solution. Now we prove the other direction. If the problem has a feasible solution, then y = r is also feasible to the dual problem. Therefore, both the primal and dual problems are feasible. According to the weak duality theorem, they both have finite optimal solution.

Answer rating: 100% (QA)

Given primal LP maximize z 3x1 2x2 subject to 2x1 x2 4 x1 x2 ... View the full answer