Every linear programming model has two forms: the primal and the dual . The original form of a linear programming model is called the primal. All the examples in this module are primal models. The dual is an alternative model form derived completely from the primal. The dual is useful because it provides the decision maker with an alternative way of looking at a problem. Whereas the primal gives solution results in terms of the amount of profit gained from producing products, the dual provides information on the value of the constrained resources in achieving that profit. The original linear programming model is called the The following example will demonstrate how the dual form of a model is derived and what it means. The Hickory Furniture Company produces tables and chairs on a daily basis. Each table produced results in $160 in profit; each chair results in $200 in profit. The production of tables and chairs is dependent on the availability of limited resources labor, wood, and storage space. The resource requirements for the production of tables and chairs and the total resources available are as follows . The dual solution variables provide the value of the resources, that is,
The company wants to know the number of tables and chairs to produce per day to maximize profit. The model for this problem is formulated as follows.
where x x This model represents the primal form. For a primal maximization model, the dual form is a minimization model. The dual form of this example model is
The dual is formulated entirely from the primal. The specific relationships between the primal and the dual demonstrated in this example are as follows. -
The dual variables, y _{ 1 }, y_{ 2 }, and y_{ 3 }, correspond to the model constraints in the primal. For every constraint in the primal there will be a variable in the dual. For example, in this case the primal has three constraints ; therefore, the dual has three decision variables . -
The quantity values on the right-hand side of the primal inequality constraints are the objective function coefficients in the dual. The constraint quantity values in the primal, 40, 216, and 240, form the dual objective function: Z = 40 y _{ 1 }+ 216 y_{ 2 }+ 240 y_{ 3 }. -
The model constraint coefficients in the primal are the decision variable coefficients in the dual. For example, the labor constraint in the primal has the coefficients 2 and 4. These values are the y _{ 1 }variable coefficients in the model constraints of the dual: 2 y_{ 1 }and 4 y_{ 1 }. -
The objective function coefficients in the primal, 160 and 200, represent the model constraint requirements (quantity values on the right-hand side of the constraint) in the dual. -
Whereas the maximization primal model has constraints, the minimization dual model has constraints.
The primaldual relationships can be observed by comparing the two model forms shown in Figure A-9. ## Figure A-9. The primaldual relationships## (This item is displayed on page A-32 in the print version) Now that we have developed the dual form of the model, the next step is determining what the dual means. In other words, what do the decision variables y A primal maximization model with constraints converts to a dual minimization model with constraints, and vice versa. ## Interpreting the Dual ModelThe dual model can be interpreted by observing the simplex solution to the primal form of the model. The simplex solution to the primal model is shown in Table A-32. ## Table A-32. The Optimal Simplex Solution for the Primal Model## (This item is displayed on page A-32 in the print version)
Interpreting this primal solution, we have
This optimal primal tableau also contains information about the dual. In the c Recall that s Let us assume that one unit of s
The negative c The c What happened to the third resource, storage space? The answer can be seen in Table A-32. Notice that the c If a resource is not completely used, i.e., there is slack, its marginal value is zero. The reason more storage space has no marginal value is because storage space was not a limitation in the production of tables and chairs. Table A-32 shows that 48 square feet of storage space were left unused (i.e., s We need to consider one additional aspect of these marginal values. In our discussion of the marginal value of these resources, we have indicated that the marginal value (or shadow price ) is the maximum amount that would be paid for additional resources. The marginal value of $60 for one hour of labor is not necessarily what the Hickory Furniture Company would pay for an hour of labor. This depends on how the objective function is defined. In this example we are assuming that all of the resources available, 40 hours of labor, 216 board feet of wood, and 240 square feet of storage space, are already paid for. Even if the company does not use all the resources, it still must pay for them. They are sunk costs. In other words, the cost of any additional resources secured are included in the objective function coefficients. As such, the profit values in the objective function for each product are unaffected by how much of a resource is actually used; the profit is independent of the resources used. If the cost of the resources is not included in the profit function, then securing additional resources would reduce the marginal value. The The Continuing our analysis, we note that the profit in the primal model was shown to be $2,240. For the furniture company, the value of the resources used to produce tables and chairs must be in terms of this profit. In other words, the value of the labor and wood resources is determined by their contribution toward the $2,240 profit. Thus, if the company wanted to assign a value to the resources it used, it could not assign an amount greater than the profit earned by the resources. Conversely, using the same logic, the total value of the resources must also be at least as much as the profit they earn. Thus, the value of all the resources must exactly equal the profit earned by the optimal solution. The total marginal value of the resources equals the optimal profit. Now let us look again at the dual form of the model.
The dual variables equal the marginal value of the resources, the shadow prices. Given the previous discussion on the value of the model resources, we can now define the decision variables of the dual, y y y y ## Use of the DualThe importance of the dual to the decision maker lies in the information it provides about the model resources. Often the manager is less concerned about profit than about the use of resources because the manager often has more control over the use of resources than over the accumulation of profits. The dual solution informs the manager of the value of the resources, which is important in deciding whether or not to secure more resources and how much to pay for these additional resources. The dual provides the decision maker with a basis for deciding how much to pay for more resources. If the manager secures more resources, the next question is "How does this affect the original solution?" The feasible solution area is determined by the values forming the model constraints, and if those values are changed, it is possible for the feasible solution area to change. The effect on the solution of changes to the model is the subject of sensitivity analysis, the next topic to be presented here. |

Introduction to Management Science (10th Edition)

ISBN: 0136064361

EAN: 2147483647

EAN: 2147483647

Year: 2006

Pages: 358

Pages: 358

Authors: Bernard W. Taylor

flylib.com © 2008-2017.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net