AMS 341 Fall 2018 Solutions to Final Exam
Test A
1. (8 pts) a) s3 enters basis (most negative obj. fn. coef.). Minimum ratio test is 50/10 - row 2.
Current basic var. in row 2 is x3 which leaves the basis.
(4pts) b) currently optimal since no negative entries in row 0.

2.(4 pts) a) x11 = 20, x12 = 10, x22 = 40, x23 = 20, x33 = 50.
(4 pts) b) x13 = 30, x31 = 20, x23 = 30, x23 = 40, x22 = 20.
(8pts) c) u1 = 10, v1 =19, v2 = 17, u2 = 9, v3 = 15, u3 = 9.
Non-basic coefficients: c13 = -1, c21 = -3, c31 = -6, c32 = -3.
Bring c31 into basis: New solution: x12 = 30 , x22 = 20, x23 = 40, x31 = 20, x33 = 30.

3.(10 pts) Use first 5 rows, last 5 columns plus dummy column. Dummy demand 3,000;
dashed entries become M (a very large number); Atl, Chi, Den have supply and demand of 30,000 (or larger).
4. (3 pts) Subtract smallest number in each row (total of 11), then subtract 2 from column 3.
( 2 pts) Cover 0's with row 3, column 1 and 2,
(3 pts) then subtract 1 from uncovered entries (and add 1 to double covered entries).
(2 pts) Solution (2,2), (4,1), plus {(1,3), (3,4)} or {(1,4), (3,3)}.

5. (5 pts) a) A from 1 to 2, B from 2 to 3, C from 2 to 4, D from 2 to 5, dummy from 5 to 3, E from 3 to 6, F from 4 to 6, G from 6 to 7.
(4 pts) b) ET(1)=0, ET(2)=7, ET(3)=12, ET(4)=10, ET(5)=15, ET(20)=12, ET(7)=23, Critical Path 1-2-5-3-6-7. Length 23. (5 pts) c) Min 3A+4B+4C+3D+6E+3F+4G, s.t. x2 >= x1 + 7 - A, x3 >= x2 + 5 - B, x4 >= x2 + 3 - C, x5 >= x2 + 8 - D, x3 >=x5,
x6 >= x3 + 5 - E, x6 >= x4 + 4 Ð F, x7 >= x6 + 3 - G. x7 - x1<= 16, A,B, . . . G <=2; all variables integer, >= 0.

6.(6 pts) Min 3x1+4x2+4x3+3x4+6x5+3x6+4x7 s.t.
(10 pts) sum(xi) = 4, x1+x2+x3+x6+x7>=2, x2+x3+x4+x5+x7>=3;
(4 pts) x3<=x4, x1+x7>=1, xi=0 or 1.

7.(14 pts) y3(0,1,2,3)=0,y3(4,5,6,7)=6, y3(8,9)=12
y2(0,1,2)=0, y2(3)=5, y2(4,5)=min{5,6}=6, y2(6)=min{10,6}=10,
y2(7)=min{10,11}=11, y2(8)=min{10,11,12}=12, y2(9)=min{15,10,11}=15
; y1(9)=min{16,17,13,15}=17 x1=3,x2=1
.
Test B
1. (4pts) a) currently optimal since no negative entries in row 0.
(8 pts) b) s2 enters basis (most negative obj. fn. coef.). Minimum ratio test is 18/3 - row 3.
Current basic var. in row 3 is x3 which leaves the basis.

2.(4 pts) a) x11 = 40, x21 = 10, x22 = 30, x32 = 215, x33 = 35.
(4 pts) b) x32 = 45, x31 = 5, x13 = 35, x21 = 40, x11 = 5.
(8pts) c) u1 = 10, v1 =20, u2 = 12, v2 = 16, u3 = 14, v3 =21.
Non-basic coefficients: c12 = +1, c13 = -6, c23 = -3, c31 = -3.
Bring c13 into basis: New solution: x11 = 10 , x13 = 30, x21 = 40, x32 = 45, x33 = 5.

3.(10 pts) Use first 5 rows, last 5 columns plus dummy column. Dummy demand 10,000;
dashed entries become M (a very large number); Alb, Pitt, KC have supply and demand of 50,000 (or larger).
4. (3 pts) Subtract smallest number in each row (total of 11), then subtract 2 from column 4.
( 2 pts) Cover 0's with row 1, column 1 and 2,
(3 pts) then subtract 1 from uncovered entries (and add 1 to double covered entries).
(2 pts) Solution (3,1), (2,2), plus {(1,3), (4,4)} or {(1,4), (4,3)}.

5. (5 pts) a) A from 1 to 2, B from 2 to 3, C from 2 to 4, D from 2 to 5, dummy from 5 to 3, E from 3 to 6, F from 4 to 6, G from 6 to 7.
(4 pts) b) ET(1)=0, ET(2)=7, ET(3)=12, ET(4)=10, ET(5)=15, ET(20)=12, ET(7)=23, Critical Path 1-2-5-3-6-7. Length 23. (5 pts) c) Min 3A+4B+4C+3D+6E+3F+4G, s.t. x2 >= x1 + 7 - A, x3 >= x2 + 5 - B, x4 >= x2 + 3 - C, x5 >= x2 + 8 - D, x3 >=x5,
x6 >= x3 + 5 - E, x6 >= x4 + 4 Ð F, x7 >= x6 + 3 - G. x7 - x1<= 18, A,B, . . . G <=2; all variables integer, >= 0.

6.(6 pts) Min 4x1+2x2+3x3+3x4+5x5+4x6+3x7 s.t.
(10 pts) sum(xi) = 4, x1+x2+x3+x4+x7>=2, x2+x3+x4+x5+x6>=3;
(4 pts) x3+x2 <=1, x1+x7>=1, xi=0 or 1.

7.(14 pts) y3(0,1,2)=0,y3(3,4,5)=5, y3(6,7,8)=10, y3(9)=15
y2(0,1)=0, y2(2)=4,y2(3)=min{4,5}=5, y2(4)=min{8,5}=8, y2(5)=min{8,9,5}=9, y2(6)=min{12,9}=12,
y2(7)=min{12,13}=13, y2(8)=min{16,13,14}=16, y2(9)=min{16,17,13}=17
; y1(9)=min{12,15,17}=17 x2=3,x3=1
.