Math 484.2  October 28, 2004.   Name:_________________________________________
Midterm 2,  5 problems, 15 points each. Return this page.
Solve linear programs where all  xi >= 0:

Solutions.

1. We rewrite the LP in standard row tableau:

 x2 x3 1 Problem 1 -1 2 1 = x1 -6 0 31 =x4 1 -3 6 -> min
This is a feasible tableau, and the  x-column is bad. So the LP is unbounded.

2. We simplify the tableau:

 x2 x1 1 Problem 2 -2* 4 -11 = x1 -6 -8 -31 =x4 -1 -3 -6 -> min
This is not a standard tableau, but the second  equation  contradicts the condition that
all    xi >= 0. So the LP is infeasible.

3.Combining the columns with constants on top, we obtain

 x2 x3 1 Problem 3 2 -4 5 = x1 6 0 7 =- x1 1 -3 6 =f -> max
This tableau is not standard, but the second equation   contradicts the condition that
all    xi >= 0. So the LP is infeasible.
4.  We rewrite th LP in standard row tableau:

 x2 x3 1 Problem 4 -2 -3 3 = x1 6* 5 -1 =x4 1 1 2 -> min
Now we pivot on 6,  following the simplex method:

 x4 x3 1 Problem 4 -1/3 -4/3 8/3 = x1 1/6 -5/6 1/6 =x2 1/6 1/6 13/6 -> min
This is an optimal tableau, so
min= 13/6 at x1 = 8/3,  x2= 1/6,  x3 = x4 =  0.

5. We drop the column with 0 on top, scale row 1,  and switch and scale columns 3 and 4:

 x2 x3 1 Problem 5 -2 4 3 = x1 6 -1 -1 =x4 -1 -3 2 -> min
This is a standard tableau.  Instead of following the simplex method, we use a short cut.
Setting   x2=x3+1  we get a  feasible tableau with
a bad column:

 x3 1 Problem 5 2 1 = x1 5 5 =x4 -4 1 -> min
So the new program is unbounded, hence  so is the original problem.