线性规划

线性规划，有时也称为线性优化，是在由线性和非负约束指定的凸多面体上最大化或最小化线性函数的问题。 简单来说，线性规划是基于一组约束，使用线性数学模型来优化结果。

线性规划在 Wolfram 语言 中实现为LinearProgramming[c, m, b]，它找到一个向量 ，该向量在约束条件 和 (对于 ) 下最小化数量 。

线性规划理论属于 凸优化理论 范畴，也被认为是 运筹学 的重要组成部分。 线性规划广泛应用于商业和经济学，但也可以用于解决某些工程问题。

经济学方面的例子包括里昂惕夫的投入产出模型、影子价格的确定等；商业应用的一个例子是在一家工厂中最大化利润，该工厂使用相同的原材料和资源制造多种不同的产品；工程应用示例包括切比雪夫逼近和结构设计（例如，平面桁架的极限分析）。

线性规划可以使用 单纯形法（Wood 和 Dantzig 1949，Dantzig 1949）求解，该方法沿可视化实体的 多面体棱边 运行以找到最佳答案。 Khachian (1979) 找到了一个 多项式时间 算法。 Karmarkar (1984) 找到了一个效率更高的 多项式时间 算法。 这种方法穿过实体的中间（使其成为所谓的 内点法），然后进行变换和扭曲。 可以说，早在 1960 年代，以内点法形式存在的屏障函数方法就已为人所知，但伴随 Karmarkar 宣布而来的媒体炒作使这些方法受到了极大的关注。

变量只能取整数值的线性规划被称为 整数规划。

在电视剧《数字追凶》(NUMB3RS) 第 4 季的开篇剧集“信任度量”（2007 年）中，数学天才 Charlie Eppes 使用了短语“你不需要 Karmarkar 算法”来表示“你不需要成为火箭科学家就能知道……”。