Math 484.2.  Dec. 4, 2014.   Midterm 2.
15 problems, 5 pts each.   Write your name here ____________________________

Return the scantron and this  page with both answers and details

(how you got your answers). Do not talk with other students in class even after finishing your midterm.

If you do not like the given answers, explain why here and choose (E) at scantron.

26. The minimal value for the job assignment problem

2  1  2  1

1  3  0  1

1  0  1  0

3  0  0  2

is (A) 0, (B) 2, (C) 4, (D) 6.

Solution. Subtract 1 from the first row and column:

0  0  1  0

0  3  0  1

0  0  1  0

2  0  0  2

Mow we can place the flow at positions with zero cost:

0  0*  1  0

0* 3   0  1

0  0   1  0*

2  0   0* 2

so min = 0. For the original problem, min = 2. (B).

27. The minimal value for the transportation  problem

supply

2  1  2  1  2  5   1

1  3  0  1  3  5   1

1  0  1  0  4  5   1

3  0  0  2  1  5   1

1     1      1     1      0     0        demand

is (A) 0, (B) 2, (C) 4, (D) 6.

Solution. The flow in the last two columns is zero, so we are back to Problem 26. (B).

28. For any numbers a, b, the system  x = a, x = b of two linear equations with one unknown x has no solutions.

(A) true, (B) false.

Solution. This is false when a = b =0. (B).

29. An optimal solution (a, b, c, d)  for the linear program given by the standard  4 by 5 row tableau

a  b  c  d     1

1  0 -1  2   -1

1 1   1  1  -10

-1 0 1   0    -1

2  1  2   1    9 -> min

is    (A) (1, 1, 1, 1), (B) (-1, 0, 1, 1), (C) (1,2, 3, 4), (D)  (0, 0, 0, 0).

Solution.  (A), (B) and (D) are not feasible.

For (C),

1   2  3  4     1

1   0 -1  2   -1 = 5

1   1   1  1  -10 = 0

-1  0  1   0    -1 = 1

2   1 2  1      9 -> min

so (C) is feasible. For the dual variables

0     1   0  -1  2   -1 = 5

-x2  1  1    1  1  -10 = 0

0   -1   0   1  0    -1 = 1

1     2    1   2  1    9 -> min

=0  =0  =0 =0

we have  -x2  + 2 = 0,  -x2   + 1 = 0,

hence 0= 1. So there is no complementary feasible solution, hence (C) is not optimal.  (E).

30 An optimal solution (a, b, c, d)  for the linear program given by the standard  row  4 by 5 row tableau

a  b  c  d     1

1  0 -1  2    1

1 1   1  1  10

-1 0 1   1    1

2  1  2 -1   9 -> min

is   (A) (1, 1, 1, 1), (B) (-1, 0, 1, 1), (C) (1,2, 3, 4), (D)  (0, 0, 0, 0).

Solution.  The tableau is row  feasible and d-column is bad, so there are no optimal solutions (for both row and column problems). (E).

31.  The value of the matrix game  with payoff matrix

 1 5 0 4 1 6 0 5 1 5

is  (A) 2.5, (B) 28/9,  (C)   11/3,  (D) 25/9.

Solution. The first and last columns go by domination:

 5 0 4 0 5 1

By graphical method, we find an equilibrium

(p, q) = ([1, 1]T/9, [1, 1, 0]/2) with the value of game 2.5:

 5 4 1 2.5* 0 2 5 2.5* 2.5’ 2.5’ 2.5’ 2.5*'

where p and q are added as the last row and the last column. (A)

32.  Consider the matrix game with payoff matrix

0  -2   1  1

2   0  -3  1

-1  3   0 -1

An optimal strategy for the column player is

(A) [3, 1, 2, 0]/6,  (B)  [0, 1, 2, 1]/4 ,    (C)  [2, 0, 1, 1]/4,    (D) ]1, 1, 1, 1]/4..

Solution. We compute payoff for the proposed strategies:

A   B     C        D

0  -2   1 1       0   1/4   1/2*     0

2  0  -3   1       0  -5/4  1/2*     0

