m1k*_*1k4 2 algorithm optimization computer-science operations-research
我们说的是金属制品厂.有一种机器可以将长铁棒切割成较小的部件,这些部件后来用于制造各种产品.
例如,我要求生产以下长度和数量的棒:2件248毫米,5件1150毫米,6件2843毫米,3件3621毫米.
那是分区输出.
在输入侧,我有(例如)3个2500mm的条,2个5000mm的条,6个8000mm的条和3个10000mm的条.
我应该找到一种如何最佳地切割输入条的方法 - 切割后的其余部分(其余部分太小而不能使用)应尽可能小.
我创建了算法,只需创建所有可能的组合,然后在其中选择最好的组合.代码有效,但只要输入和输出稍微大一点,计算就可以持续很长时间,所以我必须找到解决问题的新方法.
你有什么提示吗？
您的问题是运筹学中非常常见的问题.看看 切割库存问题.这个问题基本上是NP难的,因为你已经想到了自己.它不能很好地扩展.
怎么解决？在能够找出模型之后,最好调用一些混合整数编程求解器.我之前使用过LPSolve 5.5
可能有一些简单的算法,您可以编写特别是处理此问题的代码.当您需要添加作者未想到的一些辅助约束时,通常会出现这些算法的问题.MIP求解器是更通用的工具.