optimization - 如何确定何时使用线性编程？

Question

当我查看优化问题时，我会看到很多选择。一种是线性编程。我用抽象的术语理解了LP的工作原理，但是我发现很难看到一个特定的问题是否适合LP。是否有任何启发式方法可以帮助指导这一决策？

例如，Is there a good way to do this type of mining?中描述的工作花了几周的时间才明白如何正确构造问题。是否可以“事先”知道LP可以解决问题，而无需首先看到“如何表达”？

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

Answer 1

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

这是我的回答尝试，并且我也尝试概述如何解决此问题。

指示给定问题的问题适合用LP / IP表示：


是否需要在不同的时间间隔定期做出决定？
是否需要分配大量资源（工人，机器，车辆）？ （小时，工作，目的地）
这是一个路由问题，必须访问不同的“点”吗？
这是位置还是“布局”问题？ （整个类别的库存削减问题都属于这一类）


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

常见的LP包括：资源分配：（分配，运输，转运，背包），资产组合分配，作业计划和网络流问题。
Here's a good list of LP Applications适用于LP或IP新手。
就是说，实际上有数千种不同类型的问题可以表述为LP / IP。与我一起工作的人（研究人员，同事）形成了一种直觉。他们擅长识别问题是某种类型的Integer程序，即使他们不记得详细信息，然后可以查询这些细节。

为什么这个问题很难回答：
有很多原因为什么并不总是很直接地知道LP配方是否会削减它。


建模/制定方法中有很多“艺术”（主观性）。
经验有很大帮助。人们擅长认识到此问题可以“比喻”为另一个已知的表述
即使问题不是直接的LP，也有许多巧妙的主从技术（子问题）或嵌套技术可以使整个公式起作用。
看起来很多个目标可以合并为一个目标函数，并附加一组适当的权重。
经验丰富的建模人员会采用分解和约束松弛技术，然后对其进行补偿。


如何继续完成基本配方？

以下内容始终将我引向正确的方向。我通常首先列出决策变量，约束和目标函数。然后，我通常会在这三个对象之间进行迭代，以确保所有内容都适合。

因此，如果您遇到问题，请问自己：


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


一旦您认为LP配方已完成，可以进行一些快速的健全性检查：


我总是尝试看看是否有一个简单的解决方案（全0或全大
数字）不属于解决方案集。如果是，则
提法很可能是不正确的。一些约束是
失踪。
确保每个约束都与“相关”
决策变量。 （我偶尔会发现
只是“闲逛”。这意味着“簿记约束”
已经错过了。）


以我的经验，坚持这一原则的人几乎总是会发展所需的直觉。希望这可以帮助。