Optimization Methods Sensitivity Analysis

1 Motivation 1.1 Questions z = min s.t. � � � � Slide 1 cx Ax = b x�0 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 Global sensitivity analysis 3.1 Dependence on c G(c) = min Slide 3 cx s.t. Ax = b x�0 i G(c) = mini�1 ::: N c x is a concave function of c 0 0 3.2 Dependence on b Primal F (b) = min s.t. Dual F (b) = max s.t. cx Ax = b x�0 F (b) = maxi�1 ::: N (pi ) b is a convex function of b 0 0 1 Slide 4 pb pA�c 0 0 0 (c + q d)' (x 3) (c + q d)' (x 2) (c + q d)' (x 4) (c + q d)' (x 1) x 1 optimal . x 2 optimal . x 3 optimal . x 4 optimal f (q ) (p 1)' (b *+ q d) (p 2)' (b *+ q d) q1 q2 2 (p 3)' (b *+ q d) q q 4 Local sensitivity analysis cx s.t. Ax = b x�0 What does it mean that a basis B is optimal? 1. Feasibility conditions: B 1 b � 0 2. Optimality conditions: c ; cB B 1 A � 0 z = min 0 Slide 5 ; 0 0 ; 0 � 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- Slide 6 ed 5 Local sensitivity analysis 5.1 Changes in b bi Slide 7 becomes bi + , i.e. (P ) min c x s.t. Ax = b 0 ! x�0 (P ) min c x s.t. Ax = b + ei 0 0 x�0 � B optimal basis for (P ) � Is B optimal for (P )? 0 Slide 8 Need to check: 1. Feasibility: B 1 (b + ei ) � 0 2. Optimality: c ; cB B 1 A � 0 ; 0 0 ; 0 Observations: 1. Changes in b aect feasibility 2. Optimality conditions are not aected B 1(b + 1 ei) � 0 ij = B ]ij bj = B 1 b]j Thus, (B 1 b)j + (B 1 ei )j � 0 ) bj + ji � 0 ) ; ; ; ; ; 3 Slide 9
; bj max ; bj � � min <0  >0 ji ji
ji ji Slide 10 � � Within this range � Current basis B is optimal � z = cB B 1 (b + ei ) = cB B 1 b + pi � What if = ? � What if > ? Current solution is infeasible, but satis es optimality conditions ! use dual simplex method ; 0 0 ; 5.2 Changes in c cj Slide 11 ! cj + Is current basis B optimal? Need to check: 1. Feasibility: B 1 b � 0, unaected 2. Optimality: c ; cB B 1 A � 0 , aected ; 0 0 ; 0 There are two cases: � xj basic � xj nonbasic 5.2.1 xj nonbasic cB unaected 1 (cj + ) ; cB B Aj � 0 ) cj + � 0 0 ; Solution optimal if � ;cj What if = ;cj ? What if < ;cj ? 4 Slide 12 5.2.2 xj basic Slide 13 cB � c^B = cB + ej Then, c 0 B 1 A]j i = aj i ; c^B B 1A]i � 0 ) ci ; cB + ej ] B 1Ai � 0 0 ; 0 ; ; c ci ; aj i � 0 ) max i a <0 a ji ji What if ci � � amin >0 a ji ji is outside this range? use primal simplex 5.3 A new variable is added min c x s.t. Ax = b 0 min c x + cn+1 xn+1 s.t. Ax + An+1xn+1 = b 0 ! x�0 Slide 14 x�0 In the new problem is xn+1 = 0 or xn+1 > 0? (i.e., is the new activity profitable?) Current basis B . Is solution x = B 1 b xn+1 = 0 optimal? ; Slide 15 � Feasibility conditions are satis ed � Optimality conditions: cn+1 ; cB B 1 An+1 � 0 ) cn+1 ; p An+1 � 0? 0 ; 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 0 x�0 min c x s.t. Ax = b am+1x = bm+1 0 ! 0 x�0 If current solution feasible, it is optimal otherwise, apply dual simplex 5 Slide 16 5.5 Changes in A � � � � � � Suppose aij � aij + Assume Aj does not belong in the basis Feasibility conditions: B 1 b � 0, unaected Optimality conditions: cl ; cB B 1 Al � 0, l = 6 j , unaected Optimality condition: cj ; p (Aj + ei ) � 0 ) cj ; pi � 0 What if Aj is basic? BT, Exer. 5.3 Slide 17 ; 0 ; 0 6 Example 6.1 A Furniture company � A furniture company makes desks, tables, chairs � The production requires wood, nishing labor, carpentry labor Pro t Wood (ft) Finish hrs. Carpentry hrs. Desk 60 8 4 2 Table (ft) 30 6 2 1.5 Chair Avail. 20 1 48 1.5 20 0.5 8 6.2 Formulation Slide 19 Decision variables: x1 = # desks, x2 = # tables, x3 = # chairs max 60x1 + 30x2 + 20x3 s:t: 8x1 + 6x2 + x3 � 48 4x1 + 2x2 + 1:5x3 � 20 2x1 + 1:5x2 + 0:5x3 � 8 x1 x2 x3 �0 6.3 Simplex tableaus Initial tableau: 0 Slide 18 s1 s2 s3 x1 0 0 s1 = 48 1 s2 = 20 s2 = 8 1 6 0 1 x2 x3 -60 -30 -20 8 6 1 4 2 1.5 2 1.5 0.5 Slide 20 Final tableau: 280 s1 = 24 x3 = 8 x1 = 2 s1 s2 0 1 0 0 s3 10 10 2 -8 2 -4 -0.5 1.5 x1 0 0 0 1 x2 5 -2 -2 1.25 x3 0 0 1 0 6.4 Information in tableaus � What is B ? � What is B 1 ? ; 0 0:5 2 21 B 1=4 0 ; � � � � � � � Slide 21 21 1 83 B = 4 0 1:5 4 5 3 2 ;8 2 ;4 5 0 ;0:5 1:5 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 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? New Previous s1 = 26 24 8 x1 + x3 + s1 = 48 New solution: 4x1 + 1:5x3 = 21 ) x1 = 1:5 2 x3 = 10 2x1 + 0:5x3 =8 8 Solution change: z ; z = (60 � 1:5 + 20 � 10) ; (60 � 2 + 20 � 8) = 10 Slide 22 Slide 23 Slide 24 0 7 Slide 25 � Suppose you can hire 1h of nishing overtime at $7. Would you do it? � Another check 0 1 2 ;8 1 cB B 1 = (0 ;20 ;60) @ 0 2 ;4 A = 0 ;0:5 1:5 (0 ;10 ;10) 0 ; 6.6 Reduced costs Slide 26 z0 Slide 27 � What does it mean that the reduced cost for x2 is 5? � Suppose you are forced to produce x2 = 1 (1 table) � How much will the pro t decrease? 8x1 + x3 + s1 + 6 � 1 = 48 s1 = 26 4x1 + 1:5x3 + 2 � 1 = 20 ) x1 = 0:75 2x1 + 0:5x3 + 1:5 � 1 = 8 x3 = 10 ; z = (60 � 0:75 + 20 � 10) ; (60 � 2 + 20 � 8 + 30 � 1) = ;35 + 30 = ;5 Another way to calculate the same thing: If x2 = 1 Direct pro t from table +30 Decrease wood by -6 ;6 � 0 = 0 Decrease nishing hours by -2 ;2 � 10 = ;20 Decrease carpentry hours by -1.5 ;1:5 � 10 = ;15 Total Eect ;5 Suppose pro t from tables increases from $30 to $34. Should it be produced? At $35? At $36? 6.7 Cost ranges Suppose pro t from desks becomes 60 + . For what values of does current basis remain optimal? Optimality conditions: c ; cB B 1 A � 0 ) " 1 2 ;8 # 1 p = cB B = 0 ;20 ;(60 + )] 0 2 ;4 0 ;0:5 1:5 =;0 10 ; 0:5 10 + 1:5] j 0 0 0 ; Slide 28 j ; Slide 29 are basic Reduced costs of non-basic variables s1  x3 x1 8 2 6 3 c2 = c2 ; p A2 = ;30 + 0 10 ; 0:5  10 + 1:5 ] 4 2 5 = 5 + 1:25 0 1:5 = 10 ; 0:5 = 10 + 1:5 Current basis optimal: cs2 cs3 9 5 + 1:25 � 0 = 10 ; 0:5 � 0 ;4 � � 20 10 + 1:5 � 0 ) 56 � c1 � 80 solution remains optimal. If c1 < 56, or c1 > 80 current basis is not optimal. Suppose c1 = 100( = 40) What would you do? 6.8 Rhs ranges Suppose nishing by 32 becoming (203+ ) What happens? 2 48 3 hours 2 1 change 2 ;8 48 B 1 4 20 + 5 = 4 0 2 ;4 54 20 + 5 8 2 24 +8 2 3 0 ;0:5 1:5 = 4 8+2 5� 0 2 ; 0:5 ) ;4 � � 4 current basis optimal Note that even if current basis is optimal, optimal solution variables change: s1 = 24 + 2 x3 = 8 + 2 x1 = 2 ; 0:5 z = 60(2 ; 0:5 ) + 20(8 + 2 ) = 280 + 10 0Suppose 1 =0 1044then 1 s1 @ x3 A = @ 25 A � inf. (Use dual simplex) x1 ;3 Slide 30 ; 6.9 New activity Suppose the company has the opportunity to produce stools Prot $15 requires 1 ft of wood, 1 nishing hour, 1 carpentry hour Should the company produce stools? max 60x1 8x1 4x1 2x1 +30x2 +6x2 +2x2 +1:5x2 +20x3 +x3 +1:5x3 +0:5x3 +15x4 +x4 +s1 = 48 +x4 +s2 = 20 +x4 +s3 = 8 xi � 0 9 Slide 31 Slide 32 Slide 33 c4 ; cB B A4 = ;15 ; (0 ;10 ;10) 1! 1 =5�0 1 Current basis still optimal. Do not produce stools 0 ;1 10