6

我一直在编写软件来解决业务问题。我在浏览其中一篇 SO 帖子时遇到了 LIP。我用谷歌搜索了它，但我无法说明如何使用它来解决业务问题。感谢有人可以帮助我用外行的方式理解。

4

6 回答 6

2

首先，从维基百科阅读一个线性规划示例

现在想象一下生产猪和鸡的农民，或者生产烤面包机和真空吸尘器的工厂——现在输出（可能还有约束）是整数，所以这些漂亮的图表将逐步弯曲。这是一个很容易表示为线性规划问题的业务应用程序。

我之前使用整数线性规划来确定如何平铺 n 个相同比例的图像以最大化用于显示这些图像的屏幕空间，并且形式主义可以代表诸如调度之类的覆盖问题，但整数线性规划的业务应用程序似乎更自然的应用程序其中。

SO 用户 flolo 说：我经常遇到的用例：在数字电路设计中，您需要将对象放置/映射到芯片的某些部分（FPGA 放置）——这可以通过 ILP 来完成。同样在 HW-SW 协同设计中经常会出现分区问题：程序的哪一部分应该仍然在 CPU 上运行，哪一部分应该在硬件上加速。这也可以通过 ILP 解决。

于 2011-09-30T07:12:26.567 回答
2

ILP 基本上可以用来解决任何涉及做出一系列决策的问题，每个决策只有几个可能的结果，所有这些都是提前知道的，并且可以使用函数来描述任何选择组合的整体“质量”这不依赖于选择之间的“交互”。要了解它是如何工作的，最简单的方法是进一步限制只能为 0 或 1（最小的有用整数范围）的变量。现在：

  • 每个需要是/否答案的决定都成为一个变量
  • 目标函数应该将我们想要最大化（或最小化）的事物描述为这些变量的加权组合
  • 您需要找到一种方法来使用一个或多个线性等式或不等式约束来表达每个约束（不能同时做出的选择的组合）

例子

例如，假设您有 3 个工人 Anne、Bill 和 Carl，以及 3 个工作（除尘、打字和包装）。所有的人都可以做所有的工作，但是每个人在每个工作中都有不同的效率/能力水平，所以我们希望为每个人找到最好的任务，以最大限度地提高整体效率。我们希望每个人只执行一项工作。

变量

解决此问题的一种方法是使用 9 个变量，每个变量对应工人和工作的组合。如果 Anne 应该在最优解中 Dust，则变量 x_ad 的值为 1，否则为 0；如果 Bill 应该在最优解中打包，x_bp 将获得值 1，否则为 0；等等。

目标函数

接下来要做的是制定一个我们想要最大化或最小化的目标函数。假设根据 Anne、Bill 和 Carl 最近的绩效评估，我们有一个包含 9 个数字的表格，告诉我们他们每个人完成 3 项工作中的每一项需要多少分钟。在这种情况下，取所有 9 个变量的总和是有意义的，每个变量乘以该特定工人执行该特定工作所需的时间，并寻求最小化这个总和 - 即最小化花费的总时间完成所有工作。

约束

最后一步是给出强制执行（a）每个人只做一份工作和（b）每份工作都由一个人完成的约束。（请注意，实际上这些步骤可以按任何顺序完成。）

为了确保 Anne 只做 1 份工作，我们可以添加约束 x_ad + x_at + x_ap = 1。可以为 Bill 和 Carl 添加类似的约束。

为了确保恰好 1 个人 Dusts，我们可以添加约束 x_ad + x_bd + x_cd = 1。可以为 Typing 和 Packing 添加类似的约束。

总共有 6 个约束。您现在可以将这个 9 变量、6 约束问题提供给 ILP 求解器，它会吐出最优解之一中变量的值——其中 3 个为 1，其余为 0。 3即1告诉你哪些人应该做哪些工作！

ILP 是通用的

碰巧的是，这个特定问题具有特殊的结构，可以使用不同的算法更有效地解决它。使用 ILP 的优点是可以很容易地合并问题的变体：例如，如果实际上有 4 个人，只有 3 个工作，那么我们需要放宽约束，以便每个人最多做1 个工作，而不是完全1 份工作。这可以简单地通过将第一个 3 个约束中的每个约束中的等号更改为小于或等号来表示。

