Math 484.1 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 by -1.
standard feasible tableau:
| x2 |
x3 |
1 |
|
| 2 |
-4 |
7 |
= x1 |
| 6 |
-8* |
11 |
= x4 |
| 1 |
-3 |
6 |
-> min |
pivot step according to Phase 2 of simplex method
| x2 |
x4 |
1 |
|
| -1* |
1/2 |
3/2 |
= x1 |
| 3/4 |
-1/8 |
11/8 |
= x3 |
| -5/4 |
3/8 |
15/8 |
-> min |
pivot step according to Phase 2 of simplex method
| x1 |
x4 |
1 |
|
| -1 |
1/2 |
3/2 |
= x2 |
| -3/4 |
1/4 |
5/2 |
= x3 |
| 5/4 |
-1/4 |
0 |
-> min |
The x4-column is bad, so the program is unbounded.
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
| x2 |
-x1 |
1 |
|
| 2* |
4 |
7 |
= x1 |
| 6 |
8 |
11 |
= x4 |
| 1 |
3 |
6 |
-> min |
pivot step
| x1 |
-x1 |
1 |
|
| 1/2 |
-2 |
-7/2 |
= x2 |
| 3 |
-4 |
-10 |
= x4 |
| 1/2 |
1 |
5/2 |
-> min |
combine the first two columns. standard tableau:
| x1 |
1 |
|
| 5/2 |
-7/2 |
= x2 |
| 7 |
-10 |
= x4 |
| -1/2 |
5/2 |
-> min |
x1-column is bad,. As x1->
infinity, the objective function -> -infinity,
while x2 and x4 become
positive.
The program is unbounded.
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 |
7 |
= x1 |
| 6 |
-8 |
11 |
= x1 |
| 1 |
-3 |
6 |
-> max |
subtract the first row from the second row and multiply the third row by
-1
| x2 |
x3 |
1 |
|
| 2 |
-4 |
7 |
= x1 |
| 4 |
-4* |
4 |
= 0 |
| -1 |
3 |
-6 |
-> min |
pivot on -4 and drop the second column to obtain standard tableau
| x2 |
1 |
|
| -2 |
3 |
= x1 |
| 1 |
1 |
=x3 |
| 2 |
-3 |
-> min |
This is an optimal tableau, so min = -3 at x1 =
3, x2 = 0, x3= 1. For the origional maximization
program,
max = 3 at x1 = 3, x2 = 0,
x3= 1. (The optimal solution is unique.)
4.
| x3 |
x2 |
3 |
-x3 |
|
| 1 |
2 |
3 |
4 |
= x1 |
| 5 |
6 |
7 |
8 |
= x4 |
| 0 |
1 |
2 |
3 |
-> min |
combine the first and the last column and scale the third column to obtain
standard tableau
| x3 |
x2 |
1 |
|
| -3* |
2 |
9 |
= x1 |
| -3 |
6 |
21 |
= x4 |
| -3 |
1 |
6 |
-> min |
pivot step according to Phase 2 of simplex method
| x1 |
x2 |
1 |
|
| -1/3 |
2/3 |
3 |
= x3 |
| 1 |
4 |
12 |
= x4 |
| 1 |
-1 |
-3 |
-> min |
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 two columns, and multiply a column 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 2 of simplex method
| x2 |
x1 |
1 |
|
| 1/2 |
-1/4 |
3/4 |
=x3 |
| 2 |
2 |
1 |
= x4 |
| -1/2 |
3/4 |
-1/4 |
-> min |
x2-column is bad, so the program is unbounded.