Math 484 .1.  April 2, 2014.   Midterm 2.
10 problems, 5 pts each.   Write your name here  Vaserstein

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

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

(A) is infeasible, (B) is unbounded, (C) has an optimal solution, (D) none of the above.

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

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

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

 -1 -1 -3 -3

The third row is bad, so the LP is infeasible (A).

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, (D) none of the above.

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 2 3 7 6 5

The tableau is optimal  (C).

28. 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, (D) none of the above.

Solution. The tableau is feasible with a bad column (column 3), so the LP is unbounded (B).

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

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

is (A) 1/2, (B) 2/3, (C) 3/4, (D) none of the above.

Solution.  Let x be the unknown for the first row of the column problem. Then

x ≥ 0,  2x - 1 ≥  0, 3x -2 ≥ 0, 4x - 3  ≥ 0, -x + 1 ≥ 0, i.e.,   3/4 ≤ x ≤ 1. The objective for the column problem is

x -> max. So max  = 1  (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, (D) none of the above.

Solution. As in Problem 29,     3/4 ≤ x ≤ 1. The objective for the column problem is

-x +1  -> max. So max  = 1/4   (D).

31. As a function of parameter  t, the optimal value of the linear program

tx + (2 - t)y -> max, 0  ≤ x ≤ 1, 0 ≤ y ≤ 2

has the following slopes:

(A) -1, (B) -1, -2, (C) -2, -1, 1,  (D) none of the above.

Solution.  If  t ≤ 0, then  max = 4 - 2t  at x = 0, y =2, so the slope is -2.

If 0 ≤  t ≤ 2, then  max =4 - t  at x = 1, y = 2 so the slope is -1.

If  t ≥ 2, , then  max = t at x = 1, y = 0, so the slope is 1.  (C)

32. As a function of parameter  t, the optimal value of the linear program

x + y -> max, t  ≤ x ≤  2 - t,  t ≤ y ≤ 3 - t

has the following slopes:

(A) -1, (B)  -2, (C) -2, -1, 0,  (D) none of the above.

Solution.   The LP is feasible if and only if   t ≤ 2 - t and t ≤ 3 - t, i.e.,  t ≤ 1.

Then max = (2 - t) + (3 - t) = 5 - 2t, so the slope is -2   (B)

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

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

Here are the choices for the first pivot entry consistent with Simplex Method:

(A) -1, (B) -3, -4, (C)  1, 9,   (D) none of the above.

Soliuion.

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

Both are degenerate. Actually, the second row forces all variables on top to be 0, so the LP is infeasible.

(D.

34. The optimal value of the  job assignment problem

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

is (A) < 5, (B)  5,  (C)  6, (D) none of the above.

Solution.  min in each column is on the main diagonal: min = 0 +1 + 2 + 1 + 1 + 1 =6. (C)

35.  The optimal value  for the transportation problem

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

is (A) ≤43, (B) > 43, (C) the problem is infeasible, (D) none of the above.

Solution. Optimal potentials are added after supply column  and demand row:

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

Here is the adjusted cost (potentials for columns are subtracted from the cost) and the flow  located at positions with zero cost:

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

Now min = 0, hence min =  44 for the original problem. (B)