1. Consider the following linear programming problem and its dual: minimize cx subject to Ax=b x...

 

Transcribed Image Text:

1. Consider the following linear programming problem and its dual: minimize cx subject to Ax=b x ≥ 0. maximize by subject to Ay≤ c. and assume that both problems have an optimal solution. Fix some j. Suppose that every optimal solution to the primal satisfies x, = 0. Show that there exists an optimal solution y to the dual such that Ay < cj (where A is the j-th row of AT). Hint: Let d be the optimal cost. Con- sider the problem of minimizing -x, subject to Axb, x ≥ 0,-c¹x ≥ -d, and form its dual. 2. Show that there exist optimal solutions x and y to the primal and to the dual, respectively, such that for every j we have either a > 0 or Afy <cj. Hint: Use part (1) for each j, and then take the average of the vectors obtained. 3. Consider the following linear programming problem and its dual: minimize cx subject to Ax ≥ b x ≥ 0. maximize by subject to A y ≤ c. y ≥ 0. Assume that both problems have an optimal solution. Show that there exist optimal solutions to the primal and to the dual, respectively, that satisfy strict complementary slackness, that is: (a) For every j we have either a; > 0 or Ay <cj. (b) For every i, we have either a,x > b; or y;> 0. (Here, a, is the i-th row of A). 1. Consider the following linear programming problem and its dual: minimize cx subject to Ax=b x ≥ 0. maximize by subject to Ay≤ c. and assume that both problems have an optimal solution. Fix some j. Suppose that every optimal solution to the primal satisfies x, = 0. Show that there exists an optimal solution y to the dual such that Ay < cj (where A is the j-th row of AT). Hint: Let d be the optimal cost. Con- sider the problem of minimizing -x, subject to Axb, x ≥ 0,-c¹x ≥ -d, and form its dual. 2. Show that there exist optimal solutions x and y to the primal and to the dual, respectively, such that for every j we have either a > 0 or Afy <cj. Hint: Use part (1) for each j, and then take the average of the vectors obtained. 3. Consider the following linear programming problem and its dual: minimize cx subject to Ax ≥ b x ≥ 0. maximize by subject to A y ≤ c. y ≥ 0. Assume that both problems have an optimal solution. Show that there exist optimal solutions to the primal and to the dual, respectively, that satisfy strict complementary slackness, that is: (a) For every j we have either a; > 0 or Ay <cj. (b) For every i, we have either a,x > b; or y;> 0. (Here, a, is the i-th row of A).

Answer rating: 100% (QA)

Q1 To prove the statement well use the hint provided and consider the problem of minimizing cTx subject to Ax b x 0 and cTx d where d is the optimal cost Lets denote this problem as P The dual problem ... View the full answer