Table of contents
- 1. 6.1 Essence of Duality Theorem
- 1.1. Origin of the Dual Problem
- 1.1.1. Surplus variables
- 1.2. Summary of the Primal Dual Relationships
- 1.2.1. Weak duality
- 1.2.2. Strong Duality
- 1.2.3. Complementary Solutions Property
- 1.2.4. Complementary Optimal Solutions Property
- 1.2.5. Symmetry Property
- 1.2.6. Duality Theorem
- 1.3. Applications
- 1.1. Origin of the Dual Problem
- 2. 6.2 Economic Interpretation of Duality
Every linear programming problem has associated with it an alternative linear programming problem called the dual.
The original problem is called the primal.
6.1 Essence of Duality Theorem
If the primal problem is maximization, then the dual is minimization.
Standard form:
A primal problem is tranformable into a corresponding dual problem by:
- Primal: Coefficients of objective function.
Dual: Right hand side of functional constraints. - Primal: Right hand side of functional constraints.
Dual: Coefficients of objective function. - Primal: Coefficients of variable function
Dual: Coefficients of variable function (but different place, aka Primal = A, Dual = AT).
Example:
Origin of the Dual Problem
Only feasible solutions for the dual problem are those which satisfy the conditions for optimality for the primal, eg. only the optimal solution(s) of the primal.
A consequence of this is that the optimal value Z for the primal is the minimum (optimal) feasible value for W in the dual.
A feature of the dual is that the optimal solution provides the shadow prices of the primal.
A optimal W is equal to an optimal Z, W* = Z*
This implies that cx <= yb, for any feasible x and y.
Surplus variables
AKA slack variables for the dual.
zi - ci, where ci = objective function co-efficient
A negative value for a surplus variable indicates that the corresponding constraint is violated.
Summary of the Primal Dual Relationships
Weak duality
If x is a feasible solution for the primal problem, and y is a feasible for the dual problem, then
cx <= yb
Strong Duality
If x* is a optimal solution for the primal problem, and y* is a optimal solution for the dual problem, then:
cx* = y*b
This implies that if cx* < y*b, they are not optimal at all!
Complementary Solutions Property
At each iteration the simplex method simultaneously identifies a CPF solution x for the primal problem, and a complementary solution y for the dual problem where:
cx=yb
If x is not an optimal solution for the primal problem, then y is not feasible for the dual problem.
Complementary Optimal Solutions Property
At the final iteration the simplex method identifies an optimal solution x* for the primal problem, and a complementary solution y* for the dual problem where:
cx*=y*b
Where y*i are the shadow prices for the primal problem.
Symmetry Property
For any primal problem and its corresponding dual problem all relationships between them must be symmetric, because the dual of the dual is the primal.
Duality Theorem
The only possible relationships between a primal problem and it's dual problem are:
- If one problem has feasible solutions and a bounded objective function (eg. has a optimal solution), then so does the other. Both weak and strong duality are applicable.
- If one problem has feasible solutions and a unbounded objective function, then the other problem has no feasible solutions.
- If one problem has no feasible solutions, then the other has either no feasible solutions, or an unbounded objective function.
Applications
The number of constraint affects the computational effort far more than the number of variables.
So if m > n, the dual problem has less constraints (n) than the primal problem (m), hence the dual problem is faster to solve.
6.2 Economic Interpretation of Duality
Interpretation of the Dual Problem
The objective of the dual problem can be best interpreted as minimizing the total implicit value of the resources consumed by a activity, rather than allocated.
Table 6.6
The dual variableyi 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. Eg. the y*i values are the shadow prices.
In the dual problem m∑i=1 aijyi is interpreted as the current contribution of profit of the mix of resources that would be consumed if 1 unit of acitivity j were used ( j = 1, 2, ... , n)
W = m∑i=1 biyi can be viewed as minimizing the total implicit value of the resources consumed by the activities.
Recall that basic variables have a coefficient of zero in row 0. Therefore, we see that:
m∑i=1 aijyi = cj if xj > 0 (j = 1, 2, ...., n)
yi = 0 if xn+i > 0 (i = 1, 2, ...., m)
The first statement interprets as whenever an activity j operates at a strictly positive level (xj > 0) , the marginal value of the resources it consumes must equal the unit profit from this activity.
The second statement implies that the marginal value of the resource i is zero (yi = 0) whenever the supply of this resource is not exhausted by the activities (xn+i > 0). (Eg. a free good)
Interpretation of the Simplex Method
The goal of the simplex method is to find how to use the available resources in the most profitable feasible way.
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.
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
m∑i=1 aijyi
may be smaller than, larger than or equal to the unit profit cj obtainable from the activity.
If it is smaller, so that zj - c < 0 in row 0, then these resources can be used more profitably by initiating this activity.
If it is larger, so that zj - c > 0, then these resources are already used more profitably elsewhere.
If equal, there would be no change.
Comments