Lecture 7: Sensitivity Analysis

15.093 Optimization Methods Lecture 7: Sensitivity Analysis 1 Motivation 1.1 Questions z = min s.t. 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 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 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 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 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′ • Suppose that there is a change in either b or c for example • How do we find whether B is still optimal? • Need to check whether the feasibility and optimality conditions are satis­ fied 5 Local sensitivity analysis 5.1 Changes in b bi becomes bi + Δ, i.e. (P ) min c′ x s.t. Ax = b x≥0 → (P ′ ) min c′ x s.t. Ax = b + Δei x≥0 • B optimal basis for (P ) • Is B optimal for (P ′ )? Need to check: 1. Feasibility: B −1 (b + Δei ) ≥ 0 2. Optimality: c′ − c′B B −1 A ≥ 0′ Observations: 1. Changes in b affect feasibility 2. Optimality conditions are not affected 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 Δ≤Δ≤Δ 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 satisfies optimality conditions → use dual simplex method 5.2 Changes in c cj → cj + Δ Is current basis B optimal? Need to check: 1. Feasibility: B −1 b ≥ 0, unaffected 2. Optimality: c′ − c′B B −1 A ≥ 0′ , affected There are two cases: • xj basic • xj nonbasic 5.2.1 xj nonbasic cB unaffected (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 cB ← ĉB = cB + Δej Then, [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 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? • Feasibility conditions are satisfied • 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 x≥0 min c′ x s.t. Ax = b a′m+1 x = bm+1 x≥0 → If current solution feasible, it is optimal; otherwise, apply dual simplex 5 5.5 Changes in A • Suppose aij ← aij + Δ • Assume Aj does not belong in the basis • Feasibility conditions: B −1 b ≥ 0, unaffected • Optimality conditions: cl − c′B B −1 Al ≥ 0, l = 6 j, unaffected • 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 • A furniture company makes desks, tables, chairs • The production requires wood, finishing labor, carpentry labor Profit 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 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 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?   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 • 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 finishing hours constraint? • What is the reduced cost for x2 ? 6.5 Shadow prices Why the dual price of the finishing hours constraint is 10? • Suppose that finishing 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 ⇒ 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 7 • Suppose you can hire 1h of finishing overtime at $7. Would you do it? • Another check c′B B −1   1 2 −8 2 −4  = = (0, −20, −60)  0 0 −0.5 1.5 (0, −10, −10) 6.6 Reduced costs • 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 profit decrease? 8x1 + x3 + s1 4x1 + 1.5x3 2x1 + 0.5x3 + 6·1 = 48 s1 = 26 + 2·1 = 20 ⇒ x1 = 0.75 + 1.5 · 1 = 8 x3 = 10 z ′ − 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 profit from table +30 Decrease wood by -6 −6 ∗ 0 = 0 Decrease finishing hours by -2 −2 ∗ 10 = −20 Decrease carpentry hours by -1.5 −1.5 ∗ 10 = −15 Total Effect −5 Suppose profit from tables increases from $30 to $34. Should it be produced? At $35? At $36? 6.7 Cost ranges Suppose profit from desks becomes 60 + Δ. For what values of Δ does current basis remain optimal? Optimality conditions: cj − c′B B −1 Aj ≥ 0 ⇒ ′ p = c′B B −1 = [0, −20, −(60 + Δ)] = −[0, 10 − 0.5Δ, s1 , x3 , x1 are basic Reduced costs of non-basic variables 8 " 1 0 0 2 2 −0.5 10 + 1.5Δ] −8 −4 1.5 #   6 c2 = c2 − p′ A2 = −30 + [0, 10 − 0.5Δ, 10 + 1.5Δ]  2  = 5 + 1.25Δ 1.5 cs2 = 10 − 0.5Δ cs3 = 10 + 1.5Δ Current basis optimal:  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 becoming (20+ Δ) What happens?  finishing  hours  change by Δ   48 1 2 −8 48 2 −4   20 + Δ  B −1  20 + Δ  =  0 8 0 −0.5 1.5 8   24 + 2Δ =  8 + 2Δ  ≥ 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Δ Suppose Δ =  10 then   s1 44  x3  =  25  ← inf. (Use dual simplex) x1 −3 6.9 New activity Suppose the company has the opportunity to produce stools Profit $15; requires 1 ft of wood, 1 finishing 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 +x4 +x4 xi ≥ 0 9 +s1 +s2 +s3 = 48 = 20 =8 1 1 c4 − = −15 − (0, −10, −10) =5≥0 1 Current basis still optimal. Do not produce stools ! c′B B −1 A4 10