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

李嘉图0513

手动吧，编程解决也未必最佳，还麻烦！

lee1892

灰袍法师 发表于 2012-9-23 20:19
啊哈
列出所有方案，然后 线性求解 是可行的
我用理论最佳797的数据测试

法师，Lingo 11.0 里
LINGO 11.0\Programming Samples\Excel\Staffdll.xls
这个文件，为什么说Lingo11.dll文件未找到？
我复制了一个到SYSTEM32，而且这个DLL也不能用REGSVR32来注册
另外，用的是网上下的破解版吧

法师一维下料v3的测试数据（老窖797），DLL编译调用

次数	材料用量	方案数	利用率	最大余料	用时
100	800	39	98.92%	509	44.47
100	800	43	98.92%	350	44.19
100	800	46	98.92%	1650	43.83
100	799	49	99.04%	2418	45.45
100	800	45	98.92%	657	43.65
100	800	53	98.92%	1839	44.64
100	800	46	98.92%	1825	44.28
100	800	49	98.92%	1715	44.36
100	799	46	99.04%	280	43.92
100	800	43	98.92%	350	44.3
100	800	46	98.92%	1883	43.47
100	800	43	98.92%	350	44.7
100	800	43	98.92%	1118	42.39
100	800	39	98.92%	414	43
100	800	43	98.92%	350	44.08
100	800	46	98.92%	1445	43.39
100	800	43	98.92%	2725	44.6
100	800	45	98.92%	2415	42.44
100	799	50	99.04%	425	43.58
100	800	43	98.92%	241	44

次数	材料用量	方案数	利用率	最大余料	用时
1	801	50	98.80%	2445	0.25
2	800	43	98.92%	350	0.48
3	800	43	98.92%	350	0.77
4	800	43	98.92%	350	1.05
5	800	43	98.92%	350	1.42
6	800	43	98.92%	350	1.81
7	800	43	98.92%	350	2.28
8	800	43	98.92%	350	2.75
9	800	43	98.92%	350	3.25
10	800	43	98.92%	350	3.8
11	800	43	98.92%	350	4.34
12	800	43	98.92%	350	4.66
13	800	43	98.92%	350	5.01
14	800	43	98.92%	350	5.3
15	800	43	98.92%	350	5.69
16	800	43	98.92%	350	6.08
17	800	43	98.92%	350	6.51
18	800	43	98.92%	350	6.98
19	800	43	98.92%	350	7.65
20	800	43	98.92%	350	7.95

lee1892

灰袍法师 发表于 2012-9-22 04:37
0.3 beta 版
什么参数都取消了，扔到程序内部随机生成
本版最大改变是

你这个一维下料的代码，我把get_raw改为多种原材料随机选取长度，以对应原材料资源可认为无限的情况，我再仔细看看代码，把那个可用数量改为可选项，应该就蛮好用了，哈哈。。。嗯，应该可以不用Lingo了，编译成DLL应该速度足够了，嘿嘿

1. Public Function get_raw() As Long
   
2. Dim i As Long, j As Long
   
3. 'For i = 1 To UBound(raw_num)
   
4. '    If raw_num(i) > 0 Then
   
5. '        get_raw = i
   
6. '        Exit For
   
7. '    End If
   
8. 'Next
   
9. get_raw = Int(UBound(raw_num) * Rnd + 1)
   
10. End Function

复制代码

法师一维下料v3的测试数据（老窖797），DLL编译调用，曾经出现过搜200次800用量41方案的，未记录具体方案。。。

