Monday, June 15, 2015

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 a1, a2, … , an in the objective function of the primal will appear in the R.H.S of the constraints of the dual.
5. The constants b1, b2,…, bn 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. Zmax = 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 = cTx
such that Ax ≤ b, x≥0
Its dual is
Minimize W = bTy
such that. ATy ≥ 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 = cTx
such that Ax ≤ b, x≥0.
Hence the proof.

No comments:
Write comments

Hey, we've a very popular astronomy portal in Bangla language. If You know Bangla, You'll like it - sky.bishwo.com
Join Our Newsletter