Homework 1

Due in class, 2 February, 2012
  1. The bounds in Lemma 2.1 don't appear to be tight unless m = 1. (I could be wrong though. If you can find an example that's tight for m = 2, try m = 3.) Go through the proof and explain where tightness is lost.
  2. The following linear program was discussed in class: minimize -3x1 - 2x2 subject to x being nonnegative and
    -2x1 + x2 ≤ 1
    x1 ≤ 2
    x1 + x2 ≤ 3
    Add slack variables to convert this into standard form, and find the corners of the feasible polytope in the new coordinates.
  3. (Cowen) Find necessary and suļ¬ƒcient conditions for the numbers s and t to make the LP problem:
    Maximize x1 + x2
    subject to sx1 + tx2 ≤ 1
    x1 , x2 ≥ 0
    1. have an optimal solution
    2. be infeasible
    3. be unbounded