Sensitivity analysis of LP

Question 1

In terms of LP there are 5 questions we might ask in regards to sensitibvity analysis, name them

Answer 1

1) changes in objective funciton coefficients
2) Changes in RHS b-values
3) Changes in technology coefficients aij
4) Adding/removing a variable
5) Adding/removing a constraint

Question 2

What are the interesting questions we might ask ourselves?

Answer 2

How is the objective function value affected by a change? It is common to model profits, so naturally the change in profits is interesting.

is the current solution still optimal after a change? is it still feasible?

At what change will another solution be optimal?

At what change will the current solution become infeasible?

Question 3

Define relaxation

Answer 3

A relaxation is a modification of a problem instance that makes the feasible set LARGER.

Question 4

what happens to the obj function value if we relax a constraint?

Answer 4

The value will be better or equal, never worse.

Question 5

Define restriction

Answer 5

A restriction is a modification to a problem that decrease the feasible set.

Question 6

Is there a difference between constraint types and relaxation/restriction in terms of changing RHS value?

Answer 6

YES.

<=: increase RHS is relaxation, decrease RHS is restriction

> =: increase RHS is restriction, decrease RHS is relaxation

Question 7

Consider changing a technology coefficient aij, what can we say about relaxation vs restriction?

Answer 7

Recall that relaxation/restriction is all about what happens to the feasible region.

<= : increasing aij cause LHS to be larger, which has the same effect as reducing the RHS, which means that it is a restriction. decreasing it will cause a relaxation. We can consider aij as the cost of tech.

> = : increasing aij has the same effect as reducing RHS, which will cause a relaxation since the feasible set grows. opposite for the opposite case.

Question 8

if we add a variable, is it relaxation or restriction?

Answer 8

Adding a variable means adding a dimension. Adding a dimensions means that the set of feasible solutions grow, which means that adding a variable is a relaxation.

Question 9

if we add a constraint, is it a relaxation or restriction?

Answer 9

Restriction (might cause, might not).

Question 10

Define shadow price

Answer 10

A shadow price is associated with a constraint, and is given by the change in objective function that follows from making a marginal change in the RHS value of the corresponding constraint. Specifically: increase.

Question 11

Other name for shadow price?

Answer 11

dual value.

Marginal price.

Dual price.

Question 12

What is the dual variable

Answer 12

dual variable is the optimal value of the dual problem. More specifically, the dual problem has a set of variables, and these are the shadow prices.

Question 13

Elaborate on dual variable and signs

Answer 13

The sign of the dual variable, and therefore the shadow price, depends on whether and increase in RHS will lead to a relaxation or a restriction of the feasible region.

if we have an equality, we can not intuitively tell how the objective function will be affected and consequently which sign the corresponding dual variable will get.

However, if the constraint is inequality, the dual variable will be either non positive or non negative.

Question 14

What happens if a dual variable has value equal to 0?

Answer 14

A dual value of 0 indicates that nothing happens if we relax the constraint. this means that the constraint is not binding/active in the current solution.

Question 15

Elaborate on changing RHS coefficient

Answer 15

The central question in sensitivity analysis of changing RHS values (constraints) is “within what interval can the RHS be changed while maintaining the current optimal basis feasible and optimal?”

Changing RHS values correspond to relaxing or restricting constraints. One can then consider a change in RHS value as shifting the constraint inward or outward, and imagine how the optimal point/solution will change along the moving intersection between the constraint we change and the other fixed constraints.
At some point, we may get to the point where relaxing the constraint even more makes the constraint irrelevant because the solution/feasible region is restricted by other constraints. Similarily, we may reach a point where restricting the constraint even more will actually make the corresponding variable value be illegal, negative. It is these points (interval) that we want to capture in this kind of sensitivity analysis.

There are2 things we use:
1) x_b = B^(-1)(b + ∆b)
x_b = B^(-1)b + B^(-1)∆b

2) x_b >= 0

Regarding 1), the first part we actually have from the current (final) tableau as the RHS values.
The second part we need to calculate, but is easily calculated from the final tableau since it only requires B^(-1), which is the slack portion. ∆b are the changes we wish to make, and is typically a vector with all zeros except for the one RHS value we are interested in (meaning the constraint we are interesting in relaxing/restricting).

When we solve for x_b, the result is a vector of expressions. Some of these expressions will contain the ∆bi value as a variable. We will now use all of these expressions, along with the fact that feasibility requires x_b >= 0, to find the range of ∆bi that is legal.
Finally, it is typical to add the current optimal b-value to this result, so that the interval-result we get is the entire interval of legal b-values that will still have this current solution as feasible (referencing the current basis).

The result can look like this:
187.5 <= b1 <= 262.5

Of course, changing b will change z-value, as the values of the decision variables will change from relaxation/restriction inside of this interval. Therefore, we must also update z-values in the case where this is necessary.

Important fact to add regarding this interval: It is the interval where the shadow price of the corresponding constraint remains constant.

Question 16

When changing an objective function coefficient, what is affected?

Answer 16

Reduced costs are affected. It is also important to understand that doing something to the coefficients in the objective function will not change the constraints in any way, which means that the feasible region remains the same. This implies that whatever solution we had, will remain FEASIBLE through any change in any of the c’s.

