在m上规划n个作业带线性规划的机器

Question

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

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

Answer 1

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

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

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

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

LP倾向于适合“更高层次”的规划。比如，我应该在每家工厂制造多少产品？在这样的问题中，您通常可以将约束指定为线性不等式，并将成本（或收益）指定为线性函数，就像您必须执行以便使用LP一样。请注意，我说“每件产品多少......”而不是“多少......”。因为这是LP的另一个限制 - 变量必须能够承担真正的价值。如果您需要您的解决方案来提供整数解决方案，那么您正在寻找整数编程（或混合整数编程）问题。