Sensitivity Analysis (Post-optimality Analysis): Linear Programming

In linear programming, all model parameters are assumed to be constant; but in real life situations, the decision environment is always dynamic.

Therefore, it is important for the management to know how profit would be affected by an increase or decrease in the resource level, by a change in the technological process, and by a change in the cost of raw materials.

Such an investigation is known as sensitivity analysis or post-optimality analysis. The results of sensitivity analysis establish upper and lower bounds for input parameter values within which they can vary without causing violent changes in the current optimal solution.

The mechanics of sensitivity testing are explained with the help of following example.

Example: Sensitivity Analysis Linear Programming

Luminous Lamps produces three types of lamps - A, B, and C. These lamps are processed on three machines - X, Y, and Z. The full technology and input restrictions are given in the following table.

Solution.

The linear programming model for this problem can stated as:

Maximize z = 12x₁ + 3x₂ + x₃

subject to

10x₁ + 2x₂ + x₃ ≤ 100
7x₁ + 3x₂ + 2x₃ ≤ 77
2x₁+ 4x₂ + x₃ ≤ 80

x₁, x₂, x₃ ≥ 0

The optimal solution to this problem is given below.

Final Table

On small screens, scroll horizontally to view full calculation

An optimal policy is x₁ =73/8, x₂ = 35/8, x₃ = 0.
The associated optimal value of the objective function is 981/8.

Changes In Contribution Rate

First we investigate whether a previously determined optimal solution remains optimal if the contribution rate is changed. An increase in c_j of a variable would mean that resources from other products should be diverted to this more profitable product. The reverse is true for a minimization problem.

Changes in c_j of a non basic variable

A non basic variable can be brought into the basis only if its contribution rate becomes attractive. Hence, we need to determine the upper limit of the profit contribution (c_j) of each non basic variable. The reverse is true for a minimization problem.

From the above final simplex table, we note that profit contribution for product C is Re 1, which is not greater than its z_j. Thus, to bring x₃ into the basis, its profit contribution rate c_j must exceed Rs. 27/16 to make z_j-c_j value negative or zero (i.e., z_j-c_j ≤ 0)

Specifically:

If c_j* - c_j > (z_j-c_j), then a new optimal solution must be derived.
If c_j* - c_j = (z_j-c_j), then alternative optimal solutions exist
If c_j* - c_j < (z_j-c_j), then current optimal solution remains unchanged.

In our case c₃ = 1 and z₃-c₃ = 11/16, then

c₃* - 1 ≥ 11/16
c₃* ≥ 11/16 + 1 = 27/16

x₃ can be introduced into the basis if its contribution rate c₃ increases upto atleast Rs. 27/16. If it increases beyond that then the current solution will no longer be optimal.

Change in c_j of a Basic Variable

Let us consider the case of product A (x₁ column), and divide each z_j-c_j entry in the index row (for non basic variable) by the corresponding coefficients in the x₁ row as shown below.

- Minimum (z_j-c_j / y_1j; y_1j > 0) ≤ Δ1 ≤ Minimum (z_j-c_j / -y_1j; y_1j < 0)

Referring to the final simplex table, we observe that corresponding to the non basic variables x₃ & x₅, y_13, y₁₅ < 0 Hence,

Use Horizontal Scrollbar to View Full Details

= Minimum (11, 3) = 3

Corresponding to the non basic variable x₄, y₁₄ > 0. Hence,

= 5

Hence,

- 5 ≤ c₁* - 12 ≤ 3, i.e., 7 ≤ c₁* ≤ 15

Thus, the optimal solution is insensitive so long as the changed profit coefficient c₁* varies between Rs. 7 and Rs. 15.

Change In Available Resources

Now we investigate whether a previous optimal solution remains feasible if the available resources change. For long-term planning it is important to know the bounds within which each available resource (e.g., machine hours) can vary without causing violent changes in the current optimal solution. To illustrate, divide each quantity in the X_B column by the corresponding coefficient in the x₄ column of table.

The least positive ratio (354/11) indicates to how the number of hours of machine M₁ can be decreased. The least negative ratio (-10) indicates to how much the number of hours of machine M₁ can be increased.

Calculating the range

Lower limit = 100 - 354/11 = 746/11
Upper Limit = 100 - (-10) = 110.

Hence, the range of hours for M₁ is 746/11 to 110. By the same way, the range of hours for Machine M₂ & M3 can be calculated.

Change In Technological Coefficients

Changes in the technological coefficients reflect potential change either in the efficiency of manpower or in the state of technology. To illustrate, x₃ is non basic in the optimal solution of this example. Consider the possibility that its coefficient in second constraint is altered by Δ. Then, the associated dual is

W₁ + (2 + Δ)W₂ + W₃ ≥ 1

Substituting the current optimal values of the dual variables from the final simplex table.
15/16 + (2 + Δ) X 3/8 + 0 ≥ 1
or 27 + 6 Δ ≥ 16
or Δ ≥ - 11/6

Therefore, if Δ is smaller than - 11/6, you should enter x₃ into the basis.