47-856 Theory and Algorithms for Linear Programming
Spring 2001, Mini 3
Homework 1

Do Exercises 1-4 as indicated in the notes. Also do the following exercise:

5.
Consider a skew-symmetric LP model with

\begin{displaymath}M= \left[ \begin{array}{rr} 0 & 1 \\ -1 & 0 \end{array} \righ... ...x{ and } q= \left[ \begin{array}{r} a \\ b \end{array} \right] \end{displaymath}

for some nonnegative a and b. What condition should a and/or bsatisfy for the IPA to be satisfied? Assuming that this condition is satisfied determine the optimal set of solutions. Also, again assuming that IPA is satisfied, determine the solution $x(\mu)$ of the system (CP) given on top of p. 12 as a function of $\mu$ (note that a=0 is allowed). Compute the limit of $x(\mu)$ as $\mu$ approaches zero (again, consider the case a=0).