Sensitivity analysis

See the course about the simplex in PDF

When the optimal basic solution of the linear problem is analyzed to answer questions about changes in its formulation, the study is called sensitivity analysis.

Post-optimization is the set of techniques that make it possible to obtain the optimum of the LP problem when some data have been modified.

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

LP

This study can be motivated by several reasons:

  • the problem data is not known exactly, in which case it is important to determine how data affect the proposed solution;
  • we want to evaluate the consequences of a change of policy that would modify the data of the problem.
This course will not give a formal mathematical explanation. Marginal, reduced costs and sensitivity analysis can be obtained by many software programs when solving the simplex. We will only give examples to understand their usefulness.

Marginal costs

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

If the problem is to transform goods to sell a production with a better profit and the maximum increase in income that results from the possibility of having an additional unit of one of the goods, is the marginal value of that good . Very often, the term marginal cost is also used here.

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

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

On the other hand, if a slack variable is zero in the optimal solution is that the corresponding property is fully utilized. Subsequently, a change in availability will generally have an influence on income. That is why this slack variable (equals to zero) 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.

simplexe3

with as solution vector x* = (2,6).

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

Study 1: Variation in the objective function

We want to examine how the optimal solution changes as the coefficient of a variable in the objective function varies. To change cj is to change 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 remains itself optimal on another interval. We can thus highlight a finite number of intervals of variation for cj, with on each of them an invariant solution.

LP2

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

Let’s change the objective function by max z’ =4*x1 + 5*x2. The value of the objective function will change by x*1 = 2, while the solution vector will not be modified as shown by the graphic resolution:

simplexe6

Similarly, if c1 goes from 3 to 2, only the value of the objective function will be modified. To calculate the interval over which the coefficient x*1 is valid, we must change 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 stresses for the solution vector s*:

  • z = c1*x1 + 5*x2 et 2*x2 = 12 thus -c1/5 = 0, c1 = 0;
  • z = c1*x1 + 5*x2 et 3*x1 + 2*x2 = 18 thus -c1/5 = -3/2, c1 =15/2.

The solution x*1 is valid for a coefficient c1 from 0 to 15/2.

Study 2: variation in the second member

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 the optimal value of the objective function either. This is obvious since the optimal solution not checking with equality constraint, can be varied (a little) the second member without « touching » the optimal solution.

On the other hand, if the constraint was checked with equality at the optimum, we have a range of variation for the second member such as:

  • The solution changes but the null variables remain null 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 ui*di, therefore proportional to di.
The coefficient of proportionality is called marginal variation or dual cost or marginal profit. The dual cost ui is equal to the change in the optimum value of the objective function when the second member increases by one.

If we go out of the gap, we have a new dual cost. It is thus possible to highlight a finite number of variation intervals 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.

LP3

Consider in the example that b1=4 becomes b’1=5. Let’s make a graphical resolution of the new problem:

simplexe4

The evolution of this second member did not change 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*1 is zero: z’* – z* = y*1 = 0.

What about the decrease of b1? As the explanation for marginal costs explains, the decrease of 1 in the second member leads to a decrease in the value of the objective function by an amount equal to the marginal cost. So the decrease of 1 will not result in a change.

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

Consider now an increase of the third second member to b’3 = 19. Since the marginal cost is not zero, the optimal solution will be modified as shown in the graphical resolution.

simplexe5

We can interpret the marginal cost as: the decrease or loss of a unit of the third second member will result in an evolution of y*3 of the value of the objective function over an interval b3 between 12 and 24.

Study 3: Variation of non-basic variables

The reduced cost of the non-base variable xj, noted d, measures the increase in the objective function by increasing the value of the non-base variable by one. The reduced cost dj is the opposite of the coefficient of the variable in the objective line.

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

simplexe7

We have the following reduced cost: d3 = -2. This means that building a unit of x3 would decrease the value of the objective function by 2 (since it is off base x*3 = 0).

Let’s check by calculation: set x3 to 1. We obtain the following three inequalities: x1 ≤ 3; 2*x2 ≤ 10; 3*x1 + 2*x2 ≤ 15. The vector (5/3, 5) is a solution. We thus have an evolution of x1 of 5/3 – 2 = -1/3 and x2 = 5 -6 = -1 in the objective function (new value – old value). Its cost therefore changes from -1/3*c1 – 1*c2 + 1*c3 = -2 (1*c3 because we go from a production of 0 to 1). We find the value of the reduced cost of x3.
For x3 to become profitable, its cost must increase at least the opposite of its reduced cost.
 

 

Publicités