Econ 172A - Slides from Lecture 5Joel SobelOctober 11, 2012Econ 172A SobelAnnouncementsIQuiz 2 on October 25, 2012.IProblems: Problems on current material: Problem Set 2,2004: #1, #4; 2007: #1; 2008: #2.Midterm 1, 2004: all; Midterm 2007: #1, 4; Midterm 1,2008: #2Econ 172A SobelTheorem (Complementary Slackness)Assume problem (P) has a solution x∗and problem (D) has asolution y∗.1. If x∗j> 0, then the jth constraint in (D) is binding.2. If the jth constraint in (D) is not binding, then x∗j= 0.3. If y∗i> 0, then the ith constraint in (P) is binding.4. If the ith constraint in (P) is not binding, then y∗i= 0.Econ 172A SobelUsing Complementary Slackness to Solve DualsLet’s take a familiar example:max 2x1+ 4x2+ 3x3+ x4subject to 3x1+ x2+ x3+ 4x4≤ 12x1− 3x2+ 2x3+ 3x4≤ 72x1+ x2+ 3x3− x4≤ 10x ≥ 0The solution to this problem isx0= 42, x1= 0; x2= 10.4; x3= 0; x4= .4. We can use thisinformation (and Complementary Slackness conditions) to solvethe dual. First write the dual:min 12y1+ 7y2+ 10y3subject to 3y1+ y2+ 2y3≥ 2y1− 3y2+ y3≥ 4y1+ 2y2+ 3y3≥ 34y1+ 3y2− y3≥ 1y ≥ 0Econ 172A SobelAlgebraStep 1, check feasibility.IFirst constraint: 0 + 10.4 + 0 + 1.6 = 12. Binding. Tells younothing about y1.ISecond constraint: 0 − 31.2 + 0 + 1.2 = −30. Not binding(but satisfied). y2= 0.IThird constraint: 0 + 10.4 + 0 − .4 = 10. Binding. Tells younothing about y3.So x satisfies constraints.Econ 172A SobelStep 2, implications of positive variables.1. x1= 0 tells you nothing.2. x2> 0 tells you second dual constraint binds at solution:y1− 3y2+ y3= 43. x3= 0 tells you nothing.4. x4> 0 tells you fourth dual constraint binds:4y1+ 3y2− y3= 1.So solution to dual must satisfy: y2= 0, y1+ y3= 4, and4y1− y3= 1.This means that candidate for solution to (D) is y = (1, 0, 3)Econ 172A SobelIs it a solution?Need to check constraints we ignored:1. Non negativity2. Dual Constraints 1 and 3.These constraints do hold.It is a solution.(Check that values are equal.)Econ 172A SobelWhat Happened?1. Begin with a “guess” for Primal.2. Check feasibility. If not, stop. It cannot be a solution.3. If so, note positive variables (implies binding dual constraints)and constraints with slack (implies zero dual values).4. Use non-zero dual variables to solve the equations in dual.(Typically equal number of equations and unknowns.)5. Check feasibility of this solution (are variables nonnegative?Are the dual constraints corresponding to zero primal variablessatisfied?) If yes, then you have solutions to both Primal andDual. If not, original guess is not a solution.Econ 172A