Submitted by: Submitted by jeromearteza
Views: 10
Words: 41742
Pages: 167
Category: Business and Industry
Date Submitted: 03/19/2016 11:49 PM
6
Duality Theory and
Sensitivity Analysis
One of the most important discoveries in the early development of linear programming
was the concept of duality and its many important ramifications. This discovery revealed
that every linear programming problem has associated with it another linear programming
problem called the dual. The relationships between the dual problem and the original
problem (called the primal) prove to be extremely useful in a variety of ways. For example, you soon will see that the shadow prices described in Sec. 4.7 actually are provided by the optimal solution for the dual problem. We shall describe many other valuable applications of duality theory in this chapter as well.
One of the key uses of duality theory lies in the interpretation and implementation of
sensitivity analysis. As we already mentioned in Secs. 2.3, 3.3, and 4.7, sensitivity analysis is a very important part of almost every linear programming study. Because most of
the parameter values used in the original model are just estimates of future conditions,
the effect on the optimal solution if other conditions prevail instead needs to be investigated. Furthermore, certain parameter values (such as resource amounts) may represent
managerial decisions, in which case the choice of the parameter values may be the main
issue to be studied, which can be done through sensitivity analysis.
For greater clarity, the first three sections discuss duality theory under the assumption that the primal linear programming problem is in our standard form (but with no restriction that the bi values need to be positive). Other forms are then discussed in Sec. 6.4.
We begin the chapter by introducing the essence of duality theory and its applications.
We then describe the economic interpretation of the dual problem (Sec. 6.2) and delve
deeper into the relationships between the primal and dual problems (Sec. 6.3). Section 6.5
focuses on the role of duality theory in sensitivity...