Ara*_*ram 6 architecture algorithm linear-programming
我一直在编写软件来解决业务问题.我在浏览其中一篇SO帖子时遇到了LIP.我用谷歌搜索,但我无法解释如何使用它来解决业务问题.感谢是否有人可以帮助我理解外行.
ILP 基本上可用于解决涉及做出一系列决策的任何问题，每个决策只有几种可能的结果，所有结果都是提前已知的，并且其中任何选择组合的整体“质量”都可以使用函数来描述这并不取决于选择之间的“相互作用”。要了解其工作原理，最简单的方法是进一步限制只能为 0 或 1（整数的最小有用范围）的变量。现在：
例如，假设您有 3 名工人：Anne、Bill 和 Carl，以及 3 份工作：除尘、打字和包装。所有的人都可以完成所有的工作，但每个人在每项工作上都有不同的效率/能力水平，因此我们希望找到每个人执行的最佳任务，以最大限度地提高整体效率。我们希望每个人只执行一份工作。
设置此问题的一种方法是使用 9 个变量，每个变量对应工人和工作的每种组合。如果 Anne 应该在最优解中除尘，则变量 x_ad 的值为 1，否则为 0；如果Bill应该Pack在最优解中，x_bp将得到值1，否则为0；等等。
接下来要做的就是制定一个我们想要最大化或最小化的目标函数。假设根据 Anne、Bill 和 Carl 最近的绩效评估，我们有一个包含 9 个数字的表，告诉我们他们每个人完成这 3 项工作需要多少分钟。在这种情况下，取所有 9 个变量的总和是有意义的，每个变量乘以该特定工人执行该特定工作所需的时间，并寻求最小化这个总和——也就是说，最小化完成该任务所需的总时间。完成所有工作。
最后一步是给出约束条件，强制执行 (a) 每个人都只做 1 份工作，以及 (b) 每项工作都由 1 个人完成。（请注意，实际上这些步骤可以按任何顺序完成。）
为了确保 Anne 恰好完成 1 份工作，我们可以添加 x_ad + x_at + x_ap = 1 的约束。可以为 Bill 和 Carl 添加类似的约束。
为了确保恰好有 1 个人除尘，我们可以添加 x_ad + x_bd + x_cd = 1 的约束。可以为 Typing 和 Packing 添加类似的约束。
总共有 6 个约束。现在，您可以将这个 9 变量、6 约束问题提供给 ILP 求解器，它会返回最佳解决方案之一中的变量值 - 其中正好有 3 个为 1，其余为 0。 3=1 告诉你哪些人应该做哪些工作！
事实上，这个特定问题具有特殊的结构，可以使用不同的算法更有效地解决它。使用 ILP 的优点是可以轻松合并问题的变体：例如，如果实际上有 4 个人，只有 3 份工作，那么我们需要放宽约束，以便每个人最多做1 份工作，而不是恰好有 1 份工作。 1 份工作。这可以简单地通过将前 3 个约束中的等号更改为小于或等于号来表达。