请输入您要查询的字词:

 

单词 LinearProgramming
释义

linear programming


A linear programming problem, or LP,is a problem of optimizing a givenlinear objective function over some polyhedron. The standardmaximization LP, sometimes called theprimal problem, is

maximizecTx
s.t.Axb(P)
x0

Here cTx is the objective function and the remaining conditionsdefine the polyhedron which is the feasible region over which theobjective function is to be optimized. The dual of((P)) is the LP

minimizeyTb
s.t.yTAcT(D)
y0

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 x^ is feasible (i.e. lies in the feasible region) for((P)) and y^ is feasible for ((D)),then cTx^y^Tb. This follows readily from the above:

cTx^(y^TA)x^=y^T(Ax^)yTb.

The strong duality theorem states that if both LPs are feasible,then the two objective functions have the same optimal value. As aconsequence, ifeither LP has unbounded objective function value, the other mustbe infeasible. It is also possible for both LP to be infeasible.

The simplex methodMathworldPlanetmath (http://planetmath.org/SimplexAlgorithm) of G. B. Dantzig isthe algorithmMathworldPlanetmathmost commonly used to solve LPs; in practice it runs in polynomial timeMathworldPlanetmath,but the worst-case running time is exponential. Two polynomial-timealgorithms for solving LPs are the ellipsoid method of L. G. Khachianand 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 andalgorithms, Springer-Verlag, 2002.
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 20:14:34