于 2011-09-30T12:33:49.970 回答
1

示例 ILP 问题将类似于：

  • 最大化37∙x1 + 45∙x2

在哪里

  • x1,x2,... 应该是正整数

...但是，表格中有一组约束

  • a1∙x1+b1∙x2 < k1
  • a2∙x1+b2∙x2 < k2
  • a3∙x1+b3∙x2 < k3
  • ...

现在，对 Wikipedia 的示例进行更简单的表述：

  • 一个农民有L m² 的土地可以种植小麦或大麦或两者的组合。
  • 农夫有F克化肥和P克杀虫剂。
  • 每平方米小麦需要F1克肥料和P1克杀虫剂
  • 每平方米大麦需要F2克肥料和P2克杀虫剂

现在，

  • 令a1表示每 1 平方米小麦的售价
  • 令a2表示每 1 平方米大麦的售价
  • 令x1表示要种植小麦的土地面积
  • 让x2表示要种植大麦的土地面积
  • x1,x2是正整数（假设我们可以种植 1 平方米的分辨率）

所以，

  • 利润是a1∙x1 + a2∙x2 - 我们想要最大化它
  • 因为农民的土地面积有限：x1+x2<=L
  • 因为农民的肥料量有限：F1∙x1+F2∙x2 < F
  • 因为农夫的杀虫剂数量有限：P1∙x1+P2∙x2 < P

a1,a2,L,F1,F2,F,P1,P2,P - 都是常数（在我们的示例中：正）

我们正在寻找正整数x1,x2，它们将在给定约束的情况下最大化所述表达式。

希望清楚...

于 2011-09-30T07:33:20.163 回答
1

ILP“本身”可以直接建模很多东西。如果您搜索 LP 示例，您可能会发现很多著名的教科书案例，例如饮食问题

给定一组药丸，每种药丸都有维生素含量和每日维生素配额，找到与配额相匹配的最便宜的鸡尾酒。

许多这样的问题自然会有要求 varialbe 是整数的实例（也许你不能将药丸分成两半）

真正有趣的是，实际上大量的组合问题都归结为 LP。我最喜欢的一个是分配问题

给定一组 N 个工人、N 个任务和一个 N×N 矩阵，描述每个工人为每个任务收取多少费用，确定给每个工人什么任务以最小化成本。

大多数自然出现的解决方案都具有指数复杂性，但存在使用线性规划的多项式解决方案。

对于 ILP，ILP 具有 NP 完全性的额外好处/困难。这意味着它可以用来建模非常广泛的问题（布尔可满足性在这方面也很流行）。由于那里有许多优秀且经过优化的 ILP 求解器，因此将 NP 完全问题转换为 ILP 通常是可行的，而不是设计自己的自定义算法。

于 2011-09-30T13:56:57.493 回答
0

您可以在任何想要优化的地方轻松应用线性规划，并且目标函数是线性的。你可以制定时间表（我的意思是大，比如火车公司，他们需要优化车辆和轨道的利用率）、制作（优化胜利），几乎所有东西。有时很难将您的问题表述为 IP 和/或有时您会遇到解决方案的问题，即您必须生产例如 0.345 辆汽车才能获得最佳胜利。这当然是不可能的，所以你的限制更多：你的汽车数量变量必须是整数。即使现在听起来更简单（因为你的变量选择更少），它实际上更难。在这一刻，它变得 NP-hard。这实际上意味着您可以使用 ILP 从计算机上解决任何问题，您只需对其进行转换。

对于您，我建议您阅读一些基本的 (I)LP 内容。在我看来，我不知道有什么好的在线网站（但如果你用谷歌搜索，你会找到一些），作为一本书，我可以推荐Chvatal的Linear Programming。它有很好的例子，也描述了真实的用例。

于 2011-09-30T07:44:48.087 回答
0

这里的其他答案有很好的例子。使用整数规划和更普遍的运筹学的两个黄金标准是

  1. INFORMS（运筹学与管理科学研究所）出版的期刊 Interfaces
  2. Franz Edelman 运筹学和管理科学成就奖得主

Interfaces 发表的研究使用运筹学应用于现实世界的问题，而 Edelman 奖是一个极具竞争力的奖项，用于表彰运筹学技术在商业上的应用。

于 2013-03-19T17:22:06.547 回答