什么是线性规划？

Question

我阅读了维基百科的文章，但似乎超出了我的理解范围。它说它是用于优化的，但它与任何其他优化方法有什么不同呢？

一个介绍线性规划的答案可以帮助我开始深入研究一些不太适合初学者的材料。

- Cam

---

简单来说，它就是将你的问题重写为一组线性方程，并解决这些方程。 - FrustratedWithFormsDesigner

这太荒谬了。这个问题根本不是离题的。 - Greg Kuperberg

投票以重新开放，因为这并不完全是离题的。 - BlueRaja - Danny Pflughoeft

LP算法或代码的讨论肯定是主题。可在Super User上讨论可用的LP系统也是主题。然而，关于LP作为一种方法的讨论在这里是不相关的，因为在几个非编程领域中同样（或更）适合讨论此话题。 - David Thornley

@David：所有已发布的答案都与算法和软件开发有关。即使问题是关于LP包，超级用户网站也没有意义，因为LP包通常被用作API，而不是终端用户软件。难道按照经验和常识来确定什么属于主题，而不是按公理和假设来确定，这不是更好吗？ - Greg Kuperberg

Answer 1

到目前为止，已经给出了线性规划的代数定义和操作定义。但是还有一种几何定义。一个“多胞形”是一个n维多边形（在二维）或多面体（在三维）的推广。“凸多胞形”是一个既是多胞形又是凸集的多胞形。按照定义，线性规划是一种优化问题，您希望在凸多胞形上最大化或最小化线性函数。

例如：假设您想购买一些红色沙子和蓝色沙子的组合。还假设：

1. 您不能购买任何一种负数数量。 2. 圆形只有300磅红色沙子和400磅蓝色沙子。 3. 同时，您的吉普车重量限制为500磅。

如果您用这些约束条件在平面上画图，它是一个凸五边形。然后，无论您希望优化什么（例如，沙子中的黄金总量），您都可以知道最佳解决方案（不一定是唯一的最佳解决方案）在多胞形的一个顶点。实际上，有一个更强的结果：即使在高维情况下，任何此类线性规划问题都可以在多项式时间内解决，与约束的数量或多面体的假定边数相同。请注意，并非每个约束都对应于一条边。如果约束是一个等式，则可能会减少多胞形的维度。或者，如果约束是一个不等式，则可能不会创建边，如果它已经由所有其他约束隐含。

有许多实际的优化问题是线性规划。其中一个最早的例子是“饮食问题”：给定一堆食物种类的菜单，什么是最便宜的均衡饮食？这是一个线性规划问题，因为成本是线性的，并且因为所有约束条件（维生素，卡路里，不能购买负数食品量的假设等）都是线性的。

然而，线性规划由于一项理论原因而更为重要。它是最强大的多项式时间优化算法之一，可用作近似解决其他优化问题的替代方法，也可作为确切解决它们的子程序。

是的，另外两个常见泛化方法是凸规划和整数规划。在一定条件下，凸规划可以像线性规划一样有效，只要目标（要最大化的东西）是线性的。事实证明，凸性是线性规划具有良好算法的主要原因，而不是其相邻边是平的。

另一方面，整数规划通常很难。例如，在示例问题中，如果您必须购买固定大小的袋装沙子而不是散装，则属于整数规划。有一个定理表明它可能是NP-hard。在实践中它有多么难取决于它与线性规划的接近程度。有一些著名的整数规划问题，其中所有线性规划的顶点都是整数点，这时您可以解决线性规划问题并且解将恰好是整数值。例如，婚姻问题，如何将n个男人和n个女人彼此结婚以最大化总幸福感。（或者是将n个城市分配给n个工厂，将n个工作岗位分配给n个求职者，将n台计算机分配给n台打印机等）

- Greg Kuperberg

Answer 2

线性规划是“数学规划”（也称为“数学优化”）的一个主题。与一般的数学规划不同，线性规划中的所有约束函数和目标函数都是关于它们的变量线性的。如果您想查看Dantzig的原始工作，请从这里开始；如果您想获得教材推荐，我建议使用这个。如果您想查找自己的资源，请从查找单纯形法开始——这是一种解决这些问题的非常常见的技术，或者是更少见但肯定是多项式时间复杂度的椭球法。虽然我没有全部阅读它，但快速浏览还建议从这里开始可能是个好地方。确保您最终阅读的内容涵盖了对偶性（也许特别是Farkas引理），因为这是大多数LP求解器的核心思想。

最自然的扩展要么是整数规划（类似于LP，但所有变量必须取整数值——即没有分数部分），要么是凸规划（可能是更一般的扩展）。可以在PDF形式下找到一本好的凸优化教材here。

- Jan Gorzny

Answer 3

正如其他人所说，线性规划是解决优化问题的一种方法，其中项是线性的。

