Math 484.1  October 28, 2004.   Name:_________________________________________
Solve linear programs where all xi >= 0:

Solutions.

1. The second row says
-2-3x1  -x3 = x4  which contradicts  the condition  that all xi >= 0. So the LP is infeasible.

2. We simplify the tableau:

 x2 x1 1 Problem 2 2* -4 11 = x1 6 0 31 = x4 1 -3 6 -> min

We pivot this (nonstandard) tableau and obtain

 x1 x1 1 Problem 2 1/2 2 -11/2 =x2 3 12 -2 = x4 1/2 -1 1/2 -> min
Combining the first two columns, we obtain a feasible tableau with a bad column  ( x1-column):
 x1 1 Problem 2 2.5 -11/2 =x2 15 -2 = x4 -0.5 1/2 -> min
So the LP is unbounded.

3. We simplify the tableau  :

 x2 x3 1 Problem 3 -2 -4 7 = x1 6 -1 11 = x1 1 -3 6 =f -> max

We subtract the first row from the second row and multiply the last row by -1

 x2 x3 1 Problem 3 -2 -4 7 = x1 8* 3 4 = 0 -1 3 -6 =-f -> min

Now we pivot on 8 and drop the first column (with 0 on top):
tract the first row from the second row and multiply the last ropw by -1
 x3 1 Problem 3 -4 7 = x1 -3/8 -1/2 = x2 27/8 13/2 =-f -> min

This is a standard tableau, and the  x2 row is bad. The LP is infeasible.
A short cut: the = 0 row in the  tableau we pivoted  is infeasible in presense of
the condition that all xi >= 0.

4.We simplify the tableau:

 x3 x2 1 Problem 4 -3* 2 9 = x1 0 1 21 = x4 -3 1 6 -> min
This is a feasible (standard) tableau. We use the symplex method.
We pivot and obtain

 x1 x2 1 Problem 4 -1/3 2/3 3 =x3 0 1 21 = x4 1 -1 -3 -> min
The  x2 column is bad (and we are in Phase 2), so the LP is unbounded.

5.  We simplify the tableau:

 x2 x3 1 Problem 5 2 -4 3 = x1 6 1 7 = x4 1 0 2 -> min
The tableau is standard and optimal. So
min = 2 at  x2 =x3  =0, x1=3, x4 = 7.

 0 x2 1 -x3 Problem 5 1 2 3 4 = x1 5 6 7 -1 = x4 0 1 2 0 -> min