20

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

一个向我介绍线性编程的答案，这样我就可以开始深入研究一些初学者不太容易获得的材料，这将是最有帮助的。

4

5 回答 5

14

到目前为止的答案已经给出了线性规划的代数定义和操作定义。但也有一个几何定义。多面体是多边形（二维）或多面体（三维）的 n 维概括。凸多面体是一个多面体，它也是一个凸集。根据定义，线性规划是一个优化问题，您希望在其中最大化或最小化凸多面体上的线性函数。

例如：假设您想购买某种红沙和蓝沙的组合。还假设：

  1. 您不能购买任何一种负数。
  2. 仓库只有300磅的红沙和400磅的蓝沙。
  3. 此外，您的吉普车的重量限制为 500 磅。

如果你在平面上画出在这些限制下你可以买多少的图片，它就是一个凸五边形。然后，无论您想要优化什么（例如，沙子中的黄金总量），您都可以知道最优（不一定是唯一最优）位于多面体的一个顶点。事实上，有一个更强大的结果：即使在高维中，任何这样的线性规划问题都可以在多项式时间内、在约束的数量或多面体的假定边上解决。请注意，并非每个约束都对应于一侧。如果约束是一个等式，它可能会减少多面体的维度。或者，如果约束是不等式，如果它已经被所有其他约束隐含，它可能不会创建边。

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

但是，出于理论上的原因，线性规划更为重要。它是用于优化或任何其他目的的最强大的多项式时间算法之一。因此，它作为近似求解其他优化问题的替代方法以及精确求解它们的子程序非常重要。

是的，两个推广是凸规划和整数规划。有了一些限定，凸规划可以像线性规划一样工作，只要目标（最大化的东西）是线性的。事实证明，线性规划具有良好算法的主要原因是凸性，而不是平坦的边。

另一方面，整数编程通常很难。例如，假设在示例问题中，您必须以固定大小的袋子而不是散装购买沙子；那就是整数规划。有一个定理，它可以是 NP 难的。在实践中有多难取决于它与线性规划的接近程度。有一些整数规划问题的著名例子，其中，奇迹般地，线性规划的所有顶点都是整数点。然后你可以解决线性程序，解决方案恰好是积分。此类问题的一个例子是婚姻问题，即如何将 n 个男人和 n 个女人嫁给对方，以最大限度地提高总幸福感。（或者，n 个城市对 n 个工厂，n 个工作对 n 个申请人，n 个计算机对 n 个打印机，等等）

于 2010-07-26T19:43:47.180 回答
6

线性规划是“数学规划”的主题，也称为“数学优化”。线性程序与一般数学程序的不同之处在于，对于线性程序 (LP)，所有约束函数和目标函数相对于它们的变量都是线性的。

如果您想要 Dantzig 的原创作品，或者如果您想要一本教科书，我推荐这本，这里是一个不错的起点。如果您想查找自己的资源，请从查找Simplex 方法开始——这是解决这些程序的一种非常常见的技术，或者不太常见但绝对是多项式时间Ellipsoid 方法。虽然我还没有全部阅读，但快速浏览它也表明此PDF 可能是一个不错的起点。确保您最终阅读的任何内容都涵盖对偶性（可能特别是Farkas 引理），因为它是大多数 LP 求解器的中心思想。

最自然的扩展要么是整数程序（类似于 LP，但所有变量都必须采用整数值——也就是说，没有小数部分）要么是凸编程（也许是更一般的扩展）。一本好的凸优化教科书在此处以 PDF 形式提供。

于 2010-07-26T16:56:02.920 回答
4

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

这可能有助于了解 LP 解决了哪些类型的问题

我使用线性规划的一个例子是建立餐厅时间表。在餐厅你有技能：

  • 厨师
  • 服务器
  • 洗碗机
  • 主机
  • 巴瑟斯
  • 经理等

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

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

最后，我们有州和联邦法律，以及一些基本的“商业”规则：任何员工都不能在不加班的情况下工作超过 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}由于上面提到的界限。这三条信息指定最多只能分配一个员工作为第一个早晨厨师。

因此，一旦您定义了建模问题的所有约束，您就可以开始解决问题。如果可以找到解决方案（并且根据约束条件，问题可能不可行），它将为您提供每周劳动力成本最低的员工分配。

于 2010-07-26T17:24:10.070 回答
3

线性规划是一种涉及线性约束和线性目标函数的优化技术。编写约束是为了限制问题空间，而目标函数是您尝试最小化（或可能最大化）以满足约束的东西。单纯形算法通常用于沿着约束交点的边缘行走，以找到满足约束的目标函数的最小值（或最大值）。

在设置 LP 问题时，确保约束正确约束目标函数很重要。可以定义导致没有可能解决方案的约束（例如 x > 1 和 -x > 1）。这是过度约束。也可以对问题进行欠约束（例如，找到最小 x 使得 x < 1）。

于 2010-07-26T16:56:48.797 回答
1

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

另一个区别/特征是线性规划正在寻求最大化（或最小化）一个函数 - 你不能有效地进行多目标优化。

于 2010-07-26T16:48:24.713 回答