Optimization Methods: Duality Theory 2

Duality 2. The Dual Problem 1 Quote of the Day Every word or concept, clear as it may seem to be, has only a limited range of applicability. -- Werner Heisenberg Just as we have two eyes and two feet, duality is a part of life. -- Carlos Santana 2 Review of Last Lecture Prices max s.t. z= -3x1 + 2x2 -3x1 + 3x2 ≤6 red 1 0 -.33 -4x1 + 2x2 ≤2 gray 17.2 2 7 x1 ≥ 0, x2 ≥ 0 A set of prices for a linear program is a collection of real numbers associated with each constraint, other than the nonnegativity constraints. 3 Pricing out to get reduced costs z max s.t. For a maximization problem, treat the prices as though they really are prices on the RHS. z= Prices -3x1 + 2x2 -3x1 + 3x2 ≤6 red -4x1 + 2x2 ≤2 gray x1 ≥ 0, x2 ≥ 0 Reduced costs = original costs minus column coefficients time prices. c j − ∑ i aij pi 1 2 x1 x2 -3 - (1 × -3) - (2 × -4) 2 - (1 × 3) - (2 × 2) 4 -3 4 Pricing out a new variable If we introduce a new variable, we price it out just as we priced out all other variables. max z = -3x1 + 2x2 + 3y s.t. -3x1 + 3x2 + 4y + x3 -4x1 + 2x2 + 3y Shadow prices + x4 =6 1/3 =2 1/2 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, y ≥ 0 y 3 - (1/3 × 4) - (1/2 × 3) 1/6 If we price out a new variable, and it is its reduced cost is positive, then the opt objective value will increase if the variable can be positive. 5 Simplex Multipliers Start with an original problem Obtain a modified problem and modified tableau after several pivots. The simplex multipliers are those prices such that the reduced costs wrt to those prices are exactly the same as the reduced costs in the modified tableau. The basic variables have a reduced cost of 0. 6 Simplex multipliers for the tableau below. z x1 x2 x3 x4 1 -1 -3 3 -2 2 +2 0 0 = 0 0 -3 3 1 0 = 6 1/3 0 -4 2 0 1 = 2 1/2 z x1 x2 x3 x4 -1 0 0 -1/3 -1/2 = -3 0 1 0 1/3 -1/2 = 1 0 0 1 2/3 1/2 = 3 The tableau after two pivots. 7 Important Fact z For a problem with equality constraints, optimizing wrt the reduced costs is the same as optimizing wrt the original costs. 8 Review of Results z The shadow prices are the unit change in the optimal objective value per unit change in the RHS coefficients. z The simplex multipliers are chosen so that the reduced costs of the basic variables are 0. z The simplex multipliers for the optimal tableau are equal to the shadow prices. z The reduced costs of the nonbasic variables in the final tableau are the same as the reduced costs of the optimal solution. These are also the shadow prices of the nonnegativity constraints. 9 That’s right. We will see that dual prices are great for computing upper bounds on the objective function of a max problem. And they often have interesting interpretations. Nooz, this looks like where we left off last time. Are we finally going to see what duality is all about? We will illustrate dual prices on an ancient problem in alchemy Tim Nooz 10 The Alchemist's Problem z In 1502, the alchemist Zor Primal has set up shop creating gold, silver, and bronze medallions to celebrate the 10th anniversary of the discovery of America. His trainee alchemist (TA) makes the medallions out of lead and pixie dust. Here is the data table. Gold Silver Bronze Available TA labor (days) 2 4 5 100 lead (kilos) 1 1 1 30 pixie dust (grams) 10 5 2 204 Profit (Euros) 52 30 20 11 More on Zor Zor has decided to set up his problem as a linear program and will solve it using the simplex algorithm, using “new math”, that is, Arabic numerals. He chooses the variables x1, x2, and x3, for the number of kilos of gold, silver, and bronze respectively. 12 More on Zor The Primal LP Maximize 52 x1 + 30 x2 + 20 x3 subject to 2 x1 + 4 x2 + 5 x3 1 x1 + 1 x2 + 1 x3 ≤ 100 ≤ 30 10 x1 + 5 x2 + 2 x3 ≤ 204 x1, x2 , x3 ≥ 0 13 The Primal LP Maximize 52 x1 + 30 x2 + 20 x3 subject to 2 x1 + 4 x2 + 5 x3 1 x1 + 1 x2 + 1 x3 ≤ 100 ≤ 30 10 x1 + 5 x2 + 2 x3 ≤ 204 x1, x2 , x3 ≥ 0 z x1 x2 x3 x4 x5 x6 1 -1 -3 52 2 30 0 20 0 0 0 = 0 0 2 4 1 5 0 1 1 0 0 = 100 0 1 1 0 1 1 0 0 1 1 0 = 30 0 10 5 2 0 0 1 = 204 14 Lower bounds on the opt value. z x1 x2 x3 x4 x5 x6 1 -1 -3 52 2 30 0 20 0 0 0 = 0 0 2 4 5 1 0 1 0 1 0 = 100 labor 0 1 1 1 0 0 1 1 0 0 1 = 30 lead 0 10 5 2 0 0 1 = 204 pixie dust x = 0 is feasible. So, z = 0 is a lower bound on the opt. objective value We can obtain a solution with z = 400, by setting x3 = 20, and all other variables are 0. Can we do better? 15 More on lower bounds z Any feasible solution for a maximization problem gives a lower bound on the optimum solution. z The best lower bound is the optimum solution. In this case z* = 1176, which we get by optimizing. z But is there an easy way of obtaining upper bounds on the optimum objective value, without optimizing first? 16 On upper bounds Fact. If we can choose prices so that the reduced costs are all nonpositive, then we can obtain an upper bound. (that is, the z-row satisfies the “optimality conditions” but we may have no feasible solution with the same cost. z x1 x2 x3 x4 x5 x6 -1 -3 0 -22 2 -32 0 0 -52 0 0 = -1560 -z -22x2 – 32x3 – 52x5 = -1560 z = 1560 – 22x2 – 32x3 – 52x5 ≤ 1560 because x ≥ 0 Optimizing wrt the reduced costs is the same as optimizing wrt the original costs. 17 Duality z The purpose of duality is to obtain upper bounds on a maximization problem. z An upper bound will measure the “gap” between a current feasible solution and what may be achievable. It gives a “performance guarantee.” z e.g. If I have a solution with value 1000 (lower bound) and if I know that I can’t do better than 1500 (upper bound), then I know that my solution is at least 2/3 of the optimal solution. 18 Using prices to obtain upper bounds Prices z x1 x2 x3 x4 x5 x6 -1 1 52 -3 30 2 20 0 0 0 0 = 0 0 2 4 5 1 1 0 0 1 0 = 100 0 0 1 1 1 0 0 1 1 0 0 1 = 30 52 0 10 5 2 0 0 1 = 204 0 Reduced costs: x1 x2 52 -0×2 -52 × 1 - 0 ×10 0 30 -0×2 -52 × 1 - 0 × 10 -22 x3 x4 x5 x5 RHS 19 Using prices to obtain upper bounds Prices z x1 x2 x3 x4 x5 x6 -1 1 52 -3 30 2 20 0 0 0 0 = 0 0 2 4 5 1 1 0 0 1 0 = 100 0 0 1 1 1 0 1 0 1 0 0 1 = 30 52 0 10 5 2 0 0 1 = 204 0 0 -52 0 0 = -1560 -3 0 -22 2 -32 0 -z +22x2 + 32x3 + 52x5 = -1560 z = -22x2 – 32x3 – 52x5 + 1560 so z ≤ 1560 20 Using prices to obtain upper bounds Prices z x1 x2 x3 x4 x5 x6 -1 1 52 -3 30 2 20 0 0 0 0 = 0 0 2 4 1 5 0 1 1 0 0 = 100 0 0 1 1 0 1 1 0 0 1 1 0 = 30 100 52 0 10 5 2 0 0 1 = 204 0 0 -100 0 0 = -3000 -48 -3 -70 2 -80 0 -z +48x2 + 70x3 + 100x5 = -3000 z = -48x2 – 70x3 – 100x5 + 3000 so z ≤ 3000 Which bound is better: 1560 or 3000? 21 On Better Bounds z Suppose that you can achieve a value of 90 (lower bound). And you can show that the most you can do is Q. Which is a better value of Q, Q = 100 or Q = 200? z FACT. For a maximization problem, the lower the upper bound, the better. We want the lower bound to be as close to the true optimum as possible. 22 Using prices to obtain upper bounds Prices z x1 x2 x3 s1 s2 s3 -1 1 52 -3 30 2 20 0 0 0 0 = 0 0 2 4 5 1 1 0 0 1 0 = 100 p01 0 1 1 1 0 0 1 1 0 0 1 = 30 52 p2 0 10 5 2 0 0 1 = 204 p03 -3 0 1 -22 2 2 -32 0 3 ⎯c 0 4 -52 0 5 ⎯c 06 = ⎯c ⎯c ⎯c ⎯c -1560 -z0 Theorem. If ⎯cj ≤ 0 for all j, then z ≤ z0 Definition. If ⎯cj ≤ 0 for all j, the prices are called dual prices. 23 Exercise Prices z x1 x2 x3 x4 x5 x6 -1 1 52 -3 30 2 20 0 0 0 0 = 0 0 2 4 5 1 1 0 0 1 0 = 100 0 1 1 1 0 0 1 1 0 0 1 = 30 0 10 5 2 0 0 1 = 204 -3 2 0 0 0 0 = Can you come up with dual prices that give a better upper bound than 1560? 24 What prices give the best upper bound? z x1 x2 x3 x4 x5 x6 1 -1 -3 52 2 30 0 20 0 0 0 = 0 Prices 0 2 4 5 1 1 0 0 1 0 = 100 p1 0 1 1 1 0 0 1 1 0 0 1 = 30 p2 0 10 5 2 0 0 1 = 204 p3 Minimize 100 p1 + 30 p2 + 204 p3 52 – 2 p1 - p2 - 10 p3 ≤ 0 30 – 4 p1 - p2 - 5 p3 ≤ 0 20 – 5 p1 - p2 - 2 p3 ≤ 0 The dual linear program. 0 – p1 ≤ 0; 0 – p2 ≤ 0; 0 – p2 ≤ 0; 25 The Dual Linear Program Minimize 100 p1 + 30 p2 + 204 p3 52 – 2 p1 - p2 - 10 p3 ≤ 0 30 – 4 p1 - p2 - 5 p3 ≤ 0 20 – 5 p1 - p2 - 2 p3 ≤ 0 0 – p1 ≤ 0; 0 – p2 ≤ 0; 0 – p2 ≤ 0; Minimize 100 p1 + 30 p2 + 204 p3 s.t. 2 p1 + p2 + 10 p3 ≥ 52 4 p1 + p2 + 5 p3 ≥ 30 5 p1 + p2 + 2 p3 ≥ 20 p1, p2, p3 ≥ 0 26 The Primal LP (before adding slacks) Max 52 x1 + 30 x2 + 20 x3 subject to 2 x1 + 4 x2 + 5 x3 ≤ 100 1 x1 + 1 x2 + 1 x 3 10 x1 + 5 x2 + 2 x3 ≤ 30 ≤ 204 x1, x2 , x3 ≥ 0 The Dual LP Minimize s.t. 100 p1 + 30 p2 + 204 p3 2 p1 + p2 + 10 p3 ≥ 52 4 p1 + p2 + 5 p3 ≥ 30 5 p1 + p2 + 2 p3 ≥ 20 p1, p2, p3 ≥ 0 27 Relationships between the Primal and Dual LPs PRIMAL LP (max) Objective Coefficients RHS Coefficients Column Coefficients Row Coefficients ≤ constraints DUAL LP (min) RHS coefficients Objective Coefficients Row Coefficients Column Coefficients ≥ constraints Precise rules later in this lecture 28 Weak Duality Theorem z If there is a feasible solution x’ for the primal (max) problem, and if there is a feasible solution p’ for the dual (min) problem, then the primal objective value for x’ is at most the dual objective value for p’. For example, 52 x’1 + 30 x’2 + 20 x’3 ≤ 100 p’1 + 30 p’2 + 204 p’3 Any feasible solution for the dual problem gives an upper bound on the optimum primal solution. Any feasible solution for the primal problem gives a lower bound on the optimum dual solution. 29 On Duality Having an upper bound is great. If you know that you can achieve a profit of 1000, and you know that the max profit is at most 1050, you know that you are within 5% of optimal. But sometimes, the primal or dual problem is infeasible. Nooz 30 Examples of Primal and Dual Problems Maximize z = 2 x1 + x2 Minimize v = 4 y1 + 2y2 subject to x1 + x2 ≤ 4 subject to y1 + y2 ≥ 2 x1 - x2 ≤ 2 y1 - y2 ≥ 1 x1, x2 ≥ 0 y1, y2 ≥ 0 Example in which both the primal and dual LPs are feasible. Maximize z = 2 x1 + x2 subject to - x1 + x2 ≤ -4 Minimize v = -4 y1 + 2y2 subject to - y1 + y2 ≥ 2 x1 - x2 ≤ 2 y1 - y2 ≥ 1 x1, x2 ≥ 0 y1, y2 ≥ 0 Example in which neither the primal nor dual LPs is feasible. 31 Examples of Primal and Dual Problems Maximize z = 2 x1 + x2 subject to x1 - x2 ≤ 4 Minimize v = 4 y1 + 2y2 subject to y1 + y2 ≥ 2 - y1 - y2 ≥ 1 x1 - x2 ≤ 2 x1, x2 ≥ 0 y1, y2 ≥ 0 Example in which the primal LP is unbounded and the dual LP is infeasible. Maximize z = 2 x1 + x2 Minimize v = -4 y1 + 2y2 subject to - x1 - x2 ≤ -4 subject to - y1 + y2 ≥ 2 x1 + x2 ≤ 2 - y1 + y2 ≥ 1 x1, x2 ≥ 0 y1, y2 ≥ 0 Example in which the primal LP is infeasible, and the dual LP is unbounded. 32 Time for a mental break If you think MIT tests for undergraduates are difficult, remember that things could be worse…. MEDICINE You will be provided with a razor blade, a piece of gauze, and a bottle of scotch. Remove your own appendix. Do not suture until your work has been inspected. You will have fifteen minutes. PUBLIC SPEAKING 2500 riot-crazed aborigines will be turned loose in the classroom with you. Calm them. You may use any ancient language except Latin or Greek. 33 SOCIOLOGY Estimate the sociological problems which might accompany the end of the world. Construct a fullscale experiment to test your theory. ENGINEERING The disassembled parts of a high-powered rifle will be placed on your desk. You will also find an instruction manual, printed in Swahili. In ten minutes a hungry Bengal tiger will be admitted to the room. Take whatever action you feel appropriate. Be prepared to justify your decision. ASTROPHYSICS Define the universe. Give three examples. 34 MANAGEMENT SCIENCE Define management. Define science. How do they relate? Why? Create a generalized algorithm that can be used to optimize all managerial decisions. Design the systems interface and prepare all software necessary to program this algorithm on whatever computer may be selected by the examiner. GENERAL EXAM QUESTION FOR ANY FIELD Describe everything you know in detail. Be objective and specific. 35 Weak Duality Strong DualityTheorem Theorem z IfIf there forthe theprimal primal there is is aa feasible feasible solution solution x’for (max) (max) problem, problem, and and ifif there there is is aa feasible feasible solution p’ for thefor dual (min) then the primal solution the dualproblem, (min) problem, then the objective x’ is at value most for the is dual optimum value primalfor objective equal to objective value forobjective p’. the optimum dual value. Equivalently. If there is a feasible solution for the primal (max) problem, and if the objective value is not unbounded from above, then the optimum primal objective value for is equal to the optimum dual objective value. 36 But what if the dual problem is infeasible? If the primal problem has an optimal solution, then so does the dual, and these objective values are the same. Therefore, if the primal problem has a feasible solution and the dual problem does not have a feasible solution, then …. 37 But what if the primal problem is infeasible? If the dual problem has an optimal solution, then so does the primal, and these objective values are the same. Therefore, if the dual problem has a feasible solution and the primal problem does not have a feasible solution, then …. Note: it is possible for neither problem to have a feasible solution. 38 An example of strong duality Opt Primal solution. The Primal LP (before adding slacks) Max z= subject to 52 x1 + 30 x2 + 20 x3 5 x3 ≤ 100 1 x1 + 1 x 2 + 1 x 3 ≤ 30 10 x1 + 5 x2 + 2 x3 ≤ 204 2 x1 + 4 x2 + x1, x2 , x3 ≥ 0 The Dual LP Minimize s.t. Opt Dual solution. v = 100 p1 + 30 p2 + 204 p3 2 p1 + p2 + 10 p3 ≥ 52 4 p1 + p2 + 5 p3 ≥ 30 5 p1 + p2 + 2 p3 ≥ 20 p1, p2, p3 ≥ 0 x1 = 18 x2 = 0 x3 = 12 z = 1176 p1 = 0 p2 = 12 p3 = 4 v = 1176 39 That can’t be right. How can the two numbers always be the same? Does it work for other problems too? Tim It really is true for all linear programs. Ollie, the computationally wise owl. 40 Mira and Marnie’s M&M Adventure buy Primal max z= s.t. sell Opt Primal solution. -3x1 + 2x2 -3x1 + 3x2 ≤6 red -4x1 + 2x2 ≤2 gray x1 = 1 x2 = 3 z= 3 x1 ≥ 0, x2 ≥ 0 Dual min s.t. v= Opt Dual solution. 6p1 + 2p2 -3x1 + -4x2 ≥ -3 buy 3p1 + 2x2 ≥2 sell x1 ≥ 0, x2 ≥ 0 p1 = 1/3 p2 = 1/2 v=3 41 That’s totally amazing. And I’m not just talking turkey, whatever that means. But weren’t the optimum dual variables also the shadow prices? Tim Impressive. You must have remembered the numbers from the last lecture. The optimum dual variables are also shadow prices. And they are also the optimum simplex multipliers. Ollie, the computationally wise owl. 42 The optimum dual variables are the shadow prices, and these are also the optimum simplex multipliers. Wow! The Dual LP Min s.t. 100 p1 + 30 p2 + 204 p3 2 p1 + p2 + 10 p3 ≥ 52 4 p1 + p2 + 5 p3 ≥ 30 5 p1 + p2 + 2 p3 ≥ 20 p1, p2, p3 ≥ 0 Tim Opt Dual solution. p1 = 0 ; p2 = 12; p3 = 4 ; v = 1176 43 z x1 x2 x3 s1 s2 s3 -1 1 52 -3 0 30 -2 2 20 0 0 -12 0 -4 0 = optimal simplex multipliers -1176 0 0 2 4 1 5 0 1 1 0 0 = 100 0 0 1 1 0 1 1 0 0 1 1 0 = 30 52 12 0 10 5 2 0 0 1 = 204 4 0 52 – (0 × 2) – (12 x 1) – (4 x 10) = 0 30 – (0 × 4) – (12 x 1) – (4 x 5) = -2 20 – (0 × 5) – (12 x 1) – (4 x 2) = 0 0 – (0 × 100) – (12 x 30) – (4 x 204) = 1176 44 The optimal tableau z x1 x2 x3 s1 s2 s3 -1 1 -3 0 -2 2 0 0 -12 0 -4 0 0 0 .125 1 0 0 1 -5.75 1 .375 0 = = = 0 1 .375 0 1 0 -.25 0 .125 1 0 0 .625 1 0 1.25 -1.25 = -1176 optimal simplex multipliers 4 0 18 12 52 12 4 0 The optimal simplex multipliers give a feasible solution for the dual. And it is also optimal. 45 Optimal Dual variables as Shadow Prices z Question 1. What happens to the optimal objective value if Zor is given another two ounces of Pixie dust? (Make an assumption so that you can get a numerical answer.) z Question 2. What is the reduced cost of silver (variable x2)? 46 Question 1. What happens to the optimal objective value if Zor is given another two ounces of Pixie dust? Answer. The shadow price of Pixie dust is 4, the optimum dual variable for the constraint on pixie dust. So the objective value will go up 4 × 2 = 8 units. We need to assume that 2 is within the allowable increase. Question 2. What is the reduced cost of silver (variable x2)? Answer. 30 - 4×0 12 × 1 - 5 × 4 = -2. We would need to increase the price of silver by 2 before it became profitable to make it. 47 An interpretation of the dual Gold Silver Bronze Available Prices TA labor (days) 2 4 5 100 p1 lead (kilos) 1 1 1 30 p2 pixie dust 10 5 2 204 p3 Profit (Euros) 52 30 20 Dual: minimize 100 p1 + 30 p2 + 204 p3. A rival alchemist Roz wants to buy the supply of resources from Zor. She wants to minimize the cost of buying the resources. 2 p1 + p2 + 10 p3 ≥ 52 Zor will sell resources only if it is better than producing precious metals himself. In particular, selling the resources needed to make an ounce of gold must be worth at least as much as making the ounce of gold himself. 48 Note on interpretation z The dual is well defined always. There is not always a believable story that goes with the dual. z Sometimes, there is an interpretation or story that “explains” the dual. (Here we started with the dual, and developed the story to explain it.) z Roz wants to buy Zor’s resources at minimum cost. Zor won’t sell resources (or at least not all of them) if it making a precious metal creates more wealth than selling the resources directly. What prices should Roz set so that Zor is willing to sell all of the resources? 49 Brief summary z Duality is amazing z The dual problem is to find the prices that give the best upper bound on a max LP. z The optimum value for the dual (if it exists) is the optimal value for the primal problem (if it exists) z The optimal dual variables are the shadow prices. For a problem in standard form, these are also the simplex multipliers. 50