我應該使用哪種優化算法來使利潤最大化並具有時間限制？

我想找到一個合適的算法來解決這個問題：我應該使用哪種優化算法來使利潤最大化並具有時間限制？

假設我們有N個項目，我們知道我們需要多少錢每個項目掙錢，這是多少時間需要對每一個項目做（估計每個項目的時間）。我們有一定的時間來完成所有項目。我們希望選擇項目，使我們的利潤最大化，整體預計時間不超過可用時間。你能告訴我應該使用哪種優化算法嗎？在C＃，.NET技術或Java技術中，有沒有可以使用的東西？

來源

2011-07-08 mismas

取決於N.這是一個真正的問題，還是一個練習？如果這是一個真正的問題，我懷疑你的N會大到不能排除所有可能的組合的強力搜索。 – mbeckish

我喜歡用C＃程序替換所有管理的一般想法，但不清楚你在問什麼，或者這與編程有什麼關係。請舉例說明輸入和所需輸出。 –

@現實世界中的暴力蠻力對於這些類型的優化幾乎總是不切實際 – cordialgerm

這聽起來像直截了當Knapsack problem：

給定一組項目，每一個權重和的值，確定每個項目的計數的集合中所包含的，使得總重量爲小於或等於給定的限制，並且總值儘可能大。

在你的情況下，重量是項目所需的時間，而限制是時間限制。

通常情況下，如果你是對現實世界中這樣做，那麼蠻力就能滿足小的情況下，並與一些隨機貪婪逼近應該是好足夠的大情況下，如果你真的不關心準確的最大。但是，我懷疑是否有人會爲現實世界使用這樣一個嚴格的模型。

在理論興趣的情況下，揹包問題是NP難的，並且是一個活躍的算法領域。

來源

2011-07-08 19:44:35

謝謝大家的快速回復。這不是一個現實世界的問題，它是一個練習。我有輸入文件，其中包含這些信息：項目數量和可用時間，預計時間和每個項目的收益列表。我想創建一個輸出文件，其中包含最大的利潤和將完成的項目數量，以及將完成哪些項目。 – mismas

@mismas您可以查看：http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf這是一本關於0-1揹包問題的演講幻燈片，來自TU/e，其中Dijkstra工作:) –

你在找什麼叫做Knapsack problem。

在您的情況下，「重量」限制是時間限制，並且該值是值。

來源

2011-07-08 19:44:42

簡化，這看起來像加權http://en.wikipedia.org/wiki/Knapsack_problem。你的時間將是項目的規模和你的體重將是你的成本

來源

2011-07-08 19:45:24 dfb

從運籌學的角度來看這個問題，你正在尋找一些混合整數程序（MIP）。揹包問題的方法可能是足夠的，但沒有得到更多的細節問題，我不能提出更詳細的公式。

一旦你決定了你的公式，有幾個C＃解決方案可用於解決MIP。 Microsoft有一個Microsoft Solver Foundation，您可以查看該解決方案是否能夠解決簡單的MIP並且具有良好的C＃API IBM最近購買了可用於開發MIP公式的OPL優化包（被認爲是業界領先的）。一旦你有了OPL提供的.NET API，你可以調用它來運行你的模型。

自己走了OPL路線，我會盡量避免使用OPL .NET API，因爲它們非常麻煩。如果你的問題很簡單，你可能想要考慮解決方案的基礎，因爲它提供了一個現代和清潔的API相比OPL

來源

2011-07-08 19:57:56 cordialgerm

我應該使用哪種優化算法來使利潤最大化並具有時間限制？

回答

相關問題