Math 486. March 2, 2004 . Midterm 2.
5 problems, 15 points each. Name:
1-3. Solve the linear programs, where all xi
>= 0:
1.
| x1 |
x2 |
x3 |
-x4 |
x5 |
1 |
|
| 1 |
2 |
-3 |
5 |
6 |
2 |
= x6 |
| 0 |
-1 |
2 |
0 |
3 |
1 |
= x7 |
| -1 |
0 |
2 |
4 |
-4 |
-2 |
= -x8 |
| 2 |
0 |
3 |
0 |
1 |
2 |
= f -> min |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Solution. We multiply the columns 4, 6
and rows 1,2,4 by -1 to obtain a standard tableau. It is optimal, so
max(-f) = -2, min(f)= 2 at x1,
x2,
x3,
x4,
x5=
0, x6 = 2, x7=
1 , x8 = 2.
2.
| x1 |
x2 |
x3 |
x4 |
x5 |
1 |
|
| 1 |
2 |
-3 |
-5 |
6 |
-2 |
= -x6 |
| 0 |
-1 |
-2 |
0 |
-3 |
-1 |
= x7 |
| -1 |
0 |
2 |
4 |
-4 |
2 |
= x8 |
| 2 |
0 |
3 |
1 |
1 |
2 |
= f -> max |
|
|
|
|
|
|
|
Solution. We multiply the column 6
and rows 2, 3 by -1 to obtain a standard tableau. The x7-row
is bad, so
the LP is infeasible.
3.
| x1 |
x1 |
x3 |
-x4 |
x5 |
1 |
|
| 1 |
-2 |
-3 |
5 |
6 |
-2 |
= -x6 |
| 0 |
1 |
2 |
0 |
3 |
1 |
= x7 |
| 1 |
0 |
2 |
4 |
-4 |
2 |
= x8 |
| 2 |
0 |
-3 |
0 |
1 |
2 |
= f -> max |
Solution. We multiply the column
4, 6 and rows 2, 3 by -1 and combine the first two columns
to obtain a standard tableau. It is a row feasible and x1-column
is bad, so the LP is unbounded.
4-5. Solve matrix games:
4.
| 1 |
3 |
5 |
7 |
1 |
3 |
2 |
| 8 |
8 |
9 |
8 |
9 |
8 |
9 |
| 1 |
-5 |
4 |
3 |
4 |
9 |
1 |
| 3 |
5 |
6 |
-3 |
0 |
1 |
3 |
| 9 |
3 |
-2 |
8 |
1 |
-8 |
0 |
Solution. We have two saddle points in the second row (columns 2
and 4), and the value of game is 8.
5.
| 0 |
0 |
0 |
-2 |
-2 |
-1 |
-2 |
| 0 |
2 |
0 |
-1 |
-2 |
-1 |
-1 |
| 0 |
3 |
3 |
0 |
-2 |
0 |
-1 |
| 3 |
0 |
3 |
0 |
2 |
3 |
0 |
| 0 |
3 |
1 |
4 |
3 |
0 |
4 |
Solution. By domination, we are reduced to the southwest corner:
Its optimal strategies are [1/2, 1/2]T and
[1/2, 1/2] and the value of game is 1.5.
For the original game, the value is the same, and the optimal strategies
are
[0,0,0,1/2, 1/2]T and [1/2, 1/2,0,0,0,0,0].
There are other optimal strategies, e.g.,
[1/2, 0,0,0,0,1/2,0].