Due in class, 2 February, 2012
- 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.
- 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.
- (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
- have an optimal solution
- be infeasible
- be unbounded