Optimization Methods: Duality Theory 3

Duality 3 There are concepts much more difficult to grasp than duality in linear programming. -- Jim Orlin The concept [of nonduality], often described in English as "nondualism," is extremely hard for the mind to grasp or visualize, since the mind engages constantly in the making of distinctions and nondualism represents the rejection or transcendence of all distinctions. 1 Overview z Rules for creating a dual linear program z Complementary slackness conditions z The dual simplex algorithm 2 Rules for creating a dual linear program The Primal LP Maximize z= subject to 1 x1 + 2 x2 + 3 x3 + 8 x1 + 9 x2 12 x1 + 13 x2 16 x1 + 17 x2 x1 ? x2 ? Dual Variable 4 x4 + 10 x3 + 11 x4 + 14 x3 + 15 x4 + 18 x3 + 19 x4 x3 ? x4 ? ? ? ? 5 6 7 y1 y2 y3 The Dual LP Minimize subject to v= 5 y1 + 6 y2 + 7 y3 8 9 10 11 y1 + 12 y2 + 16 y3 y1 + 13 y2 + 17 y 3 y1 + 14 y2 + 18 y3 y1 + 15 y2 + 19 y3 y1 ? y2 ? y3 ? ? ? ? ? 1 2 3 4 3 The SOB approach sensible, odd, and bizarre The Primal LP Max s.t. z= 1 x1 + 2 x2 + 3 x3 + 8 x1 + 9 x2 + 4 x4 10 x3 + 11 x4 ≤≥ 5 S 12 x1 + 13 x2 + 14 x3 + 15 x4 = 6 O 16 x1 + 17 x2 + 18 x3 + 19 x4 ≥≤ 7 B x1 ≥ 0, x2 ≥ 0, x3 uis, S S O x4 ≤ 0 ? B uis. unconstrained in sign 4 The SOB approach sensible, odd, and bizarre The Dual LP Min s.t v= 5 y1 + 6 y2 + 7 y3 16 y3 ≥≤ 1 S 9 y1 + 13 y2 + 17 y3 ≥≤ 2 S 10 y1 + 14 y2 + 18 y3 == 3 O 11 y1 + 15 y2 + 19 y3 ≤≥ 4 B 8 y 1 + 12 y2 + y1 ≥ 0, y2 uis y3 ≤ 0 S O B 5 More Rules Primal max i-th constraint ≤ i-th constraint = i-th constraint ≥ i-th variable ≥ 0 i-th variable free i-th variable ≤ 0 S: Dual min i-th variable ≥ 0 i-th variable free i-th variable ≤ 0 i-th constraint ≥ i-th constraint = i-th constraint ≤ S O B S O B sensible O: odd B: bizarre The SOB technique is due to Art Benjamin 6 The Primal LP Maximize z= subject to 1 x1 + 2 x2 + 3 x3 + 8 x1 + 9 x2 + 4 x4 10 x3 + 11 x4 ≤a 5 12 x1 + 13 x2 + 14 x3 + 15 x4 =b 6 16 x1 + 17 x2 + 18 x3 + 19 x4 ≥c 7 x1 ≥ d0, x2 ≥ e0, f x3 free, x4 ≤ g0 The Dual LP Minimize subject to v= 5 y1 + 6 y2 + 7 y3 8 y1 + 12 y2 + 16 y3 d ≥ 1 9 y1 + 13 y2 + 17 y3 e ≥ 2 10 y1 + 14 y2 + 18 y3 11 y1 + 15 y2 + 19 y3 =f 3 g ≤ 4 y1 ≥a 0, y2 free, b y3 ≤c 0 7 Shadow Price Method The Primal LP Maximize subject to z= 1 x1 + 2 x2 + 3 x3 + 8 x1 + 9 x2 + 4 x4 10 x3 + 11 x4 ≤ 5 12 x1 + 13 x2 + 14 x3 + 15 x4 = 6 16 x1 + 17 x2 + 18 x3 + 19 x4 ≥ 7 x1 ≥ d0, x2 ≥ e0, f x3 free, x4 ≤ g0 RHS of constraint (1) increases from 5 to 5.1 implies Primal LP is less constrained implies z increases or stays the same implies y1 ≥ 0. RHS of constraint (3) increases from 7 to 7.3 implies Primal LP is _______________ implies z _________________________ implies y3 ____ 8 Another Primal-Dual Pair z Jane Jetson is trying to design a diet for George on her home food dispenser so as to satisfy requirements and minimize cost. Space Burgers Saturn Shakes Venus Flies Requirements Carbs 4 2 0 12 Fat 3 4 0 8 Protein 4 1 2 20 Cost (in $100s) 5 4 2 9 Jane’s Linear Program x1 = number of Spaceburgers x2 = number of Saturn Shakes x3 = number of Venus Flies minimize z = 5 x1 + 4 x2 + 2 x3 subject to 4 x1 + 2 x2 + 3 x1 + 4 x2 + 4 x1 + 1 x2 + 2 x3 x1, x2 , x3 ≥ 0 ≥ 12 ≥ 8 ≥ 20 10 Primal Linear Program min z = 5 x1 + 4 x2 s.t 4 x 1 + 2 x2 3 x1 + 4 x2 4 x1 + 1 x2 x1, x2 , x3 ≥ 0 + 2 x3 + ≥ 12 + ≥ 8 + 2 x3 ≥ 20 carbs fat protein p1 p2 p3 Dual Linear Program Max v = 12 p1 + 8 p2 + 20 p3 cost of nutrients s.t ≤ 5 4 p 1 + 3 p2 + 4 p3 burgers 2 p1 + 4 p2 + 1 p3 ≤ 4 shakes + 2 p3 ≤ 2 flies p1, p2 , p3 ≥ 0 11 Spacely Sprockets has decided to make food pellets. Mr. Spacely wants to Jane to buy all foods from him. How should he price them to maximize profit and so that Jane is willing to purchase all foods from him? Dual Linear Program Max s.t z = 12 p1 + 8 p2 + 20 p3 4 p 1 + 3 p2 + 4 p3 cost of pellets ≤ 5 2 p1 + 4 p2 + 1 p3 ≤ 4 2 p3 ≤ 2 Spaceburgers Saturn shakes Venus flies p1, p2 , p3 ≥ 0 12 Complementary Slackness Conditions Let x* denote a primal feasible solution. Let p* denote a dual feasible solution. Complementary slackness conditions. 1. For all i, if the i-th constraint is an inequality constraint that is not tight at the optimum solution, then p*i = 0. 2. If the x*j > 0, then the j-th constraint of the dual problem is tight, and thus the reduced cost of x*j is 0. Theorem. If x* and p* are optimal primal and dual solutions, then they satisfy the complementary slackness conditions. 13 Complementary Slackness Conditions min v = 5 x1 + 4 x 2 + 2 x3 s.t 4 x 1 + 2 x2 + 3 x1 + 4 x2 + 4 x1 + 1 x2 + 2 x3 x1, x2 , x3 ≥ 0 ≥ 12 ≥ 8 ≥ 20 carbs fat protein Opt Solution: x1 = 3, x2 = 0, x3 = 4, z = 23 What does complementary slackness tell us about the optimal dual variables (also known as shadow prices? Discuss it with your neighbor. p2 = 0; the reduced costs of x1 and x3 are 0. p2 = 0; 4 p1 + 3 p2 + 4 p3 = 5; 2 p3 = 2. 14 More on complementary slackness z If there is a unique optimum tableau, then the complementary slackness conditions will give the equations for a unique optimum dual solution. Dual Linear Program Max s.t z = 12 p1 + 8 p2 + 20 p3 4 p 1 + 3 p2 + 4 p3 ≤ 5 2 p1 + 4 p2 + 1 p3 ≤ 4 2 p3 ≤ 2 p1, p2 , p3 ≥ 0 p2 = 0; 4 p1 + 3 p2 + 4 p3 2 p3 = 2. = 5; p2 = 0 p3 = 1 p1 = 1/4 15 Theorem on Complementary Slackness If x* is feasible for the primal, and if p* is feasible for the dual, and if the pair (x*, p*) satisfy complementary slackness conditions, then 1. x* is optimal for the primal problem and 2. p* is optimal for the dual problem Primal solution: x1 = 3 x2 = 0 x3 = 4 Dual Solution p1 = ¼ p2 = 0 p3 = 1 The complementary slackness conditions are satisfied. Thus they are both optimal. 16 Complementary Slackness: An alternative representation Primal solution: x1 = 3 x2 = 0 x3 = 4 Dual Solution p1 = ¼ p2 = 0 p3 = 1 x1 × (4 p1 + 3 p2 + 4 p3 - 5) = 0 3×0=0 x2 × (2 p1 + 4 p2 + 1 p3 - 4) = 0 0 × -2.5 = 0 x3 (2 p3 4×0=0 - 2) = 0 17 Mental Break 18 The Dual Simplex Algorithm z x1 x2 x3 x4 1 -3 3 -2 2 0 0 = 0 Objective function. 0 -3 3 1 0 = 6 Constraint 1 0 -4 -4 2 0 1 = 2 Constraint 2 If there are m constraints, a basic solution has m basic variables. The basic solution is obtained by setting the nonbasic variables to 0, and solving the system of equations. 19 Basic Feasible Solutions z x1 x2 x3 x4 1 -3 3 -2 2 0 0 = 0 0 -3 3 1 0 = 6 0 -4 2 0 1 = 2 z x1 x2 x3 x4 1 3 -3 -1 -2 20 0 0 1 = 0 3 -3 30 1 -1.5 0 = 3 6 0 -2 -4 21 0 .5 1 = 1 2 0 2 A solution is called a basic feasible solution, (bfs) if it is a basic solution and if it satisfies the nonnegativity constraints. Another bfs 20 Basic Dual Feasible Bases z x1 x2 x3 x4 1 -3 3 -2 2 0 0 = 0 0 -3 3 1 0 = 6 0 -4 2 0 1 = 2 x1 x2 x3 x4 z 1 1 3 -3 0 -2 2 2/3 0 0 = 4 0 0 -3 -1 31 1 1/3 0 = 6 2 0 -4 -2 2 0 0 -2/3 1 = 2 -2 A solution is called a basic dual feasible solution, if it is a basic solution and if it satisfies the optimality conditions with the z-row coefficients ≥ 0 (reduced costs are non-negative.) This tableau gives a basic dual feasible solution. The primal basic solution is x2 = 2 and x4 = -2, and so it is not a bfs. 21 How did you know where to pivot to get that dual feasible basis? There is no general rule on where to pivot. Just focus on the fact that it shows it is a basic dual solution. Where are the dual variables? The dual variables are “hidden”. They are the simplex multipliers. Why are we learning this? Tim We are learning this to learn the dual simplex algorithm. Ollie, the computationally wise owl. 22 Pivoting in the Dual Simplex Algorithm z x1 x2 x3 s1 s2 s3 1 -52 -30 -20 0 0 0 = 0 0 2 4 5 1 0 0 = 100 0 1 1 1 0 1 0 = 30 0 10 5 2 0 0 1 = 204 z x1 x2 x3 s1 s2 s3 1 48 20 0 0 0 10 = 2040 0 -23 -8.5 0 1 0 -2.5 = -410 0 0 -4 -1.5 0 0 1 -0.5 = -72 0 0 5 2.5 1 0 0 0.5 = 102 10 A dual feasible tableau RHS RHS Zor’s initial tableau Prices 23 A Dual Feasible Pivot z x1 x2 x3 s1 s2 s3 RHS 1 48 20 0 0 0 10 = 2040 0 -23 -8.5 0 1 0 -2.5 = -410 0 -4 -1.5 0 0 1 -0.5 = -72 0 5 2.5 1 0 0 0.5 = 102 A dual feasible tableau 1 48 ­ 4Δ 20­ 1.5Δ 0 0 Δ 10 ­ .5Δ = 2040 ­ 72Δ Step 1. Choose a row that is an infeasible constraint. Step 2. Add Δ times that row to the z-row. Step 3. Choose Δ maximum so that all coefficients are non­ negative. This determines the pivot column. 24 Finding the max value of Δ. z x1 x2 x3 s1 s2 s3 1 48 20 0 0 0 10 = 2040 0 -23 -8.5 0 1 0 -2.5 = -410 0 -4 -1.5 0 0 1 -0.5 = -72 0 5 2.5 1 0 0 0.5 = 102 1 48 ­ 4Δ 20­ 1.5Δ Δ 10 ­ .5Δ 48/4 20/1.5 0 s = argmin {⎯cj/ ⎯a2j: ⎯a2j < 0}. s = 1. 0 RHS = 2040 ­ 72Δ 10/.5 {48/4, 20/1.5, 10/.5}. Pivot on the component in constraint 2, column x1. If ⎯a2j ≥ 0, the dual is unbounded from below, and the primal is infeasible. 25 The Dual Simplex Pivot z x1 x2 x3 s1 s2 s3 RHS 1 48 0 20 2 0 0 0 12 10 4 = 2040 1176 0 -23 0 -8.5 1/8 0 1 0 -23/4 -2.5 3/8 = -410 4 0 1 -4 3/8 -1.5 0 0 - 1/4 1 1/8 -0.5 = 18 -72 0 5 0 2.5 5/8 1 0 0 5/4 -0.5 1/8 = 102 12 Divide constraint 2 by -4. Subtract 48 times the new constraint 2 from the z-row Add 23 times the new constraint 2 to constraint 1. Subtract 5 times the new constraint 2 from constraint 31. The resulting tableau will be dual feasible. If it is also a bfs, then it is optimal, and we can quit. Otherwise keep pivoting. 26 Another dual simplex pivot z x1 x2 x3 s1 s2 s3 RHS 1 2 3 1 0 0 0 = 5 0 2 4 5 1 0 0 = 10 0 -2 -1 1 0 1 0 = -3 0 1 1 1 0 0 1 = -2 1. Does this tableau give an upper bound on the optimal primal objective value? 2. What happens if we choose the second constraint as the pivot row? 3. What happens if we choose the third constraint at the pivot row? 27 Answers Answer 1. The optimal primal value is at most 5 because z + 2x1 + 3x2 + x3 = 5 and x ≥ 0. What happens if we choose the second constraint as the pivot row? The min ratio test gives min {2/2, 3/1} = 1 The column giving the min ratio is the column for x1. So, we pivot on the -2 What happens if we choose the third constraint as the pivot row? The min ratio test gives nothing. The dual is unbounded. The constraint is “x1 + x2 + x3 + s1 = -2” The primal has no feasible solution. 28 Comments on the Dual Simplex Algorithm z Alternative to primal simplex algorithm in which we relax primal feasibility, but require the z-row to satisfy the optimality conditions. z Dual simplex pivot rule: determined by a min ratio test. z Very efficient in practice for lots of large problems (great alternative to primal simplex) z If add an inequality constraint to an LP, the current basis may not be a bfs, but it stays dual feasible. (Very common in integer programming.) – The old basis can be used as a starting point for the dual simplex method 29