钢筋搭配最优方案

三坛老窖

1588078/37 发表于 2017-8-17 18:29
代码?????????????

你是要学习算法还是要使用此类软件解决实际问题？

如果是学习，EH中有许多帖子在讨论这个问题，你搜一下就是了。
我认为最有深度的帖子是：
http://club.excelhome.net/thread-920256-1-1.html
其中法师的代码是公开的，且十分优异。我刚才试了下，你这组数据用法师的代码可获得12米×1523的解（搜索次数1000，耗时37秒）。这个结果已经优于大部分国内的商用软件。沿着该帖，你似乎可遍历有关讨论该问题的所有帖子。
如果是要使用此类软件解决实际问题，百度一下“一维下料”等，能搜到一大堆解决此问题的商用软件，你下载几个试用下就是了。

weiqigreen

用lingo求解的结果：






根据优化的结果，仅使用12M的钢筋即可达到最优结果。当然，实际中可能有9M库存而不得不用的情况，还需要加另外的结束条件。

aimisiyou

weiqigreen 发表于 2017-8-18 00:43
用lingo求解的结果：

你是将所有切割方案都考虑进来得到这个结果吗？但那样处理量就太大了。若限定余料，虽然方案数量大大减少加快处理速度，但不知会不会将最优解给漏掉。

三坛老窖

weiqigreen 发表于 2017-8-18 00:43
用lingo求解的结果：

lingo能出这结果，果然名不虚传。不知lingo求得此结果，速度如何？

总用量18228000（12×1519；9×20+12×1504）这结果，我也可求得，不过有些费劲（耗时在100秒左右），且最长余料不如你这个结果。

三坛老窖

这是一组国内某知名软件几年前用于演示的数据，当时该软件能获得的最好结果是1882，耗时大约在90秒左右。
我测试过，在大约相当的耗时前提下，法师的代码可获得1879的结果。
国际上有个CutLogin 1D的软件，是我见过的最好的软件，其能获得的最好结果也是1879
当年法师一再推荐的GoNest 1D，在这组数据前就弱爆了。
诸位有兴趣的大侠，不妨用自己的代码测试下这组数据，看看能达到什么程度。

棒料数据				49	零件数据		1		零件数据		2		零件数据		3
序号	长度	可用量	单价		序号	长度	需求量		序号	长度	需求量		序号	长度	需求量
1	6000	1000	100.00		1	386	24		21	1286	24		41	2586	24
					2	476	96		22	1376	24		42	2686	24
					3	486	608		23	1386	392		43	2786	24
					4	506	24		24	1476	1188		44	2886	4
					5	536	32		25	1486	54		45	2926	12
切口宽度：0					6	576	872		26	1586	24		46	2936	20
					7	586	210		27	1676	192		47	2986	8
					8	606	624		28	1686	54		48	3076	32
					9	636	40		29	1776	24		49	4386	4
					10	686	140		30	1786	112
					11	706	2		31	1876	1746
					12	736	6		32	1886	72
					13	776	304		33	2036	40
					14	791	24		34	2076	64
					15	886	134		35	2086	100
					16	906	48		36	2176	96
					17	1026	96		37	2186	64
					18	1036	64		38	2206	32
					19	1176	698		39	2476	88
					20	1186	120		40	2486	48

weiqigreen

aimisiyou 发表于 2017-8-18 08:02
你是将所有切割方案都考虑进来得到这个结果吗？但那样处理量就太大了。若限定余料，虽然方案数量大大减少 ...

理论上，9米和12米一共有1400多种切割方式，也就是1400多个变量。依旧相当快，出乎我的意料，可能是模式很简单的原因。
从求解状态可看出，变量数1475个，迭代了141次就找到了Global optimal solution ，用时仅1秒。可见lingo相当强大。
PS:电脑是I5处理器，8G内存，win10 64bit，lingo11，64位版。

weiqigreen

三坛老窖 发表于 2017-8-18 12:01
lingo能出这结果，果然名不虚传。不知lingo求得此结果，速度如何？

总用量18228000（12×1519；9×20+ ...

1S，迭代141步，见26楼图。
请问：法师的代码写在哪里了，我得拜读拜读！

三坛老窖

weiqigreen 发表于 2017-8-18 12:53
1S，迭代141步，见26楼图。
请问：法师的代码写在哪里了，我得拜读拜读！

法师的代码在21楼链接中

cbtaja

一楼附件中的数据，用9m和12m两种长度的钢筋混合开料，手工排料结果，利用率达    99.956%
排料结果.rar (58.3 KB, 下载次数: 20)

2017-8-21 19:24 上传

点击文件名下载附件

cbtaja

一维排料辅助工具（半自动）：
http://club.excelhome.net/thread-1364206-1-1.html