Math 484.002.  April 30,2016.  Midterm 2.  
10 problems, 5 pts each.   Write your name here  Vaserstein

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 do not like 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

(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 an optimal tableau. (C).

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

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

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

Solution.    

(D)

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

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

Solution.  The second row is bad. (A).

29. The optimal value of

(3t + 2)x + (3-t)y -> max, 0 ≤ x ≤ 1,  0 ≤ 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.  max = max(0, 3 - t, 3t+2, 2t + 5) = max (3 - t,  2t + 5,  3t + 2) =

3 - t when t ≤  -2/3,

2t + 5 when  -2/3  ≤ t ≤ 3,

3t + 2  when t ≥ 3.

(D).

30.    The optimal value for

y -> min,  |x| + |y| ≤ 2, x ≤ t

as a function of the parameter t  has slopes

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

Solution.  

When t<-2, then |x|>2, the problem is infeasible.

When -2 < t < 0, |x|=-x ≥ -t, |y| ≤ 2 + t, then y ≥  -(2 + t) = -2 - t, so the slope is -1.

When t≥ 0, |x|≤ t, let x=0 and y=-2, then the minimum of y is -2, so the slope is 0.

Therefore the slopes (when they exist) are -1, 0.

(E).

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.   Here are the values for all 6 variables in the row problem:

 1      2      3     1

------------------

  0    1  -1    1   =    0

  1  -1    0    1   =    0

-1    0    1    2   =    4

-1  -1     2    0              .

So we get a feasible solution. Now we look for a complementary feasible solution for the column problem.

 For the dual variables   a, b, c ≥ 0 at the left margin we obtain 4 linear equations by complementary slackness:

c = 0,  -b -1  =  0, -a + b -1 = 0, a + 2 = 0. So there are no complementary feasible solutions to the column problem.

 (C).

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

2   t-1

t   0 

has an optimal solution for

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

Solution.  If t  ≥  1, the tableau is optimal.

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

a feasible tableau with a bad column. (A)

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

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

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

Solution.

(C) .

34. The optimal value of the  job assignment problem

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

Solution.  The cost is  ≥ 0, and there is a zero in each row. We subtract 1 from the columns 4 and 6 to get 0 in each column:

Now we  find a zero cost assignment:

For the original cost, mim = 2.

(B).

35.  The optimal value  for the transportation problem

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

Solution. The balance condition: 19 = 19. The flow in the last 3 columns and the last row is 0, so the cost is 0 in these line, hence we cross out them. 

Now we subtract 2, 2,  1, 2 from the cost in the first 4 columns (Phase 1 of Hungarian method), the total cost is reduced by  10 + 2 +  5 + 2 = 19.

Now we try to place the flow at positions with the zero cost. We start with the columns 5 where there is no choice:

After this, we have only one row left, so  we select all remaining position in this row.

The total  cost is 0 = min   For the original problem,     min= 19.   (A).