University:
University of California, Berkeley
Course:
MATH 56 Linear Algebra
Academic year:

2019
Views:

336

Pages:

14
Author:

StellarSymphony

Sensitivity, IP Overview Sensitivity analysis Integer Linear Programming Review Writing Logic Statements Examples Job Scheduling Problem Plan for a move Terminology ▶ Shadow price yi = Dual variable Change of the objective function from one unit increase in its right-hand side bi ▶ Reduced cost rj = Dual slack = (c⊤ − y⊤ A)j Amount by which the cost coefficient of non-basic variable cj must be lowered for that variable to become basic ▶ Allowable increase/decrease P ▶ Optimal solution x ∗ and objective nj=1 cj xj∗ may change ▶ Whether a decision variable is basic or non-basic stays unchanged ▶ Whether a constraint is binding or non-binding stays unchanged Terminology For a problem in symmetrical form, let (x̄, ȳ) be primal-dual feasible point satisfying complementary slackness. Let s̄ be corresponding primal slack and r̄ be corresponding dual slack. ▶ Decision variable x̄j is basic if x̄j ̸= 0 (¯ rj = 0 due to CS) ▶ Decision variable x̄j is non-basic if x̄j = 0 (¯ rj < 0 in general) P P ▶ Constraint nj=1 aij xj ≥ bi is binding if nj=1 aij x̄j = bi (s̄i = 0) P P ▶ Constraint nj=1 aij xj ≥ bi is not binding if nj=1 aij x̄j > bi (ȳi = 0 due to CS) Example: continuous knapsack AMPL notation ▶ x – primal variable; ▶ x.rc – reduced cost or dual slack; ▶ x.current – objective coefficients (ci ); ▶ conname – shadow price or dual variable; ▶ con.slack – primal slack; ▶ con.current – right hand side (bj ); ▶ ...down and ...up are the minimal and the maximal value of the corresponding parameter ci or bj such that the problem stays within the allowable increase/decrease range How to derive sensitivity analysis: Key Idea In order for a change to be withing the allowable range, both of these must be true at the solution point: ▶ Whether a decision variable is basic or non-basic stays unchanged. ▶ Whether a constraint is binding or non-binding stays unchanged. Types of analysis ▶ Case 1: Change bi ▶ Case 1a: Change bi of non-binding constraint ▶ Case 1b: Change bi of binding constraint ▶ Case 1c: Find g if Case 1b. ▶ Case 2: Change cj ▶ Case 2a: Change cj of non-basic variable ▶ Case 2b: Change cj of basic variable ▶ Case 3: Change aij ▶ Case 3a: Change aij of non-basic variable ▶ Case 3b: Change aij of basic variable ▶ Case 4: Add a new constraint ▶ Case 5: Add a new decision variable Case 2a: Change cj of non-basic variable Change cj of non-basic variable ▶ Reduced cost rj ̸= 0 1 rj = cj − m X aij yi i=1 ▶ Consider c3 which has reduced cost r3 = −0.4 ▶ Allowable increase: −rj = 0.4 ▶ Allowable decrease: +∞ ▶ Consider changing c3 from 2 to 2.1 ▶ New optimal solution: Unchanged ▶ New optimal objective value: Unchanged ▶ It’s possible to change several cj for non-basics variables at the same time! 1 rj = 0 for non-basic variable means multiple optimal solutions Case 2b: Change cj of basic variable Change cj of basic variable max 24x1 +(5 + δ)x2 +2x3 +3x4 s.t. 3x1 +8x2 +14x3 +6x4 20x1 +10x2 +2x3 +15x4 x2 x1 x2 x3 x4 ≤ ≤ ≥ ≥ ≥ ≥ ≥ 60 100 5 0 0 0 0 Case 2b: Change cj of basic variable Consider the Dual problem: min 60y1 +100y2 +5y3 s.t. 3y1 +20y2 8y1 +10y2 +y3 14y1 +2y2 6y1 +15y2 y1 y2 y3 ≥ ≥ ≥ ≥ ≥ ≥ ≤ Optimal solution y1 = 0, y2 = 1.2, y3 = −7 24 5+δ 2 3 0 0 0 (1) (2) (3) (4) (5) (6) (7) Case 2b: Change cj of basic variable min s.t. +100y2 +5y3 +20y2 +10y2 +y3 +2y2 +15y2 y2 y3 = = ≥ ≥ ≥ ≤ 24 5+δ 2 3 0 0 (1) (2) (3) (4) (6) (7) Case 2b: Change cj of basic variable From (1) we get y2 = 24 20 (satisfies (3), (4), (6)), substitute in (2) y3 = −7 + δ. From (7) δ≤7 Case 2b: Change cj of basic variable Change cj of basic variable ▶ Reduced cost rj = 0 ▶ Consider c2 ▶ Allowable increase: 7 ▶ Allowable decrease: +∞ ▶ Consider changing c2 from 5 → 10 ▶ New optimal solution: Unchanged ▶ New optimal objective value: n X j=1 cjnew xj∗ = n X j=1 cj xj∗ + δx2∗ = 110