Econ 172A Slides from Lecture 5 Joel Sobel October 11 2012 Econ 172A Sobel Announcements Econ 172A I Quiz 2 on October 25 2012 I Problems 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 2 Sobel Theorem Complementary Slackness Assume problem P has a solution x and problem D has a solution y 1 If xj 0 then the jth constraint in D is binding 2 If the jth constraint in D is not binding then xj 0 3 If yi 0 then the ith constraint in P is binding 4 If the ith constraint in P is not binding then yi 0 Econ 172A Sobel Using Complementary Slackness to Solve Duals Let s take a familiar example max 2x1 subject to 3x1 x1 2x1 4x2 x2 3x2 x2 3x3 x3 2x3 3x3 x4 4x4 3x4 x4 x 12 7 10 0 The solution to this problem is x0 42 x1 0 x2 10 4 x3 0 x4 4 We can use this information and Complementary Slackness conditions to solve the dual First write the dual min 12y1 7y2 10y3 subject to 3y1 y2 2y3 2 y1 3y2 y3 4 y1 2y2 3y3 3 4y1 3y2 y3 1 y 0 Algebra Step 1 check feasibility I First constraint 0 10 4 0 1 6 12 Binding Tells you nothing about y1 I Second constraint 0 31 2 0 1 2 30 Not binding but satisfied y2 0 I Third constraint 0 10 4 0 4 10 Binding Tells you nothing about y3 So x satisfies constraints Econ 172A Sobel Step 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 4 3 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 and 4y1 y3 1 This means that candidate for solution to D is y 1 0 3 Is it a solution Need to check constraints we ignored 1 Non negativity 2 Dual Constraints 1 and 3 These constraints do hold It is a solution Check that values are equal What 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 variables satisfied If yes then you have solutions to both Primal and Dual If not original guess is not a solution