15 093 Optimization Methods Lecture 7 Sensitivity Analysis 1 Motivation 1 1 Questions z min s t Slide 1 c x Ax b x 0 How does z depend globally on c on b How does z change locally if either b c A change How does z change if we add new constraints introduce new variables Importance Insight about LO and practical relevance 2 Outline Slide 2 1 Global sensitivity analysis 2 Local sensitivity analysis a Changes in b b Changes in c c A new variable is added d A new constraint is added e Changes in A 3 Detailed example 3 3 1 Global sensitivity analysis Dependence on c Slide 3 G c min s t c x Ax b x 0 i G c mini 1 N c x is a concave function of c 3 2 Dependence on b Slide 4 Primal F b min c x s t Ax b x 0 Dual F b max p b s t p A c F b maxi 1 N pi b is a convex function of b 1 c q d x3 c q d x2 c q d x4 c q d x1 x1 o p t i m a l x2 o p t i m a l x3 o p t i m a l x4 o p t i m a l q f q p1 b q d p2 b q d q1 q2 2 p3 b q d q 4 Local sensitivity analysis Slide 5 c x Ax b x 0 z min s t What does it mean that a basis B is optimal 1 Feasibility conditions 2 Optimality conditions B 1 b 0 c c B B 1 A 0 Slide 6 Suppose that there is a change in either b or c for example How do we nd whether B is still optimal Need to check whether the feasibility and optimality conditions are satis ed 5 Local sensitivity analysis 5 1 Changes in b bi becomes bi i e P min c x s t Ax b x 0 Slide 7 P min c x s t Ax b ei x 0 B optimal basis for P Is B optimal for P Slide 8 Need to check 1 Feasibility B 1 b ei 0 2 Optimality c c B B 1 A 0 Observations 1 Changes in b a ect feasibility 2 Optimality conditions are not a ected Slide 9 B 1 b ei 0 ij B 1 ij bj B 1 b j Thus B 1 b j B 1 ei j 0 bj ji 0 3 max ji 0 bj ji bj ji 0 ji min Slide 10 Within this range Current basis B is optimal z c B B 1 b ei c B B 1 b pi What if What if Current solution is infeasible but satis es optimality conditions use dual simplex method 5 2 Changes in c Slide 11 cj cj Is current basis B optimal Need to check 1 Feasibility B 1 b 0 una ected 2 Optimality c c B B 1 A 0 a ected There are two cases xj basic xj nonbasic 5 2 1 xj nonbasic Slide 12 cB una ected cj c B B 1 Aj 0 cj 0 Solution optimal if cj What if cj What if cj 4 5 2 2 xj basic Slide 13 cB c B cB ej Then c c B B 1 A i 0 ci cB ej B 1 Ai 0 B 1 A ji aji ci aji 0 max aji 0 ci ci min aji 0 aji aji What if is outside this range use primal simplex 5 3 A new variable is added min s t c x Ax b x 0 Slide 14 min s t c x cn 1 xn 1 Ax An 1 xn 1 b x 0 In the new problem is xn 1 0 or xn 1 0 i e is the new activity prof itable Current basis B Is solution x B 1 b xn 1 0 optimal Slide 15 Feasibility conditions are satis ed Optimality conditions cn 1 c B B 1 An 1 0 cn 1 p An 1 0 If yes solution x B 1 b xn 1 0 optimal Otherwise use primal simplex 5 4 A new constraint is added min c x s t Ax b a m 1 x bm 1 x 0 min c x s t Ax b x 0 If current solution feasible it is optimal otherwise apply dual simplex 5 Slide 16 5 5 Changes in A Slide 17 Suppose aij aij Assume Aj does not belong in the basis Feasibility conditions B 1 b 0 una ected Optimality conditions cl c B B 1 Al 0 l 6 j una ected Optimality condition cj p Aj ei 0 cj pi 0 What if Aj is basic BT Exer 5 3 6 Example 6 1 A Furniture company Slide 18 A furniture company makes desks tables chairs The production requires wood nishing labor carpentry labor Pro t Wood ft Finish hrs Carpentry hrs 6 2 Desk 60 8 4 2 Table ft 30 6 2 1 5 Chair 20 1 1 5 0 5 Avail 48 20 8 Formulation Slide 19 Decision variables x1 desks x2 tables x3 chairs max 60x1 30x2 20x3 s t 8x1 6x2 x3 4x1 2x2 1 5x3 2x1 1 5x2 0 5x3 x1 x2 x3 6 3 48 20 8 0 Simplex tableaus Slide 20 Initial tableau s1 s2 s2 0 48 20 8 s1 0 1 s2 0 s3 0 1 1 6 x1 60 8 4 2 x2 30 6 2 1 5 x3 20 1 1 5 0 5 Final tableau s1 x3 x1 6 4 s1 0 1 0 0 280 24 8 2 s2 10 2 2 0 5 s3 10 8 4 1 5 x1 0 0 0 1 x2 5 2 2 1 25 x3 0 0 1 0 Information in tableaus What is B Slide 21 1 8 1 5 4 0 5 2 2 8 2 4 0 5 1 5 1 B 0 0 What is B 1 B 1 1 0 0 Slide 22 What is the optimal solution What is the optimal solution value Is it a bit surprising What is the optimal dual solution What is the shadow price of the wood constraint What is the shadow price of the nishing hours constraint What is the reduced cost for x2 6 5 Shadow prices Slide 23 Why the dual price of the nishing hours constraint is 10 Suppose that nishing hours become 21 from 20 Currently only desks x1 and chairs x3 are produced Finishing and carpentry hours constraints are tight Does this change leaves current basis optimal 8x1 x3 s1 4x1 1 5x3 2x1 0 5x3 New solution 48 21 8 Slide 24 New Previous s1 26 24 x1 1 5 2 x3 10 8 Solution change z z 60 1 5 20 10 60 2 20 8 10 Slide 25 7 Suppose you can hire 1h of nishing overtime …