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