Primal/Dual Problems
Associated with every
LP problem, which will be referred to a primal problem,
there is a corresponding dual problem. See Section 3.5.1
in the text. In a certain way, the dual problem is a transposition
of the primal problem. This is meant to imply that if the primal problem
is a minimization problem the dual problem will be a maximization one. If
the primal problem has nvariables, the dual problem will have n constraints.
If the primal problem has mconstraints, the dual problem will have mvariables.
For the discussion of duality, the standard primal problem is generally defined
as a maximization problem with <= inequalities (though the
standard problem in the LP programming discussion was a minimization problem
see 3.10  3.12 and the constraints were equalities).
The standard primal problem (normal
maximum problem) in this section is defined as:
Maximize 

Subject to:


Side Constraints


The dual of the above problem (normal
minimum problem) is defined as:
Minimize 

Subject to:


Side Constraints


The primal/dual pair enjoy the following properties in problem
formulation:
 The number of dual
variables is the same as the number of primal constraints
 The number of dual
constraints is the same as the number of primal variables
 The coefficient
matrix A of the primal problem is transposed to provide the coefficient
matrix of the dual problem
 The inequalities
are reversed in direction
 The maximization
problem of the primal problem becomes a minimization problem in the dual
problem
 The cost coefficients
of the primal problem become the right hand sides of the dual problem. The
right hand side values of the primal become the cost coefficients in the
dual problem
 The primal and
dual variables both satisfy the non negativity condition.
For more details see
Example 3.5 in the text.
The primal/dual problem
also share many relationships in their solution:
1.
The primal and dual problem have the same value for the optimal objective
function. This is however true only if the problems have optimal solutions.
2. If x is any feasible solution to the primal
problem, and y is any feasible solution to the dual problem,
then w(y) >= z(x). This feature provides an estimate
of the bounds of the dual optimal value if a feasible primal solution
is known. This results also holds for the reverse case when a feasible dual
is known.
3. If the primal problem is unbounded, the dual problem
is infeasible. The unbounded problem implies that the objective function
value can be pushed to infinite limits. This happens if the feasible domain
is not closed. Of course practical considerations will limit the objective
function value to corresponding limits on the design variables. The inverse
relationship holds too. If the dual problem is unbounded, the primal is infeasible.
4. If the ith primal constraint is an equality constraint,
the ith dual variable is unrestricted in sign. The reverse holds too. If
the primal variable is unrestricted in sign, then the dual constraint is
an equality.
5. Obtaining primal solution from dual solution:
(i) If the ith dual constraint is a strict inequality,
then the ith primal variable is nonbasic (for optimum solutions only).
(ii) if the ith dual variable is basic, then the ith
primal constraint is a strict equality.
6. Recovering primal solution from final dual Table:
When the primal and dual problems are in the standard form, the value of
the ith primal variable equals the reduced coefficient (that is the coefficient
in the last row of the final table) of the slack/surplus variable associated
with the ith dual constraint.
7. If a ith dual variable is nonbasic, the value
of its reduced cost coefficient is the value of the slack/surplus variable
of the corresponding primal constraint.
8. Obtaining Dual Solution from Primal Solution:
When the primal and dual problems are in the standard form, the value of
the ith dual variable equals the reduced coefficient (that is the coefficient
in the last row of the final table) of the slack/surplus variable associated
with the ith primal constraint.
9. If a ith primal variable is nonbasic, the value
of its reduced cost coefficient is the value of the slack/surplus variable
of the corresponding dual constraint.