X hits on this document





33 / 63

The Dual


TIME OUT for John Von Neumann

John Von Neumann, the famous Hungarian mathematician, is credited with many contributions in science and mathematics, including crucial work on the development of the atomic bomb during World War II and the development of the computer fol- lowing the war. In 1947 George Dantzig visited Von Neumann at

the Institute for Advanced Study at Princeton and described the linear programming technique to him. Von Neumann grasped the technique immediately, because he had been working on similar concepts himself, and went on to explain duality to Dantzig for the first time.

purchase one hour of labor, we would be willing to pay up to $20 for it because that is the amount by which it would increase profit.

The cj - zj values for slack variables are the marginal values of the constraint resources, i.e., shadow prices.

The negative c - z row values of $20 and $6.67 are the marginal values of labor (s1) and wood (s2), respectively. These dual values are also often referred to as shadow prices, since they reflect the maximum “price” one would be willing to pay to obtain one more unit of the resource.



If a resource is not completely used, i.e., there is slack, its marginal value is zero.

What happened to the third resource, storage space? The answer can be seen in Table A-32. Notice that the c - z row value for s3 (which represents unused storage space) is zero. This means that storage space has a marginal value of zero; that is, we would not be willing to pay anything for an extra foot of storage space.



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., s3 = 48) after the 4 tables and 8 chairs were produced. Since the company already has 48 square feet of storage space left over, an extra square foot has no additional value; the company cannot even use all the storage space it has available.

The shadow price is the maximum amount that should be paid for one additional unit of a resource.

We need to consider one additional aspect of these marginal values. In our discus- sion 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 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 objec- tive 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 will reduce the mar- ginal value.

The total marginal value of the resources equals the optimal profit.

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.

Document info
Document views412
Page views412
Page last viewedSat Dec 10 23:05:28 UTC 2016