还是靠VBA来帮我计算最少用你多少根棍子吧

灰袍法师

三坛老窖 发表于 2012-9-18 21:14
好极了！期盼有个标杆。
就一维、一种原料规格的下料，我的程序有信心与国外的专业版软件作比试。

其实我的算法跟你差不多
每次只算一根原料的“最佳”方案
我的最佳定义是：用子函数给切割方案一个评估分
打分时综合考虑 较长产品优先，组合的产品数较少优先（实际上就是变相的较长产品优先），余料最小优先三个因素
靠参数控制这三个选择，实际效果虽然不错，但是计算结果的稳定性不够好，受参数影响很大
而现在我的改良重点是找出一个适合绝大多数情况的参数。
另一方面，我本来打算并不是用这个算法，不过写到一半测试一下，居然效果不错，就懒得再搞更复杂的了。
我本来的算法是：对所有原料种类，列出所有可行组合方案（或者说，一万个最好的组合方案）
然后根据要生产的产品，用牛顿法逐步逼近。
其实写程序不麻烦，麻烦的是测试，改良，再测试，再改良。。。。。。无限循环。。。。。。
对比两种算法就更加要命。

doryan

我做的方法大概是列出 所有的组合
然后计算所有组合对材料的需求数量 除以 每种材料的库存量 得出每种材料的珍稀程度 大概可以这么理解
越小越稀有 越大越优先使用 用这个来评分
其他大概和你们差不多
结果是1510根
速度则是慢多了 穷举组合方式非常耗时
代码就不发上来献丑了

灰袍法师

doryan 发表于 2012-9-19 11:56
我做的方法大概是列出 所有的组合
然后计算所有组合对材料的需求数量 除以 每种材料的库存量 得出每种材料 ...

我也想过这个做法
你不需要穷举所有组合
for i=1 to 所有产品
  for j=1 to 这个原料最多可以放多少个产品i
      生成包含j个产品的n个组合方案（我觉得生成10-100个即可）
   next j
next i

doryan

灰袍法师 发表于 2012-9-19 16:39
我也想过这个做法
你不需要穷举所有组合
for i=1 to 所有产品

嗯 是个好思路 这样代码速度提升很多
我用两次大循环写成函数
第一个函数 负责计算当前材料的组合
第二个函数 负责计算当前材料的稀缺程度 以及选择并生成一种切割方案

当第二个函数所有切割方案执行完毕后
判定当前材料种类是否减少了
没有减少则放宽切割的条件 减少了就调用第一个函数 重新计算可能的组合
知道所有切割完毕

结果还是比较理想的 速度是糟糕的
我去研究研究老酒的算法

很难想象一维就如此困难 二维 三维那怎么办。。。。

doryan

嗯？ 老酒的只是个结果 没有算法么。？
封在dll里了么....

pp9257

下面发个截图 。cad的插件 msteel  线形下料优化组合的界面

三坛老窖

灰袍法师 发表于 2012-9-18 22:01
其实我的算法跟你差不多
每次只算一根原料的“最佳”方案
我的最佳定义是：用子函数给切割方案一个评估 ...

关于最佳的定义，对整体方案而言，比较好办：如果不考虑整体方案采用的方式（即单根的切割方案）数和切割次数，直接用方案的材料利用率或需求根数来评判即可；如果考虑这两个因素，则将其折算为成本进行评判。该题的难点就在于对切割方式的评价，这是一个采用分层思想解此题而绕不开的难题。
我在最初采用【分层+穷举最优】思路解此题时就遇到这个问题，当两个方式的利用率相同时（设定利用率最大为最优），如何取舍？我尝试过使用如下3个标准：
1.先出现（或后出现）者为优；
2.给每个零件分配一个权重（与零件按长度排序的序次有关），计算两个方式的重量，以重量大者优先。（这与你的想法有些类似）
3.抽签，即随机选择
对于1、2 两个标准，有一个明显的缺陷，即对于给定的一组数据，只能得到唯一的整体方案。对于标准2，还有一个问题，就是你现在所面临的，如何找到一个分配权重的方法，使之能对所有数据都有较好的适应性。我觉得这是个更难的问题！反倒是标准3，多点几次运行按钮，往往能得到比用标准1和2更优的解。在47楼SM 59-22-314那组数据如果把切口宽度改为10mm，我当时用1和2的标准都只能得到59根的解，而用标准3，则有50%的概率能得到58根的结果。
我认为：我们现在所采用的解题方法，从整体来看，其实都是一种贪婪的思想。所以，通过选择合适的切割方式，以期一次性获得令人满意的整体“最优解”，是比较困难的。
而我47楼的思路，则绕开的这个难题。因为通过随机，可以提供较多的整体方案供评价。这样，问题就变成了如何快速的提供较优异的整体方案用于筛选。我目前对切割方式的评价很简单，就一个等式，指标=方式的有效长度+系数×方式最大可重复次数，系数与方式切换成本和单根原料成本关联。

灰袍法师

三坛老窖 发表于 2012-9-19 22:21
关于最佳的定义，对整体方案而言，比较好办：如果不考虑整体方案采用的方式（即单根的切割方案）数和切割 ...

我认为：我们现在所采用的解题方法，从整体来看，其实都是一种贪婪的思想。
================================================
我本来的想法跟doryan的差不多
生成一个保证可以切出全部产品的“方案库”，这一步很简单
然后从方案库选出切出全部产品，而且最好的方案组合，这一步就可以用上好多选择方法了。
不过，既然你的随机切都有这么高的利用率，倒是不必再研究其它切法了，呵呵。

附件是 0.2 beta 版 (稍微有点实用价值)
基本上需要三步走
1 设置左上角的 步长 为 2-20 的数值，大概找出最优解的放宽范围
然后把这个值填入B1，把搜索次数降低到10，步长改为2
放宽范围的意思是：选择原料切割方案的时候，并不一定选择余料最低的那个，而是满足 余料长度 小于 放宽范围 的方案，都进行评分，最后选最分的那个
2 评分就是把每个产品的权重加起来，权重打分目前靠人手估算
一般来说，给“较难处理”的产品一个较高的权重，权重取值 -100 到 500 之间，也不需要啰嗦到每个产品一个得分，先直接全部0，然后调整几个就可以了。
3 每次运行完毕，还是要靠人手估计哪些产品“是较难处理的”，再微调权重。
其实这三步靠程序做也可以，不过没找到一个较好的尝试算法之前，尝试全部组合的时间就太长了，不切实际。
一般来说，人手调整个2-3次就能找到比较好的解。
0.3 beta 版发布，本帖附件删除。

三坛老窖

doryan 发表于 2012-9-19 18:02
嗯？ 老酒的只是个结果 没有算法么。？
封在dll里了么....

呵呵，在你回帖这会儿，老酒正在喝老酒呢。
确实是封在dll里了，兄弟你可不要怪老酒小样，老酒这两天因为撞到如此大运，乐得还没有回过神来，还想独乐乐几天，等回过神来了，再拿出来与兄弟们众乐乐。不过，你说没有算法，就不对了，我觉得47楼，我已将算法描述的够清楚了，以你的功底，自己琢磨琢磨，写出来应该不是问题吧。

pp9257

你们都是大师……
线性的研究各位都差不多了，也很成熟了

有兴趣做二维的吗?