线性规划数学

线性规划，一种数学建模技术，其中，当受到各种约束时，线性函数将最大化或最小化。这项技术对于指导商业计划，工业工程以及（在较小程度上）社会科学和物理科学中的定量决策很有用。

优化：线性编程

尽管现在已广泛用于解决日常决策问题，但线性编程在1947年之前还是相对未知的。没有任何意义的工作

。

线性规划问题的解决方案简化为找到线性表达式（称为目标函数）的最优值（取决于问题，最大或最小）

受到一系列表示为不平等的约束的约束：

a，b和c是由问题的能力，需求，成本，利润以及其他要求和限制所确定的常数。应用此方法的基本假设是，需求与可用性之间的各种关系是线性的。也就是说，x _i的任何一个都不提高到1的幂。为了获得该问题的解，有必要找到线性不等式系统的解（即，n个值的集合）同时满足所有不等式的变量x _i）。然后通过将x _i的值代入定义f的方程式来评估目标函数。

线性规划方法的应用最早是在1930年代后期由苏联数学家Leonid Kantorovich和美国经济学家Wassily Leontief分别在制造计划和经济学领域进行尝试的，但数十年来一直被忽略。在第二次世界大战期间，线性编程被广泛用于处理运输，计划和资源分配，但要受到成本和可用性等某些限制。这些应用极大地建立了该方法的可接受性，并在1947年引入了美国数学家George Dantzig的单纯形法，进一步简化了线性规划问题的求解，从而进一步推动了该方法的发展。

但是，随着尝试着涉及更多变量的越来越复杂的问题，必要的操作数量呈指数增长，甚至超过了功能最强大的计算机的计算能力。然后，在1979年，俄罗斯数学家Leonid Khachiyan发现了多项式时间算法，其中计算步骤的数量是变量数量的幂而不是指数形式的幂，因此可以解决迄今无法解决的问题。但是，在实际应用中，Khachiyan的算法（称为椭球法）比单纯形法慢。1984年，印度数学家Narendra Karmarkar发现了另一种多项式时间算法，即内部点方法，该方法与单纯形法相比具有竞争优势。