OR320/520 Fall 1999 Prelim2 Solution ------------------------------------- 1) The original problem is min 11 y1 + 3 y2 + y3 subject to 5 y1 + y2 - y3 >= 2 y1 + y2 + y3 = 1, y1 >= 0, y2 unrestricted, y3 >= 0. a) The dual problem is max 2 x1 + x2 subject to 5 x1 + x2 <= 11 x1 + x2 = 3 - x1 + x2 <= 1, x1 >= 0, x2 unrestricted. Here a "max" problem is the dual of a "min" problem; x1 is nonnegative because it corresponds to a >= constraint in a min prob; x2 is unrestricted because it corresponds to an = constraint; the first and third inequalities are <= because they correspond to nonnegative variables; and the second constraint is an equality because it corresponds to an unrestricted variable. b) It's hard to draw a good picture in ascii, so here's a description of what it should look like. Note that to say that (2,1)^T "solves the dual" means that is is not only feasible, but also optimal. In x1-x2 space, the constraints are: you must lie *on* the line through (3,0)^T and (0,3)^T; you must lie below and to the right of the line through (-1,0)^T and (0,1)^T; you must lie below and to the left of the line through (11/5,0)^T and (0,11)^T; and you must lie to the right of the vertical axis. So the feasible region is just the line segment from (1,2)^T to (2,1)^T. Either by drawing lines of constant objective value or by comparing the values at the two CPF solutions above, you get (2,1)^T as the optimal solution. c) Here, finding an optimal *solution* means finding the optimal values of the yi's -- it's not enough to give the optimal *value*. The key here is to use complementary slackness. Here are the steps: The optimal x1 is nonzero, and x1 corresponds to the first constraint of the original problem. So at optimality, this >= constraint must hold as an equation. (A number of you said that because x2 is nonzero, the second constraint holds as an equation. But it was an equation anyway! You shouldn't say that this is cause and effect; if the optimal x2 had turned out to be zero, the second constraint would still be an equation!) Next we look at the slacks in the dual optimal solution. The first LHS evaluates to 11, so there is no slack, and we cannot conclude anything about y1, which corresponds to this constraint. The third LHS evaluates to -1 (-2 + 1), which is strictly less than the RHS 1. So we conclude that the corresponding variable y3 must be zero at optimality. (Again, you shouldn't consider the second constraint. You know that there will be no slack, since the constraint *is* an equation, so it won't tell you anything about y2.) Now the optimal y must have y3 = 0, and from the constraints 5 y1 + y2 = 2, y1 + y2 = 1. Solving these two simultaneous equations gives you y1 = 1/4, y2 = 3/4, so the optimal y is (1/4, 3/4, 0). You can check that this has objective value 5, the same as the dual solution (2,1)^T. d) The corresponding changes to the dual are that x1 is now unrestricted, and the equation x1 + x2 = 3 becomes a <= constraint. So the old solution x = (2,1)^T is still feasible. Also, the old solution y = (1/4, 3/4, 0) is still feasible in the new constraints (the first constraint does hold at equality and y2 is nonnegative). Also, we still have complementary slackness (since x1 + x2 = 3), so we still have that these solutions are optimal. Alternatively, they have the same objective function values of 5, so they remain optimal. You can also argue that the new problem is *more constrained* than it was before (a >= constraint is now an =, and an unrestricted variable must now be nonnegative). So the optimal value can only go up. But the old optimal solution y = (1/4, 3/4, 0) satisfies the new constraints and gives optimal value 5. So it must still be optimal. Note that you can't just say that it is still feasible -- you must argue that it remains optimal. 2) a) Remember, when the objective is in the form of a maximization (as it must be in order to write the simplex tableau), the signs in row 0 are the opposite of what they'd be in an algebraic formulation. Thus, max -16x1 -17x2 -20x3 will show up in row 0 as [16 17 20]. The tableau is as follows: Z x1 x2 x3 x4 x5 RHS 1 16 17 20 0 0 0 0 -40 -30 -25 1 0 -100 0 -20 -40 -50 0 1 -100 b) The above solution is clearly NOT feasible. Our slack variables take on values of -100, and we are always constrained so that all variables must always be positive. The solution IS dual feasible, however, since all our row 0 coefficients are positive. Therefore, the best way to optimize this problem is by using the DUAL SIMPLEX METHOD. Here, we'd select x4 as the leaving basic variable, and use the dual-min-ratio-test to determine the entering basic variable. Here, the entering basic variable would be x1. c) We observe that in the optimal solution, the basic variables are x1 and x2. Thus, B is formed by the columns A1 and A2 from the original A-matrix: B = [-40 -30] [-20 -40] B^-1 is formed from the final two columns of the optimal tableau. Thus, B^-1 = [-4/100 3/100] [ 2/100 -4/100] d) The optimal solution to the dual of (P) is obtained by looking at the row 0 coefficients. Since primal slacks correspond to dual originals, the row 0 coefficients corresponding to x4 and x5 represent the values of the dual originals, y1 and y2. Similarly, the primal originals correspond to the dual slacks. Therefore, [y1 y2 y3 y4 y5] = [3/10 2/10 0 0 5/2] e) Computing feasible range for b1: For our optimal solution to remain feasible, the inequality B^-1 * b >= 0 must still hold. So we find the values necessary: B^-1 * b = [-4/100 3/100] * [ b1 ] >= 0 [ 2/100 -4/100] [-100] (-4 * b1)/100 + (3/100 * -100) >= 0 (2 * b1)/100 + (-4/100 * -100) >= 0 -4 * b1 >= 300 -------> b1 <= -75 2 * b1 >= -400 -------> b1 >= -200 Therefore, the range of b1 for which our solution remains optimal is -200 <= b1 <= -75 If b1 = -150, we are still within our optimal range, so our current solution is still optimal. However, the objective value and the x-values do change: B^-1 * b = [-4/100 3/100] * [-150] = [3] [ 2/100 -4/100] [-100] [1] cB * B^-1 * b = [-16 -17] * [3] = -65 [1] So our new solution is [x1 x2 x3 x4 x5] = [3 1 0 0 0], Z = -65 f) The current solution to stay optimal, row 0 coefficients of nonbasic variables should be nonnegative. The coefficients are determined by the following formula: [c3*, c4*, c5*] = [c1, c2] * B^-1 * [A3, A4, A5] - [c3, c4, c5] = [c1, -17] * B^-1 * [A3, A4, A5] - [-20, 0, 0] = [-1/2*c1 - 11/2, -4/100*c1 - 34/100, 3/100*c1 + 68/100] In order c3*, c4*, c5* to be nonnegative, c1 should satisfy c1 <= -11, c1 <= -17/2, c1 >= -68/3 which gives the following range for staying optimal: -68/3 <= c1 <= -11 If c1 changes to -10, then the new row 0 coefficients of nonbasic variables are [c3*, c4*, c5*] = [-1/2, 6/100, 38/100] and the new objective function value is c_B * B^-1 * b = [-10, -17] * [1, 2] = -44 . Since the coefficient of c3 in row 0 is negative, then the current basis is not optimal any more. Primal simplex should be applied to reoptimize. g) To add a variable to a problem, we simply compute the new values of that column by using the old values and B^-1. A common error here was to assume A6 (let's call the new variable x6) was [-0.5] [-0.2] We should be following the lead of the other columns, which are already calculating percentages, not decimals. Thus, A6 = [-50] [-20] B^-1 * A6 = [-4/100 3/100] * [-50] = [ 1.4] [ 2/100 -4/100] [-20] [-0.2] In order for us to want x6 to be a basic variable, c6* must be less than 0. Thus, c6 = cB * B^-1 * A6 - c6 <= 0: cB * B^-1 * A6 - c6 = [-16 -17] * [ 1.4] - c6 <= 0 [-0.2] -22.4 + 3.4 - c6 <= 0 ------> c6 >= -19 Thus, if c6 >= -19, we would want to add Coco Fistula to our diet.