Linear Programming Problem Duality
|
Primal |
Dual |
|---|---|
minimize:cTx subject to:Ax = b |
maximize:λTb subject to:λTA ≤ cT this is the asymmetric form of the duality relation. In this form the dual vector λ is not restricted to be non-negative |
Lemma 1 (Weak Duality Lemma)
If x and λ are feasible for Primal and dual, respectively, then cTx ≥ λTb
It means that the objective function value of the primal is always greater than or equal to the objective function value of the dual. In other words any feasible solution of the primal minimization problem is an upper bound on the dual maximization optimum. Similarly, any feasible solution of the dual maximization task is a lower bound on the primal minimization optimum
Example Primal Dual
|
Primal |
Dual |
|---|---|
minimize:2x1 + x2 + 4x3 subject to:x1 + x2 + 2x3 = 3 x1, x2, x3 ≥ 0 |
maximize:3b1 + 5b2 subject to:b1 + 2b2 ≤ 2 |