-1 3   0  -1      0   1/2* -3/4   1/4*

So the value of game is ≤ 0 hence B, C  and D are not optimal.

Using [3, 1, 2]T/6, the row player gets 0 in the worst case, so the value of game  is ≥ 0.

Therefore (A) is optimal.  (A).

33.   A least-squares solution (x, y, z)  for the system

x+y +z = 7,  2x + 2y  + 2z = 7      is

(A) (3,1, 11), (B) (6.5, 0, 4),  (C)  (19/3, 1/2, 5), (D) (10, 1, 1).

Solution. Set  t = x +y + z. Then the system is   t = 7, 2t = 7. We want to minimize  (t- 7)2 +  (2t- 7)2 .

Writing this as  (t- 7)2 +  (t- 7/2)2  +  (t- 7/2)2 +  (t- 7/2)2     +  (t- 7/2)2        we see that the minimum is at  the mean of   7, 7/2, 7/2,  7/2, and 7/2.

The mean is   t = 21/5 = 4.2.  (E).

34.   An  optimal solution  x  for    |2x| +  |x-1| +  |x - 3| +  |3x- 6| ->  min

is  (A) 0, (B)  3,  (C)   5/3, (D) 1.5.

Solution. The optimal solution is  the LAD fit  x  for  the numbers 0, 0, 1,3, 2, 2, 2, which is the median 2. (E)

35.   max( |2x|,   |x-1|,  |x - 3| ,  |x- 2| )  ->  min.

The optimal solution x is (A) 1, (B) 1.5,  (C) 1.8, (D) -100.

Solution.  The second and the last terms are never maximal, i.e.,

max( |2x|,   |x-1| ,   |x - 3| ,  |(x- 2|) )   = max( |2x|,    |x - 3| ) ..

The     max( |2x|,    |x - 3| )   is minimal when  0  ≤ x ≤ 3 and  |2x|=  |x - 3| , i.e.,  2x = 3 - x, i.e.,  x = 1. (A)

36.  The value of the matrix game  with payoff matrix

 1 3 1 -4 6 1 -1 6 2 0 2 0 -1 1 1 2 0 1 2 0 0

is  (A) 2.5, (B) 8/3,  (C)  0,  (D) 0.1.

Solution.

 1 3 1 -4 6 1 -1 6 2 0 2 0 -1 1 1 2 0’ 1 2 0’ 0’

The best pure strategy for the row player is the last row.

The worst case payoff for it  is 0. Can it be improved?

If yes,  all 7 payoffs for any optimal strategy (for the row player)  are positive.

Looking at the last 2 payoffs, we conclude that it not possible.

An optimal strategy for the column player is [0, 0, 0, 0, 0,  0.5, 0.5].

(The northeast 2 by 2 corner is the Heads & Tails game. We know its value and the optimal strategies)

(C).

37.   Consider the matrix game with payoff matrix

0  -2   1 -1   9

2   0  -3  1  -2

-1  3    0 1    0

An optimal strategy for the column player is

(A) [3, 1, 2, 0, 0]/6,  (B)   [0, 1, 2, 1, 0]/4,    (C)  [2, 0, 1, 1, 1]/5,    (D) [1, 1, 1, 1, 1]/5.

Solution.  Here are the payoffs for the proposed strategies:

A     B    C    D

0  -2   1 -1   9      0           9/5

2   0  -3  1  -2      0

-1  3    0 1    0      0     1            3/5

So A is better (in the sense of the worst-case payoff)  than B, C, and D  hence  B, C, and D  are not optimal.

When the row player uses  p = [3, 1, 2]/6T, we have an equilibrium

A

0  -2    1 -1   9      0

2   0  -3   1  -2      0

-1   3    0  1    0      0

p     0   0   0  0 25/6   0*’

(A).

38. For any number t, the equation   (t+1)x = t has a solution x.

(A) true, (B false.

Solution.  This is false when t = -1.  (B).

39. A median of the numbers 0,-1,-2, 1, 2, 3, 0, 0    is

(A) 0.5, (B) 0, (C) 3/7, (D) 1.