在m上規劃n個作業帶線性規劃的機器

Question

聽說您可以使用線性規劃來計劃問題。我並不真正瞭解如何做到這一點，因爲線性規劃是最優化的，並且大規模規劃（例如，在m臺機器上規劃n個作業）具有指數難度。

那麼我怎樣才能解決例如一個問題100個工作和10臺機器使用線性編程？你能給我一些解釋或進一步閱讀嗎？

Answer 1

那麼我該如何解決例如一個問題100個工作和10臺機器使用線性編程？

一般情況下，你不能。這不是線性規劃（LP）適用的那種規劃問題。

在LP問題中，您有一組要解決的變量。你有一組代表這些變量約束的線性不等式。而且，這些變量的線性函數（即沒有指數，沒有除法，不存在「if-then-else」等）表示給定解決方案的成本（或收益）。

如果您有這樣的問題，您可以使用LP來有效地生成最佳解決方案。車間調度，就像你問的那樣，不是那種問題。

LP傾向於適合「更高層次」的規劃。比如，我應該在每家工廠製造多少產品？在這樣的問題中，您通常可以將約束指定爲線性不等式，並將成本（或收益）指定爲線性函數，就像您必須執行以便使用LP一樣。請注意，我說「每件產品多少......」而不是「多少......」。因爲這是LP的另一個限制 - 變量必須能夠承擔真正的價值。如果您需要您的解決方案來提供整數解決方案，那麼您正在尋找整數編程（或混合整數編程）問題。