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 x3 -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.