Math 484.1  October 28, 2004.   Name:_________________________________________
Midterm 2,  5 problems, 15 points each.  Return this page.
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