大家好！不知道有没有人跟我探讨一下B题的结果！

suisg

<>大家好！我做的是B题，不知道大家有没有兴趣跟我探讨一下结果，我的结果为：一维切割需要用板：801个，板材利用率：99.5%，其中割缝算做有效部分，需要61个板。二维结果为457板，板材利用率97.93%，采用的是基于滚动的贪婪算法（一二维问题均这样）。不知道大家的结果怎么样，也不知道大家觉得我的结果如何？</P>

suisg

<>为什么没人回贴？</P>

[此贴子已经被作者于2004-9-22 14:33:08编辑过]

wendua

我的结果每个比你少用1块，呵呵，方法和你的差不多，都是贪婪法。

suisg

郁闷啊！我们的时间太紧了，最后部分的优化结果不好，你是怎么用的贪婪法啊？我们是一部分一部分的算的，前部分的结果不好了，就再加进几个零件，你呢？

afook

<>我们的第一题已达理论最优，799根原材料即可，唯一可惜在第二题用错了数量</P><>我们采用的是列生成算法，是个不错的算法！</P>[em03]

suisg

<>列生成算法？能不能具体介绍一下？是不是把所有可能的排列方式写成列的形式，然后再列出规划方程求解啊？另外，根据估算，最理想的情况也不过是797根啊，而且还需要考虑工期，楼上的大哥是不是……</P>
<>能否详细介绍一下？</P>

afook

<>列生成算法是目前在国外比较热门和先进的算法，在求解NP难问题中常常可以达到近似最优，相应的文章国外的论文有很多，而国内则相对少很多，在google上查询"delayed column generation "你会得到很多有关列生成算法的信息。当然你还可能查到什么王氏算法，配对合并算法等等，这些都是国内很少论文提到的。</P><>列生成主要是增加一个子问题，运用背包原理将约束降低，再分别迭代，去除不太优的组合，层层递推，而留取最优的组合。这样就使得开始给定的一种初始下料方式，不断通过列生成过程转换成新的更优下料方式。从而达到近似最优。</P><>如果不考虑工期，是799块原材料，但其中要求前4天走的急件不能够完成，所以再把问题分开考虑如下：</P><P>如果只考虑前4天的急件生产，则只需要2天即可，</P><P>如果只考虑前6天的急件生产（包括前4天的急件），则只需要3天就满足了，</P><P>所以总的看来，只要考虑急件先生产即可满足题意。而后分开计算，得到共需要800根，在内部做局部优化，可以得到799根，这个结果非常振奋人心！</P><P>可惜----我们的第二问错用了数量。。。。</P><P>遗憾。。。。</P>

tzjz

<>无非是线性规划的prime-dual叠代求解</P><>我们用遗传算法做的</P>

yangpu82

[em01]