自力更生：钢筋下料组合优化正式版发布（一维）

aoe1981

　　问题来由：
　　lm1221发了一个帖子，叫做《优化组合》，其中提出了钢筋下料组合优化的问题，有很强的实际意义和理论意义，很是吸引人。链接如下：
　　http://club.excelhome.net/thread-1159602-1-1.html

　　解决方案：
　　对此问题，一开始我只有好奇，无力解决。给出完美解决方案是本论坛“神级大师”（群子言）灰袍法师，链接如下：
　　http://club.excelhome.net/forum. ... 1159602&pid=7903812
　　法师的帖子功能强大，可以解决的问题甚至超出了lm1221本来提出的问题，适应性极强。本来该问题应当就此打住，在高人面前不能造次了，但无赖“好奇害死猫”，我想一探其中的算理、算法。可是，读懂法师的附件对于我简直是“天书”！只有像群子这样同级别的大神，才可能探得精微，更何况，该解决方案也是群子发现、推荐并做了应用改良，改善了使用界面。向二位大神致敬！！！
　　然而，我一直在“不能不折腾”……
　　仔细品读香川做的三条注：

此程序算法代码为  Excel Home 神级大师【灰袍法师】原创、香川群子仅作实用化排版改进

①原料规格：可选多种(至少定一种)、按顺序对应其可用数量优先使用。

②产品需求：排除正好等于原料规格、以及剩余料小于最小规格的需求部分、写入框内。(无须排序)

③采用随机组合算法求接近最优解……可能会有多种方案可供选择。也不保证是最最优(99.9%是)

　　将思路放在了“随机”二字上，似乎自我发现了一些解决问题的眉目……

　　反复折腾，也做了一个出来。只是也顶多算是一个练手的、尝试的、学习的，因为有以下特点：
　　1.只支持一种规格的钢材原料，不支持多规格的，这与lm1221的原问题一致；
　　2.从随机入手，却没有实现随机，反倒依赖于原始数据从大到小的排序，准确应当称呼为：“排序＋小遍历”；
　　3.是否能得到较好的结果：没有经过大量不同类型数据的对比测试，不敢保证，就原帖数据，确实得到了……

　　发此帖目的：投石问路，我会抽时间在下面详述我的思路。

　　附件如下：
　　 钢筋下料优化（排序版）.rar (38.62 KB, 下载次数: 898)

2014-10-28 15:59 上传

点击文件名下载附件

　　实现了真正的随机算法的正式版附件如下：
　　 钢筋下料优化（正式版）.rar (48.36 KB, 下载次数: 2493)

2014-11-1 21:28 上传

点击文件名下载附件

　　（该附件值得下载，本帖其他附件（当然专指我的附件，不包括附带上传的法师的附件）不值一提，只是一种研究过程的记录，作为本问题的初学，还是可参考的）
　　关于该附件的详细介绍见16楼及以后：
　　http://club.excelhome.net/forum. ... 1161444&pid=7919929



　　附带末尾吹个牛：
　　我的正式版附件，在只有一种规格原材的情况下：
　　比法师的强！
　　备注：是说比法师的附件的部分功能强，不是比法师“一维下料”附件的全部，更不是比法师本人。在不被冤枉的前提下，愿意挨砖，更希望能得到法师的批驳！




补充内容 (2018-1-20 21:36):
我这个附件很低端，是随机算法，得到的结果不是最好的。建议您搜索灰袍法师、香川群子、三坛老窖……诸位大神的作品。

补充内容 (2018-1-20 21:37):
我这个附件很低端，是随机算法，得到的结果不是最好的。建议大家搜索灰袍法师、香川群子、三坛老窖……诸位大神的作品。

补充内容 (2018-1-20 21:37):
我这个附件很低端，是随机算法，得到的结果不是最好的。建议大家搜索灰袍法师、香川群子、三坛老窖……诸位大神的作品。

aoe1981

　　附件一角：
　　

aoe1981

首先说一下我的解决问题的核心思路：
我是以下料需求为出发点，以此确定最经济的原材供给量，类似“以销定产”。
而不是在原材的限制与下料需求的双重制约下，寻求可行并且经济的方案，这一点正是大神法师的附件可以完美胜任并解决的，说到此，太让人佩服了！
赞赞赞……无穷大……

aoe1981

