artificial-intelligence - 使用线性规划在 m 台机器上规划 n 个工作

Question

我听说你可以使用线性规划来解决规划问题。我真的不明白如何做到这一点，因为线性规划是最优的，并且大规模规划（例如在 m 台机器上规划 n 个工作）具有指数难度。

那么我如何使用线性编程解决例如 100 个工作和 10 台机器的问题？你能给我一些解释或进一步阅读吗？

Answer 1

那么我如何使用线性编程解决例如 100 个工作和 10 台机器的问题？

一般来说，你不能。这不是线性规划（LP）适用的那种规划问题。

在 LP 问题中，您有一组要求解的变量。您有一组表示这些变量的约束的线性不等式。而且，您拥有代表给定解决方案的成本（或收益）的那些变量（即，没有指数、没有除法、没有“if-then-else”等）的线性函数。

如果你有这样的问题，你可以使用 LP 来有效地生成最优解。车间调度，就像你问的那样，不是那种问题。

LP倾向于将自己用于“更高级别”的计划。比如，我应该在每个工厂生产多少每种产品？在这样的问题中，您通常可以将约束指定为线性不等式，将成本（或收益）指定为线性函数，正如您必须这样做才能使用 LP。请注意，我说的是“每种产品有多少……”而不是“有多少……”。因为这是 LP 的另一个限制——变量必须能够取真实值。如果您需要您的解决方案来提供整数解决方案，那么您正在查看整数规划（或混合整数规划）问题。