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