DUALITY THEORY:ECONOMIC INTERPRETATION OF DUALITY

ECONOMIC INTERPRETATION OF DUALITY

The economic interpretation of duality is based directly upon the typical interpretation for the primal problem (linear programming problem in our standard form) presented in Sec. 3.2. To refresh your memory, we have summarized this interpretation of the primal problem in Table 6.6.

Interpretation of the Dual Problem

To see how this interpretation of the primal problem leads to an economic interpretation for the dual problem,1 note in Table 6.4 that W is the value of Z (total profit) at the cur- rent iteration. Because

1Actually, several slightly different interpretations have been proposed. The one presented here seems to us to be the most useful because it also directly interprets what the simplex method does in the primal problem.

each bi yi can thereby be interpreted as the current contribution to profit by having bi units of resource i available for the primal problem. Thus,

The dual variable yi is interpreted as the contribution to profit per unit of resource i (i = 1, 2, . . . , m), when the current set of basic variables is used to obtain the primal solution.

In other words, the yi values (or y*i

prices discussed in Sec. 4.7.

values in the optimal solution) are just the shadow For example, when iteration 2 of the simplex method finds the optimal solution for the Wyndor problem, it also finds the optimal values of the dual variables (as shown in the bottom row of Table 6.5) to be y1* = 0, y2* = , and y3* = 1. These are precisely the shadow prices found in Sec. 4.7 for this problem through graphical analysis. Recall that the resources for the Wyndor problem are the production capacities of the three plants being made available to the two new products under consideration, so that bi is the num- ber of hours of production time per week being made available in Plant i for these new products, where i = 1, 2, 3. As discussed in Sec. 4.7, the shadow prices indicate that individually increasing any bi by 1 would increase the optimal value of the ob- jective function (total weekly profit in units of thousands of dollars) by y*i . Thus, y*i can be interpreted as the contribution to profit per unit of resource i when using the optimal solution.

This interpretation of the dual variables leads to our interpretation of the overall dual problem. Specifically, since each unit of activity j in the primal problem consumes aij units of resource i,

i=1 aijyi is interpreted as the current contribution to profit of the mix of resources that would be consumed if 1 unit of activity j were used ( j = 1, 2, . . . , n).

For the Wyndor problem, 1 unit of activity j corresponds to producing 1 batch of product j per week, where j = 1, 2. The mix of resources consumed by producing 1 batch of prod- uct 1 is 1 hour of production time in Plant 1 and 3 hours in Plant 3. The corresponding mix per batch of product 2 is 2 hours each in Plants 2 and 3. Thus, y1 + 3y3 and 2y2 + 2y3 are interpreted as the current contributions to profit (in thousands of dollars per week) of these respective mixes of resources per batch produced per week of the respective products.

For each activity j, this same mix of resources (and more) probably can be used in other ways as well, but no alternative use should be considered if it is less profitable than 1 unit of activity j. Since cj is interpreted as the unit profit from activity j, each functional constraint in the dual problem is interpreted as follows:

i=1 aij yi > cj says that the actual contribution to profit of the above mix of re- sources must be at least as much as if they were used by 1 unit of activity j; oth- erwise, we would not be making the best possible use of these resources.

For the Wyndor problem, the unit profits (in thousands of dollars per week) are c1 = 3 and c2 = 5, so the dual functional constraints with this interpretation are y1 + 3y3 > 3 and 2y2 + 2y3 > 5. Similarly, the interpretation of the nonnegativity constraints is the following:

yi > 0 says that the contribution to profit of resource i (i = 1, 2, . . . , m) must be nonnegative: otherwise, it would be better not to use this resource at all.

can be viewed as minimizing the total implicit value of the resources consumed by the activities. For the Wyndor problem, the total implicit value (in thousands of dollars per week) of the resources consumed by the two products is W = 4y1 + 12y2 + 18y3.

This interpretation can be sharpened somewhat by differentiating between basic and

