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 x to infinity. Then f -> infinity, while    x6 = 2, x7 = 1, and  x8 = x5/(3000005*305) -2 is positive for sufficiently large   x . 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

 0 3 3 0

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