algorithm - 我应该使用什么算法来最大化生产计划中的资源利用率？

Question

我应该用什么样的算法来解决这个问题？

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

这听起来很主流，足以让某人解决它，但它超出了我有限的算法知识范围。非常感谢任何解决此问题的建议。

Answer 1

这迫切需要混合整数规划 (MIP)，它位于线性规划 (LP) 之上。 LP 部分(实变量上的线性不等式)通常使用单纯形算法求解。 MIP 部分处理整数约束(例如，什么顺序最好？)。这些都不是您想要从头开始实现的东西!这个领域已经有很多很多年的发展，并且可以使用一流的解决方案。考虑将 CPLEX 用于商业解决方案或将 SOPLEX 用于免费解决方案。如果您是 .NET 类型，请查看 Microsoft 的 Solver Foundation。

希望这对您有所帮助。