Math 484.2 November 3, 2011. Midterm 2.
5 problems, 15 pts each. \Write your name here ____________________________ and on the other side.
Write down how you got your answer.
1. Solve the linear program where all xi ≥ 0:
|
x1 |
x2 |
-2 |
-x5 |
|
|
1 |
2 |
3 |
4 |
= x3 |
|
- 1 |
2 |
1 |
-3 |
= -x2 |
|
2 |
2 |
3 |
0 |
--> max |
Solution. We are going to change the tableau to make it standard. We pivot on -1 in the first column:
|
x1 |
x2 |
-2 |
-x5 |
|
|
1 |
2 |
3 |
4 |
= x3 |
|
- 1* |
2 |
1 |
-3 |
= -x2 |
|
2 |
2 |
3 |
0 |
--> max |
->
|
-x2 |
x2 |
-2 |
-x5 |
|
|
-1 |
4 |
4 |
1 |
= x3 |
|
-1 |
2 |
1 |
-3 |
= x1 |
|
-2 |
4 |
5 |
-6 |
--> max |
Now we combine the first two columns. permute and scale the last two columns, and scale the last row:
|
x2 |
x5 |
1 |
|
|
5 |
-1 |
-8 |
= x3 |
|
3 |
3 |
-2 |
= x1 |
|
-6 |
-6 |
10 |
--> min |
The first column is bad although we are in Phase 1 yet. Now we set
x5 = 0 and send x2 to infinity. The objective function goes to -infinity and we are feasible for large x2 .
So the LP is unbounded.
2. Check whether x1 = 0, x2 =3.4, x3 =0, x4 = 5/2, x5 = 0, x6 =0, x7 =10,
x8 = 0 is an optimal solution for the LP written in a stanfdard tableau:
|
x1 |
x2 |
x3 |
x4 |
x5 |
1 |
|
|
1 |
-2 |
3 |
1 |
5 |
6 |
= x6 |
|
-1 |
2 |
-3 |
4 |
-5 |
0 |
= x7 |
|
2 |
1 |
0 |
2 |
1 |
-5 |
= x8 |
|
2 |
0 |
1 |
1 |
3 |
-1 |
-> min |
Solution. The first constraint does not hold, so the proposed "solution" is not feasible hence it is noit optimal.
Remark. x1 = 0, x2 =3.4, x3 =0, x4 = 0.8, x5 = 0, x6 =0, x7 =10, x8 = 0 is an optimal.
3-4. Solve transportation problems:
|
2 |
3 |
3 |
2 |
1 |
2 |
1 |
2 |
1 |
9 |
|
1 |
2 |
3 |
1 |
1 |
1 |
1 |
3 |
1 |
8 |
|
2 |
2 |
1 |
3 |
1 |
1 |
3 |
3 |
2 |
9 |
|
3 |
1 |
3 |
1 |
2 |
1 |
2 |
3 |
4 |
8 |
|
6 |
1 |
6 |
1 |
6 |
1 |
6 |
1 |
6 |
dem \ sup |
Solution. The following basic feasible solution is optimal.
Optimal potentials are also given. The corresponding adjusted cost is ≥ 0. It is 0 at the selected positions.
The minimal total cost is 40.
|
|
1 |
0 |
1 |
0 |
1 |
0 |
1 |
2 |
1 |
|
|
0 |
2 |
3 |
3 |
2 |
1 3 |
2 |
1 |
2 |
1 6 |
9 |
|
0 |
1 6 |
2 |
3 |
1 |
1 |
1 |
1 2 |
3
|
1 |
8 |
|
0 |
2 |
2 |
1 6 |
3 |
1 3 |
1 |
3 |
3 |
2 |
9 |
|
-1 |
3 |
1 1 |
3 |
1 1 |
2 |
1 1 |
2 4 |
3 1 |
4 |
8 |
|
|
6 |
1 |
6 |
1 |
6 |
1 |
6 |
1 |
6 |
dem \ sup |
4.
|
3 |
1 |
3 |
2 |
1 |
2 |
3 |
2 |
1 |
9 |
|
3 |
3 |
3 |
1 |
1 |
3 |
1 |
3 |
1 |
8 |
|
2 |
2 |
3 |
3 |
1 |
1 |
3 |
1 |
2 |
9 |
|
2 |
3 |
3 |
3 |
2 |
1 |
2 |
3 |
2 |
8 |
|
6 |
1 |
6 |
1 |
6 |
1 |
6 |
1 |
6 |
dem \ sup |
Solution. Here is an optimal solution using the least cost 1:
|
3 |
1 1 |
3 |
2 |
1 2 |
2 |
3 |
2 |
1 6 |
9 |
|
3 |
3 |
3 1 |
1 1 |
1
|
3 |
1 6 |
3 |
1 |
8 |
|
2 |
2 |
3 4 |
3 |
1 4 |
1 |
3 |
1 1 |
2 |
9 |
|
2 6 |
3 |
3 1 |
3 |
2 |
1 1 |
2 |
3 |
2 |
8 |
|
6 |
1 |
6 |
1 |
6 |
1 |
6 |
1 |
6 |
dem \ sup |
min= 34.
5. Solve job assignment problem
|
1 |
2 |
3 |
1 |
2 |
|
2 |
3 |
5 |
1 |
2 |
|
3 |
2 |
1 |
3 |
1 |
|
1 |
3 |
4 |
5 |
1 |
|
1 |
1 |
2 |
1 |
0 |
Solution. We cannot use the least number in each column and get 4 but we can get min=5:
|
1 |
2* |
3 |
1 |
2 |
|
2 |
3 |
5 |
1* |
2 |
|
3 |
2 |
1* |
3 |
1 |
|
1* |
3 |
4 |
5 |
1 |
|
1 |
1 |
2 |
1 |
0* |