Math 486. March 22, 2007 . 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 |
2 |
4 |
-4 |
2300 |
= -x8 |
| 2 |
0 |
3-300 |
0 |
1 |
2 |
= f -> min |
Solution. We multiply the last row
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 = 10-12,
x7= 1013
, x8 = 2300.
2.
| x1 |
x2 |
x3 |
x4 |
x5 |
-1 |
|
| 1 |
2 |
-3 |
-5 |
6 |
-2 |
= -x6 |
| 0 |
-10-100 |
-2 |
0 |
-3 |
1-300 |
= x7 |
| -1 |
0 |
2 |
4 |
-4 |
2 |
= x8 |
| 2 |
0 |
3 |
1 |
1 |
2 |
= f -> max |
|
|
|
|
|
|
|
Solution. We multiply the rows 2,
3 by -1 to obtain a standard tableau. The x7-row
is bad, so
the LP is infeasible.
3.
| x1/30000001 |
x1/3000002 |
x3/3000003 |
x4/3000004 |
x5/3000005 |
-1 |
|
| 1/300001 |
-1/300002 |
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. If we set x5
= x1,
we obtain a tableau with a bad column
( x1-column) of
type (-,-,-,+). The tableau is not feasible.
Setting x3
=x4 = 0 and sending x1 = x5
to
infinity we get arbitrary large feasible values. 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. We have a saddle point in the last row, column 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-10-100 |
0 |
3 |
0 |
2 |
3 |
0 |
| 0 |
3 |
1 |
4 |
3 |
0 |
4 |
Solution. By domination, we are reduced to the southwest
corner:
Optimal strategies are [3, 3- 10-100]T
/(6-10-100)
and
[3, 3- 10-100]
/(6-10-100)
and the value of game is 3(3- 10-100)
/(6-10-100)
.
For the original game, the value is the same, and optimal
strategies
are
[0,0,0,3, 3- 10-100]T
/(6-10-100)
and [3, 3- 10-100,0,0,0,0]
/(6-10-100).