i get how we go till Dual price calcuaion i dont get the optimal range and the reduced cost can you help example 3.6-3 (tOycO model)
TOYCO uses three operations to assemble three types of toys—trains, trucks, and cars. The
daily available times for the three operations are 430, 460, and 420 mins, 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 mins, respectively. The corresponding
times per train and per car are (2, 0, 4) and (1, 2, 0) mins (a zero time indicates that the opera-
tion is not used).
3.6 Sensitivity Analysis 129
Letting x1, x2, and x3 represent the daily number of units assembled of trains, trucks, and
cars, respectively, the associated LP model is given as:
Maximinze z = 3x1 + 2x2 + 5x3
subject to
x1 + 2x2 + x3 … 430 1Operation 12
3x1 + 2x3 … 460 1Operation 22
x1 + 4x2 … 420 1Operation 32
x1, x2, x3 Ú 0
Using x4, x5, and x6 as the slack variables for the constraints of operations 1, 2, and 3, respec-
tively, 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 associ-
ated revenue is $1350.
Determination of dual prices and feasibility ranges. We will use the TOYCO model to
show how this information is obtained from the optimal simplex tableau. Recognizing
that the dual prices and their feasibility ranges are rooted in making changes in the
right-hand side of the constraints, suppose that D1, D2, and D3 are the (positive or nega-
tive) changes made in the allotted daily manufacturing time of operations 1, 2, and 3,
respectively. The original TOYCO model can then be changed to
Maximinze z = 3x1 + 2x2 + 5x3
subject to
x1 + 2x2 + x3 … 430 + D1 1Operation 12
3x1 + 2x3 … 460 + D2 1Operation 22
x1 + 4x2 … 420 + D3 1Operation 32
x1 , x2 , x3 Ú 0
To express the optimum simplex tableau of the modified problem in terms of the
changes D1, D2, and D3, we first rewrite the starting tableau using the new right-hand
sides, 430 + D1 , 460 + D2 , and 420 + D3 .
130 Chapter 3 The Simplex Method and Sensitivity Analysis
The two shaded areas are identical. Hence, if we repeat the same simplex itera-
tions (with the same row operations) as in the original model, the columns in the two
highlighted area will also be identical in the optimal tableau—that is,
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
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
The new optimum tableau provides the following optimal solution:
z = 1350 + D1 + 2D2
x2 = 100 + 1
2 D1 - 1
4 D2
x3 = 230 + 1
2 D2
x6 = 20 - 2D1 + D2 + D3
We now use this solution to determine the dual prices and the feasibility ranges.
Dual prices: The value of the objective function can be written as
z = 1350 + 1D1 + 2D2 + 0D3
The equation shows that
1. A unit change in operation 1 capacity 1D1 = {1 min2 changes z by $1.
2. A unit change in operation 2 capacity 1D2 = {1 min2 changes z by $2.
3. A unit change in operation 3 capacity 1D3 = {1 min2 changes z by $0.
This means that, by definition, the corresponding dual prices are 1, 2, and 0 ($/min) for
operations 1, 2, and 3, respectively.
The coefficients of D1, D2, and D3 in the optimal z-row are exactly those of the
slack variables x4, x5, and x6. This means that the dual prices equal the coefficients of
the slack variables in the optimal z-row. There is no ambiguity as to which coefficient
3.6 Sensitivity Analysis 131
applies to which resource because each slack variable is uniquely identified with a
constraint.
Feasibility range: The current solution remains feasible if all the basic variables remain
nonnegative—that is,
x2 = 100 + 1
2 D1 - 1
4 D2 Ú 0
x3 = 230 + 1
2 D2 Ú 0
x6 = 20 - 2D1 + D2 + D3 Ú 0
Simultaneous changes D1, D2 , and D3 that satisfy these inequalities will keep the solu-
tion feasible. The new optimum solution can be found by substituting out the values of
D1, D2, and D3.
To illustrate the use of these conditions, suppose that the manufacturing
time available for operations 1, 2, and 3 are 480, 440, and 400 mins, respectively. Then,
D1 = 480 - 430 = 50, D2 = 440 - 460 = -20, and D3 = 400 - 420 = -20. Substi-
tuting in the feasibility conditions, we get
x2 = 100 + 1
2 1502 - 1
4 1 -202 = 130 7 0 1feasible2
x3 = 230 + 1
2 1 -202 = 220 7 0 1feasible2
x6 = 20 - 21502 + 1 -202 + 1 -102 = -110 6 0 1infeasible2
The calculations show that x6 < 0, hence the current solution does not remain feasible.
Additional calculations will be needed to find the new solution (see Chapter 4).
Alternatively, if the changes in the resources are such that D1 = -30, D2 = -12,
and D3 = 10, then
x2 = 100 + 1
2 1 -302 - 1
4 1 -122 = 88 7 0 1feasible2
x3 = 230 + 1
2 1 -122 = 224 7 0 1feasible2
x6 = 20 - 21 -302 + 1 -122 + 1102 = 78 7 0 1feasible2
The new (optimal) feasible solution is x1 = 88, x3 = 224, and x6 = 68 with z = 3102 +
21882 + 512242 = $1296. Notice that the optimum objective value can also be com-
puted using the dual prices as z = 1350 + 11 -302 + 21 -122 + 01102 = $1296.
The given conditions can produce the individual feasibility ranges associated
with changing the resources one at a time (as defined in Section 3.6.1). For example,
a change in operation 1 time only means that D2 = D3 = 0. The simultaneous condi-
tions thus reduce to
x2 = 100 + 1
2 D1 Ú 0 1 D1 Ú -200
x3 = 230 7 0
x6 = 20 - 2D1 Ú 0 1 D1 … 10
s 1 -200 … D1 … 10
This means that the dual price for operation 1 is valid in the feasibility range
-200 … D1 … 10.
We can show in a similar manner that the feasibility ranges for operations 2 and 3
are -20 … D2 … 400 and -20 … D3 … ∞ . respectively (verify!).
132 Chapter 3 The Simplex Method and Sensitivity Analysis
Resource amount (minutes)
Resource Dual price($) Feasibility range Minimum Current Maximum
Operation 1 1 -200 … D1 … 10 230 430 440
Operation 2 2 -20 … D2 … 400 440 440 860
Operation 3 0 -20 … D3 6 ∞ 400 420 ∞
11Available LP packages usually present this information as standard output. Practically none provide the
case of simultaneous conditions, presumably because its display is cumbersome for large LPs.
We can now summarize the dual prices and their feasibility ranges for the TOYCO
model as follows:11
It is important to notice that the dual prices will remain applicable for any simul-
taneous changes that keep the solution feasible, even if the changes violate the individ-
ual ranges. For example, the changes D1 = 30, D2 = -12, and D3 = 100 will keep the
solution feasible even though D1 = 30 violates the feasibility range -200 … D1 … 10,
as the following computations show:
x2 = 100 + 1
2 1302 - 1
4 1 -122 = 118 7 0 1feasible2
x3 = 230 + 1
2 1 -122 = 224 7 0 1feasible2
x6 = 20 - 21302 + 1 -122 + 11002 = 48 7 0 1feasible2
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 + 11302 + 21 -122 +
011002 = $1356.
3.6.3 Algebraic sensitivity Analysis—Objective Function
In Section 3.6.1, we used graphical sensitivity analysis to determine the conditions that
will maintain the optimality of the solution of a two-variable LP. In this section, we
extend these ideas to the general LP problem.
Definition of reduced cost. To facilitate the explanation of the objective func-
tion sensitivity analysis, first we need to define reduced costs. In the TOYCO model
(Example 3.6-2), the objective z-equation in the optimal tableau can be written as
z = 1350 - 4x1 - x4 - 2x5
The optimal solution does not produce toy trains (x1 = 0). The reason can be seen from
the z-equation, where a unit increase in x1 (above its current zero value) decreases z by
$4—namely, z = 1350 - 4 * 112 - 1 * 102 - 2 * 102 = $1346.
3.6 Sensitivity Analysis 133
We can think of the coefficient of x1 in the z-equation (= 4) as a unit cost because
it causes a reduction in the revenue z. But where does this “cost” come from? We know
that the revenue per unit of x1 is $3 (per the original model). We also know that the
production of toy train incurs cost because it consumes resources (operations time).
Thus, from the standpoint of optimization, the “attractiveness” of x1 depends on the
cost of consumed resources relative to revenue. This relationship defines the so-called
reduced cost and is formalized in the LP literature as
aReduced cost
per unit b = aCost of consumed
resources per unit b - 1Revenue per unit2
To appreciate the significance of this definition, 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 recommends producing toy trucks (x2 = 100 units) and no toy
trains (x1 = 0). The reason is that the cost of the resources used by one toy truck
(i.e., 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 see that an unprofitable variable
(such as x1) can be made profitable in two ways:
1. By increasing the unit revenue.
2. By decreasing the unit cost of consumed resources.
In most situations, the price per unit is dictated by market conditions and may be
difficult to increase at will. On the other hand, reducing the consumption of resources
is a more viable option because the manufacturer may be able to reduce cost by mak-
ing the production process more efficient.
Determination of the optimality ranges. We now turn our attention to determin-
ing the conditions that will keep a solution optimal. The development is based on the
definition of reduced cost.
In the TOYCO model, let d1, d2, and d3 represent the change in unit revenues for
toy trucks, trains, and cars, respectively. The objective function then becomes
Maximize z = 13 + d12x1 + 12 + d22x2 + 15 + d32x3
We first consider the general situation in which all the objective coefficients are
changed simultaneously.
With the simultaneous changes, the z-row in the starting tableau appears as:
Basic x1 x2 x3 x4 x5 x6 Solution
z - 3 - d1 -2 - d2 -5 - d3 0 0 0 0
134 Chapter 3 The Simplex Method and Sensitivity Analysis
Basic x1 x2 x3 x4 x5 x6 Solution
z 4 - 1
4 d2 + 3
2 d3 - d1 0 0 1 + 1
2 d2 2 - 1
4 d2 + 1
2 d3 0 1350 + 100d2 + 23d3
x2 - 1
4 1 0 1
2 -1
4 0 100
x3 3
2 0 1 0 1
2 0 230
x6 - 1
4 0 0 -2 1 1 20
When we generate the simplex tableaus with the same sequence of entering
and leaving variables used in the original model (before the changes d j are made), the
optimal iteration will appear as follows (convince yourself that this is indeed the case
by carrying out the simplex row operations):
The new optimal tableau is the same as in the original optimal tableau, except
for the reduced costs (z-equation coefficients). This means that changes in the
objective-function coefficients can affect the optimality of the problem only. (Com-
pare with Section 3.6.2, where changes in the right-hand side affect feasibility
only.)
You really do not need to carry out the simplex row operation to compute the
new reduced costs. An examination of the new z-row shows that the coefficients of
d j are taken directly from the constraint coefficients of the optimum tableau. A con-
venient way for computing the new reduced cost is to add a new top row and a new
leftmost column to the optimum tableau, as shown by the shaded areas in the following
illustration.
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
The entries in the top row are the change dj associated with variable xj. For the leftmost
column, the top element is 1 in the z-row followed by d i basic variable x i. Keep in mind
that d i = 0 for slack variable xi.
To compute 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,
3.6 Sensitivity Analysis 135
add them up, and subtract the top-row element from the sum. For example, for x1 ,
we have
Reduced cost for x1 = [4 * 1 + 1 -1
4 2 * d2 + 3
2 * d3 + 2 * 0] - d1
= 4 - 1
4 d2 + 3
2 d3 - d1
The current solution remains optimal so long as the new reduced costs (z-
equation coefficients) remain nonnegative (maximization case). We thus have the
following simultaneous optimality conditions corresponding to nonbasic x1, x4, and x5:
4 - 1
4 d2 + 3
2 d3 - d1 Ú 0
1 + 1
2 d2 Ú 0
2 - 1
4 d2 + 1
2 d3 Ú 0
Remember that the reduced cost for a basic variable is always zero, as the modified
optimal tableau shows.
To illustrate the use of these conditions, suppose that the objective function
of TOYCO is changed from z = 3x1 + 2x2 + 5x3 to z = 2x1 + x2 + 6x3 . Then,
d1 = 2 - 3 = - $1, d2 = 1 - 2 = - $1, and d3 = 6 - 5 = $1. Substitution in the
given conditions yields
4 - 1
4 d2 + 3
2 d3 - d1 = 4 - 1
4 1 -12 + 3
2 112 - 1 -12 = 6.75 7 0 1satisfied2
1 + 1
2 d2 = 1 + 1
2 1 -12 = .5 7 0 1satisfied2
2 - 1
4 d2 + 1
2 d3 = 2 - 1
4 1 -12 + 1
2 112 = 2.75 7 0 1satisfied2
The results show that the proposed changes will keep the current solution (x1 = 0,
x2 = 100, x3 = 230) optimal (with a new value of z = 1350 + 100d2 + 230d3 =
1350 + 100 * -1 + 230 * 1 = $1480). If any condition is not satisfied, a new solu-
tion must be determined (see Chapter 4).
The preceding discussion has dealt with the maximization case. The only differ-
ence in the minimization case is that the reduced costs (z-equations coefficients) must
be … 0 to maintain optimality.
The optimality ranges dealing with changing dj one at a time can be developed
from the simultaneous optimality conditions. 12 For example, suppose that the objective
coefficient of x2 only is changed to 2 + d2 —meaning that d1 = d3 = 0. The simultane-
ous optimality conditions thus reduce to
4 - 1
4 d2 Ú 0 1 d2 … 16
1 + 1
2 d2 Ú 0 1 d2 Ú -2
2 - 1
4 d2 Ú 0 1 d2 … 8
s 1 -2 … d2 … 8
12The individual ranges are standard outputs in all LP software. Simultaneous conditions usually are not part
of the output, presumably because they are cumbersome for large problems.