Math 484.2 October 23, 2003. Name:________L. Vaserstein_______________
Midterm 2, 5 problems, 15 points each.
Solve linear programs where all xi >= 0:
1.
| -2 |
x2 |
3 |
-x3 |
|
| 1 |
2 |
3 |
4 |
= x1 |
| 5 |
6 |
-7 |
8 |
=-x4 |
| 0 |
1 |
2 |
3 |
-> min |
combine two columns with constants on top together and multiply
a column and a row by -1.
standard feasible tableau:
| x2 |
x3 |
1 |
|
| 2 |
-4* |
7 |
= x1 |
| -6 |
8 |
31 |
= x4 |
| 1 |
-3 |
6 |
-> min |
pivot step according to Phase 2 of simplex method
| x2 |
x1 |
1 |
|
| 1/2 |
-1/4 |
7/4 |
= x3 |
| -2* |
-2 |
45 |
= x4 |
| -1/2 |
3/4 |
3/4 |
-> min |
pivot step according to Phase 2 of simplex method
| x4 |
x1 |
1 |
|
| -1/4 |
-3/4 |
13 |
= x3 |
| -1/2 |
-1 |
45/2 |
= x2 |
| 1/4 |
5/4 |
-21/2 |
-> min |
The tableau is optimal, so min = -21/2=-10.5 at x1=0,
x2=
45/2, x3=13, x4= 0.
2.
| -2 |
-x2 |
-3 |
-x1 |
|
| 1 |
2 |
3 |
4 |
= x1 |
| 5 |
6 |
7 |
8 |
= x4 |
| 0 |
1 |
2 |
3 |
-> min |
combine two columns with constants on top together and multiply
a column by -1
| x2 |
-x1 |
1 |
|
| -2* |
4 |
-11 |
= x1 |
| -6 |
8 |
-31 |
= x4 |
| -1 |
3 |
-6 |
-> min |
pivot step
| x1 |
-x1 |
1 |
|
| -1/2 |
2 |
-11/2 |
= x2 |
| 3 |
-4 |
2 |
= x4 |
| 1/2 |
1 |
-1/2 |
-> min |
combine the first two columns. standard tableau:
| x1 |
1 |
|
| -5/2 |
-11/2 |
= x2 |
| 7 |
2 |
=x4 |
| -1/2 |
-1/2 |
-> min |
x2-row is bad, so the program is infeasible.
3.
| 2 |
x2 |
3 |
-x3 |
|
| 1 |
2 |
3 |
4 |
= x1 |
| 5 |
6 |
7 |
8 |
=- x1 |
| 0 |
1 |
2 |
3 |
-> max |
combine two columns with constants on top together and multiply
a column by -1.
| x2 |
x3 |
1 |
|
| 2 |
-4 |
11 |
= x1 |
| 6 |
-8 |
31 |
= -x1 |
| 1 |
-3 |
6 |
-> max |
add the first row from the second row and multiply the third row by -1
| x2 |
x3 |
1 |
|
| 2 |
-4 |
11 |
= x1 |
| 8 |
-12* |
42 |
= 0 |
| -1 |
3 |
-6 |
-> min |
pivot on -12 and drop the second column to obtain standard tableau
| x2 |
1 |
|
| -2/3 |
-3 |
= x1 |
| 2/3 |
7/2 |
= x3 |
| 1 |
9/2 |
-> min |
The x1-row is bad, so the program is infeasible.
4.
| x3 |
x2 |
1 |
-x3 |
|
| 1 |
2 |
3 |
4 |
= x1 |
| 5 |
6 |
7 |
0 |
=x4 |
| 0 |
1 |
2 |
3 |
-> min |
combine the first and the last column to obtain standard tableau
| x3 |
x2 |
1 |
|
| -3* |
2 |
3 |
= x1 |
| 5 |
6 |
7 |
=x4 |
| -3 |
1 |
2 |
-> min |
pivot step according to Phase 2 of simplex method
| |
x2 |
1 |
|
|
2/3 |
1 |
|
|
28/3 |
12 |
|
|
-1 |
|
-> min |
(irrelevant entries are not shown). Now x2-column is bad, so the program is unbounded.
5.
| 0 |
x2 |
-1 |
-x3 |
|
| 1 |
2 |
3 |
4 |
= -x1 |
| 5 |
6 |
7 |
8 |
= x4 |
| 0 |
1 |
2 |
3 |
-> min |
drop the first column, switch columns, and multiply a column
and a row by -1 to obtain standard tableau
| x2 |
x3 |
1 |
|
| -2 |
4 |
3 |
= x1 |
| 6* |
-8 |
-7 |
= x4 |
| 1 |
-3 |
-2 |
-> min |
pivot step according to Phase 1 of simplex method
| x4 |
x3 |
1 |
|
|
4/3 |
2/3 |
= x1 |
| 1/6 |
4/3 |
7/6 |
= x2 |
|
-5/3 |
|
-> min |
This is a feasible tableau with x3-column
bad, so the program is unbounded.