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

No electronics is allowed.   Write both answers and details. Write only answers on scantron. Return this page and the scantron.

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

2x -> max. So max  = 2 (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)