(New page: Every linear programming problem, referred to as a primal problem, can be converted in a dual problem, which provides an upper bound to the optimal value of the primal problem. In matrix f...) |
|||
| Line 1: | Line 1: | ||
| − | Every linear programming problem, referred to as a primal problem, can be converted in a dual problem, which provides an upper bound to the optimal value of the primal problem. In matrix form, we express the primal problem as: | + | Every linear programming problem, referred to as a primal problem, can be converted in a dual problem, which provides an upper bound to the optimal value of the primal problem. In matrix form, we express the primal problem as: |
| − | Maximize | + | Maximize <math>c^Tx</math> |
| − | Subject to | + | Subject to <math>Ax \geq b, x\geq 0</math> |
| − | The corresponding dual problem is: | + | The corresponding dual problem is: |
| − | Minimize | + | Minimize <math>b^Ty</math> |
| − | Subject to | + | Subject to <math>A^Ty\geq c, y\geq 0</math> |
| − | Where y is used instead of x as the variable vector. | + | Where y is used instead of x as the variable vector. |
There are two ideas fundamental to duality theory. One is the fact that the dual of a dual linear program is the original primal linear program. Additionally, every feasible solution for a linear program gives a bound on the optimal value of the objective function of its dual. | There are two ideas fundamental to duality theory. One is the fact that the dual of a dual linear program is the original primal linear program. Additionally, every feasible solution for a linear program gives a bound on the optimal value of the objective function of its dual. | ||
Latest revision as of 09:06, 31 March 2008
Every linear programming problem, referred to as a primal problem, can be converted in a dual problem, which provides an upper bound to the optimal value of the primal problem. In matrix form, we express the primal problem as:
Maximize $ c^Tx $
Subject to $ Ax \geq b, x\geq 0 $
The corresponding dual problem is:
Minimize $ b^Ty $
Subject to $ A^Ty\geq c, y\geq 0 $
Where y is used instead of x as the variable vector.
There are two ideas fundamental to duality theory. One is the fact that the dual of a dual linear program is the original primal linear program. Additionally, every feasible solution for a linear program gives a bound on the optimal value of the objective function of its dual.
