Math 486.  March 2, 2004 .  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 1 2 -3 5 6 2 = x6 0 -1 2 0 3 1 = x7 -1 0 2 4 -4 -2 = -x8 2 0 3 0 1 2 = f -> min
Solution. We multiply    the columns 4,  6  and rows 1,2,4 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 = 2, x7= 1 , x8 = 2.

2.
 x1 x2 x3 x4 x5 1 1 2 -3 -5 6 -2 = -x6 0 -1 -2 0 -3 -1 = x7 -1 0 2 4 -4 2 = x8 2 0 3 1 1 2 = f -> max
Solution. We multiply    the column   6  and rows 2, 3  by -1 to obtain a standard tableau. The  x7-row is bad, so
the LP is infeasible.

3.
 x1 x1 x3 -x4 x5 1 1 -2 -3 5 6 -2 = -x6 0 1 2 0 3 1 = x7 1 0 2 4 -4 2 = x8 2 0 -3 0 1 2 = f -> max

Solution. We multiply    the column   4, 6  and rows 2, 3  by -1  and combine the first two columns to obtain a standard tableau. It is a row feasible and   x1-column is bad, so  the LP is unbounded.

4-5. Solve matrix games:
4.
 1 3 5 7 1 3 2 8 8 9 8 9 8 9 1 -5 4 3 4 9 1 3 5 6 -3 0 1 3 9 3 -2 8 1 -8 0
Solution. We have two saddle points in the second row (columns 2 and 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 0 3 0 2 3 0 0 3 1 4 3 0 4
Solution. By domination, we are reduced  to the southwest corner:
 3 0 0 3

Its optimal strategies are [1/2, 1/2] and   [1/2, 1/2]  and the value of game is 1.5.
For the original game, the value is the same, and the optimal strategies are
[0,0,0,1/2, 1/2] and   [1/2, 1/2,0,0,0,0,0]. There are other optimal strategies, e.g.,
[1/2, 0,0,0,0,1/2,0].