最优下料问题的数学模型.pdfVIP

最优下料问题的数学模型 摘要 本文通过对两个问题进行分析，分别建立模型一、模型二。针对模型一，设计程序 贪心算法，通过 Matlab 编程，得出相应结果。针对模型二，文中通过将二维问题转换 成为一维问题，引用规划模型，做出相应分析。 在问题一中，为解决一维下料问题，根据一维下料问题的特点，建立起由其约束条 件组合而成的规划模型，在随机决策的基础上利用贪心算法取每个决策中的最优值，较 快地获得问题的最优解为：前6 天下料方案整和为一个方案比制定4 天，6 天方案更优， 且前6 天需用原材料根数为268，利用率为99.21%，3 天完成；剩余下料方案为需用原 材料根数为538，利用率为98.92%，6 天完成。（详见表6-1 和附录表6-2、表6-3） 在问题二中，基于零件长、宽两个方向上的限制的情况后，根据问题2 中待加工的 零件的宽只集中在50mm，30mm，35mm，20mm 四种规格上，将二维问题转化为一维问题， 分别用一维下料问题的方法寻求四种宽度条材在一维情况下的最优方案。在这一过程 中，可根据一维下料问题求解的方法，建立模型二，解多目标整数规划，再进行最优组 合，可以得到两个阶段所使用的条材。 关键词： 贪心算法 最优下料 规划 1 一、问题的重述 “下料问题(cutting stock problem)”是把相同形状的一些原材料分割加工成若干 个不同规格大小的零件的问题，此类问题在工程技术和工业生产中有着重要和广泛的应 用. 这里的“实用下料问题”则是在某企业的实际条件限制下的单一材料的下料问题。 L 现考虑单一原材料下料问题. 设这种原材料呈长方形，长度为 ,宽度为 ，现在 W 需要将一批这种长方形原料分割成 种规格的零件, 所有零件的厚度均与原材料一致， m 但长度和宽度分别为(l , w ), , (l , w ) ，其中w ＜l L, w W,i 1, ,m . m 种零件 1 1 m m i i i 的需求量分别为n ,,n .下料时，零件的边必须分别和原材料的边平行。这类问题在 1 m 工程上通常简称为二维下料问题。特别当所有零件的宽度均与原材料相等，即 w W,i 1,,m ，则问题称为一维下料问题。 i 一个好的下料方案首先应该使原材料的利用率最大，从而减少损失，降低成本，提 高经济效益。其次要求所采用的不同的下料方式尽可能少，即希望用最少的下料方式来 完成任务。因为在生产中转换下料方式需要费用和时间，既提高成本，又降低效率。此 外，每种零件有各自的交货时间，每天下料的数量受到企业生产能力的限制。因此实用 下料问题的目标是在生产能力容许的条件下，以最少数量的原材料，尽可能按时完成需 求任务, 同时下料方式数也尽量地小.请你们为某企业考虑下面两个问题。 1、建立一维单一原材料实用下料问题的数学模型, 并用此模型求解下列问题，制 定出在生产能力容许的条件下满足需求的下料方案, 同时求出等额完成任务所需的原 材料数，所采用的下料方式数和废料总长度.单一原材料的长度为 3000mm, 需要完成一 项有53种不同长度零件的下料任务. 具体数据见表一，其中 为需求零件的长度， 为 l n i i 需求零件的数量. 此外，在每个切割点处由于锯缝所产生的损耗为5mm. 据估计，该企