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:

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.**

**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

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.

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

_{j}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 c_{j}, with on each of them an invariant solution.

_{j}measures the increase in the objective function if the unit cost c

_{j}is increased by one unit. 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_{1} + 5*x_{2}. 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:

Similarly, if c_{1} 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 = c
_{1}*x_{1}+ 5*x_{2}et 2*x_{2}= 12 thus -c_{1}/5 = 0, c_{1}= 0; - z = c
_{1}*x_{1}+ 5*x_{2}et 3*x_{1}+ 2*x_{2}= 18 thus -c_{1}/5 = -3/2, c_{1}=15/2.

The solution x*_{1} is valid for a coefficient c_{1} 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 u
_{i}*d_{i}, therefore proportional to d_{i}.

_{i}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.

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

_{1}is zero: z’* – z* = y*

_{1}= 0.

What about the decrease of b_{1}? 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.

_{1}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 b

_{1}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.

_{3}of the value of the objective function over an interval b

_{3}between 12 and 24.

## Study 3: Variation of non-basic variables

_{j}, noted d, measures the increase in the objective function by increasing the value of the non-base variable by one. The reduced cost d

_{j}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:

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

_{3}to 1. We obtain the following three inequalities: x

_{1}≤ 3; 2*x

_{2}≤ 10; 3*x

_{1}+ 2*x

_{2}≤ 15. The vector (5/3, 5) is a solution. We thus have an evolution of x

_{1}of 5/3 – 2 = -1/3 and x

_{2}= 5 -6 = -1 in the objective function (new value – old value). Its cost therefore changes from -1/3*c

_{1}– 1*c

_{2}+ 1*c

_{3}= -2 (1*c

_{3}because we go from a production of 0 to 1). We find the value of the reduced cost of x

_{3}.

_{3}to become profitable, its cost must increase at least the opposite of its reduced cost.