Math 484.2   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 2 7 0 1 -1 -6 5 -1 6 11 1 2 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 7 0 1* -1 -6 5 -1 6 11 1 2 1 -8

 7 6 5 1 2 3

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

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

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

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

(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:

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

 -1 -1 -3 -2

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

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

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

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

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

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

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

Pivoting on 4 in the first row gives an optimal tableau with the last entry 9/4.

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

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

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

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

-2x -1  -> max. So max  = -3   (D).

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

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

has the following slopes:

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

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

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

If  t ≥  1, 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, 0 ≤ x ≤    t,  0≤ y ≤ 1 - 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   0 ≤ t ≤ 1.

Then max = t+ (1 - t) =1, so the slope is 0.   (D)

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) -2,  7, (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

(D).

34. The optimal value of the  job assignment problem

 3 1 3 1 2 1 3 1 3 2 1 2 3 3 5 1 4 2 3 2 2 2 2 2 1 1 3 1 3 1 1 2 2 1 1 1

is (A) < 7, (B)  7,  (C) > 7.

Solution.

 3 1 3 1 2 1* 3 1 3 2 1* 2 3 3 5 1* 4 2 3 2 2* 2 2 2 1 1* 3 1 3 1 1* 2 2 1 1 1

*min in column. min = 1 +1  +1  +2  +1  +1  = 7. (B)

35. The optimal value  for the transportation problem

 4 3 4 3 2 1 3 3 3 9 3 3 3 5 1 1 3 3 2 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) ≤61, (B) 62, (C)  63, (D) none of the above.

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

 4 3 4 3 2 1 3 3 3 9 -1 3 3 3 5 1 1 3 3 2 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 2 2 1 1 1 2 1 2

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 =  61 for the original problem. (A)