了解LP解决的问题类型可能会有所帮助。

我用线性规划的一个例子是制定餐厅时间表。在餐厅中，您有技能集：

- 厨师 - 服务员 - 洗碗工 - 主持人 - 清洁工 - 经理等

您还有员工，每个员工都具有一个或多个技能集。每个员工也有特定的可用性。例如，Bob不能在星期天早上工作，因为他是当地教堂的牧师。员工还有相关的成本。 Bob可能是10.50美元/小时，而Suzy是5.15美元/小时。最后，员工可能有最低保证小时数。由于Bob已经是员工15年了，老板说他至少会得到35小时。

餐厅本身有需求。例如，它有3个班次：早晨，下午和晚上，每个班次都有一组人员配备要求：我们需要1名厨师，1名服务员，1名经理在早上，下午需要3名厨师，2名服务员，2名主持人，2名经理，在晚上需要4名厨师，4名服务员，3名主持人，2名经理，2名清洁工。每个班次都有一个持续时间，并且您可以通过将持续时间乘以员工的小时工资来计算每个班次的成本。

最后，我们有州和联邦法律以及一些基本的“业务”规则：没有员工能够工作超过8个小时而不加班费。没有员工可以安排少于2小时的班次（因为为了进行2个小时的班次而做出30分钟的通勤是很糟糕的），员工不能同时工作两个班次等。

现在，在满足所有这些要求的情况下，给我一个符合要求且产生最低劳动力成本的时间表。

这是线性规划优化问题的一个例子。

线性程序通常包括：

目标函数、变量、变量范围和约束条件。

由于我们想要最小化成本，因此我们的目标函数将涉及员工工作的班次和相关成本（班次持续时间*工资）。

在这种情况下，变量是每个员工可以工作的班次。

这些变量的范围是0到1之间的整数，因为员工要么在班次中工作（1），要么不在班次中工作（0）。顺便说一句，这是一个特殊的程序，称为二进制整数程序或BIP，因为所有变量都是整数（没有分数值），所有值都是0或1。

约束条件是基于上述要求的等式/不等式约束。

例如，如果Bob和Suzy都可以在早上担任厨师，那么 Bob_Morning_Cook1_Shift + Suzy_Morning_Cook1_Shift = 1 ，其中 Bob_Morning_Cook_Shift = {0,1} 和 Suzy_Morning_Cook_Shift = {0,1} 由上面提到的范围限制。这三个信息指定最多只能分配一个员工作为第一个早班厨师。

因此，一旦您定义了模型问题的所有约束条件，就可以开始解决问题。如果找到解决方案（根据约束条件，问题可能是无法实现的），它将给出产生最低周劳动力成本的员工分配。

- Alan

Answer 4

线性规划是一种优化技术，涉及线性约束和线性目标函数。约束用于限定问题空间，而目标函数是要尝试最小化（或最大化）以满足约束的内容。通常使用单纯形算法沿着约束交点的边缘进行遍历，以找到最小（或最大）值的目标函数，同时满足约束。

设置LP问题时，确保约束适当地限制了目标函数非常重要。可能会定义导致没有可能解决方案（例如x>1且-x>1）的约束。这是过度约束的情况。也可能会低估问题的约束条件（例如找到min x，使得x <1）。

- andand

---

我知道现在问题已经关闭，问这个可能没有意义，但是能否那位给我点踩的人解释一下为什么呢？谢谢。 - andand

Answer 5

线性规划的一个重要区别（或至少是其特征）是将约束建模为线性方程，即它们都采用c_1 x_1 + c_2 x_2...的形式。维基百科文章的标准形式部分对此进行了很好的概述。

另一个不同之处/特点是，线性规划旨在最大化（或最小化）一个函数 - 您无法有效地进行多目标优化。

- awshepard

---

难道最大化一个函数不是常态吗？ - Mathias

@Mathias - 或许这是常态，但并不是唯一存在的优化类型。 - awshepard

实际上，我很想听听你的想法！优化问题在数学上是某个函数的最小化，因为你不能同时最小化同一变量的2个函数，通常你最终会最小化这些函数中的单个函数（比如它们的加权组合...）。 - Mathias

@Mathias - 维基百科提到优化的“最简单情况”是最小化/最大化一个函数，然后链接到多目标优化页面。也许让我/我们的讨论感到困惑的是，我的一位教授曾将背包问题称为多目标优化问题（最小化重量，最大化价值）; 回想起来，它实际上只是在满足背包只能容纳一定数量的约束条件下最大化价值。 - awshepard

@Mathias（续）-多目标优化页面还提到了函数聚合方法，但是指出在选择权重方面它是主观的...显然我需要做更多的阅读来熟悉这些内容... :)。 - awshepard