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.