nonbasic variables in the primal problem for any given BF solution (x1, x2, . . . , xn+m). Recall that the basic variables (the only variables whose values can be nonzero) always have a coefficient of zero in row 0. Therefore, referring again to Table 6.4 and the ac- companying equation for zj, we see that

(This is one version of the complementary slackness property discussed in Sec. 6.3.) The economic interpretation of the first statement is that whenever an activity j operates at a strictly positive level (xj > 0), the marginal value of the resources it consumes must equal (as opposed to exceeding) the unit profit from this activity. The second statement implies that the marginal value of resource i is zero ( yi = 0) whenever the supply of this resource is not exhausted by the activities (xn+i > 0). In economic terminology, such a resource is a “free good”; the price of goods that are oversupplied must drop to zero by the law of supply and demand. This fact is what justifies interpreting the objective for the dual prob- lem as minimizing the total implicit value of the resources consumed, rather than the re- sources allocated.

To illustrate these two statements, consider the optimal BF solution (2, 6, 2, 0, 0) for the Wyndor problem. The basic variables are x1, x2, and x3, so their coefficients in row 0 are zero, as shown in the bottom row of Table 6.5. This bottom row also gives the corresponding dual solution: y1* = 0, y2* = , y= 1, with surplus variables (z- c ) = 0 and 2 3* 1* 1 (z2* - c2) = 0. Since x1 > 0 and x2 > 0, both these surplus variables and direct calculations indicate that y1* + 3y3* = c1 = 3 and 2y2* + 2y3* = c2 = 5. Therefore, the value of the resources consumed per batch of the respective products produced does indeed equalthe respective unit profits. The slack variable for the constraint on the amount of Plant 1 capacity used is x3 > 0, so the marginal value of adding any Plant 1 capacity would be zero ( y1* = 0).

Interpretation of the Simplex Method

The interpretation of the dual problem also provides an economic interpretation of what the simplex method does in the primal problem. The goal of the simplex method is to find how to use the available resources in the most profitable feasible way. To attain this goal, we must reach a BF solution that satisfies all the requirements on profitable use of the resources (the constraints of the dual problem). These requirements com- prise the condition for optimality for the algorithm. For any given BF solution, the requirements (dual constraints) associated with the basic variables are automatically satisfied (with equality). However, those associated with nonbasic variables may or may not be satisfied.

In particular, if an original variable xj is nonbasic so that activity j is not used, then the current contribution to profit of the resources that would be required to undertake each unit of activity j may be smaller than, larger than, or equal to the unit profit cj obtainable from the activ- ity. If it is smaller, so that zj - cj < 0 in row 0 of the simplex tableau, then these resources can be used more profitably by initiating this activity. If it is larger (zj - cj > 0), then these resources already are being assigned elsewhere in a more profitable way, so they should not be diverted to activity j. If zj - cj = 0, there would be no change in profitability by initiating activity j.

Similarly, if a slack variable xn+i is nonbasic so that the total allocation bi of resource i is being used, then yi is the current contribution to profit of this resource on a marginal basis. Hence, if yi < 0, profit can be increased by cutting back on the use of this resource (i.e., increasing xn+i). If yi > 0, it is worthwhile to continue fully using this resource, whereas this decision does not affect profitability if yi = 0.

Therefore, what the simplex method does is to examine all the nonbasic variables in the current BF solution to see which ones can provide a more profitable use of the re- sources by being increased. If none can, so that no feasible shifts or reductions in the current proposed use of the resources can increase profit, then the current solution must be optimal. If one or more can, the simplex method selects the variable that, if increased by 1, would improve the profitability of the use of the resources the most. It then actu- ally increases this variable (the entering basic variable) as much as it can until the mar- ginal values of the resources change. This increase results in a new BF solution with a new row 0 (dual solution), and the whole process is repeated.

The economic interpretation of the dual problem considerably expands our ability to analyze the primal problem. However, you already have seen in Sec. 6.1 that this inter- pretation is just one ramification of the relationships between the two problems. In Sec. 6.3, we delve into these relationships more deeply.