Dual and Primal

Dual and Primal
Rules:
1. If the primal contains n variables and m constraints, then the dual contains m variables and n constraints.
2. Max problem in the primal becomes minimization problem in the dual and vice versa.
3. The minimization problem has less or equal type constraints while minimization problem has greater or equal type constraints.
4. The constant coefficient a₁, a₂, … , a_n in the objective function of the primal will appear in the R.H.S of the constraints of the dual.
5. The constants b₁, b₂,…, b_n in the constraints of the primal will appear on the constant coefficient of the objective function of dual problem.
6. Variables of both problems are non-negative.

Properties of primal and dual:
1. The optimal value of the objective function of the primal is equal to the optimal value of the objective function of the dual i.e. Z_max = W _min
2. If the primal has an unbounded solution, the dual will not have a feasible solution & vice versa.
Theorem: The dual of dual is primal.
Proof:
Without loss of generality, we will restrict ourselves to primal lps in standard form.
Suppose the primal is
Maximize Z = c^Tx
such that Ax ≤ b, x≥0
Its dual is
Minimize W = b^Ty
such that. A^Ty ≥ C, y≥0
Which can be written in standard form
Maximize
-W = (-b)^Ty
such that. (-A)^Ty ≤ -C, y≥0
The dual of the dual is therefore,
Minimize Z = (-C)^Tx
such that. ((-A)^T)^Tx ≥ -b, x ≥ 0
But this is equivalent to
Maximize Z = c^Tx
such that Ax ≤ b, x≥0.
Hence the proof.