Math 486. March 20, 2008 . 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 |
|
| 1011 |
2 |
3 |
5 |
6 |
10-12
|
=- x6 |
| 0 |
-1 |
-2 |
0 |
3 |
1013 |
= -x7 |
| -1 |
0 |
0
|
4 |
-4 |
2300 |
= -x8 |
| 2 |
0 |
3-300 |
0 |
1 |
2 |
= f -> min |
Solution. We multiply the last row, the
x3-column,
and the x4-column
by -1 to obtain a standard tableau.
| x1 |
x2 |
x3 |
x4 |
x5 |
-1 |
|
| 1011 |
2 |
-3 |
-5 |
6 |
10-12
|
=- x6 |
| 0 |
-1 |
2 |
0 |
3 |
1013 |
= -x7 |
| -1 |
0 |
0
|
-4 |
-4 |
2300 |
= -x8 |
| -2 |
0 |
3-300 |
0 |
1 |
2 |
= -f -> max |
It is feasible. Setting x3 =
x2/2 and x4 = x2, we obtain a smaller standard
feasible tableau with a bad x2
-column. So this smaller LP is unbounded, hence the original
problem is also unbounded.
2.
| x1 |
x2 |
x3 |
x4 |
x5 |
-1 |
|
| 1 |
2 |
-3 |
-5 |
6 |
2 |
= -x6 |
| 0 |
-10-100 |
-2 |
0 |
-3 |
-10-300 |
= x7 |
| -1 |
0 |
2 |
4 |
-4 |
-2 |
= x8 |
| 2 |
0 |
3 |
1 |
1 |
0
|
= x9 |
-1
|
-2
|
-10-100 |
0
|
0
|
0
|
= f -> max |
Solution. We multiply the rows 2,
3 and 4 by -1 to obtain a standard tableau. So max = 0 at x1= x2=
x3 = x4 = x5 = 0,
x6= 2, x7=
10-300, x8
=2, x9 =
0.
3.
| x1/30000001 |
x1/3000002 |
x3/3000003 |
x4/3000004 |
x5/3000005 |
-1 |
|
| 1/300001 |
-1/3000002 |
1/300003 |
1/300004 |
0 |
-2 |
= -x6 |
1/30001
|
-1/30002 |
-2/3003 |
0 |
0
|
-1 |
= -x7 |
| 1/3001 |
0 |
2/3003 |
3/3004
|
-4/3005 |
2 |
= -x8 |
| 2/301 |
0 |
-1/303 |
0 |
1/305 |
2 |
= f -> max |
Solution. Combine the first two columns
to obtain a standard tableau. The fifth column is bad. We set x1= x3= x4 = 0 and send x5 to infinity. Then f -> infinity, while x6 = 2, x7 = 1, and x8 = x5/(3000005*305) -2 is positive for sufficiently large x5 . Thus, the LP is unbounded.
4-5. Solve matrix games:
4.
| 1 |
3 |
5-10-100 |
7 |
1 |
3 |
2 |
| 8 |
8+10-100 |
9 |
8+10-100 |
9 |
8 |
9 |
| 1 |
-5 |
4 |
3 |
4 |
9 |
10-100 |
| 3 |
5 |
6 |
-3 |
-10-100 |
1 |
3 |
| 8+10-100 |
9
|
9
|
8 |
9
|
8 |
9-10-100 |
Solution. Set e = 10-100. Using pure strategies (the 2nd row and
the
fourth column), 8 <= the value of game
< =
8+ e.
The column player best pure strategies are the rows 2 and
5. They gives him at least 8. So they are optimal up to 100
digits.
If the column player chooses Column 1 or 4, she pays him at most 8+e. So these pure strategies are optimal up to 100 digits.
It is easy to improve c1 and c4 using mixed strategies (e..g, (c1+c4)/2
improves both). It is easy to improve r2 and r5 (e.g. (r2+r5)/2
improves both).
By domination, we can
cross out the rows 1 and 4 and the columns 3, 5. Column 7 is dominated by (c2+2ec4)/(1+2e).
Optimal strategies are [0, 6, e, 0, 8]T/(14+e)
and [1, 0, 0, 1,0, 12+e, 0 ]/(14+e) . The value of game is
(112+9e)/(14+e).
5.
| 0 |
0 |
0 |
-2 |
-2 |
-1 |
-2 |
| 0 |
2 |
0 |
-1 |
-2 |
-1 |
-1 |
| 0 |
3 |
3 |
0 |
-2 |
0 |
-1 |
| 3+10-100 |
0 |
3 |
0 |
2 |
3 |
0 |
| 0 |
3 |
1 |
4 |
3 |
0 |
4 |
Solution. Rows 1 and 2 are domimated by Row 4, so we
cross them out. Column 3 is dominated by Column 6, so
Column 3 goes.
Now the first remaining row is dominated by the last row, so it goes.
By additional dominations,
we are reduced to
Optimal strategies are [1/2, 1/2]T
and
[1/2, 1/2]
and the value of game is 3/2.
For the original game, the value is the same, and optimal
strategies
are
[0,0,0, 1/2,1/2]T
and [0, 1/2,0, 0, 0,
1/2, 0].