15.093 Optimization Methods Lecture 7: Sensitivity Analysis1 Motivation 1.1 Questions Slide 1 ′ z = min c x s.t. Ax = b x ≥ 0 • How does z depend globally on c? on b? • How does z change lo c ally 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 Slide 3 ′ G(c) = min c x s.t. Ax = b x ≥ 0 ′ iG(c) = mini=1,...,N c x is a concave function of c 3.2 Dependence on b Slide 4 Primal Dual ′ F (b) = min c x F (b) = max p ′ b s.t. Ax = b s.t. p ′ A ≤ c ′ x ≥ 0 F (b) = maxi=1,...,N (pi)′ b is a conve x function of b 1' ( x3) ( c +q d) ' 2 ( c + q d) x1) . . . ( x ) 4 ( c +q d) ' ( x )( c +q d) ' ( x1 optimal x2 optimal x3 optimal x4 optimal q ( p3) ( b * + q d) ( p2) ( b * + q d) ( p1) ( b * + q d) q f ( q ) ' ' ' q1 q2 24 Local sensitivity analysis ′ z = min c x s.t. Ax = b x ≥ 0 What does it mean that a basis B is optimal? 1. Feasibility conditions: B−1b ≥ 0 ′ ′2. Optimality conditions: c − cB B−1A ≥ 0 ′ Slide 5 Slide 6 • 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 Slide 7 bi becomes bi + Δ, i.e. (P ) min c ′ x (P ′ ) min c ′ x s.t. Ax = b → s.t. Ax = b + Δei x ≥ 0 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 − cB B−1A ≥ 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−1b]j Thus, (B−1b)j + Δ(B−1 ei)j ≥ 0 ⇒ bj + Δβji ≥ 0 3 Slide 8 Slide 9 ⇒    bj bj max − ≤ Δ ≤ min − βji >0 βji βji <0 βji Slide 10 Δ ≤ Δ ≤ Δ Within this range • Current basis B is optimal ′ ′ • z = cBB−1(b + Δei) = cBB−1b + Δpi • What if Δ =Δ? • What if Δ > Δ? Current solution is infeasible, but satisfies optimality conditions → use dual simplex method 5.2 Changes in c Slide 11 cj → cj + Δ Is c urrent basis B optimal? Need to check: 1. Feasibility: B−1b ≥ 0, unaffected ′ ′2. Optimality: c − cB B−1A ≥ 0 ′ , affected There are two cases: • xj basic • xj nonbasic 5.2.1 xj nonbasic Slide 12 cB unaffected (cj + Δ) − cB ′ B−1Aj ≥ 0 ⇒ cj + Δ ≥ 0 Solution optimal if Δ ≥ −cj What if Δ = −cj? What if Δ < −cj? 45.2.2 xj basic Slide 13 cB ← cˆB = cB + Δej Then, ′ ′[c − cˆBB−1A]i ≥ 0 ⇒ ci − [cB + Δej] ′ B−1Ai ≥ 0 [B−1A]ji = aji ci ci ci − Δaji ≥ 0 ⇒ max ≤ Δ ≤ min aji <0 aji aji >0 aji What if Δ is outside this range? use primal simplex 5.3 A new variable is added Slide 14 ′ ′min c x min c x + cn+1xn+1 s.t. Ax = b → s.t. Ax + An+1xn+1 = b x ≥ 0 x ≥ 0 In the new problem is xn+1 = 0 or xn+1 > 0? (i.e., is the new activity prof-itable?) Slide 15 Current basis B. Is solution x = B−1b, xn+1 = 0 optimal? • Feasibility conditions are satisfied • Optimality conditions: ′ cn+1 − cB B−1A n+1 ≥ 0 ⇒ cn+1 − p ′ An+1 ≥ 0? • If yes, solution x = B−1b, xn+1 = 0 optimal • Otherwise, use primal simplex 5.4 A new constraint is added Slide 16 ′min c x′min c x s.t. Ax = b s.t. Ax = b → ′ a m+1x = bm+1 x ≥ 0 x ≥ 0 If current solution feasible, it is optimal; otherwise, apply dual simplex 55.5 Changes in A Slide 17 • Suppose aij ← aij + Δ • Assume Aj does not belong in the basis • Feasibility conditions: B−1b ≥ 0, unaffected • Optimality conditions: cl − cB ′ B−1Al ≥ 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 Slide 18 • A furniture company makes desks, tables, chairs • The production require s wood, finishing labor, carpentry labor Desk Table (ft) Chair Avail. Profit 60 Wood (ft) 8 Finish hrs. 4 Carpentry hrs. 2 6.2 Formulation Decision variables: 30 6 2 1.5 20 1 1.5 0.5 x1 = # desks , x2 = # tables, x3 = # chairs max 60x1 + 3 0x2 + 2 0x3 s.t. 8x1 + 6 x2 + x3 4x1 + 2 x2 + 1 .5x3 2x1 + 1 .5x2 + 0 .5x3 x1, x2, x3 6.3 Simplex tableaus Initial tableau: s1 = s2 = s2 = 0 48 20 8 s1 s2 s3 0 0 0 1 1 1 6 -48 20 8 Slide 19 ≤ 48 ≤ 20 ≤ 8 ≥ 0 x1 -60 8 4 2 x2 -30 6 2 1.5 x3 -20 1 1.5 0.5 Slide 20Final tableau: s1 = x3 = x1 = s1 s2 s3 x1 x2 x3 280 0 10 10 0 5 0 24 1 2 -8 0 -2 0 8 0 2 -4 0 -2 1 2 0 -0.5 1.5 1 1.25 0 6.4 Information in tableaus Slide 21 • What is B?   1 1 8 B =  0 1.5 4  0 0.5 2 • What is B−1?   1 2 −8 B−1 =  0 2 −4  0 −0.5 1.5 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 …