Introduction to Optimization Recitation 4 - Solutions

Problem 1 a) The following figure shows the feasible region and an isocostline. We note that the optimal solution indeed agrees with the company claim. b) x1 is the number of wrenches, we are therefore interested in the range of c1. We see from the figure in a) that the optimal solution is at the intersection of constraints (1) and (2). When we decrease c1, the slope of the isocost line decreases and becomes parallel to constraint (2) when c1=c2, that is when c1=100, therefore the allowable decrease is 30. Now when we increase c1, the isocost line eventually becomes parallel to constraint (1), when c1=1.5c2, or when c1=150. Page 1 of 7 This agrees with the sensitivity report. c) We note from the figure, that when we increase steel availability, we can only do so until the maximum number of wrenches becomes a limiting factor and the optimal solution switches from being at the intersection of constraints (1) and (2) to being at the intersection of (2) and (4). At the intersection of (2) and (4), x1=15 and x2=6 (x1=15 is given by (4) and substitude that into (2) to get the value of x2). Then we see that the RHS of (1) has increased to 1.5*15 + 6=28.5. Again, when we decrease the RHS of (1) the optimal solution we eventually switch to the intersection of (2) and (3). At that point the values of x1 and x2 (solve the two equations for the two unknowns) are 7.5 and 13.5 respectively. At that point the RHS of (1) is 1.5*7.5+13.5=24.75. This results agree with the sensitivity report. d) If steel capacity increases to 28000, the optimal objective function value becomes 2460 + 60(28-27) = 2520. Note that the shadow price for steel is 60, and it is valid for an increase up to 1.5 according to the sensitivity report. e) This is kind of a trick question! When we resolve the LP with 23000 molding hours, the optimal earnings is $2500 - not what we would have predicted using the shadow price for the molding hours constraint (2460 + 40*2 = 2540). The reason is that we varied the RHS for molding outside its allowable range. Outside of that range, a different basis will be optimal and the shadow price for molding ($40) will no longer be valid. f) We will apply the “pricing out” operation described in lecture. For a contribution of $60, we can price out the screwdriver at: 60 – 60(0.5) – 40(0.8) – 0(0.3) = -2. This means that it wouldn’t be profitable to produce screwdrivers in this case. It would become profitable if the price was $62. Problem 2 a) See recitation4.xls b) The shadow price is zero indicating that the constraint is not tight c) If we increase the RHS of the fat constraint we are increasing the size of the feasible region – since we are minimizing, we expect to do at least as well, therefore it makes perfect sense that the shadow price is negative. Page 2 of 7 d) Using recitaiton4.xls we note that the allowable range is [11.945, 14] for this solution to remain optimal. Increase of 1.5 is within the range – therefore the optimal objective value would increase by 1.5 * .67 = 1.005. Since the increase is within the allowable range, we know that the optimal solution is still at the intersection of the three tight constraints, but the RHS of one of them has changed. Using Cytools to solve for the decision variables we get the following sequence of tableau’s: Grade 1 0.7 0.9 0.5 Grade 2 0.8 0.8 0.6 Grade 3 0 0.8 0.4 10 13.5 7.5 Grade 1 1 0 0 Grade 2 1.142857 -0.22857 0.028571 Grade 3 0 0.8 0.4 14.28571 0.642857 0.357143 Grade 1 1 0 0 Grade 2 0 1 0 Grade 3 4 -3.5 0.5 17.5 -2.8125 0.4375 Grade 1 1 0 0 Grade 2 0 1 0 Grade 3 0 0 1 Solution 14 0.25 0.875 And we see that the optimal solution is 14 pounds of Grade 1, 0.25 pounds of Grade 2 and 0.875 pounds of Grade 3. e) Because all the decision variables are nonzero. f) Using the shadow prices, introducing one unit of Supergrade2000 would affect the objective value by .69- 3*.31-2.5*.67+1.14*.3 = -1.564 <0, our optimal solution would go down if we introduced Supergrade2000 into the feed, therefore it should be included. Problem 3 – Looking back at Phase 1 (Adapted from AMP) a) To find an initial basic feasible solutions we apply the steps introduced in lecture 6. Step 0. Start with a tableau for the original LP z Page 3 of 7 x1 x2 x3 x4 RHS 1 0 0 0 -3 1 -2 0 0 1 1 3 -2 1 -1 1 0 1 0 1 0 4 1 11 Step 1. Write the constraints of the original LP x1 1 -2 0 x2 1 1 3 x3 1 -1 1 x4 1 0 1 RHS 4 1 11 Step 2. Create new variables called “artificial variables” which will be the basic variables for the new LP We introduce artificial variables x5, x6, and x7 Maximize Subject to z = 3 x1 + 2 x3 x1 + x2 + x3 + x4 + x5 =4 + x6 =1 -2 x1 + x2 – x3 3 x2 + x3 + x4 + x7 = 11 x1, x2, x3, x4, x5, x6, x7 ≥ 0 x1 1 -2 0 x2 1 1 3 x3 1 -1 1 x4 1 0 1 x5 1 0 0 x6 0 1 0 x7 0 0 1 RHS 4 1 11 Step 3. Choose an objective so that the artificial variables will be 0 in an optimal solution, assuming that there is a bfs for the original problem w 1 0 0 0 x2 0 1 1 3 x1 0 1 -2 0 x3 0 1 -1 1 x4 0 1 0 1 x5 1 1 0 0 x6 1 0 1 0 x7 1 0 0 1 RHS 0 4 1 11 Step 4. Subtract constraints 1, 2 to the objective constraint so that the tableau becomes canonical We use cytools to help us (see recitation4.xls) and we get the following tableau. w 1 0 Page 4 of 7 x1 1 1 x2 -5 1 x3 -1 1 x4 -2 1 x5 0 1 x6 0 0 x7 0 0 RHS -16 4 0 0 -2 0 1 3 -1 1 0 1 0 0 1 0 0 1 1 11 Step 5. Solve the Phase 1 Problem using the simplex algorithm Again we use Cytools to help us with pivoting (see recitation4.xls) and we get the following tableau: w 1 0 0 0 x1 0 1 0 0 x2 0 0 1 0 x3 0 0.666667 0.333333 0 x4 1 0.333333 0.666667 -1 x5 3 0.333333 0.666667 -2 x6 2 -0.33333 0.333333 -1 x7 0 0 0 1 RHS -2 1 3 2 We notice that the objective value is <0, therefore the orginal LP is infeasible and we do not need to carry out steps 6-8. b) Now assuming b=9 we repeat steps 1-4 and get the following table at the end of step 5: w 1 0 0 0 x1 0 1 0 0 x2 0 0 1 0 x3 0 0.666667 0.333333 0 x4 1 0.333333 0.666667 -1 x5 3 0.333333 0.666667 -2 x6 2 -0.33333 0.333333 -1 x7 0 0 0 1 RHS 0 1 3 0 We note that the objective value is 0 but we still have an artificial variable in the basis, we therefore need to do one more pivot and drive x7 out of the basis, by letting x4 enter the basis. w 1 0 0 0 x1 0 1 0 0 x2 0 0 1 0 x3 0 0.666667 0.333333 0 x4 0 0 0 1 x5 1 -0.3333 -0.6667 2 x6 1 -0.6667 -0.3333 1 x7 1 0.333333 0.666667 -1 Step 6. Eliminate the artificial variables, and put back in the original objective function z 1 0 0 0 x1 -3 1 0 0 x2 0 0 1 0 x3 -2 0.666667 0.333333 0 x4 0 0 0 1 RHS 0 1 3 0 Step 7. Add multiples of constraints), etc to get the tableau in canonical form We add three times the first row to the zero-row and obtain the following tableau: Page 5 of 7 RHS 0 1 3 0 z 1 0 0 0 x1 0 1 0 0 x2 0 0 1 0 x3 0 0.666667 0.333333 0 x4 0 0 0 1 RHS 3 1 3 0 Step 8. Solve the original LP starting with the previous bfs Using Cytools (see recitation4.xls), we obtain the following final optimal tableau: z 1 0 0 0 x1 0 1.5 -0.5 0 x2 0 0 1 0 x3 0 1 0 0 x4 0 0 0 1 RHS 3 1.5 2.5 0 An optimal solution is (z,x1,x2,x3,x4) = (3,0,2.5,1.5,0). c) There are multiple optimal solutions because the cost coefficient of the nonbasic variable x1 is zero. This means that we can allow x1 to enter the basis and perform a pivot. This results in the following tableau: z 1 0 0 0 x1 0 1 0 0 x2 0 0 1 0 x3 0 0.666667 0.333333 0 x4 0 0 0 1 RHS 3 1 3 0 And we have found an alternative optimal BFS: (z,x1,x2,x3,x4) = (3,1,3,0,0). d) Both optimal solutions are degernerate because a basic variable (x4) is zero. Problem 4 a) The geometric equivalent of a constraint in 3 dimensions is a plane in the 3-dimensional space. Depending on whether we have a equal to, less than or equal to, or greater than or equal to constraint, we take all points on the plane, on or under the plane, or on or above the plane. b) Two adjacent corner points in 3 dimensions also share an edge, which is defined by the intersection of two constraints. (Notice how this is similar to the case when we define a line in 3-dimensional space by the intersection of 2 planes.) c) There is no such bound. Consider the following LP: Page 6 of 7 max z s.t. − 1 ≤ x1 ≤ 1 − 1 ≤ x2 ≤ 1 z ≤ 1 − x1 − x 2 z ≤ 1 + x1 − x 2 z ≤ 1 − x1 + x 2 z ≤ 1 + x1 + x 2 z ≥ 0. This LP yields the following 3-d plot: 1 0.75 1 0.5 0.25 0.5 0 -1 0 -0.5 -0.5 0 0.5 1 -1 The optimal value is the corner point at the top of the pyramid, and it is already adjacent to 4 corner points. However, by using constraints in terms of x1 and x2 only, it is easy to see that we can describe any regular polygon with k sides in the plane z=0 (to obtain this, use one inequality constraint for each side). If we take these constraints and add the 4 z-constraints from above, we obtain a pyramid with a regular polygon with k sides (instead of 4 sides) at its base. Its top corner point will be adjacent to k corner points. Since we can do this for any k, it follows that there is no limit, even in 3 dimensions. (Note: this explanation is more detailed and rigorous that is required of you in the homework.) d) No. Consider the feasible set described in point (c) (or any other feasible set in 3 dimensions), and take an objective parallel to an edge, but not parallel to any of the constraints. In this case, all the points on the edge are optimal, thus we have multiple optimal solutions, yet the objective is not parallel to any constraint. Page 7 of 7