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 and   x4-column  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).