2010-10-12 40 views
0

我應該用什麼樣的算法來解決這個問題?我應該使用什麼算法來最大限度地提高生產計劃中的資源利用率?

Ore is blended in a particular ratio to produce metal with the desired quality characteristics. The ore is blended in batches of 5, the batches are to be mixed in a particular ratio that will maximize ore utilization as well as produce an output of the desired quality. 
1. A batch of ore contains 30 or more minerals 
2. The percentage proportion of each mineral within a batch is known 
3. Batches blended with each other should produce a product meeting a criteria such as 
    0.5 < m1 < 0.52 
    0.2 < m2 < 0.21 
    a3 < m3 < b3 
    .... 
    .... 
    a30 < m30 < b30 
    where m1, m2, m3 ... m30 are percentage presence of ore in the final product and a1,a2...a30;b1,b2...b30 are tolerable limits within which quality is maintained 
4. In what order should n batches (n <= 20) be processed to maximize ore output 
5. In what ratio should the batches be blended so that quality is maintained 

這聽起來已經足夠讓人們解決這個問題,但它超出了我有限的算法知識範圍。任何解決這個問題的指針都非常感謝。

回答

2

這是在混合整數規劃(MIP),它位於線性規劃(LP)的頂部哭出來。 LP部分(實際變量的線性不等式)通常通過使用單純形算法來解決。 MIP部分處理整數約束(例如,哪個順序最好?)。這些都不是你想從頭開始實施的事情!在這個領域已經有很多幾十年的發展,並且有一流的解決方案。考慮用於商業解決方案的CPLEX或用於免費解決方案的SOPLEX。如果您是.NET類型的用戶,請查看微軟的Solver Foundation。

希望這會有所幫助。

1

它看起來好像你應該開始看linear programming。有很多軟件包可以解決這些問題,像Matlab或Mathematica這樣的通用系統也具備這些功能,或者您可以使用自己喜歡的語言編寫自己的代碼(如果您感覺幸運的話)。

這並不完全清楚你的問題是嚴格線性的,所以你可能不得不閱讀這個主題,但它是開始學習優化問題的好地方。

相關問題