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:
3-10-100 0
0 3

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).