我的附件有两大核心步骤，代码是分了4截的，更为详细一点，但就解决问题而言，主要是两步：
第一步：排除整料与准整料；
　　（所谓准整料，是我起的名字，意思就是说：与一根最短下料相加也会超出一根整料长度的下料规格，也即必须使用一根整料而无法与其他下料规格相搭配优化的下料规格）
第二步：可以搭配下料的组合优化。

aoe1981

如何理解“优化”？这涉及到我发明的两个核心概念：理想余料与余料方差。
优化的方案应当是：
1.在可能的情况下实现理想余料；
　　（　理想余料＝整料长度＊理想根数－下料总长度
　　　　理想根数＝roundup(下料总长度/整料长度,0)　）
2.余料方差最大。
　　（余料方差最大的意思，说成白话就是：余料尽量余大料，也即尽量减少余料根数）


备注：
　　如果理想余料不可能实现，则下一个较理想的可实现的余料是：
　　理想余料＋整料长度＊1

　　再下一个是：
　　理想余料＋整料长度＊2


　　依次类推……

aoe1981

上楼的“理想”二字，可以进一步形象地想像成：当准备下料时，先把所有的原材焊接起来，然后逐一按下料规格进行再切割，此时余料自然最小……呵呵，当然这是不可能的……
不过，理想余料可以通过搭配下料的方式实现，这就是寻求最优组合，但是也有些情况是注定实现不了的，于是又有一个概念：实现余料。
实现余料＝理想余料＋整料长度＊n
（上述式子中的n，应当为小于下料根数一半的数。呵呵，关于这句结论，我不提供理论证明，我是在具体数据的研究、测试中发现的，属于一个猜测……）

aoe1981

　　下面，给出一组数据说明“余料方差”最大时的方案寻优：

	根数	余料	第1段	第2段	第3段	第4段	第5段	第6段	第7段
整料	2	0	9000
准整料	1	100	8900
准整料	1	500	8500
搭配料一	4	0	6350	2650
	2	0	6000	3000
	1	0	3000	1000	1000	1000	1000	1000	1000
	1	2650	6350
	余料方差	7022500	=SUM(C5:C8^2)
搭配料二	4	0	6350	2650
	2	0	6000	3000
	1	1000	3000	1000	1000	1000	1000	1000
	1	1650	6350	1000
	余料方差	3722500	=SUM(C11:C14^2)
搭配料三	4	0	6350	2650
	2	0	6000	3000
	1	2000	3000	1000	1000	1000	1000
	1	650	6350	1000	1000
	余料方差	4422500	=SUM(C17:C20^2)

aoe1981

　　楼上列出的三种方案都实现了以下数据下的“理想余料”，但余料方差不太相同：

序号	下料长度	数量/根
1	9000	2
2	8900	1
3	8500	1
4	1000	6
5	2650	4
6	6350	5
7	6000	2
8	3000	3

　　可以想见的是：余料方差越大，则余料越集中，根数相对越少，对整料的占用就少……
　　（因此，上楼的方案“搭配料一”更为优化一些……）
　　我想，虽然我是钢筋下料这方面的外行，这样是比较经济的……
　　至此，我想，我完成了什么叫做“优化方案”的衡量指标的数学化……
　　这点想来还是让人头脑清楚一些的……

aoe1981

　　下面是一组极端数据，可以说明：实现余料与理想余料之间的关系：

序号	下料长度	数量/根
1	4510	1
2	4510	1
3	4510	1
4	4510	1
5	4510	1
6	4510	1
7	4510	1
8	4510	1
下料总长	36080
理想根数	5	=ROUNDUP(B10/9000,0)
理想余料	8920	=B11*9000-B10
实现根数	8
实现余料	35920	=B14*9000-B10
关系	35920＝8920+9000*3
3为小于下料根数8的一半

aoe1981

　　下面是一组与灰袍法师附件《一维下料》对比的测试图：
　　对比数据如下：

序号	下料长度	数量/根
1	1200	6
2	2650	3
3	6350	5
4	6000	1
5	3000	4

　　法师结果图：
　　

　　aoe1981结果图：
　　

　　可见，两个结果一致。
　　法师的附件，随机搜索次数我调到了1000，应该是比较大的一够数字，搜索还是比较充分的……

　　当然，得需要更多的样本数据，不是随手乱写的，最好是来自生产实践的……