2

当我查看优化问题时，我看到了很多选项。一是线性规划。我从抽象的角度理解 LP 是如何工作的，但我发现很难看出一个特定的问题是否适合 LP。是否有任何启发式方法可以帮助指导这一决定？

例如，Is there a good way to do this type Mining 中描述的工作？我花了几周的时间才看到如何正确地构造问题。是否有可能“提前”知道问题可以由 LP 解决，而无需先看到“如何表达它”？

是否有我可以用来确定问题是否适合 LP 的清单？该主题是否有标准（可读）参考？

4

1 回答 1

7

启发式（和/或清单）来确定手头的问题是否真的是线性程序。

这是我的回答尝试，我也尝试概述我将如何解决这个问题。

表明给定问题适合表述为 LP/IP 的问题：

  1. 是否需要在不同的时间间隔定期做出决定？
  2. 是否有许多资源（工人、机器、车辆）需要分配任务？（时间、工作、目的地）
  3. 这是一个路由问题，必须访问不同的“点”吗？
  4. 这是位置还是“布局”问题？（整个切股问题都属于这一类）

对这些问题回答“是”意味着 LP 公式可能有效。

常见的LP问题包括：资源分配：（Assignment、Transportation、Trans-shipment、knapsack）、Portfolio Allocation、Job Scheduling和网络流问题。 这是一个很好的 LP 应用程序列表，适用于任何刚接触 LP 或 IP 的人。也就是说，实际上有 1000 多种不同类型的问题可以表述为 LP/IP。与我共事过的人（研究人员、同事）会产生直觉。他们擅长识别问题是某种类型的整数程序，即使他们不记得细节，然后他们可以查找这些细节。

为什么这个问题很难回答： 为什么要知道 LP 公式是否会削减它并不总是直截了当的原因有很多。

  1. 建模/制定方法中有很多“艺术”（主观性）。
  2. 经验有很大帮助。人们善于认识到这个问题可以“比作”另一个已知的公式
  3. 即使一个问题不是一个直接的 LP，也有许多巧妙的主从技术（子问题），或嵌套技术，使整体制定工作。
  4. 看起来像多个目标的东西可以组合成一个目标函数，并附加一组适当的权重。
  5. 经验丰富的建模者采用分解和约束松弛技术，然后对其进行补偿。

如何继续完成基本公式？

以下一直引导我朝着正确的方向前进。我通常首先列出决策变量、约束和目标函数。然后，我通常会在这三个之间进行迭代，以确保一切都“合适”。

所以，如果你手头有问题，问问自己：

  • 什么是决策变量 (DV)？ 我发现这始终是开始制定过程的好地方。DV的种类有多少？（哪个资源得到哪个任务，什么时候开始？）
  • 什么是约束？
    一些限制很容易看到。其他人则采取了一些戏弄。必须根据您的决策变量以及施加的任何常量/限制来编写约束。
  • 什么是目标函数？
    需要最大化或最小化的数量是多少？注意：有时，不清楚目标函数是什么。没关系，因为它很可能是一个约束满足问题。

一旦你认为你的 LP 公式已经完成，可以进行一些快速的健全性检查：

  1. 我总是尝试查看一个微不足道的解决方案（全 0 或全大数字）是否不是解决方案集的一部分。如果是，那么该公式很可能是不正确的。缺少一些约束。
  2. 确保每个约束都与决策变量“相关”。（我偶尔会发现只是“挂在那里”的约束。这意味着错过了“簿记约束”。）

根据我的经验，坚持下去的人几乎总是会培养出所需的直觉。希望这可以帮助。

于 2012-03-31T02:56:27.410 回答