Math 484.3.  November 5, 2014.   Midterm 2.
10 problems, 5 pts each.   Write your name here  Vaserstein

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

Do not talk with other students in class even after submitting 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 -2 -2 -2

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

Solution. By Simplex Method, Phase 1, the pivot entry is the third entry in the first column (since

1/(-1) > 2/(-1) > 3/(-1):

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

pivot step

 -1 -1 -1 2 -1 -1 -2 1 1 1 1 1 1 -1 -1 -1

Now we go to Phase 2 and pivot on the second -1 in the second column and obtain  an optimal  tableau

 -1 -1 -1 2 -1 -1* -2 1 1 1 1 1 1 -1 -1 -1

pivot step

 + -1 + + 2 1 1 -2

(C).

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

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

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

Solution. By Simplex Method, Phase 1, the pivot entry is the second entry in the second column:

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

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

The tableau is feasible. Now we pivot on -1 in the first column and obtain a feasible tableau with the third column being bad.  (B).

Another solution (without pivoting). Let a, b, c be the variables on the top. We set  a =  2c and b = 2c+2.

The we obtain a feasible tableau with a bad column:

c    1

0  1

1  0

8  3

-3  4

So this LP is unbounded (send c to infinity). Therefore the original problem is unbounded.

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

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

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

Solution. Adding the first two constraints we get a constraint  which cannot be satisfied (A).

29. The optimal value for the linear program given by a standard tableau with the matrix

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

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

Solution.   The first row is bad (D).

30. The optimal value for the linear program given by a standard tableau with the matrix

 -2 -3 -4 1 1 -1 -2 -3 -1 1

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

Solution. The fourth column is bad.     (D).

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   =  0

-1  -1     2    0              .

So we get a feasible solution. For the dual variables   a, b, c at the left margin we obtain 3 linear equations by complementary slackness.

Here is the solution:

1     2    3      1

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

-1 |  0    1  -1     1 | =   0

-2 |  1   -1   0     1 | =   0

-3 |-1     0   1   -2 | =   0

1 | -1   -1   2     0 |

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

= 0   =0 = 0

So the correct answer is (B). The optimal value is 3.

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

1  -2   t

3  -1   0

has an optimal solution for

(A) t ≥ 0,  (B) all t, (C) t ≤ 0.

Solution.  Let  x be the dual variable for the first row. We get  1/2 ≤ x ≤ 3.  For any objective function (including our function -tx) we have an optimal solution

(namely, x = 1/2 or x = 3).  (B).

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

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

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

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

Soliuion.

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

(B).

34. The optimal value of the  job assignment problem

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

is (A) ≤  4, (B)  5,  (C)  ≥ 6.

Solution.   This assignment uses the least cost in each row:

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

So min = 6   (C) .

35.  The optimal value  for the transportation problem

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

is (A) ≤40, (B) > 43, (C) the problem is infeasible.

Solution. Total supply is less than total demand (C) .