Page 280 -

260 CHAPTER 6 SIMPLEX-BASED SENSITIVITY ANALYSIS AND DUALITY

HighTech should be willing to pay up to E2.80 per hour for it. A similar interpre-
tation can be given to the z j value for each of the non-basic slack variables.
With a greater-than-or-equal-to constraint, the value of the dual price will be less
than or equal to zero because a one-unit increase in the value of the right-hand side
cannot be helpful; a one-unit increase makes it more difficult to satisfy the con-
straint. For a maximization problem, then, the optimal value can be expected to
decrease when the right-hand side of a greater-than-or-equal-to constraint is
increased. The dual price gives the amount of the expected improvement – a
negative number, since we expect a decrease. As a result, the dual price for a
greater-than-or-equal-to constraint is given by the negative of the z j entry for the
corresponding surplus variable in the optimal simplex tableau.
Finally, it is possible to calculate dual prices for equality constraints. They are
given by the z j values for the corresponding artificial variables. We will not develop
this case in detail here because we have recommended dropping each artificial
variable column from the simplex tableau as soon as the corresponding artificial
variable leaves the basis.
Try Problem 3, parts (a), To summarize, when the Simplex method is used to solve a linear programming
(b) and (c), for practise problem, the dual prices for the constraints are contained in the final tableau.
in finding dual prices
from the optimal simplex Table 6.1 summarizes the rules for determining the dual prices for the various
tableau. constraint types in a maximization problem solved by the Simplex method.
Recall that we convert a minimization problem to a maximization problem by
multiplying the objective function by 1 before using the Simplex method. Never-
theless, the dual price is given by the same z j values because improvement for a
minimization problem is a decrease in the optimal value.
To illustrate the approach for calculating dual prices for a minimization problem,
recall the M&D Chemicals problem that we solved in Section 5.7 as an equivalent
maximization problem by multiplying the objective function by 1. The linear pro-
gramming model for this problem and the final tableau are restated as follows, with x 1
and x 2 representing manufacturing quantities of products A and B, respectively.
Min 2x 1 þ 3x 2
s:t:
1x 1 125 Demand for product A
1x 1 þ 1x 2 350 Total production
2x 1 þ 1x 2 600 Processing time
x 1 ; x 2 0

x 1 x 2 s 1 s 2 s 3
Basis c B 2 3 0 0 0
2 1 0 0 1 1 250
x 1
3 0 1 0 2 1 100
x 2
0 0 0 1 1 1 125
s 1
z j 2 3 0 4 1 800
c j – z j 0 0 0 4 1

Following the rules in Table 6.1 for identifying the dual price for each constraint
type, the dual prices for the constraints in the M&D Chemicals problem are given in
Table 6.2. Constraint 1 is not binding, and its dual price is zero. The dual price for

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.