如何决定何时使用线性编程？

Question

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

例如,描述的工作是否有一种很好的方法来进行这种类型的挖掘？花了几周才看到如何正确地解决问题.是否有可能"提前"知道LP可以解决问题,而不首先看到"如何表达它"？

有没有我可以用来确定问题是否适合LP的清单？是否有针对此主题的标准(可读)参考？

Answer 1

启发式(和/或检查表)来确定手头的问题是否真的是一个线性程序.

这是我尝试回答的问题,我也试图概述我是如何解决这个问题的.

表明特定问题适合制定为LP/IP的问题:

1. 是否需要在不同的时间间隔定期进行决策？
2. 是否有许多资源(工人,机器,车辆)需要分配任务？(小时,工作,目的地)
3. 这是一个路由问题,必须访问不同的"点"吗？
4. 这是一个位置还是"布局"问题？(整类切割问题属于这一类)

对这些问题回答是,这意味着LP配方可能有效.

常见的LP包括:资源分配:(分配,运输,转运,背包),投资组合分配,作业调度和网络流量问题. 对于刚接触LP或IP的人来说,这是一个很好的LP应用程序列表.也就是说,实际上有1000种不同类型的问题可以表述为LP/IP.我与之合作的人(研究人员,同事)培养了一种直觉.他们善于认识到问题是某种类型的整数程序,即使他们不记得细节,然后他们可以查找.

为什么这个问题很难回答: 有很多原因导致为什么LP制剂会削减它并不总是直截了当.

1. 在建模/制定方法中存在许多"艺术"(主观性).
2. 经验帮助很大.人们善于认识到这个问题可以被"比作"另一个已知的公式
3. 即使问题不是直接的LP,也有许多聪明的主从技术(子问题)或嵌套技术使整个配方工作.
4. 看似多个目标的内容可以组合成一个目标函数,并附加一组适当的权重.
5. 经验丰富的建模人员采用分解和约束放松技术,然后对其进行补偿.

如何继续完成基本配方？

以下总是引导我朝着正确的方向前进.我通常首先列出决策变量,约束和目标函数.然后我通常在这三个中进行迭代,以确保一切"适合".

所以,如果您手头有问题,请问自己:

• 什么是决策变量(DV)？ 我发现这始终是开始制定过程的好地方.有多少种类型的DV？(哪个资源获取哪个任务,何时开始？)
• 有什么约束？
  一些限制很容易看到.其他人则稍微挑逗一下.必须根据决策变量和强加的任何常数/限制来编写约束.
• 什么是目标函数？
  需要最大化或最小化的数量是多少？注意:有时候,目标函数是什么并不清楚.这没关系,因为它很可能是一个约束满足问题.

一旦您认为您的LP配方完成,您将进行几次快速的完整性检查:

1. 我总是试着看一个简单的解决方案(全0或全部大数字)是不是解决方案集的一部分.如果是,那么配方很可能是不正确的.缺少一些约束.
2. 确保每个约束与决策变量"相关".(我偶尔会发现只是"挂在那里"的约束.这意味着错过了" 簿记约束 ".)

根据我的经验,坚持下去的人几乎总是发展所需的直觉.希望这可以帮助.