Sensitivity analysis

Question 1

Why do we care about sensitivity analysis?

Answer 1

It is very common for problem information to change after the original problem has been formulated. In order to gain quick access to cases where we change minor things about hte problem, we use sensitivity analysis rather than solving the entire problem again.

Also, using sensitivity analysis gives us GREAT insight into how our optimal solution look like. What constraints are most important, etc.

Finally, there is often great UNCERTAINTY in the parameters we use as input. For instance, demand constraints. By using sensitivity analysis, we can gain an understanding in how conclusive our solution is.

Question 2

There are some “questions” we typically have that we consider as part of sensitvity analyssi. Elaborate

Answer 2

1) Changes made to an objective function coefficient

2) Changes made RHS coefficient

3) Change in constraint coefficient

4) Add or remove a constraint

5) add or remove a variable

Question 3

Given the questions, what are we actually itnerested in figuring out, like what response from those changes are we looking for?

Answer 3

1) How is the objective function value affected by the change

2) Is the current solution still optimal after the change? is it still feasible?

3) At what change will another basic solution be optimal?

4) At what change will the current basic solution become infeasible?

Question 4

What is relaxation

Answer 4

Relaxation refer to making the feasible region larger

Question 5

Restriction

Answer 5

Making the feasible region smaller

Question 6

If a problem is relaxed, what can we say about the objective function value?

Answer 6

It will become better or remain the same. It will never be worse

Question 7

if we change RHS value, is this relaxation or restriction?

Answer 7

Depends on the direction and the constraint.

if we increase the value of RHS coefficient in a <= constraint, we relax the problem.

Question 8

elaborate on changing constraint coefficients in terms of relaxation or restriction

Answer 8

Again, it depends on the direction and the type of constraint. In general, changing such a coefficient is analoguous to changing RHS value in the same constraint. If we make LHS value larger, and the constraint is <=, then we are restrictign the problem.

Question 9

Define shadow price

Answer 9

The shadow price for a constraint is given by the change in objective function value when making a marginal increase in the RHS.

So, a shadow price is connected to a specific constraint, and is determined by how a change in its RHS (b coefficient) ill affect the objective function value.

Question 10

Other names for shadow price

Answer 10

Dual price, dual value, marginal price

Question 11

What is the relationship between the dual and primal problem

Answer 11

For every LP problem, there is a dual problem. There is a dual variable for every constraint in the primal problem. The shadow price is the optimal value to this dual variable in the optimal oslution.

Question 12

What can we say about shadow prices and ocnstraints in tregards to changing the optimal objective function value?

Answer 12

Only constraints that are active/binding in the optimal solution can affect the objective function value. This means that only these shadow prices will have non-zero values.

One has to understand that a shadow price tell us how the objective function is affected by changing the RHS of a constraint. Either relaxing it, or constraining it. If the constraint is not binding, then this change makes no difference to the objective function value (for small marginal steps).

Question 13

Given a shadow price, what stops us from multipliying it with the size of the change, and find the total change in obj func val?

Answer 13

The shadow price is only constant in a certain neighborhood. We need to find the interval where the shadow price remains constant.

Question 14

Recall that feasability requirement for xb on matrix notation AND its optimality condition

Answer 14

xb = B^(-1)b >= 0

It is optimal if the reduced costs are larger than 0 (min problem) or smaller than zero (max problem). Recall how simplex tableau adds another flipped sign on top of this.

cn-bar = cn - cbB^(-1)N >= 0 (min problem)

Question 15

why is the matrix notation for reduced costs in optimal tableau so important?

Answer 15

It tells us how the solution is defined from input variables.

We have the b vector, the cn, cb, N, and the inverse of B.

So, we actually need two identitites:
1) The xb = B^(-1)b >= 0
2) reduced cost

given these two, we can evaluate how changes to the input parameters affect the optimal solution

for these two, it is basically about whether the solution still remains optimal, or whether it still remains feasible.

