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,-cx -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 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 b; or y;> 0. (Here, a, is the i-th row of A).