This assignment has four problems, of equal weight.

1   Given any matrix A, and vectors b and c (such that the multiplications below are defined), consider the pair of dual problems

  (P)   max c^Tx   s.t.   Ax = b,   x > 0

  (D)   min b^T y   s.t.   A^Ty > c

• Give examples to show that all 4 cases of the Duality Theorem are possible.
• Use the Duality Theorem to prove Farkas' Lemma: Given any matrix A and vector b, the following statements are equivalent:
  • The system Ax = b,   x > 0 is consistent
  • A^Ty > 0   implies   b^Ty > 0
• Prove: If x and y are feasible soutions of (P) and (D) resp., then x and y are optimal for their respective problems iff x^T (A^Ty - c) = 0

2   Text, p. 153, Exercise 21.

3   Text, p. 153, Exercise 22.

4   Text, p. 153, Exercise 23.