Question 16

Elaborate on how we treat cases where the constraint is >= iun regards to the optimal tableau matrix notaiton

Answer 16

The signs must be flipped. Meaning, the signs that occur in the optimal tableau are not the correct ones in terms of finding hte matrices and identitites we need for the sensitivity analysis. Therefore, when we construct the intermediary matrices and identities, we flip the signs.

Question 17

How does changing something in b affect the optimal solution?

Answer 17

Considering how the reduced costs determine if we need to change a solution or not, and the fact that the reduced costs does not include the b term, we know that changing basis is not the question when we consider changing RHS cvoefficents.

however, feasibility is the core issue here.el

Question 18

elaborate on changing a RHS coefficnet

Answer 18

The question we ask is:
“Witihn which interval can a RHS coefficient vary in order for the current basic solution to stay feasible?”.

So, we are looking at the interval where we can relax or resrtrict the constraint within making the current optimal solution infeasible.

When we talk about “current optimal solution” we are referring to which variables we have in the basis.

This is easily understood by considering what happens if we relax the constraint infinitely much, and look at what happens with the problem. if there are other constraints included in the problem, one of them will take over as the most restrictive constraint, and from this point on the constraint we relaxed serve no impact anymore. At this point, a different set of constraints is involved, which means that we have a different set of non basic and basic variables.

We use the delta approach to compute the interval (along with the feasibility requirement):

xb = B^(-1)(b + ∆b) >= 0

xb = B^(-1)b + B^(-1)∆b >= 0

B^(-1)b + B^(-1)∆b >= 0

B^(-1)b is a constant vector, and is the b vector values in the optimal tableau.

B^(-1) is the salck portion of the tableau in fnal tab.
the ∆b is a vector, and we typically look at only one change at a time. Therefore, this vector can look like this:

(∆b1, 0, 0, 0)^T

Some other case can look like this:

(0, 0, ∆b3, 0)^T

When we use the infeasibility thing, we get some equations that must be satisfied for ∆bi, and then we add the original bi value, to find the interval for bi that keeps the same basis as optimal.

What is the value of this?
in this interval, the shadow price remains constant.

Question 19

How is the feasible region affected by a change in objective function coefficients?

What is the implicaiton of this?

Answer 19

The feasible region is not affected

the implication of this is that we cannot change objective function coefficients and suddenly get an infeasible solution.

Question 20

What is the question we ask in regards to changing objectivie function coefficniets?

Answer 20

Within which interval can an objective function coefficient vary in order for the current optimal solution to remain optimal?

Question 21

if the change in an objective function coeffciient is too large, how is this represented on the tableau?

Answer 21

We basically get reduced costs that change their signs. The sign of at least on reduced cost will indicate that the corresponding variable can enter the basis and improve the objective function value. Hence, another basic solution becomes optimal.

Question 22

how do we look into the interval for legal objective function coefficeints?

Answer 22

Firstly, we use deltas: ∆cn, and ∆cb.

We know the reduced costs are given as:

cn - cb B^(-1)N

So we add the deltas:

cn-bar = (cn + ∆cn) - (cb + ∆cb)B^(-1)N

The requirement for optimality is that this must be greater than 0 for minimization problems, and less than 0 for maximization problems.

Note how a change to a nonbasic coefficient will make a small impact, while a change to a basic coefficent will change the entire row of reduced costs.

Question 23

elaborate on adding a new variable

Answer 23

The question is whether the new variable is basic or non-basic.

If it becomes non-basic, we’re good and dont have to do anything.

We compute its reduced cost by using the formula:

ck-bar = ck - cb B^(-1) ak

where ak is the vector corresponding to the constraint column of this variable. ck refer to the variable’s contribution to the objective.

If the reduced cost for this variable becomes (depending on the type of problem) so that the newly added variable becomes the entering basic variable, we are “fucked”, and need to continue solving the problem. If not, we know that the variable is non-basic in optimal solution.