# 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 main goal of the management is to know how sensitive the solution is to the original data.

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.

Product Machine Profit per unit
M1 M2 M3
A 10 7 2 12
B 2 3 4 3
C 1 2 1 1
Available Time 100 77 80

Solution.

The linear programming model for this problem can stated as:

Maximize z = 12x1 + 3x2 + x3

subject to

10x1 + 2x2 + x≤ 100
7x1 + 3x2 + 2x3 ≤ 77
2x1+ 4x2 + x3 ≤ 80

x1, x2, x3 ≥ 0

The optimal solution to this problem is given below.

Final Table

On small screens, scroll horizontally to view full calculation

cj 12 3 1 0 0 0
cB Basic variables
B
x1 x2 x3 x4 x5 x6 Solution values
b (= XB)
12 x1 1 0 -1/16 3/16 -1/8 0 73/8
3 x2 0 1 13/16 -7/16 5/8 0 35/8
0 x6 0 0 -17/8 11/8 -9/4 1 177/4
zj   12 3 27/16 15/16 3/8 0
zj-cj   0 0 11/16 15/16 3/8 0

An optimal policy is x1 =73/8, x2 = 35/8, x3 = 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 cj 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 cj 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 (cj) 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 zj. Thus, to bring x3 into the basis, its profit contribution rate cj must exceed Rs. 27/16 to make zj-cj value negative or zero (i.e., zj-cj ≤ 0)

Specifically:

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

In our case c3 = 1 and z3-c3 = 11/16, then

c3* - 1 ≥ 11/16
c3* ≥ 11/16 + 1 = 27/16

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

Change in cj of a Basic Variable

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

- Minimum (zj-cj / y1j; y1j > 0) ≤ Δ1 ≤ Minimum (zj-cj / -y1j; y1j < 0)

Referring to the final simplex table, we observe that corresponding to the non basic variables x3 & x5, y13, y15 < 0 Hence,

Use Horizontal Scrollbar to View Full Details

 Minimum 11/16 ------- -(-1/16) , 3/8 ----- -(-1/8)

= Minimum (11, 3) = 3

Corresponding to the non basic variable x4, y14 > 0. Hence,

 Minimum 15/16 ------- 3/16

= 5

Hence,

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

Thus, the optimal solution is insensitive so long as the changed profit coefficient c1* 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 XB column by the corresponding coefficient in the x4 column of table.

XB x4 XB / x4
73/8 3/16 146/3
35/8 -7/16 -10
177/4 11/8 354/11

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

Calculating the range

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

Hence, the range of hours for M1 is 746/11 to 110. By the same way, the range of hours for Machine M2 & 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, x3 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

W1 + (2 + Δ)W2 + W3 ≥ 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 x3 into the basis.

This chapter focussed on a unifying concept, namely, duality. The term 'Duality' implies that every linear programming problem, whether of maximization or minimization, is associated with another linear programming problem based on the same data.

The management of a company rarely confines its interest to the numerical values of an optimal solution. Actually, the management is interested in knowing the impact of changes in the input parameter values on the optimal solution. Such an investigation is termed a sensitivity analysis.