Operations Research Review Solutions

Review Solutions, Exam 2, Operations Research 1. Prove the weak duality theorem: For any x feasible for the primal and y feasible for the dual, then... HINT: Put the primal so that Ax ≤ b and the dual so that AT y ≥ c SOLUTION: With the primal and dual in normal form, then yT Ax ≤ yT b and xT A T y ≥ xT c Noting that xT AT y = (Ax)T y = yT (Ax), we get that: cT x ≤ yT Ax ≤ bT y 2. Show that the solution to the dual is y = (cTB B −1 )T (if the primal and dual are both feasible). HINT: Strong duality might be useful. SOLUTION: Ignore the hint, which should have read: “Consider Row 0”. In the optimal tableau, the coefficients of Row 0 are all non-negative. Therefore, cTB B −1 A − cT ≥ 0 ⇒ cTB B −1 A ≥ cT The vectors on the right and left are in rows. Transpose them for columns: AT (cTB B −1 )T ≥ c Therefore, if we define y = (cTB B −1 )T , we know that y is feasible for the dual. Now, is y optimal for the dual? Now we can use strong duality: yT b = cTB B −1 b = cT x so y is optimal for the dual. 3. Solve using big-M: max z = 2x1 + 3x2 st 2x1 + x2 ≥ 4 x1 − x2 ≥ −1 x2 ≤ 3 x1 , x2 ≥ 0 Side remark: In the third constraint, I meant to make the first variable less than 3, but we’ll go ahead and solve the one that is written. SOLUTION: Notice that we do not want the negative b2 , so multiply that constraint by −1. This makes constraints 2 and 3 “normal” (with slack variables), so we only need one excess variable for the first constraint. This means we have only one artificial variable, and the tableau is: x1 x2 e1 s2 s3 a1 rhs −2 −3 0 0 0 M 0 2 1 −1 0 0 1 4 −1 1 0 1 0 0 1 0 1 0 0 1 0 3 x1 x2 e1 s2 s3 a1 rhs −2 − 2M −3 − M M 0 0 0 −4M 2 1 −1 0 0 1 4 −1 1 0 1 0 0 1 0 1 0 0 1 0 3 → 1 Now, after pivoting in Column 1, and second row (counting the top as the first), we get: x1 x 2 e 1 s2 s3 a1 rhs 4 0 −2 −1 0 0 1 + M 1 1/2 −1/2 0 0 1/2 2 3 0 3/2 −1/2 1 0 1/2 0 1 0 0 1 0 3 At this stage, we might ignore the artificial variable, and the rest of the problem is the standard simplex method. The optimal tableau is: x1 x2 e1 s2 s3 a1 rhs 0 0 0 −2 5 M 13 1 0 0 −1 1 0 2 0 1 0 0 1 0 3 0 0 1 −2 3 −1 3 And we see that the feasible set (and the LP) is unbounded. 4. Solve the last problem again using the dual simplex method. NOTE: We end up back at the regular simplex method after the first step. x1 x2 e1 s2 s3 rhs x1 x2 e1 s2 s3 rhs −2 −3 0 0 0 0 0 −2 −1 0 0 4 −2 −1 1 0 0 −4 → 1 1/2 −1/2 0 0 2 −1 1 0 1 0 1 0 3/2 −1/2 1 0 3 3 3 0 1 0 0 1 0 1 0 0 1 (You can check that (2, 0) satisfies the constraints). If we continue with the usual simplex method, we get the same tableau as before (so the LP is unbounded). 5. Going back to the original LP in (1), if the constraint x1 + x2 ≤ 4 is added, does the basis stay optimal? If not, find the new basis (and the new solution). SOLUTION: Graphically, this makes the feasible set bounded. If we put in x1 = 2, x2 = 3, the constraint is not satisfied, which means that this solution is not the optimal one with the new constraint: x1 x2 e1 s2 s3 s4 rhs 0 0 0 −2 5 0 13 1 0 0 −1 1 0 2 0 1 0 0 1 0 3 0 0 1 −2 3 0 3 1 1 0 0 0 1 4 2 (1) To initialize the array, we’ll pivot on columns 1 and 2: x1 x2 e1 s2 s3 s4 rhs 0 0 0 −2 5 0 13 1 0 0 −1 1 0 2 0 1 0 0 1 0 3 3 0 0 1 −2 3 0 0 0 0 1 −2 1 −1 (2) And now we see that we can pivot in the fourth column (which gives us the positive Row 0 to start the dual simplex): x1 x2 e1 s2 s3 s4 rhs 0 0 0 0 1 2 11 1 0 0 0 1 1 1 0 1 0 0 1 0 3 0 0 1 0 −1 2 1 0 0 0 1 −2 1 −1 (3) Now we use the dual simplex algorithm, and pivot in the fifth column to try to get something primal-feasible. x 1 x 2 e1 s2 s3 s4 rhs 0 0 0 1/2 0 5/2 21/2 1 0 0 −1/2 0 1/2 3/2 0 1 0 1/2 0 1/2 5/2 0 0 1 −1/2 0 3/2 3/2 0 0 0 −1/2 1 −1/2 1/2 (4) EXTRA: See if you understood what just happened in terms of the primal and dual. For your convenience, the constraints are: 2x1 + x2 −x1 + x2 x2 x1 + x2 ≥4 ≤1 ≤3 ≤4 2y1 − y2 + y4 ≥ 2 y1 + y2 + y3 + y4 ≥ 3 Now, in Equation (1), the original solution, x1 = 2, x2 = 3 satisfied the first three constraints. We incorporate the last constraint to get Equation (2). The negative sign in the RHS indicates that (2, 3) is no longer feasible in the primal. The negative sign in Row 0 is not feasible for the dual (since y2 ≥ 0). However, pivoting in the fourth column to get Equation (3), we now have a solution that is feasible for the dual: y1 = y2 = 0, y3 = 1, y4 = 2. The value you see in the upper right corner is yT b = 11. However, we still do not have a feasible point for the primal. Pivoting in the last step to get Equation (4) gets us to a point that is feasible in the primal: x1 = 3/2, x2 = 5/2 AND the dual: y1 = y3 = 0, y2 = 1/2 and y4 = 5/2, and we now have the optimal solution for both the primal and dual! 3 6. Using the big-M method on a maximization problem, I got the following tableau: x3 a1 a2 x1 x2 x3 s1 e1 e2 a1 a2 rhs −1/2 + 2M −5/2 + M M 1/2 + M M M 0 0 2 − 3M 1/2 1/2 1 1/2 0 0 0 0 2 −3/2 −1/2 0 −1/2 −1 0 1 0 2 −1/2 −1/2 0 −1/2 0 −1 0 1 1 Should I stop or should I go? If I stop, what should I conclude? SOLUTION: Please stop! The conclusion is that the LP is infeasible. 7. Use the two phase method to solve the following max z = x1 + x2 st x1 − x2 − x3 = 1 −x1 + x2 + 2x3 − x4 = 1 x1 , x2 , x3 , x4 ≥ 0 SOLUTION: Starting things off, recall that we change our objective function to: max z = −a1 − a2 or z + a1 + a2 = 0. Incorporating this into the tableau, we get the following. We initialize by making the last two columns pivot columns as shown: x1 x2 x3 x4 a1 a2 rhs 0 0 0 0 1 1 0 1 −1 −1 0 1 0 1 −1 1 2 −1 0 1 1 x1 x2 x3 x4 a1 a2 rhs 0 0 −1 1 0 0 −2 1 −1 −1 0 1 0 1 −1 1 2 −1 0 1 1 → Now we perform the Simplex Method, and we get: x1 x2 x3 x4 a1 a2 rhs 0 0 0 0 1 1 0 1 −1 0 −1 2 1 3 0 0 1 −1 1 1 2 x1 x2 x3 x4 a1 a2 rhs 0 0 0 0 1 1 0 1 −1 0 −1 2 1 3 0 0 1 −1 1 1 2 → Now we have a feasible point. Remove the artificial variables and put in the original Row 0 coefficients, then make columns 1 and 3 pivot columns again. We then get: x1 x2 x3 x4 rhs 0 −2 0 −1 3 1 −1 0 −1 3 0 0 1 −1 2 From which we conclude that we have an unbounded LP. 8. Consider the LP and the optimal tableau with missing Row 0. x1 x2 s 1 max z = 3x1 + x2 s.t. 2x1 + x2 ≤ 4 3x1 + 2x2 ≥ 6 4x1 + 2x2 = 7 x1 , x2 ≥ 0 0 0 1 4 0 1 0 e2 a2 a3 rhs 1 0 0 − 12 0 −2 2 − 23 0 1 −1 1 1 2 3 2 1 Find Row 0. SOLUTION: Row 0 coefficients are given by cTB B −1 A − c cTB = [0, 1, 3] where However, we can compute them individually. The first three are zero. The coefficient for e2 : [0, 1, 3][0, −2, 1]T = 1 The coefficient for a2 : [0, 1, 3][0, 2, −1] + M = 1 + M The coefficient for a3 : [0, 1, 3][−1/2, −3/2, 1]T + M = 3/2 + M The optimal RHS is: [0, 1, 3][1/2, 3/2, 1]T = 9/2 Therefore, the optimal tableau is: x1 x2 s1 e2 a2 a3 rhs 0 0 0 1 −1 + M 3/2 + M 9/2 1 0 0 1 0 0 − 12 2 3 0 1 0 −2 2 − 32 2 1 0 0 1 −1 1 1 9. Consider the following LP and its optimal tableau: x1 x2 x3 s1 s2 rhs 8 1 0 0 2 16 2 2 0 1 −1 4 6 1 1 0 1 8 max z = 4x1 + x2 + 2x3 st 8x1 + 3x2 + x3 ≤ 12 6x1 + x2 + x3 ≤ 8 x1 , x2 , x3 ≥ 0 (a) Find the range of values for the coefficient of x3 which keeps the current basis optimal. SOLUTION: We see that x3 is a basic variable, so we change its value by substituting 2 + ∆ in for 2 in the vector cTB , then we check the effect of that on Row 0 for non-basic variables. we showed in class that the effect of that is to take the old Row 0, then we add ∆ times the second row of the optimal table- Recall we only check non-basic variables: [8, 1, 0, 0, 2] + ∆[6, 1, 0, 0, 1] ≥ 0 ⇒ 8 + 6∆ ≥ 0 1+∆ ≥0 2+∆ ≥0 ⇒ ∆ ≥ −1 (b) Find the range of values for the coefficient of x1 which keeps the current basis optimal. SOLUTION: We check cTB B −1 a1 − (c1 + ∆) ≥ 0, or in this case, [0, 2] · [2, 6]T − (4 + ∆) ≥ 0 ⇒ ∆≤8 (c) Find the range of values for the RHS of each constraint that keeps the current basis optimal. 5 SOLUTION: For b1 , we have: −1  −1 B b + ∆(B )1 = 4 8   +∆ 1 0  ≥0 ⇒ −4 ≤ ∆ For b2 , we have: −1 −1 B b + ∆(B )2 =  4 8   +∆ −1 1  ≥0 ⇒ −8 ≤ ∆ ≤ 4 (d) Write the dual, and solve it using the tableau for the primal (given above). SOLUTION: The dual is in normal form, so we can write it directly: min w = 12y1 + 8y2 st 8y2 + 6y2 3y1 + y2 y2 + y2 y1 , y2 ≥4 ≥1 ≥2 ≥0  ⇒ y= 0 2  10. Give an argument why, if the primal is unbounded, then the dual must be infeasible. SOLUTION: Suppose the dual was feasible. Then there exists a y that satisfies the constraints for the dual. But in that case, for every x in the primal, cT x ≤ bT y But we said that the primal was unbounded, so that cT x → ∞. This is a contradictionThus, the dual must be infeasible. Chapter 6 Review Problems: 3, 4 (except 4(b)), 6, 9, 10, 16, 17, 20, 21, 23, 33, 34. 6