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 n-variables, the dual problem will have n- constraints. If the primal problem has m-constraints, the dual problem will have m-variables. 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 primal objective
Subject to:
 primal constraints
Side Constraints
 primal side constraints

The dual of the above problem (normal minimum problem) is defined as:
Minimize dual objective
Subject to:
 dual constraints
Side Constraints
 duall side constraints

The primal/dual pair enjoy the following properties in problem formulation:
  1. The number of dual variables is the same as the number of primal constraints
  2. The number of dual constraints is the same as the number of primal variables
  3. The coefficient matrix A of  the primal problem is transposed to provide the coefficient matrix of the dual problem
  4. The inequalities are reversed in direction
  5. The maximization problem of the primal problem becomes a minimization problem in the dual problem
  6. 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
  7. 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 non-basic (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 non-basic, 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 non-basic, the value of its reduced cost coefficient is the value of the slack/surplus variable of the corresponding dual constraint.