Math 339 Chapter 6 Review Solutions

Chapter 6 Review Solutions 3. Write the LP in normal form, and the optimal tableau is given in the text (to the right): x1 ≥ 0 x2 ≥ 0 x3 ≥ 0 rhs y1 ≥ 0 1 1 1 ≤6 6 0 1 ≤8 y2 ≥ 0 0 1 1 ≤2 y3 ≥ 0 ≥5 ≥1 ≥2 x1 x2 x3 s 1 s2 s3 rhs 0 1/6 0 0 5/6 7/6 9 0 1/6 0 1 −1/6 −5/6 3 1 1 −1/6 0 0 1/6 −1/6 0 1 1 0 0 1 2 (a) For the dual, just go down the columns: min w = 6y1 + 8y2 + 2y3 st y1 + y2 ≥ 5 y1 + y3 ≥ 1 y1 + y2 + y3 ≥ 2 y1 , y2 , y2 ≥ 0 (b) For the change in c1 , use the row corresponding to x1 . The new Row 0 is therefore: 5+∆ 7−∆ 1−∆ 0 0 6 6 6 In order for each of these to remain non-negative, −5 < ∆ < 1. 0 (c) In this case, x2 is a non-basic variable. We saw last time that the only change to the optimal Row 0 would be in this coefficient, which becomes 16 − ∆, so ∆ ≤ 1/6. 4. (a) From the LINDO output, we see that the coefficient 300 can increase by 20 or decrease by any amount. Therefore, 310 will keep the current basis, and the new value of z will be New z = Old z + (10)(88) = 33, 420 (b) Look at the Row 3 “RIGHTHAND SIDE RANGES”. The allowable increase is 0.4, which is less than the requested increase of 1. Therefore, we cannot answer the question from the LINDO output. (c) Look at Row 5, an increase of 1 would be allowed, but looking at the SLACK/SURPLUS, we are not currently using all the steel we have. Therefore, we should not buy any more. (d) Look at the constraint labelled 6). We are allowed to drop it by 2, and the shadow price is −20, so the profit is: 32, 540 + (−2)(−20) = 32, 580. (e) The new column for jeeps (without Row 0) is a4 = [1.2, 0, 2, 4, 0, 0]T . The coefficient in Row 0 is 600. The new Row 0 coefficient for this column would be: 600 − cTB B −1 a4 Recall that cTB B −1 is the solution to the dual, which we can read directly from the LINDO output. 600 − [400, 350, 0, 0, −20, 0] [1.2, 0, 2, 4, 0, 0]T = −120 Since this is negative, this variable would be brought into the optimal basis. We SHOULD produce jeeps. 1 6. (a) The dual is straightforward (use the normal form as in 3). The optimal dual solution can be read off of Table 55 (Look at the coefficients for the slack variables): y1 = 1/2 y2 = 1/2 (b) If you change b2 , then the optimal changes by (use second column of B −1 stored in the column for s2 ) " # " # 6 −1 +∆ 1 1/2 Making both of these positive, we see that −2 < ∆ < 6. If b2 is 12, that means ∆ = 2, and the new RHS will be [6 − 2, 1 + 1]T = [4, 2]T , which means x1 = 2 and x2 = 4. Just to finish it off, the new z−value would be found using the shadow price (dual solution): New z = 9 + 2(1/2) = 10 9. (a) The dual is: min w = 50y1 + 15y2 + 10y3 st y1 + 2y2 + y3 ≥ 3 y1 − y2 + y3 ≥ 4 y1 + y2 ≥ 1 y1 ≥ 0, y2 ≤ 0, y3 urs To read the dual from Table 56, consider columns s1 , e2 (or a2 ), and a3 . Therefore, y1 = 1, y2 = 0, y3 = 3. (And the optimal value of w is 80). (b) For changes in x1 , note that it is a non-basic variable. Therefore, the only change to the optimal Row 0 will be in this column, and it will be 1−∆. Therefore, ∆ < 1. (c) For changes in x2 , look at the bottom row of B −1 A (we can exclude the artificial variables). We see that the only changes will be to x1 , and its new Row 0 coefficient is 1 + ∆. Therefore, as long as ∆ > −1, the current basis remains optimal. 10. We’re getting more practice reading things off of the optimal tableau. In this case, (a) The dual is straightforward. The solution (reading off of Row 0 from Table 57) is y1 = 0, y2 = 1. (b) Changing b2 means that the optimal RHS becomes: " 4/3 1/3 # " +∆ −2/3 1/3 # So that −10 < ∆ < 2. If b2 = 5, then we have ∆ = −5, and the new RHS becomes [14/3, 5/3]T (so x1 = 5/3 and x2 = 0), and the new optimal value is: z = 10 + (1)(−5) = 5 16. More practice reading things off the LINDO output. This time it’s jewels! 2 (a) We are allowed to decrease by 100, so the new coefficent of −190 is allowed. The new value of z would be: New z = 19, 000 − (90)(15) = 17, 650 (b) Look at constraint labeled 6) to see if it is allowed (and it is). Therefore, 19, 000 + (−2)(−200) = 19, 400 (c) Labor is constraint labeled 4), and the dual price is $200. (d) Sapphires are constraint 3), and the dual price is 0. That is because we have an extra 10 already. (e) The new column (not including Row 0) for Type 3 would be a4 = [4, 2, 1, 0, 0]. Labeling the new Row 0 coefficient c4 , then we want to compute −c4 + cTB B −1 a4 which again is computed using the dual solution: −550 + 100 · 4 + 0 + 200 · 1 + 0 + 0 = 50 This new Row 0 coefficient is positive, so it would not have been brought into the optimal basis. Therefore, we would NOT produce any rings of Type 3. 17. The beginning and ending tableaus are shown below: x1 x2 e1 e2 rhs x1 x2 e1 e2 rhs 2 1 0 0 0 0 5 0 2 −16 → −1 −1 1 0 −5 0 −3 1 −1 3 −1 2 0 1 −8 1 −2 0 −1 8 20. Some practice with complementary slackness. Writing the dual, we have: min w = 5y1 + 8y2 st y1 + 2y2 ≥ 3 2y1 + 3y2 ≥ 4 y1 + y2 ≥ 1 2y1 + 3y2 ≥ 5 y1 , y2 ≥ 0 To use complementary slackness, we need to know which constraints are binding and which are not. Try some: Constraints 1 and 2 do not intersect in the first quadrant. Constraints 1 and 3 do not intersect either. Constraints 1 and 4 do intersect in the first quadrant, and give y1 = 1, y2 = 1, and w = 13 (and excess variables e1 and e4 are 0). Therefore in the primal, x2 = 0 and x3 = 0. Furthermore, the two slack variables are zero, so we solve x1 + 2x4 = 5 ⇒ x1 = 1, x4 = 2 2x1 + 3x4 = 8 Using this solution, z = 13 as well, so we know that this is an optimal solution. 3 21. This is a graphical problem, so I will only list the answers: (a) Basis remains optimal if c1 > 3. (b) Basis remains optimal if c2 < 4/3. (c) 0 ≤ b1 ≤ 9 (d) b2 ≥ 10. 23. More practice reading things off the optimal tableau. (a) The dual is straightforward. Its optimal solution (from Row 0 of Table 63) is y1 = 20, y2 = 0 y3 = 10 (b) Changing the price of Ale, use the bottom row of the tableau to get the new Row 0: 0 0 20 − ∆/3 0 10 + 2∆/3 Therefore, the current basis remains optimal if −15 < ∆ < 60. Therefore, the price P can range: 25 < P < 100. (c) Same question, but now for Beer (use the first row). The optimal Row 0 becomes: 0 0 20 + 2∆/3 10 − ∆/3 0 Therefore, −30 < ∆ < 30, and price P for beer is: 20 < P < 80. (d) How much can the amount of corn vary? Corn is the first constraint RHS, or b1 . Changing this quantity gives the optimal RHS as:       0 40 2 1 ∆      10  +  −1  ≥  0  3 3 0 40 −1 Solving, we get: −20 < ∆ < 10. Therefore, the amount of corn can drop by 20 lbs or increase by 10 lbs and we will keep the current optimal basis. (e) Hops is the second constraint, so:       40 0 0 1       10  + ∆  1  ≥  0  3 40 0 0 Therefore, ∆ > −4/3 (and we can increase by any amount). (f) For malt, we do the same as the previous 2 items:       40 −1 0 1 ∆      10  +  −1  ≥  0  3 3 40 2 0 4 ⇒ −20 < ∆ < 10 (g) For malt liquor, we would consider adding the column [0.5, 3, 3] to the matrix A, with coefficient of 50 in Row 0. Then the optimal Row 0 coefficient would be (use the dual): −50 + 20(0.5) + 0(3) + 10(3) = −10 Since this is negative, we would add malt liquor into the optimal basis (using simplex), so we should manufacture it! (h) All constraints are scaled by 16, the objective function is the same. (i) The dual is divided by 16. Remark: (h) and (i) are interesting side notes, but aren’t that important. 33. From the given information, we know that cTB = [c1 , c2 ] cTB B −1 = [1, 2] and where the info on the right was taken from the optimal tableau. Transposing both sides, we have: " −1 T (B ) cB = 1 2 # " T −1 ⇒ (B ) cB = 1 2 # " ⇒ cB = B T 1 2 # " = 7 10 # Therefore, c1 = 7 and c2 = 10. 34. (a) We’ll compute the values in Row 0 by parsing out −cT + cTB B −1 A We have cTB = [0, 20, 10] (note the columns of the identity in the optimal tableau for the order). To get B −1 , we have to know which columns of the original tableau were the three columns of the identity matrix. Some thought will give you the columns (in order) labeled a1 , s2 , a3 . Therefore,  B −1  1 −1 −1  1 0  = 0  1 −1 0 ⇒ cTB B −1 = [10, 10, 0] Therefore, the coefficient for s2 is cTB B −1~e2 , or 10. The coefficient for a1 is 10 + M The coefficient for a3 is M . (b) The dual and its solution are: min w = 150y1 + 40y2 + 20y3 st y1 + y2 ≥ 20 y1 + y3 ≥ 10 y1 urs, y2 ≥ 0, y3 ≤ 0 y1 = 10, y2 = 10, y3 = 0. 5