Math 484.004.  Nov. 2, 2016.  Midterm 2.
10 problems, 5 pts each.   Write your name here  Dr. V,

No electronics is allowed.   Write both answers and details (show your work). Write only answers on scantron. Return this page and the scantron.

If you disagree with the given answers, explain why here and choose (E) at scantron.

Do not talk with other students in class even after finishing your papers.

26. The linear program given by a standard row tableau with the matrix

 1 0 0 -3 1 0 -1 2 1 -1 -1 -1 -1 1 2 -2

(A) is infeasible, (B) is unbounded, (C) has an optimal solution.

Solution.   According  to the simplex method, we  pivot on 1 in the first row.

This gives a feasible tableau with the first column bad. (B).

27. The linear program given by a standard row tableau with the matrix

 -1 -2 -2 -1 -1 1 0 1 -1 2 3 1 3 -1 4 -5 2 1 -7 6 -1 -8 0 0

The number of choices for the pivot entry consistent with the simplex method is

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

Solution.     The tableau is row feasible so we go to Phase 2. The tableau is not terminal.

 -1* -2 -2* -1 -1 1 0 1 -1 2 3 1 3 -1 4 -5* 2 1 -7 6 -1 -8 0 0

(D)

28. The linear program given by a standard row tableau with the matrix

 -1 0 -2 0 0 -1 -3 2 -3 -1 0 0 7 6 -1 -8

(A) is infeasible, (B) is unbounded, (C) has an optimal solution, (D) has no solutions.

Solution.   The tableau is row feasible, so we go to Phase 2. The are no bsd columns and the tableau is noy optimal.

The simplex method tells us to use -2 as the pivot entry. After a degenerate pivot step, we get an optimal tableau.

(C).

29. The optimal value of

(3t + 2)x + (3-t)y -> max;  x, y ≥0,. x + y ≤ 1

as a function of the parameter t has slopes

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

Solution.  The feasible region has 3 corners, so

max = max(0, 3 - t, 3t+2) = max (3 - t,  3t + 2) =

3 - t when t ≤ 1/4,

3t + 2  when t ≥ 1/4.

(E).

30.    The optimal value for

y -> max,   y ≥0,.  |x| + |y| ≤ 1,  x  =  t

as a function of the parameter t  has slopes

(A) 1, (B) 1, -1, (C) 0,  -1. (D) -1, 0.

Solution.

When t< -1 or t > 1,  the program  is infeasible.

If -1    t ≤ 0, then  max = 1+t, so the slope is  1.

If  0 ≤ t ≤ 1, then  max = 1 - t, so the slope is -1.

(B).

31. A linear program is given a standard row tableau with the matrix

0    1  -1    1

1   -1   0    1

-1    0   1    2

-1  -1    2   0 .

Setting the variables on the top to be  1, 2, and 3, we obtain

(A) an infeasible solution, (B) an optimal solution, (C) a feasible solution which is not optimal.

Solution.  See #31 on this web  page.

(C).

32. A linear program   given a standard  row  tableau with the matrix

1        t-1

t+1      0

has an optimal solution for

(A) t ≥ -2,  (B) all t, (C) t ≤ 0. (D) t ≤ -1.

Solution.  If t   1, the tableau is optimal.

If  -1 ≤ t < 1  pivoting on 1  produces  an optimal tableau. If t < 0,  pivoting on 2 produces

a feasible tableau with a bad column.So the answer is: for t ≥ -1.

(E)

33. A linear program given by a standard row tableau with the matrix

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

How many choices for the first   pivot entry which are consistent with Simplex Method?

(A) 0, (B) 3, (C)  4,  (D)  6.

Solution.

The second row is bad, so the tableau is terminal.
(A).

34. The optimal value of the  job assignment problem

 1 0 3 1 0 2 0 1 0 2 1 1 3 0 2 2 0 2 0 2 1 1 2 2 0 0 3 1 0 2 1 0 1 0 1 0

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

Solution.  The cost is  ≥ 0, and there is a zero jn each row and column. However we cannot place the flow at positions with the zero cost because the big (5 by 2) positive block in  the rows 1-5, columns 4, 6.

We destroy the block  subtracting 1 from each of  5 first  rows and adding 1 to  columns 1,2,3,5. Here is the resulting adjusted cost matrix:

 1 0 3 0 0 1 0 1 0 1 1 0 3 0 2 1 0 1 0 2 1 0 2 1 0 0 3 0 0 1 2 1 2 0 2 0

Now we find a zero cost assignment:

 1 0 3 0* 0 1 0 1 0* 1 1 0 3 0* 2 1 0 1 0* 2 1 0 2 1 0 0 3 0 0* 1 2 1 2 0 2 0*

For the original cost, min = 1.

(A).

35.  The optimal value  for the transportation problem

 2 2 3 4 5 6 2 2 2 1 2 4 4 5 6 7 2 2 1 2 3 5 5 6 7 8 0 1 2 4 4 6 6 7 8 9 2 1 2 6 1 2 3 2 2 3 0 0 0 demand\supply

is (A) ≤25, (B) ≥ 29 , (C) the problem is infeasible, (D) lies in the interval    26 ≤ min ≤ 28.

Solution. The balance condition: 13 = 13. So the program has an optimal solution.

The flow in the last 3 columns   is 0, so the cost is 0 in these columns.  We cross out them.

 2 2 3 4 5 6 1 2 4 6 5 6 7 2 3 5 5 6 7 8 4 4 6 6 7 8 9 6 1 2 3 2 2 3 demand\supply

Now we subtract 0, 1,  2, 3. 4.  5  from the cost in the columns  and 1, 2, 3, 4 from the cost in the rows (Phase 1 of Hungarian method), the total cost is reduced by

2+ 6 + 6 + 8 + 15  +  1 + 4 + 12 + 24 = 37 + 41 =  78.

Here is the adjusted cost:

 1 0 0 0 0 0 1 0 1 0 0 0 0 2 0 0 1 0 0 0 4 0 0 0 0 0 0 6 1 2 3 2 2 3 demand\supply

Now there are many optimal solutions with the zeo cost E.g.,

 1 1 1 1 2 2 2 4 3 3 6 1 2 3 2 2 3 demand\supply

It can be completed to a basic optimal solution but this is not required.

For the original problem,     min= 78.   (B).

A shortcut. Instead of computing the minimal cost min, we can get a lower bound by

multiplying the supply in each row by the minimal cost in this row and adding these products up:

min ≥ 1*2 + 2*1 + 4*3 + 6*4 = 40. So the answer is (B).