Linear programming

In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear.

Duality

Every linear programming problem, referred to as a primal problem, can be converted into an equivalent dual problem. In matrix form, we can express the primal problem as:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: maximize mathbf{c}^T mathbf{x}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: subject to mathbf{A}mathbf{x} le mathbf{b}, , mathbf{x} ge 0

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The equivalent dual problem is:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: minimize mathbf{y}^T mathbf{b}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: subject to mathbf{y}^T mathbf{A} ge mathbf{c}^T, , mathbf{y} ge 0

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

where y is used instead of x as variable vector.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~