Math 486.  March 18, 2010 .  Midterm 2.   5 problems, 15 points each. Name (here and on every page):

1-3. Solve the linear programs, where  all xi >=  0:
1.
x1 x2 -x3 -x4 x5 -1
1011 2 0 0 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 0 0 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

The first row is bad, so the program is infeasible.

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 1
 0
 0
 = f -> max
Solution. We multiply    the   rows 2, 3 and 4   by -1 to obtain a standard tableau.

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
-20-31-10= -x9
-1
 -2
 -10-100 1
 0
 0
 = f -> max


This  tableau is feasible. From the first row,  we see that    0 <=  x7  <=  10-300. Now it is easy to see that  also  x3, and  x5  must be very close to 0 hence
x2  must be very close to 0
Setting these 4 variables to be 0  (which implies that  x4   = 2 x1   and   x1 = 2/9)   gives a very good approximate solution with f = 2/9.
Here is the optimal solution found by computer:
max = (4 + 17 e^3 - 9 e^4)/18
at  x2 = x5 = x7 = x8 = x9 = 0,
x1 = (2 - 5 e^3)/9, x3 = e^3/2, x4 = (8 + 7 e^3)/18, x6 = 4 + 4 e^3,
where e = 10-100.  The approximate solution agrees with the exact solution up to about 300 digits after the decimal point.

3.
x1/30000001 x1/3000002 x3/3000003 x4/3000004 x5/3000005 -1
1/300001 -1/3000002 1/300003 1/300004 0 2 = -x6
-1/3000002
 -1/3000002 -2/3003 0 0
 1 = -x7
1/3001 0 2/3003 -1/3000002
 -4/3005 2 = -x8
2/301 0 1/3000002 0 1/305 2 = f -> min

Solution. Combine the first two columns and multiply the last row by -1 to obtain a standard tableau.  This standard tableau is optimal, so

max=2 (hence min(f) = -2)  at x1= x3=x4=x5= 0, x6=2, x7= 1, x8 = 2.


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 8 10-100
3 5 6 -3 -10-100 1 3
8+10-100 9
 9
 8 9
 8 9 -10-100

Solution.

There is a saddle point at row 2, column 6 with the payoff = 8. Another equilibrium is at row 5, column 6


  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 5, 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

  c1 c2 c5
r4 3-e 0 2
r5 0 3 3

where e = 10-100. By graphical method, optimal strategies are [3, 3-e]T/(6-e)   and  [3, 3- e, 0]/(6-e)    and the value of game is 3(3-e)/(6-e).
For the original game, the value is the same, and  optimal strategies are
[0,0,0, 3,3-e]T/(6-e)   and   [3, 3-e,0, 0, 0, 0, 0]/(6-e) . The c5 column above is dominated by c2 column, so it can be crossed out -- T.B.