The question is not about the feasible region, but rather about what changes we can make to the c-value while still keeping the current basic solution OPTIMAL.

Question 16

Consider changing an objective value coefficient. What is the tell-sign that a change is outside of the interval?

Answer 16

If a change is outside the interval, one of the reduced costs (at least) will get a sign that indicates that the corresponding variable can enter the basis and improve the objective function value. We do not want that, as it would mean that we are outside of the legal interval.

if it is a min problem, we want all of the c_n values to remain greater than 0.

Question 17

Elaborate on changing an objective function coefficient that is basic vs non basic

Answer 17

In the final tableau, the following equation describe the coefficients of reduced costs:

• (cn - cb B^(-1)N)

cn refer to the coefficients of the objective function variables that we selected as non basic, and the same with cb.

From the equation we can see that changing cn only leads to a change by the same amount that we change it with, and it will only affect the reduced costs of the very specific variable that it correspond to. However, changing a cb-value is more impactful as it is multiplied with the factor of B^(-1)N.

Question 18

How do we find sensitivity interval of changing an objective function coefficient?

Answer 18

We are interested in the interval that retains the current optimal solution as optimal. to find this interval, we need some inequality equations that base on infeasibility and can deliver various legal ranges.

From the matrix notation, we know that changing obj func coeff will only affect the obj row. In addition, changing a non basic variable coefficient will do very little change. However, basic variable coefficient changes affect entire row.

We use the following equation:

c = - (cn - cb B^(-1)N)

A change is symbolized like this:

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

Here we have some different parts. cn and cb we already have. B^(-1)N we have from the non-basic variable section in optimal tableau.

Calculating the equations is the first step. The second step is to solve the equations with ∆-values against the feasibility constraint. This constraint will vary based on whether the problem is a max or a min problem.

Question 19

mathematically, how is the model affected by adding another variable?

Answer 19

Say we add a variable xk to the problem. The variable xk will have an objective function coefficient ck and a constraint column ak.

Introducing this new part extends nicely, and we dont have to re-compute other parts of the optimal tableau due to how the row-vector and matrix oeprations are computed.

What we do, is solve for the coefficient of the new variable. We can find the interval that makes it NOT AFFECT the current optimal solution. This is done by including it as a non basic variable, and solving for its coefficient to see what it would need to be to not give a vlaue that makes it possible to enter the new variable in basis and improve Z:

Question 20

we add a variable xk to the model. What do we need to do?

Answer 20

Recall that adding a variable includes adding an objective function coefficient and a constraint column.

We want to calculate its reduced cost to see if the inclusion of this variable will impact the current optimal solution.

The whole point is that if the addition of this variable along with its constraint column will make its objective function row coefficient in such a way that we wont have the optimal solution anymore, we must redo.

We use the formula “ck - cbB^(-1)N”. This is the value that we are checking against the requirements that will depend on whether the problem is a max or min problem.
Then the question is: How the fuck do we find cbB^(-1)N?
First of all, we are only interested in a single column of the N matrix. Therefore, we actually end up having:
“ck - cbB^(-1)ak”, where ak is the newly added constraint column.
The entire part of cbB^(-1) is found as the shadow prices. ak is given. Then all we have to do is compute the dot product, and we have the solution.

Recall that the point is that we assume that the new variable is in fact non-basic in the optimal tableau.

For a min problem, if ck^(bar) = ck - cbB^(-1)N >= 0, the new variable does not affect the current optimal solution. If < 0, this variable will enter the basis and may improve obj function. in such case, we perform additional iterations.

Question 21

Elaborate on adding a new constraint to the mix

Answer 21

When we add a constraint, the question is whether the current optimal solution will be affected or not.

How can we test this?

We need to add the constraint row, as well as slack variable, to the system. Then we need to convert the row by performing a pivot operation so that the basic variable, which is going to be the new slack variable, is expressed as a function of only non-basic vriables.

Here is the key: after performing the row operation, we check the RHS value for the newly added slack (basic variable). If it is negative, it means that introducing this constraint to the mix made the current solution infeasible. If this is the case, we have to re-optimize. apparantely the dual simplex works great for this, as it switch between feasible and infeasible anyways, so that we dont need to re-do the entire problem.

Recall: We just added a constriant, no new decision variable. Only new slack variablem which gives ana additional variable in the basis. We want to add the restriction/constraint, convert it by a pivot operation to make it canonical, and see if the solution is feasible or not.

Question 22

why is there a difference between finding the sensitivity interval of a coefficient whose variable is basic vs non basic?

Answer 22

If we want to find the sensitivity interval for a coefficient of a variable that is NONBASIC in the current optimal tableau, we can simply take a look at the current non-basic coefficients, and add the ∆ to test: (c_n^T + ∆c_n^T) - c_b^T B^(-1)N, and make this for instance “<0” if the case is maximization problem. this is very simple, because we can make it “current coefficient in optimal tableau + ∆c_n”, which is very easy to calculate. However, if the coefficient of the variable we are interesting in actually corresponds to basic variable, we must perform more computations because of the B^(-1)N term that affects the current optimal solutions as well.