Post-optimal sensitivity analysis

Contents

When the basic fix optimal of the PL problem is analyzed to answer questions about changes in its formulation, the study is called post-optimal sensitivity analysis.

We call post-optimization all the techniques making it possible to obtain the optimum of the PL problem when certain data have undergone modifications.

We consider the problem of linear programming general in its stand art form:

This study can be motivated by several reasons:

the data of the problem is not known with exactitude, in which case it is important to determine to what extent this affects the proposed solution;
we want to assess the consequences of a policy change that would modify the facts of the problem.

Marginal costs

The marginal cost of a good is called the minimum increase in expenditure, compared to the optimal solution, which would result from the use of an additional unit of this good, when the problem posed consists of producing goods at the lowest cost.

If the problem posed consists in transforming goods to sell a production with a better profit and the maximum increase in income which results from the possibility of having an additional unit of one of the goods, is the marginal value of this good . Very often, the qualifier marginal cost is also used in this case.

The marginal costs y * are therefore the net effects associated with the gap variables, since it is these variables that determine the surpluses (or shortages) of goods. These are the values of the variables in the Z line.

If a difference variable is not zero, in the optimal solution, it means that the corresponding good is already surplus. Therefore, having an additional unit of this good will have no influence on the income. The slack variable has zero marginal value.

On the other hand, if a variance variable is zero in the optimal solution, it is because the corresponding good is totally used. Subsequently, a variation in availability will generally have an influence on income. This is why this zero deviation variable in the optimal solution has a non-zero marginal value, and this marginal value specifies the variation of the economic function resulting from the use of an additional unit of the associated good.

with the solution vector x* = (2,6). Be careful here the line shows the value of Z and not -Z (hence the positive values).

We can measure the sensitivity of the optimal solution to a change in a line term or a coefficient in the objective.

Study 1: variation in objective function

We want to examine how the optimal solution varies when the coefficient of one of the variables in the objective function varies. Modify the c_j is equivalent to modifying the slope of the objective function.

The variation of a coefficient in the objective function over a certain interval does not lead to a modification of the optimal solution. Outside this interval, we have a new solution which itself remains optimal on another interval. We can thus highlight a finite number of variation intervals for c_j, with on each of them an invariant solution.

The value of the j-th variable at the optimum x*_j measures the increase in the objective function if the unit cost c is increased by one unit_j. Logical and trivial behavior since the objective function is composed of the sum of c_j* x_j.

Let's change the objective function by max z' =4*x₁ + 5 * x₂. The value of the objective function will change by x *₁ = 2, while the solution vector will not be modified as shown in graphics resolution :

Likewise if c₁ goes from 3 to 2, only the value of the objective function will be modified. To calculate the interval over which the coefficient x*₁ is valid, we need to scale the objective function until it is parallel to the other constraints.

That is, when the slope of the objective function is equal to the slope of the saturated constraints for the solution vector s*:

z = c₁* x₁ + 5 * x₂ and 2 * x₂ = 12 so -c₁/ 5 = 0, c₁ = 0;
z = c₁* x₁ + 5 * x₂ and 3 * x₁ + 2 * x₂ = 18 so -c₁/ 5 = -3/2, c₁ =15/2.

The coefficient x *₁ is therefore valid for c₁ between 0 and 15/2.

When the problem is large, it is possible to calculate the cost variation using the simplex by adding a delta on the cost to vary as in the following example:

The solution remains optimal as long as the line of -Z has negative numbers so if:

Study 2: variation in the second limb

When the second member of a constraint varies (in a certain interval), if this constraint was not saturated, then the solution does not change and neither does the optimal value of the objective function. This result is obvious since the optimal solution does not satisfy the constraint with equality, we can vary (a little) the second member without “touching” the optimal solution.

On the other hand, if the constraint were checked with equality with the optimum, one has an interval of variation for the second member such as:

