|
|
|
|
linear programming
|
(Topic)
|
|
|
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
Here $c^Tx$ 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 $({\ref{eq:primal}})$ is the LP
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 $\hat{x}$ is feasible (i.e. lies in the feasible region) for $(\ref{eq:primal})$ and $\hat{y}$ is feasible for $(\ref{eq:dual})$ , then $c^T\hat{x}\le\hat{y}^Tb$ . This follows readily from the above: $$ c^T\hat{x}\le(\hat{y}^TA)\hat{x}=\hat{y}^T(A\hat{x})\le y^Tb $$ 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 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.
- 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.
|
"linear programming" is owned by mathcam. [ full author list (2) | owner history (1) ]
|
|
(view preamble | get metadata)
See Also: duality in mathematics
| Also defines: |
linear programming problem, objective function, feasible region, feasible |
| Keywords: |
linear programming |
|
|
Cross-references: ellipsoid, polynomial-time, running, polynomial time, algorithm, consequence, strong, theorem, duality, convex polyhedron, primal, polyhedron
There are 15 references to this entry.
This is version 9 of linear programming, born on 2003-06-16, modified 2006-10-13.
Object id is 4369, canonical name is LinearProgrammingProblem.
Accessed 14239 times total.
Classification:
| AMS MSC: | 90C05 (Operations research, mathematical programming :: Mathematical programming :: Linear programming) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