搜索	材料用量	方案数	利用率	最大余料	用时
10	800	43	98.92%	350	3.95
20	800	43	98.92%	350	8.37
30	800	43	98.92%	350	13.29
40	800	43	98.92%	350	18.02
50	800	43	98.92%	350	23.08
60	800	53	98.92%	444	27.57
70	800	43	98.92%	350	32.68
80	800	45	98.92%	1165	36.08
90	800	43	98.92%	350	41.52
100	799	50	99.04%	225	45.99
100	800	50	98.92%	2725	45.19
100	799	47	99.04%	1226	46.34
100	800	43	98.92%	350	46.7
100	800	45	98.92%	743	46.64
100	800	52	98.92%	425	46.17
200	800	48	98.92%	1999	94.68
200	799	51	99.04%	1831	93
200	800	48	98.92%	1257	91.09
200	799	50	99.04%	1831	95.17
200	800	49	98.92%	1257	92.77

综上数据，法师的V3版的评分标准是控制方案数最少，从其低次数搜索结果的稳定性来看，效率应该较老窖的办法更高一些。对于单一原材料长度，增加搜索次数对结果没有明显的帮助。

lee1892

灰袍法师 发表于 2012-9-22 04:37
0.3 beta 版
什么参数都取消了，扔到程序内部随机生成
本版最大改变是

solve subset sum 里用到的 relax range 变量改为
原材料长 ÷ 最长产品
原材料长 ÷ 最短产品
之间的随机数，search个10次内就能得到798数量44方案的解了，呵呵

法师，你自己设定的参数不合适啊。。。
直接VBA的测试数据，编译成DLL应该快一倍以上。。。

次数	材料用量	方案数	利用率	最大余料	用时
10	799	51	99.04%	1031	6.54
10	800	55	98.92%	2120	7.2
10	798	40	99.17%	145	5.45
10	798	47	99.17%	680	6.14
10	799	53	99.04%	2415	7.7
10	800	46	98.92%	2286	6.16
10	798	50	99.17%	790	6.25
10	798	45	99.17%	940	5.52
10	799	53	99.04%	2127	6.31
10	799	50	99.04%	2422	5.81

楼上老窖，你改用法师的吧，应该比你的靠谱的多。。。呵呵
法师原来还是用的FFD(First Fit Decreasing)的方法啊。。。对于多种材料用随机选取的办法不好，应该选选得。。。

也传一个结果，法师的代码优化后，搜索10次，798用料+39方案。。。

三坛老窖

持续改善确实是一个提高产品质量的法宝。
老窖的一维下料代码也在改善中，目前的状态是：797这组数据已能找到797的最优解（原以为不存在的），找到798的解，一般在1s左右；能适应多种原料规格。
目前老窖正在探究二维的问题，lee1892老兄之字典神贴中的关系网思路，在此问题中似乎有用武之地。

lee1892

三坛老窖 发表于 2012-12-4 23:23
持续改善确实是一个提高产品质量的法宝。
老窖的一维下料代码也在改善中，目前的状态是：797这组数据已能找 ...

嗯，我刚接触这类背包问题。看你之前的完全随机的做法，明显会很分散。法师这里用的应该属于BFD(Best Fit Decreasing)的一种优化方式。感觉他那个求子集的过程有不少的优化空间。

我有时间再仔细琢磨琢磨，他在里头用了不少莫名其妙的常量，还没弄明白都哪冒出来的～～

另外，如果考虑通用性的话，应该考虑同根材料切不同长度的成本，比如我这不同方案的成本反而很低。再有就是余料也可以卖钱的～～

我打算就在法师的基础上改了，成本代码初步工作，慢慢改进好了～～

2维的我这用不大上，就不费脑细胞了，呵呵。

wuxinyun1999

lee1892 发表于 2012-12-4 23:58
嗯，我刚接触这类背包问题。看你之前的完全随机的做法，明显会很分散。法师这里用的应该属于BFD(Best Fit ...

哈哈,没看这个贴,兄弟也是牛人.不过这块我用不上
这次就是从那个帖子来顶你的.

incognito

27 楼的数据，最优是： 193

incognito

68楼，2维的解：78。

Not sure global or local.

qby740

手动吧，编程解决也未必最佳，还麻烦！