线性规划

线性规划一种数学建模技术，在这种技术中，一个线性函数在不同的条件下得到最大化或最小化约束．这种技术在指导商业计划中的量化决策方面非常有用工业工程在较小的程度上，在社会而且物理科学．

线性规划问题的解简化为寻找线性表达式的最优值(最大或最小，取决于问题本身)目标函数）不平等的:受一组用不等式表示的约束的:

的一个的年代,b的年代,c是由问题的能力、需求、成本、利润以及其他要求和限制所决定的常数。应用这种方法的基本假设是，需求和可得性之间的各种关系是线性的;也就是说，没有一个x_我取非1的幂。为了得到这个问题的解，必须求出线性方程组的解不平等(即的集合n变量的值x_我同时满足所有不等式)的值进行代入，对目标函数进行评估x_我在这个方程中f．

线性规划方法的应用最早是在20世纪30年代末由苏联数学家认真尝试的列昂尼德•Kantorovich美国经济学家瓦西里•里昂惕夫在生产进度和经济学但他们的工作被忽视了几十年。在二战期间，线性规划被广泛用于处理运输、调度和资源分配受某些限制，如成本和可用性。这些应用证明了该方法的可接受性，并取得了进一步的进展动力1947年随着美国数学家的引入乔治Dantzig的单纯形法，极大地简化了线性规划问题的求解。

然而，随着涉及更多变量的复杂问题越来越多，必要操作的数量呈指数级增长，甚至超过了最强大的计算能力电脑．1979年，这位俄国数学家Leonid Khachiyan发现了一个多项式时间算法在这种方法中，计算步数的增长是变量数量的幂，而不是指数增长，因此可以解决迄今为止无法解决的问题。然而,Khachiyan的算法(称为椭球法)在实际应用中比单纯形法速度慢。1984年，印度数学家纳伦德拉·卡马卡发现了另一种多项式时间算法内点法与单纯形法相比具有一定的竞争力。