Sensitivity Analysis

Question 1

How to change the cost vector cₖ->cₖ’ where xₖ is a non-basic variable

Answer 1

(z is unchanged)
when j=k
if cₖ’≥cₖ then zₖ-cₖ≤0 so the solution remains optimal
if zₖ-cₖ>0 then introduce xₖ into the basis by running simplex until optimal

Question 2

How to change the cost vector cₖ->cₖ’ where xₖ is a basic variable

Answer 2

(z is changed)
1. calculate cₖ’-cₖ
2. calculate z’ⱼ-cⱼ = zⱼ-cⱼ+(cᵢₖ-cᵢₖ’)yᵢₖ for all j!=k
3. for j=k z’ⱼ-cⱼ’=0
4. The new objective function is given by
cb’B-¹b=cbᵀB-¹b +(zₖ-cₖ)b*ₖ
5. write up new tableu and run simplex until optimal

Question 3

z’ⱼ-cⱼ =

after replacing the cost vector xₖ is basic

Answer 3

z’ⱼ-cⱼ = zⱼ-cⱼ+(cᵢₖ-cᵢₖ’)yᵢₖ

Question 4

z’ⱼ-cⱼ’

after replacing the cost vector xₖ is basic

Answer 4

z’ⱼ-cⱼ’=0

Question 5

cb’B-¹b=

after replacing the cost vector xₖ is basic

Answer 5

cb’B-¹b=cbᵀB-¹b +(zₖ-cₖ)b*ₖ

Question 6

How to change the RHS vector b->b’

Answer 6

• > if one of the components of B-¹b’ is negative the current basis B is infeasible => dual problem is unbound => changed problem is infeasible
• > if B-¹b’>0 the current basis remains optimal. The new optimal value is given by cbB-¹b’

Question 7

How to add a new activity

adds a new variable with a new cost, determines if it is worthwhile to add the variable

Answer 7

1. calculate zₙ+₁+cₙ+₁
2. if zₙ+₁ - cₙ+₁ ≤ 0 then no new rows are added => the original solution is optimal
3. if zₙ+₁ - cₙ+₁ >0 then introduce xₙ+₁ into the basis
   - add an xₙ+₁ column to the tableu (zero row = -(zₙ+₁+cₙ+₁) other rows are yₙ+₁=B-¹aₙ+₁
   - run simplex until optimal

Question 8

How to add a new constraint

aᵐ+¹x≥bₘ+₁

Answer 8

1. introduce a slack to put into standard form
2. add a new row and column for xₘ+₁ (column is 0,…,0,1 row is abᵐ+¹ , anᵐ+¹)
3. restore any unit vector columns xₘ+₁ |-> xₘ+₁ + (-k)xb
4. apply dual simplex method until RHA column are all positive (except objective value).