Operations Research/Sensitivity analysis

Sensitivity Analysis deals with finding out the amount by which we can change the input data for the output of our linear programming model to remain comparatively unchanged. This helps us in determining the sensitivity of the data we supply for the problem. If a small change in the input (for example in the change in the availability of some raw material) produces a large change in the optimal solution for some model, and a corresponding small change in the input for some other model doesn't affect its optimal solution as much, we can conclude that the second problem is more robust than the first. The second model is less sensitive to the changes in the input data

We will consider the case of sensitivity of the optimum solution to changes in the availability of the resources. (Right hand side of the constraints.)

If in any linear programming problem there are n variables and m constraints we can think as the right hand sides as being the representatives of the amount of resources. For example, consider our old chemical company model:

Maximize z = $5x_{1}+4x_{2}$

subject to,

$6x_{1}+4x_{2}\leq 24$ ,

$x_{1}+2x_{2}\leq 6$ ,

$x_{2}-x_{1}\leq 1$ ,

$x_{2}\leq 2$ ,

$x_{1},x_{2}\geq 0$ .

The right hand sides represented various resources: the amount of raw materials 1 and 2, the market limit, and the daily demand. Now if these right hand sides were changed the whole problem would change. Suppose we want to know is the worth of any particular resource. More precisely, we want to know how much is the amount of the first raw material being 24 units available really important. If we increase the amount from 24 to 25 our optimal value changes to 21.75, whereas previously it was 21. So a unit increase in the amount of the first resource changes the optimal value (which is the total profit) by 0.75. This can be therefore thought of as the unit worth of the first resource. The technical term for this is the first resources' shadow price.

Determination of shadow prices

To determine the shadow prices for the resources individually by increasing them one by one and solving the associated linear models is extremely inefficient. Let us examine another way of calculating the shadow prices.

Consider the following linear system:

Maximize z = $3x_{1}+2x_{2}+5x_{3}$

subject to,

$x_{1}+2x_{2}+x_{3}\leq 430$ ,

$3x_{1}+2x_{3}\leq 460$ ,

$x_{1}+4x_{2}\leq 420$ ,

$x_{1},x_{2},x_{3}\geq 0$ .

The optimal simplex table with slack variables $x_{4},x_{5},x_{6}$ is:

Basic	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$x_{5}$	$x_{6}$	BFS
z	4	0	0	1	2	0	1350
$x_{2}$	${\frac {-1}{4}}$	1	0	${\frac {1}{2}}$	${\frac {-1}{4}}$	0	100
$x_{3}$	${\frac {3}{2}}$	0	1	0	${\frac {1}{2}}$	0	230
$x_{6}$	2	0	0	-2	1	1	20

Now to find out the shadow prices write the above model's standard form as follows:

$x_{1}+2x_{2}+x_{3}=430-x_{4}$ ,

$3x_{1}+2x_{3}=460-x_{5}$ ,

$x_{1}+4x_{2}=420-x_{6}$ .

If resource 1 is increased by one unit it means that the first slack variable is decreased by one unit so that the equality between the left and the right hand sides remains unchanged. A similar thing holds for all other resources as well.

From the optimal simplex table we have the following constraint:

$z+4x_{1}+x_{4}+2x_{5}+0x_{6}=1350$ .

This can be rewritten as:

$z=1350-4x_{1}+1(-x_{4})+2(-x_{5})+0(-x_{6})=1350$ .

Given that a decrease in the value of a slack variable is equivalent to an increase in its resource, we get

$z=1350-4x_{1}$ +1(increase in resource 1)+2(increase in resource 2)+0(increase in resource 3)=1350

Thus we can see that:

A one unit increase in resource 1 increases z by 1
A one unit increase in resource 2 increases z by 2
A one unit increase in resource 3 increases z by 0

Thus the shadow prices are 1, 2 and 0 respectively.