### Homework 1

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 -3
*x*_{1}
- 2*x*_{2} subject to *x* being nonnegative and

-2*x*_{1} + *x*_{2} ≤ 1

*x*_{1} ≤ 2

*x*_{1} + *x*_{2} ≤ 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 *x*_{1} + *x*_{2}

subject to *sx*_{1} + *tx*_{2} ≤ 1

*x*_{1} , *x*_{2} ≥ 0

- have an optimal solution
- be infeasible
- be unbounded