linear programming
A linear programming problem, or LP, is a problem of optimizing a given linear objective function over some polyhedron. The standard maximization LP, sometimes called the primal problem, is
maximize | ${c}^{T}x$ | |||
s.t. | $Ax\le b$ | (P) | ||
$x\ge 0$ |
Here ${c}^{T}x$ is the objective function and the remaining conditions define the polyhedron which is the feasible region over which the objective function is to be optimized. The dual of $(\mathit{\text{(P)}})$ is the LP
minimize | ${y}^{T}b$ | |||
s.t. | ${y}^{T}A\ge {c}^{T}$ | (D) | ||
$y\ge 0$ |
The linear constraints for a linear programming problems define a convex polyhedron, called the feasible region for the problem. The weak duality theorem states that if $\widehat{x}$ is feasible (i.e. lies in the feasible region) for $(\mathit{\text{(P)}})$ and $\widehat{y}$ is feasible for $(\mathit{\text{(D)}})$, then ${c}^{T}\widehat{x}\le {\widehat{y}}^{T}b$. This follows readily from the above:
$${c}^{T}\widehat{x}\le ({\widehat{y}}^{T}A)\widehat{x}={\widehat{y}}^{T}(A\widehat{x})\le {y}^{T}b.$$ |
The strong duality theorem states that if both LPs are feasible, then the two objective functions have the same optimal value. As a consequence, if either LP has unbounded objective function value, the other must be infeasible. It is also possible for both LP to be infeasible.
The simplex method^{} (http://planetmath.org/SimplexAlgorithm) of G. B. Dantzig is the algorithm^{} most commonly used to solve LPs; in practice it runs in polynomial time^{}, but the worst-case running time is exponential. Two polynomial-time algorithms for solving LPs are the ellipsoid method of L. G. Khachian and the interior-point method of N. Karmarkar.
References
- 1 Chvátal, V., Linear programming, W. H. Freeman and Company, 1983.
- 2 Cormen, T. H., Leiserson, C. E., Rivest, R. L., and C. Stein, Introduction to algorithms, MIT Press, 2001.
- 3 Korte, B. and J. Vygen, Combinatorial optimization: theory and algorithms, Springer-Verlag, 2002.
Title | linear programming |
Canonical name | LinearProgramming |
Date of creation | 2013-03-22 13:41:41 |
Last modified on | 2013-03-22 13:41:41 |
Owner | mathcam (2727) |
Last modified by | mathcam (2727) |
Numerical id | 12 |
Author | mathcam (2727) |
Entry type | Topic |
Classification | msc 90C05 |
Synonym | LP |
Related topic | DualityInMathematics |
Defines | linear programming problem |
Defines | objective function |
Defines | feasible region |
Defines | feasible |