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.
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|
The linear programming model for this problem can stated as:
Maximize z = 12x1 + 3x2 + x3
10x1 + 2x2 + x3 ≤ 100
7x1 + 3x2 + 2x3 ≤ 77
2x1+ 4x2 + x3 ≤ 80
x1, x2, x3 ≥ 0
The optimal solution to this problem is given below.
On small screens, scroll horizontally to view full calculation
|cB|| Basic variables
|x1||x2||x3||x4||x5||x6|| Solution values
b (= XB)
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)
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, 3) = 3
Corresponding to the non basic variable x4, y14 > 0. Hence,
- 5 ≤ c1* - 12 ≤
3, i.e., 7 ≤ c1* ≤
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|
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.