Math 484.2 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 
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)