ECONOMIC INTERPRETATION OF DUALITY
linear programming problem can be viewed as a resource allocation model in
which the objective is to maximize revenue subject to the availability of
limited re-sources. Looking at the problem from this standpoint, the associated
dual problem of-fers interesting economic interpretations of the LP resource
formalize the discussion, we consider the following representation of the
gen-eral primal and dual problems:
a resource allocation model, the primal problem has n economic activities and m
resources. The coefficient Cj in the primal represents the
revenue per unit ofactivity j. Resource i, whose
maximum availability is bi , is
consumed at the rate aij units per unit of activity j.
1. Economic Interpretation of Dual Variables
4.2.3 states that for any two primal and dual feasible solutions, the values of the objective functions, when
finite, must satisfy the following inequality:
strict equality, z = w, holds when both the primal and
dual solutions are optimal. Let us consider the optimal condition z = w first. Given that the primal problem
represents a resource allocation model, we can think of z as representing revenue dollars. Because bi
represents the number of units available of resource i, the
z = w can be
expressed dimensionally as
means that the dual variable, yi represents the worth per unit of resource i. As
stated in Section 3.6, the standard name dual
(or shadow) price of resource i replaces
the name worth per unit in all LP
literature and software packages.
same logic, the inequality z < w associated with any two feasible
pri-mal and dual solutions is interpreted as
< (Worth of resources)
relationship says that so long as the total revenue from all the activities is
less than the worth of the resources, the corresponding primal and dual
solutions are not opti-mal. Optimality (maximum revenue) is reached only when
the resources have been ex-ploited completely, which can happen only when the
input (worth of the resources) equals the output (revenue dollars). In economic
terms, the system is said to be unstable (nonoptimal)
when the input (worth of the resources) exceeds the output (revenue). Stability occurs only when the two quantities are
Mikks model (Example 2.1-1) and its dual are given as:
the Reddy Mikks model deals with the production of two types of paint (interior
and exterior) using two raw materials Ml and M2 (resources 1 and 2) and subject to market and demand limits
represented by the third and fourth constraints. The model determines the
amounts (in tons/day) of interior and exterior paints that maximize the daily
revenue (expressed in thousands of dollars).
optimal dual solution shows that the dual price (worth per unit) of raw
material Ml (re-source 1) is yl = .75 (or
$750 per ton), and that of raw material M2
(resource 2) is y2 = .5 (or
$500 per ton). These results hold true for specific feasibility ranges as we showed in Section 3.6. For resources 3 and
4, representing the market and demand limits, the dual prices are both zero,
which indicates that their associated resources are abundant. Hence, their
worth per unit is zero.
PROBLEM SET 4.3A
Example 4.3-1, compute the change in the optimal revenue in each of the
following cases (use TORA output to obtain the feasibility ranges):
constraint for raw material M1 (resource 1) is 6xl + 4x2 ≤ 22.
constraint for raw material M2
(resource 2) is x1
+ 2x2 ≤ 4.5.
market condition represented by resource 4 is x2 ≤ 10.
Electronics manufactures four types of simple cables for a defense contractor. Each cable
must go through four sequential operations: splicing, soldering, sleeving, and
inspection. The following table gives the pertinent data of the situation.
contractor guarantees a minimum production level of 100 units for each of the
the problem as a linear programming model, and determine the optimum production
b. Based on
the dual prices, do you recommend making increases in the daily capacities of
any of the four operations? Explain.
c. Does the
minimum production requirements for the four cables represent an advan-tage or
a disadvantage for NWAC Electronics? Provide an explanation based on the dual
d. Can the
present unit contribution to revenue as specified by the dual price be
guar-anteed if we increase the capacity of soldering by 1O%?
produces leather jackets and handbags. A jacket requires 8 m2 of
leather, and a handbag only 2 m2• The labor requirements for the two
products are 12 and 5 hours, re-spectively. The current weekly supplies of
leather and labor are limited to 1200 m2 and 1850 hours. The company
sells the jackets and handbags at $350 and $120, respectively. The objective is
to determine the production schedule that maximizes the net revenue. BagCo is
considering an expansion of production. What is the maximum purchase price The
company should pay for additional leather? For additional labor?
2. Economic Interpretation of Dual Constraints
constraints can be interpreted by using Formula 2 in Section 4.2.4, which
states that at any primal iteration,
maximization optimality condition thus says that it is economically advantageous
to increase an activity to a positive level if its unit revenue exceeds its
unit imputed cost.
use the TOYCO model of Section 3.6 to demonstrate the computation. The details
of the model are restated here for convenience.
assembles three types of toys: trains, trucks, and cars using three operations.
Available assembly times for the three operations are 430,460, and 420 minutes
per day, respectively, and the revenues per toy train, truck, and car are $3,
$2, and $5, respectively. The assembly times per train for the three operations
are 1,3, and 1 minutes, respectively. The corresponding times per truck and per
car are (2,0,4) and (1,2,0) minutes (a zero time indicates that the operation
is not used).
Letting x1,x2,and x3 represent the daily number of units assembled of
trains, trucks and cars, the associated LP model and its dual are given as:
optimal primal solution calls for producing no toy trains, 100 toy trucks, and 230 toy cars. Suppose that TOYCO is
interested in producing toy trains as well. How can this be achieved? Looking
at the problem from the standpoint of the interpretation of the reduced cost for xl> toy trains will become
attractive economically only if the imputed cost of the resources used to
produce one toy train is strictly less than its unit revenue. TOYCO thus can
either in-crease the unit revenue per unit by raising the unit price, or it can
decrease the imputed cost of the used resources (= y1 + 3y2
+ y3). An increase in
unit price may not be possible because of market competition. A decrease in the
unit imputed cost is more plausible because it entails making improvements in
the assembly operations. Letting r1, r2, and r3 represent the propor-tions by which the unit times of
the three operations are reduced, the problem requires deter-mining r1, r2, and r3 such that the new imputed cost per
per toy train is less than its unit revenue-that is,
values of r1 and r2
between 0 and 1 that satisfy r1 + 6r2 > 4 should make toy trains
profitable. However, this goal may not be achievable because it requires
practically impossible reductions in the times of operations 1 and 2. For
example, even reductions as high as 50% in these times (that is, rl = r2 = .5) fail to satisfy the given condition. Thus,
TOYCO should not produce toy trains unless an increase in its unit price is
Example 4.3-2, suppose that for toy trains the per-unit time of operation 2 can
be reduced from 3 minutes to at most 1.25 minutes. By how much must the
per-unit time of operation 1 be reduced to make toy trains just profitable?
Example 4.3-2, suppose that TOYCO is studying the possibility of introducing a
fourth toy: fire trucks. The assembly does not make use of operation 1. Its
unit assembly times on operations 2 and 3 are 1 and 3 minutes, respectively.
The revenue per unit is $4. Would you advise TOYCO to introduce the new
JoShop uses lathes and drill presses to produce four types of machine parts, PPl, PP2, PP3, and PP4. The table
below summarizes the pertinent data.
parts that are not produced by the present optimum solution, determine the rate
of deterioration in the optimum revenue per unit increase of each of these
Consider the optimal solution of JoShop in Problem 3. The company estimates
that for each part that is not produced (per the optimum solution), an
across-the-board 20% re. duction in machining time can be realized through process
improvements. Would these improvements make these parts profitable? If not, what is the minimum
percentage re-duction needed to realize revenueability?