The solution changes but the zero variables remain zero and the non-zero variables remain non-zero: the structure of the solution does not change.
The variation of the second member i causes a variation of the optimal value of the objective function equal to u_i* d_i, therefore proportional to d_i.

The coefficient of proportionality is called marginal variation or dual cost or marginal profit. The dual cost u_i is equal to the variation of the optimal value of the objective function when the second member increases by one unit.

If we leave the interval, we have a new dual cost. We can thus highlight a finite number of intervals of variation for the second member with, on each of them, a value for the dual cost. On the different intervals, the sensitivity analysis does not give the optimal solution since the numerical values of the variables depend on the exact value of the second member.

Consider in the example that b₁ =4 becomes b'₁ = 5. Let's perform a graphic resolution of the new problem:

The evolution of this second member has not modified the optimal solution, the value of the objective function does not change. It was easy to predict this change because the marginal cost of the slack variable y*₁ is zero: z'* – z* = y*₁ = 0.

When is the decrease in b₁ ? As the explanation on marginal costs explains, decreasing the second member by 1 causes the value of the objective function to decrease by an amount equal to marginal cost. So the decrease of 1 will not lead to modification.

To know the possibilities of evolution of the stock without changing the value of the optimal solution, it is necessary to add a delta in the second member studied as shown in the following example:

The solution remains optimal as long as the simplex is not degenerate, that is to say that the second member is positive:

The increase and decrease do not change the value of the objective function over a small interval, but if b₁ is less than 2, we see on the graphical resolution that the optimal solution will be changed. The validity interval of y*₁ = 0 is therefore for b₁ between 2 and infinity.

Now consider an augmentation of the third right hand side to b'₃ = 19. Since the marginal cost is not zero, the optimal solution will be modified as shown in the graphical resolution.

We can therefore interpret the marginal cost by: the decrease or loss of one unit of the third second member will cause y* to change₃ of the value of the objective function over an interval b₃ comprised between 12 and 24.

Study 3: variation of non-base variables

The reduced cost of the non-base variable x_j, denoted by_j, measures the increase in the objective function if the value of the non-base variable is increased by one unit. The reduced cost of_j is the opposite of the coefficient of the variable in the goal line Z.

The optimal solution will not change until the cost of the non-base variable is better than the optimal value of the objective function (so if the coefficient is between -infinity and Z for a maximization problem).

Let's go back to the previous example with a new constraint and a new variable:

We have the following reduced cost: d₃ = -2. This means that to build a unit of x₃ would decrease the value of the objective function by 2 (since it is out of basis x*₃ = 0).

Let's check by calculation: fix x₃ to 1. We obtain the following three inequalities: x₁ ≤ 3; 2 * x₂ ≤ 10; 3 * x₁ + 2 * x₂ ≤ 15. The vector (5/3, 5) is solution of the system. We therefore have an evolution of x₁ of 5/3 – 2 = -1/3 and x₂ = 5 -6 = -1 in the objective function (new value – old value). Its cost therefore changes by -1/3*c₁ - 1 C₂ + 1 * c₃ = -2 (1 * c₃ because we go from a production of 0 to 1). We find the value of the cost reduced by x₃.

So that x₃ becomes profitable, its cost must increase at least the opposite of its reduced cost.

Study 4: variation in production

If the value has_ij changes in a saturated constraint, then neither the optimal solution nor the optimal value is kept.

If the value has_ij changes in an unsaturated constraint and a base variable, then the value can vary between + or – infinity (depending on a min or max) to S_i/ x *_i. with S_i the slack variable.

Indeed by adding a delta variable in the cost of the variable based on the targeted constraint then it suffices to inject the optimal vector and solve the equation as in the following example:

If the value has_ij changes in any constraint and an off-base variable, then only a negative variation (in the case of a max) can make the product viable in this constraint. It is then necessary to solve the simplex by incorporating the delta and to verify its various criteria of optimality.