Week 6: Sensitive Analysis
Week 6: Sensitive Analysis
Week 6: Sensitive Analysis
1
1. Sensitive Analysis
Sensitivity Analysis is a systematic study of how, well, sensitive, the solutions of the LP are
to small changes in the data. The basic idea is to be able to give answers to questions of the
form:
1. If the objective function changes in its parameter c i , how does the solution change?
2. If the resources available change. how does the solution change?
3. If a new constraint is added to the problem, how does the solution change?
Solution:
Let x1=number of unit of product 1
X2=number of unit of product 2
Maximize z=30x1+20x2
Subject to
2x1+ x2 ≤ 8 (machine 1)
X1+ 3x2≤8 (machine 2)
X1,x2 ≥ 0
Solution:
2
c- Set x2=0 , this lead to x1=8
If the daily capacity is increased from 8 hours to 9 hours, the new optimum will occur
at point G. The rate of change in optimum z resulting from changing machine 1
capacity from 8 hours to 9 hours can be computed as follows:
This means that a unit increase (decrease) in machine 1 capacity will increase
(decrease) revenue
by $14.00. clear that the dual price of $14.00/hr remains valid for changes (increases
or decreases) in machine 1 capacity that move its constraint parallel to itself to any
point on the line segment BF.
3
Minimum machine 1 capacity [at B=(0,2.67)]= 2*0 +1* 2.67=2.67
Maximum machine 1 capacity[ at f=(8,0)]= 2*8+1*0=16
2.67≤machine 1 capacity ≤ 16
The conclusion is that the dual price of $2.00/hr for machine 2 will remain applicable
for the range
4 ≤machine 2 capacity ≤ 14
The dual prices allow making economic decisions about the LP problem, as the
following questions demonstrate:
Question 1: If JOBCO can increase the capacity of both machines, which machine
should receive higher priority?
The dual prices for machines 1 and 2 are $14.00Ihr and $2.00/hr.l11is means that each
additional hour of machine 1 will increase revenue by $14.00, as opposed to only
$2.00 for machine 2. Thus, priority should be given to machine 1.
4
Question 5. We know that the change in the optimum objective value equals (dual
price x change in resource) so long as the change in the resource is within the
feasibility range. What about the associated optimum values of the variables?
The optimum values of the variables will definitely change. However, the level of
information we have from the graphical solution is not sufficient to determine the new
values.
Maximize z= c1x1+c2x2
Imagine now that the line z is pivoted at C and that it can rotate clockwise and
counterclockwise. The optimum solution will remain at point C so long as
z = Cx1 + cx2 lies between the two lines x1 + 3x2 = 8 and 2xI +x2 = 8. This
means that the ratio (c1/c2) can vary between 1/3 and 2/1, which yields the
following condition:
5
1 𝑐1 2
3
≤ 𝑐2 ≤ 1
This information can provide immediate answers regarding the optimum solution as
the following questions demonstrate:
Question 1. Suppose that the unit revenues for products 1 and 2 are changed to $35
and $25, respectively. Will the current optimum remain the same?
The solution at C will remain optimal because c1/c2 = 1.4 remains within the
optimality range (0.333,2). When the ratio falls outside this range, additional
calculations are needed to find the new optimum . Notice that although the values of
the variables at the optimum point C remain uncha nged, the optimum value of z
changes to
Question 2. Suppose that the unit revenue of product 2 is fixed at its current value of
C2 = $20.00. What is the associated range for cj, the unit revenue for product 1 that
will keep the optimum unchanged?
1 𝑐1 2
≤ ≤
3 𝑐2 1
1 𝑐1 2
≤ 20 ≤ 1
3
1
∗ 20 ≤ 𝑐1 ≤2*20
3
6.666 ≤ 𝑐1 ≤ 40
We can similarly determine the optimality range for Cz by fixing the value of CI at
$30.00. Thus,
1 30 2
≤ 𝑐2 ≤ 1
3
Reverse
3 𝑐2 1
≥ ≥
1 30 2
6
Equivalent to
1 𝑐2 3
≤ 30 ≤ 1
2
1 3
∗ 30 ≤ 𝑐2 ≤ 1 ∗ 30
2
15 ≤ 𝑐2 ≤ 90
we used the graphical solution to determine the dual prices (the unit worths of
resources) and their feasibility ranges. This section extends the analysis to the general
LP model. A numeric example (the TOYCO model) will be used to facilitate the
presentation.
TOYCO assembles three types of toys-trains, trucks, and cars-using three operations.
The daily limits on the available times for the three operations are 430,460, and 420
minutes, respectively, and the revenues per unit of toy train, truck, and car are $3, $2,
and $5, respectively. The assembly times per train at the three operations are 1, 3, and
1 minutes, respectively. The corresponding times per train and per car are (2,0,4) and
(1,2,0) minutes (a zero time indicates that the operation is not used).
maximize z=3x1+2x2+5x3
subject to
x1+2x2+x3≤430 (operation 1)
x1,x2,x3≥0
7
Using X4, Xs, and X6 as the slack variables for the constraints of operations 1,2, and
3, respectively, the optimum tableau is
Basic X1 X2 X3 X4 X5 X6 solution
Z 4 0 0 1 2 0 1350
X2 -1/4 1 0 1/2 -1/4 0 100
X3 3/2 0 1 0 1/2 0 230
X6 2 0 0 -2 1 1 20
The solution recommends manufacturing 100 trucks and 230 cars but no trains. The
associated revenue is $1350.
Determination of Dual Prices: The constraints of the model after adding the slack
variables X4, Xs, and X6 can be written as follows:
or
With this representation, the slack variables have the same units (minutes) as the
operation times. Thus, we can say that a one- minute decrease in the slack variable is
equivalent to a one- minute increase in the operation time.
can use the information above to determine the dual prices from the z-equation in the
optimal tableau:
Given that a decrease in the value of a slack variable is equivalent to an increase in its
operation time, we get
8
z = 1350- 4xl + 1 x (increase in operation 1 time)
Basic X1 X2 X3 X4 X5 X6 solution
Z 4 0 0 1 2 0 1350
yields directly the dual prices, as the following table shows:
The dual prices also indicate that, when allocating additional resources, Operation 2
may be given higher priority because its dual price is twice as much as that of
Operation 1.
Determination of the Feasibility Ranges: Let D1,D2 and D3 be the changes (positive
or negative) in the daily manufacturing time allocated to operations 1,2, and 3,
respectively. The model can be written as follows:
9
subject to
x1,x2,x3≥0
The procedure is based on recomputing the optimum simplex tableau with the
modified right- hand side and then deriving the conditions that will keep the solution
feasible and The starting tableau will thus appear as:
solution
basic X1 X2 X3 X4 X5 X6 RHS D1 D2 D3
Z -3 -2 -5 0 0 0 0 0 0 0
X4 1 2 1 1 0 0 430 1 0 0
X5 3 0 2 0 1 0 460 0 1 0
X6 1 4 0 0 0 1 420 0 0 1
The columns under Dj, D2, and D3 are identical to those under the starting basic
columns X4, Xs, and x6- This means that when we carry out the same simplex
iterations as in the original model, the columns in the two groups must come out
identical as well Effectively, the new optimal tableau will become
solution
basic X1 X2 X3 X4 X5 X6 RHS D1 D2 D3
Z 4 0 0 1 2 0 1350 1 2 0
X2 -1/4 1 0 1/2 -1/4 0 100 1/2 -1/4 0
X3 3/2 0 1 0 1/2 0 230 0 1/2 0
X6 2 0 0 -2 1 1 20 -2 1 1
z = 1350 + D1 + 2D2
x3=230+1/2D2
x6 = 20 -2D1 + D2 + D3
Interestingly, as shown earlier, the new z-value confirms that the dual prices for
operations 1,2, and 3 are 1,2, and 0, respectively. The current solution remains
10
feasible so long as all the variables are nonnegative, which leads to the following
feasibility conditions:
x3 = 230 + 1/2 D2 ≥ 0
x6 = 20 - 2D1 + D2 + D3 ≥ 0
Any simultaneous changes D1, D2, and D3 that satisfy these inequalities will keep
the solution feasible. If all the conditions are satisfied, then the new optimum solution
can be found through direct substitution of D1,D2 and D3 in the equations given
above.
To illustrate the use of these conditions, suppose that the manufacturing time
available for operations 1,2,and 3 are 480,440, and 410 minutes respectively. Then,
Dl =480 - 430 = 50, D2 = 440 - 460 = -20, and D3 = 410 - 420 = -10. Substituting in
the feasibility conditions, we get
The calculations show that X6 < 0, hence the current solution does not remain feasible
Additional calculations will be needed to find the new solution. Alternatively, if the
changes in the resources are such that Dl = -30, D2=-12,and D3= 10, then
The given conditions can be specialized to produce the individual feasibility ranges
that result from changing the resources one at a time
Case 1. Change in operation 1 lime from 460 to 460 + Dl minutes. This change is
equivalent to setting D2 = D3=0 in the simultaneous conditions, which yields
11
1
𝑥2 = 100 + 𝐷1 ≥ 0 → 𝐷1 ≥ −200
2 → −200 ≤ 𝐷1 ≤ 10
𝑥3 = 230 > 0
𝑥6 = 20 − 2𝐷1 ≥ 0 → 𝐷1 ≤ 10
Case 2. Change in operation 2 time from 430 to 430 + ~ minutes. This change is
equivalent to setting D1 = D3 = 0 in the simultaneous conditions, which yields
1
𝑥2 = 100 − 4 𝐷2 ≥ 0 → 𝐷2 ≤ 400
𝑥3 = 230 + 2𝐷2 ≥ 0 → 𝐷2 ≥ −460 → −20 ≤ 𝐷2 ≤ 400
1
𝑥6 = 20 + 𝐷2 ≥ 0 → 𝐷2 ≥ −20
Case 3. Change in operation 3 time from 420 to 420 + D3 minutes. This change is
equivalent to setting D1 = D2 = 0 in the simultaneous conditions, which yields
𝑥2 = 100 > 0
𝑥3 = 230 > 0 → −20 ≤ 𝐷3 ≤ ∞
𝑥6 = 20 + 𝐷3 ≥ 0
summarize the dual prices and their feasibility ranges for the
simultaneous changes that keep the solution feasible, even if the changes violate the
individual ranges. For example, the changes Dl = 30, D2 = -12, and D3 = 100, will
keep the solution feasible even though D1 = 30 violates the feasibility range
−200 ≤ 𝐷1 ≤ 10 as the following computations show
1 1
𝑥2 = 100 + − = 118 > 0
2 30 4 −12
𝑥3 = 23 −12 = 224 > 0
𝑥6 = 20 − 2 30 + −12 + (100) > 0
12
This means that the dual prices will remain applicable, and we can compute the new
optimum objective value from the dual prices as z = 1350 + 1(30) + 2(-12) +0(100) =
$1356
basic x1 x2 x3 x4 x5 x6 solution
z 4 0 0 1 2 0 1350
x2 -1/4 1 0 1/2 -1/4 0 100
x3 3/2 0 1 0 1/2 0 230
x6 2 0 0 -2 1 1 20
z+4x1+x4+2x5=1350
or
z=1350-4x1-x4-2x5
the optimal solution does not recommend the production of toy trains (x1= 0). this
recommendation is confirmed by the information in the z-equation because each unit
increase in (xi) above its current zero level will decrease the value of z by $4 -
namely,z = 1350 - 4 x (1) - 1 x (0) 2 x (0) = $1346.
in the original toyco model the revenue per unit for toy trucks $2) is less than that for
toy trains (= $3). yet the optimal solution elects to manufacture toy trucks (x2 = 100
units) and no toy trains (x1= 0). the reason for this (seemingly nonintuitive) result is
that the unit cost of the resources used by toy trucks (le., operations time) is smaller
than its unit price. the opposite applies in the case of toy trains. with the given
definition of reduced cost we can now see that an unprofitable variable (such as x1)
can be made profitable in two ways:
13
most real- life situations, the price per unit may not be a viable option because its
value is dictated by market conditions. the real option then is to reduce the
consumption of resources, perhaps by making the production process more efficient.
determination of the optimality ranges: we now turn our attention to determining the
conditions that will keep an optimal solution unchanged. the presentation is based on
the definition of reduced cost.
in the toyco model, let dt> dz, and d3 represent the change in unit revenues for
toy trucks, trains, and cars, respectively. the objective function then becomes
maximize z=(3+d1)x1+(2+d2)x2+(5+d3)x3
z-row in starting tableau appear as
basic x1 x2 x3 x4 x5 x6 solution
z -3-d1 -2-d2 -5-d3 0 0 0 0
when we generate the simplex tableaus using the same sequence of entering and
leaving variables in the original model (before the changes dj are introduced), the
optimal iteration will appear as:
basic x1 x2 x3 x4 x5 x6 solution
z 4-0.25d2+1.5d3-d1 0 0 1+0.5d2 2-0.25d2+0.5d3 0 1350+100d2+230d3
x2 -1/4 1 0 1/2 -1/4 0 100
x3 3/2 0 1 0 1/2 0 230
x6 2 0 0 -2 1 1 20
a convenient way for computing the new reduced cost is to add a new top row and a
ne w leftmost column to the optimum tableau, as shown by the shaded areas
below.
d1 d2 d3 0 0 0
basic x1 x2 x3 x4 x5 x6 solution
1 z 4 0 0 1 2 0 1350
d2 x2 -1/4 1 0 1/2 -1/4 0 100
d3 x3 3/2 0 1 0 1/2 0 230
0 x6 2 0 0 -2 1 1 20
to explain to appear z-coefficient as: the new reduced cost for any variable (or the
value of z), multiply the elements of its column by the corresponding elements in the
leftmost column, add them up, and subtract the top-row element from the sum.
d1
left column x1 (x1-column*left-column)
1 4 4*1
d2 -1/4 -1/4*d2
d3 3/2 3/2*d3
0 2 2*0
reduced cost for x1=4-1/4d2+3/2d3-d1
applying the same rule to the solution column produces z = 1350 + l00d2 + 230d3.
14
left column solution (x1-column*left-column)
1 1350 1350
d2 100 100*d2
d3 230 230*d3
0 20 20*0
reduced cost for z=1350+100d2+230d3
note: because we are dealing with a maximization problem, the current solution
remains optimal so long as the new reduced costs (z-equation coefficients) remain
nonnegative for all the nonbasic variables. we thus have the following optimality
conditions corresponding to nonbasic x1, x4, and x5:
1 3
4 − d2 + d3 − d1 ≥ 0
4 2
1
1 + d2 ≥ 0
2
1 1
2 − d2 + d3 ≥ 0
4 2
1 3 1 3
4 − 4 d2 + 2 d3 − d1 = 4 − 4 ∗ 1 + 2 ∗ 1 − −1 ≥ 0 satisfied
1 1
1 + d2 = 1 + ∗ 1 ≥ 0 satisfied
2 2
1 1 1 1
2 − d2 + d3 = 2 − ∗ 1 + ∗ 1 ≥ 0 satisfied
4 2 4 2
the results show that the proposed changes will keep the current solution (xl = 0,
x2 = 100, x3 = 230) optimal. hence no further calculations are needed, except that
the objective value will change to z= 1350 + 100d2 + 230d3 == 1350 + 100 x -1 +
230 x 1 = $1480
the general optimality conditions can be used to determine the special case where the
changes dj occur one at a time instead of simultaneously. this analysis is equivalent to
considering the following three cases:
15
the individual conditions can be accounted for as special cases of the simultaneous
case.5
case 1. set d2 = d3 = 0 in the simultaneous conditions, which gives
4 − d1 ≥ 0 → −∞ < d1 ≤ 4
3
4 + d3 ≥ 0 → d3 ≥ −8/3
2
1
2 + d3 ≥ 0 → d3 ≥ 4
2
−8/3 ≤ d3 ≤ ∞
the given individual conditions can be translated in terms of the total unit revenue.
for example, for toy trucks (variable x2), the total unit revenue is 2 + d2 and the
associated condition −2 ≤ d3 ≤ 8 translates to
−2 + 2 ≤ 2 + d2 ≤ 8 + 2
0$ ≤ uint revenue of toy truck ≤ 10$
this condition assumes that the unit revenues for toy trains and toy cars remain fixed
at $3 and $5, respectively.
the allowable range ($0, $10) indicates that the unit revenue of toy trucks (variable
x2) can be as low as $0 or as high as $10 without changing the current optimum,
xl= 0, xz = 100, x3 = 230. the total revenue will change to 1350 + 100d2, however
16