两阶段法求解1.5维切割问题熊慧李大卫（辽宁科技大学理学院，鞍山114044）；切割问题亦称为下料问题。多维切割问题是机加工、木材加工和造纸等行业在生产中二-经常遇见的实际问题。1.5维切割问题是介于一维和二维切割问题之间的一类问题。针对1.5维切割f=问题的特殊性，采用两阶段方法进行求解。**阶段是将1.5维切割问题转化为一维切割问题，第二I-阶段首先利用一种启发式算法得到一组初始解，然后使用粒子群算法对初始解进行优化，得*终解。f；：1.5维切割问题；两阶段方法；启发式算法；粒子群算法I切割问题是介于一维和二维之间的，可以把此类切割问题定义为1.5维切割问题。目前对于1.5维切割问题的讨论非常少。
按照一维切割问题的求解方法去处理1.5维切割问题还不合适，若把它作为单纯的二维问题来解决，又会带来很多不必要的损失。针对这一问题，本文提出一种1.5维切割的优化排样模型。
本文所研究的1.5维切割问题可以描述为：用一批长为L，宽为W的矩形板材，切割出m种长度分别为lL），宽度同为w的小矩形件d，个i=1，2，L，M），求如何切割使得原料*省。
根据此类切割问题的特殊性，可以建立如下的数学模型：因为原板材的宽为W，板材条，设需要宽为w长为L的条形板材数为n，所以，n个条形板材需要原板材=n.张。这样，此问题就可以建立数学模型：成材数。
另外，在提供宽为w的条形板材的时候还可以取=n、条，同样，设需要宽为w长为W的条形板材数为n，所以，n个条形板材需要原板材张。数学模型与前面的类似。在计算得到两组解后，取较优的一组解。
该下料数学模型是典型的整数线性规划模型。目标函数f（X）记录下料过程原材料的浪费数。约束条件既规定了待下料零件在原材料上的合理排样，又满足了待下料零件的数量要求。这样，就将解决1.5维切割问题转化成解决一个一维切割问题。
2粒子群算法粒子群算法ParticleSrnrm-PS）是继蚁群算法之后又一群体智能算法，该算法模拟鸟群飞行觅食的行为，通过鸟群之间的集体协作使群体达到目的。在粒子群算法中，每个粒子根据自己的飞行经验和同伴的飞行经验来调整自己的飞行速度和方向，从而寻找问题的*优解。它是一种随机搜索算法，而且是从多个初始点开始进行搜索的，比较容易克服局部*优问题％步骤1：采用随机产生的位置和速度在整个解空间中初始化粒子群。
步骤2：对于每个粒子，根据适应度函数计算其适应度函数值。
步骤3：比较每个粒子的适应度和个体极值p.如果当前值优于p，就设置当前值为新的p，粒子当前的位置xld为新*来稿日期：2006- 12-29 *基金项目：辽宁省教育厅高等学校科学研究项目05L008）的pbet的位置XPM.比较适应度函数值时，需根据具体的优化问题确定。可能数值越大越优，也可能怡怡相反。
步骤4：比较所有粒子的适应度函数值和全局极值qbeit.如果当前值优于qbest，就设置当前值为新的qbest，粒子当前的位置Xid为新的qbet的位置Xid8.步骤5：改变每个粒子的速度和位置。
步骤6：如果满足了停止循环的准则，就可终止计算；否则转到步骤2继续循环。
3粒子群算法求解1.5维切割问题流程3.1初始解的确立设q是当前第i种材料剩下的需求量（i=1，2，L，m），RL是在输出时的总切边损失，TL是当前切边损失，C是当前订货材料的总根数，d是第i种订货材料当前能选取的*大数量。
得到的一个数组p就是问题的一个可行解，即解空间的一个粒子。其中size表示这个可行解需要切割条形板材数为size，m就表示要切割m种小矩形件。这个数组每一列的和分别等于需求量di，而每一行表示在一根条形板材上排样切割的方案。
3.2适应度函数选取每个可行解的切边损失为适应度函数，所以适应度函数值越小，其对应的解越优。
3.3更新粒子的速度由于每个粒子的行和列的取值都有约束，所以在选取速度时不能随意取值，在这里，我们将随机选取数组的一行，将它加和到随机选取的另一行中，同时保证新生成的这一行不能超出约束条件。这样，就完成了粒子的更新。
4算法求解实例为了验证算法的实用性，下面以实际数据为例使用本文提出的算法进行求解。
问题1：设原材料的大小为15*10cm2.要求切割的零件大小及数量如下：3*1cm2的10件，5*1cm2的15件，2*1cm2的20件。通过使用算法求解，结果如下图所示：a）和：b）是使用**种转换模式的求解结果，图中阴影部分表示为所切割的零件。a）和b）说明了使用2块板材就可以完成下料，而板材利用率达96.7%. 2问题1第二种转换模式的求解结果a）、b）和c）是使用第二种转换模式的求解结果，图中阴影部分表示为所切割的零件。在此种模式下使用了3块原板材，很明显，板材的利用率非常低。所以本题选取所示排列。
采用本文提出的两阶段算法中第二阶段的混合粒子群算法，还可以运用到一维切割问题中。在这里，我们来讨论中的例子。
问题2：原材料长3m，需切割的零件坯料分别为长2.2m的3件、长1.8m的3件、长1.2m的4件、长0.5m的6件、长0.3m的6件。求*优下料方案（不考虑切口损失）。
用基于遗传算法的求解方法计算，中的结果如表1所示。
用本文所提出的混合粒子群算法计算，结果如表2所示。
经对比表1与表2可知，两种方法都需要原材料8根，材料的利用率同为92%，但是后者的剩余材料的可利用率远远高于前者，此结果说明对于求解切割问题，本文所采用的混合粒子群以消费者为导向的产品设计研究于东玖冯亚娟（河海大学机电工程学院工业设计系，常州213022）3市场的急剧变革和日益严重的产品同质化现象，急需产品设计观念的突破。通过研究消！！费者价值观的转变，提出更注重消费者情感体验的整体产品的概念，从产品设计的角度探讨如何通过3：产品设计；消费者价值观；整体产品；顾客让渡价值1消费者价值观的转变消费者决定市场，研究消费者价值观的转变可以为正确认识市场的变化提供帮助。价值观是一个人对周围的客观事物包括人、物、事）的意义、重要性的总评价和总看法，也是一个人的思想体系的一部分。消费观念是人们的价值观在消费活动中的算法要优于中遗传算法。
下料方式板材类型下料根数余料表2基于粒子群算法的求解结果下料方式板材类型下料根数余料5结论针对1.5维切割问题，提出了两阶段求解方法。采用该方法求解，材料的利用率高，余料得到*小化。对同问题多次运行可以给出多种利用率近似的方案，便于从多个优化解中择优。此外，本文提出的第二阶段的混合粒子群算法同样适合与求解一维线性切割问题，而且与遗传算法相比，同样具有很好的求解结果。
