下料问题含代码程序

1、摘要关键字：整数规划模型 多目标决策优化NP问题 下料方案 分支定界法“下料问题(cutting stock problem)”是把相同形状的一些原材料分割加工成若干个不同规格大小的零件的问题，此类问题在工程技术和工业生产中有着重要和广泛的应用. 这里的“实用下料问题”则是在某企业的实际条件限制下的单一材料的下料问题。现考虑单一原材料下料问题. 设这种原材料呈长方形，长度为,宽度为，现在需要将一批这种长方形原料分割成种规格的零件, 所有零件的厚度均与原材料一致，但长度和宽度分别为，其中wi. 种零件的需求量分别为.下料时，零件的边必须分别和原材料的边平行。这类问题在工程上通常简称为二维下料问题

2、。特别当所有零件的宽度均与原材料相等，即，则问题称为一维下料问题。一个好的下料方案首先应该使原材料的利用率最大，从而减少损失，降低成本，提高经济效益。其次要求所采用的不同的下料方式尽可能少，即希望用最少的下料方式来完成任务。因为在生产中转换下料方式需要费用和时间，既提高成本，又降低效率。此外，每种零件有各自的交货时间，每天下料的数量受到企业生产能力的限制。因此实用下料问题的目标是在生产能力容许的条件下，以最少数量的原材料，尽可能按时完成需求任务, 同时下料方式数也尽量地小.就某企业考虑下面两个问题：1 建立一维单一原材料实用下料问题的数学模型, 并用此模型求解下列问题，制定出在生产能力容许的条

3、件下满足需求的下料方案, 同时求出等额完成任务所需的原材料数，所采用的下料方式数和废料总长度. 单一原材料的长度为 3000mm, 需要完成一项有53种不同长度零件的下料任务. 具体数据见表一，其中 为需求零件的长度，为需求零件的数量. 此外，在每个切割点处由于锯缝所产生的损耗为5mm. 据估计，该企业每天最大下料能力是100块 ，要求在4天内完成的零件标号()为: 5,7,9,12,15,18,20,25, 28,36,48;要求不迟于6天完成的零件标号()为：4，11，24, 29,32,38,40,46,50. (提示：可分层建模。(1).先考虑用材料既少,下料方式又少的模型, 或先仅考

4、虑所用材料最少的模型及增加一种下料方式大致相当于使原材料总损耗增加0.08%情况下的最佳方案。(2).在解决具体问题时,先制定4天的下料方案,再制定6天的下料方案,最后制定53种零件的下料方案. 这一提示对第2题也部分适用.)表1 需求材料的数据 单位：mm123456789101743168015321477131312851232121711801177421610438460486101112131415161718192011051055104610321030975893882847845824882830163821222324252627282930830795766745730

5、7197146956456303084434184490303132333435363738394061060059058858257854048835534330212108482196832452424142434445464748495032051541441140532831329027526588860136468286602286515253255184155 19257242 建立二维单一原材料实用下料问题的数学模型, 并用此模型求解下列问题.制定出在企业生产能力容许的条件下满足需求的下料方案, 同时求出等额完成任务所需的原材料块数和所需下料方式数.这个问题的单一原材料的长度为

6、3000mm,宽度为100mm, 需要完成一项有43种不同长度和宽度零件的下料任务. 具体数据见表二，其中 分别为需求零件的长度、宽度和数量. 切割时的锯缝可以是直的也可以是弯的，切割所引起的锯缝损耗忽略不计.据估计，该企业每天最大下料能力是20块 要求在4天内完成的零件标号()为: 3,7,9,12,15, 18, 20, 25, 28, 36. 表2 需求材料的数据 单位：mm12345678910110510551046103210309958938828478453020503020603020 303024612242457241001201081112131415161718192

7、0830795766745732722714690665633302035303045503020309040121268741012270902122232425262728293063060059058858257854048845543430352020302050202030906125082082496246220162923132333435363738394042041541441140532831329027526520302030203050302030402440180536121286862002686414243255184155302050 69235752本文要解决

8、的是一个典型的多目标决策优化问题。一个好的下料方案首先应该使原材料的利用率最大，从而减少损失，降低成本，提高经济效益。其次要求所采用的不同的下料方式尽可能少，即希望用最少的下料方式来完成任务。因为在生产中转换下料方式需要费用和时间，既提高成本，又降低效率，故企业都希望尽可能地减少下料方式的数目。此外，每种零件有各自的交货时间，每天下料的数量受到企业生产能力的限制。因此实用下料问题的目标是在生产能力容许的条件下，在规定的时间需求内，以最少数量的原材料，尽可能按时完成需求任务，同时下料方式数也尽量地小。为顺利解决这一问题，我们先从最基本的单目标决策问题人手，以材料损耗最少为目标，由于个别零件的生产

9、有时间的要求，因此，在下料时就应该优先生产那些有时间限制要求的零件，并且通过不同的数学原理建立多个单目标决策的最优化模型，得出最初的结果，并加以比较分析，然后逐步增加其约束条件，并根据这些约束条件进一步完善我们的最优化模型，求出在需求的时间段内下料方式和损耗都最少的最优结果，紧接着再求出剩余板材下料方式和损耗的最优结果，从而最终得出既满足时间条件限制又满足损耗少、下料方式数小的最优结果。具体流程图如下： 图1 总体流程图1. 假设每次切割都准确无误。2. 每天下料的数量受到企业生产能力的限制，在未完成需求任务前，每天下料的数量等于最大下料能力。3. 模型一中每切得一个规格的零件需要的原材料。4

10、. 除最后一天外，其余每天均达到最大下料能力。5. 除了要求在规定时间内完成所需零件外，不要求其余零件加工排列顺序。6. 模型二中，切割所引起的锯缝损耗忽略不计。4.符号说明符号符号解释说明需求零件的数量需求零件的长度需求零件的宽度第i种下料方式可生产第j种零件的数量不同的下料方式所使用的原材料的数目每种下料方式应用于每个原材料上所剩的余料使用下料方式的种类第种零件所需要生产的数量原材料长度，为30004天内需要完成的零件编号建立集合6天内需要完成的零件编号建立集合理论所采用的原材料数目实际采用原材料的数目完成任务后的材料利用率问题二中4天内需要完成的零件编号建立集合对于一维优化下料问题，属于

11、整数规划问题，从计算复杂性理论分析，该问题属于NP难题,即无法在多项式时间(在计算复杂度理论中，指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数)内求解。虽然整数规划问题是NP难题，但是线性问题却是有有效算法的。所以要想求出下料方案的最优解，可以考虑不先求解整数规划问题而先来求解其相应的线性问题，然后用计算机程序进行求解。首先考虑在满足时间需求的情况下，材料总损失最少的情况，然后尽量使得总的下料方式数目最少，故这里要寻找到所有下料方式中利用率最高的方式，同时在满足生产力要求的情况下进行适当调整，采用尽可能少的下料方式，这样便可以得到一维下料问题的优化结果。根据题意，现有数量充足的长

12、度为3000mm的原材料，需要完成一项有53种不同长度零件的下料任务。要求在生产能力许可的条件下，既省材料又容易操作(即下料方式尽可能少)，由于本文问题的特殊性，还需要考虑个别标号的零件在4天内及6天内完成。故先对数据进行预处理，将4天和6天内完成的任务筛选出来，优先处理后再进行其他标号零件的加工。按照前面的分析，我们现假设有m种不同的下料方式，再根据每种零件的需求量，可求得每种零件应用的次数，这样采用第一种下料方式生产的第一种零件的个数为个，同理可知，表示第i种下料方式可生产第j种零件的数量，则采用第m种下料方式所能得到的第j种零件的数量表示为，为更好地表示这个对应关系，建立如下对应关系矩阵

13、：则使用m种不同的下料方式所使用的原材料的数目为，同样用矩阵的方式来表示，则有所需原材料数目为：由于我们以原材料总损耗最少为目标，所以首先计算每种下料方式产生的余料长度，由于在每个切割点处由于锯缝所产生的损耗为5mm. 故每种下料方式应用于每个原材料上所剩的余料表达式为： 则建立原材料总损耗最少的目标函数为： ()其中表示第种下料方式所消耗的原材料数目，表示第种下料方式所得余料。又为方便企业加工生产，减少不必要的更换下料方式所产生的麻烦，企业希望所采用的下料方式尽可能少，因此建立第二个目标函数：1)由于所要生产的每种型号的零件数量题中已经给定，故有限制条件： ()其中，表示第种下料方式可生产第

14、j种零件的数量，表示第种下料方式所消耗的原材料数目，表示第种零件所需要生产的数量，。2)由于题目中所给出的各个编号的零件都有给定的长度，且原材料长度已定，故在考虑了锯缝后，还要考虑原材料长度对下料方式的限制，即对于任意一种下料方式，所得到的零件总长度与锯缝总长度之和要小于等于每根原材料的总长度，同时还要考虑对于每一种下料方式的废料长度要小于零件的最小长度，由题中所给数据可知，需要生产的零件长度最小为，故此约束表达式为：其中为每个编号对应的零件长度。3)因为所需零件的生产有时间的限制，相应编号的零件必须在规定的时间内生产完成，要求4天完成的零件编号为：，共有11种零件；要求6天内完成的零件编号为

15、：，共有9种型号的零件。为了在最短时间内完成所有零件生产的任务，在满足该企业每天最大下料能力100块的生产能力条件下，我们在6天内完成的任务中增加4天内需要完成的任务，即6天内需要生产20种型号的零件，为方便下文叙述，我们将4天内需要完成的零件编号建立集合，即，同理将6天内需要完成的零件编号建立集合，即，对此建立约束条件表达式为：其中表示第种下料方式中所切割的第种零件数占这种下料方式中所切割的零件4天内需要完成零件数的权数，因此表示4天内完成零件制定零件所用的原材料数，根据该企业的生产能力要求，上述表达式所计算出采用的原材料总数要小于等于，另外若，则表示第种下料方式中没有切割到集合中的零件；同

16、理，表示第种下料方式中所切割的第种零件数占这种下料方式中所切割的零件6天内需要完成零件数的权数，因此表示6天内完成零件制定零件所用的原材料数，根据该企业的生产能力要求，上述表达式所计算出采用的原材料总数要小于等于，另外若，则表示第种下料方式中没有切割到集合中的零件。综上所述，针对本文一维下料问题建立如下数学模型：目标函数约束条件 对于该问题，首先考虑在满足时间需求的情况下，材料总损失最少的情况，然后尽量使得总的下料方式数目最少，由于本文问题的特殊性，还需要考虑个别标号的零件在4天内及6天内完成。故先对数据进行预处理，将4天和6天内完成的任务筛选出来，优先处理后再进行其他标号零件的加工。将集合和

17、集合中的零件进行优先处理，利用lingo软件编程，先不考虑下料方式的数目对结果的影响，在满足原材料总损失最小的前提下再调整下料方式的数目，同时在保证生产集合和集合中的零件的基础上，只要在生产能力许可范围内，还可以生产其他对生产时间没有限制的零件。对此，运行程序得到的这一批零件生产的结果，然后再利用matlab程序对所得下料方式进行调整，然后针对个别存在问题的下料方式进行调解后得到的最终结果为：表3 优先考虑有时间限制零件的处理结果下料方式零件尺寸(mm)及数量余料(mm)原材料(块)1265(11)3542343(8) 184(1)3733600(4) 265(2)45514645(1) 60

18、0(3) 265(2)015645(4) 265(1)135216750(4)5171105(2) 600(1) 155(1)25181105(2) 645(1)135291477(1) 645(1) 600(1) 255(1)131101477(2) 411811290(2) 265(8) 255(1)0112735(2) 290(4) 355(1)0113290(10)552814578(1) 1105(2) 184(1)18115578(5)90116847(1) 730(1) 695(2)13217730(4)65718343(6) 265(1) 630(1)16119847(1) 7

19、30(2) 343(1) 328(1)2120847(3) 414(1) 35121348(7) 540(1)241122882(1) 488(4)146123882(3) 265(1)74100241030(1) 1477(1) 414(1)661251030(1) 577(1) 328(1) 265(2) 515(1)31261030(2) 645(1) 265(1)152271030(2) 577(1) 343(1)41281057(2) 265(1) 610(1)11291182(2) 600(1)263301232(2) 265(1) 255(1)62311313(2) 328(1)

20、99232343(3) 265(1) 1680(1)61合计1235273由表3可知，优先生产有时间限制的零件，则共有32种下料方式，所产生的废料为1235mm，共需要原材料的数量为273块。接下来开始生产没有时间限制的零件，因为有时间限制的零件已经生产完毕，故在此不予以考虑，除去生产有时间限制的零件后，利用lingo程序运行得到结果后，再利用matlab程序对所得下料方式进行调整，然后针对个别存在问题的下料方式进行调解后得到的最终结果为： 表4 没有时间限制零件的处理结果余料(mm)下料方式零件尺寸(mm)及数量原材料(块)151184(15) 155(1) 32052275(10)5814

21、33313(9)3144411(5) 184(4) 155(1)1935411(7)71256795(1) 515(4)1857320(8) 155(2)1898355(5) 184(4)11259355(8)428010540(5)27011582(5)384612766(1) 588(1) 155(10)14013588(5)26214590(1) 582(4)1315590(2) 540(1) 313(4)13016590(5)21017610(4) 540(1)318518610(4) 355(1)3519630(1) 610(3) 355(1) 155(1) 15120630(4)

22、414(1)110521630(4) 355(1)612922714(4)11123719(2) 588(2) 355(1)110924719(4)49925766(3) 588(1)16526795(3) 540(1)222527830(3) 275(1)118228830(1) 313(1)83029847(3) 414(1)213330893(1) 515(3) 414(1)13831975(2) 588(1) 414(1)138321032(2) 893(1)3131331032(2) 795(1)110341046(2) 893(1)2153351177(1) 830(2)19036

23、1177(1) 893(1) 830(1)11371177(2) 155(4)16381177(2) 355(1) 275(1)226391177(2) 610(1)116401217(2) 540(1)311411285(2) 414(1)1107421285(2) 313(1)29220431532(1) 411(3)1168441532(1) 255(6)37128451532(1) 405(2) 255(2)1108461532(1) 405(2) 275(1) 255(1) 1145471532(1) 405(3)44282481532(1) 588(2)20134491680(1)

24、 588(2)213112501680(1) 588(1) 610(1)172511680(1) 411(3)135521743(1) 1217(1)283531743(1) 582(2)139541743(1) 893(1) 155(2)1191555540(2)16822合计550如表4所示，除去所有有时间限制的零件，以及为了调整其余料与有时间限制的零件一同优先生产的零件之外，剩下的没有时间限制的零件生产共需要55种下料方式，所产生的废料总长度为6822mm，且需要550块原材料。综上可知，完成所有零件的生产，要采用种下料方式，且共需要块原材料，所产生的余料总长度为：。通过对本文中的一维下

25、料问题建立数学模型，并结合lingo程序计算，得到了完成任务的满意结果。为进一步验证模型的结果，提出利用率这一概念，即理论用料所占实际用料的百分比。首先针对表1，我们可以求出完成这项任务所需要的理论用料数目(即所采用的原材料数目)，建立数学表达式为：其中为每种型号零件要求的长度，为每种型号零件所要求的数量，。代入表1中相关数据进行计算可以得到理论上需要采用的原材料数目为块，由于实际采用原材料的数目为块，所以可得完成任务后的材料利用率为：，可知利用率相对较高，也说明了此模型的可用性。为方便查看，将所得到的结果做成如下表格： 表5 求得完成任务的最终结果原材料总数823块采用下料方式数87种产生废

26、料长度8057mm材料利用率96.80%对于二维下料问题，下料方式要同时满足零件长、宽方面的要求，所以要远比一维下料问题复杂。由于二维下料问题与一维下料问题有一定的相似性，我们尝试着将二维下料问题转化为一维下料问题来解决。1）对表2所给出的数据进行分析，可以知道所有需求加工的零件宽度均集中于20mm、30mm、35mm、50mm这四种规格，对于这四种规格的零件进行集中处理，原材料的长度为3000mm，宽度为100mm，将其看成是宽度分别为20mm、30mm、35mm、50mm且长度为3000mm的条材。2）为了尽量节省材料，我们使原材料在宽边上尽量利用完全，这样只有几种宽边完全利用的组合方式(

27、7种)，分别为：5050，503020， 30302020，353530，2020202020，453520，602020。我们把零件按宽边的规格分为6类(20，30，35，45，50，60)，由于所给数据中只有一种型号的零件宽度为45mm，也只有一种型号的零件宽度为60mm，因此在总材料损耗最小的前提下，可以对这两个型号的零件进行单独处理。由上分析可知每一类零件都可按模型一的处理一维下料问题的方式找到最优的方案，然后再把它们按上述的几种方式进行优化组合，最后再对优化组合剩余的部分进行考虑。组合方式例子如图2所示：图2组合方式为50-30-20的下料方式示意图 3）建立如一维下料问题的数学模型

28、，现假设有k种不同的下料方式，再根据每种零件的需求量，可求得每种零件应用的次数，这样采用第一种下料方式生产的第一种零件的个数为个，同理可知，表示第i种下料方式可生产第j种零件的数量，则采用第k种下料方式所能得到的第j种零件的数量表示为，为更好地表示这个对应关系，建立如下对应关系矩阵：则使用k种不同的下料方式所使用的原材料的数目为，同样用矩阵的方式来表示，则有所需原材料数目为：由于我们将问题二转化为了一维下料问题，所以采用模型一的建模方式，将原材料分为6种宽度规格的条材，同样以每种宽度规格的原材料总损耗最少为目标，首先计算每种宽度每种下料方式产生的余料长度，然后进行组合。故每种下料方式应用于每个

29、原材料上所剩的余料表达式为： ，其中 。则建立每种宽度原材料总损耗最少的目标函数为： ()其中表示第种下料方式所消耗的原材料数目，表示第种下料方式所得余料。又为方便企业加工生产，减少不必要的更换下料方式所产生的麻烦，企业希望所采用的下料方式尽可能少，因此建立第二个目标函数：1)由于所要生产的每种型号的零件数量题中已经给定，故有限制条件： ()其中，表示第种下料方式可生产第j种零件的数量，表示第种下料方式所消耗的原材料数目，表示第种零件所需要生产的数量，。2)由于题目中所给出的各个编号的零件都有给定的长度，且原材料长度已定，故还要考虑原材料长度对下料方式的限制，即对于任意一种下料方式，所得到的零

30、件总长度与锯缝总长度之和要小于等于每根原材料的总长度，同时还要考虑对于每一种下料方式的废料长度要小于零件的最小长度，由题中所给数据可知，需要生产的零件长度最小为，故此约束表达式为：其中为每个编号对应的零件长度。3)因为所需零件的生产有些型号有时间的限制，相应编号的零件必须在规定的时间4天内生产完成，要求4天完成的零件编号为：，共有10种零件，为方便下文叙述，我们将4天内需要完成的零件编号建立集合，即为了在最短时间内完成所有零件生产的任务，在满足该企业每天最大下料能力20块的生产能力条件下，我们优先考虑有时间限制的零件进行生产，对此建立约束表达式为：其中表示第种下料方式中所切割的第种零件数占这种

31、下料方式中所切割的零件4天内需要完成零件数的权数，因此表示4天内完成零件制定零件所用的原材料数，根据该企业的生产能力要求，上述表达式所计算出采用的原材料总数要小于等于，另外若，则表示第种下料方式中没有切割到集合中的零件。综上所述，针对本文二维下料问题建立如下数学模型：目标函数其中其中约束条件对于该问题，首先考虑在满足时间需求的情况下，各种宽度的条材总损失最少的情况，然后尽量使得总的下料方式数目最少，由于本文问题的特殊性，还需要考虑个别标号的零件在4天内完成。故先对数据进行预处理，将4天内需要完成的任务筛选出来，优先处理后再进行其他标号零件的加工。将集合中需要在4天内完成的零件进行优先处理，通过

32、对这些数据的分析，有7种型号的零件(共需722个)需要采用宽度为30mm的条材，有2种型号的零件(共需60个)需要宽度为20mm的条材，有1种型号的零件共需12个需要宽度为50mm的条材。然后利用lingo软件编程，运行程序得到的这一批宽度不同的零件生产结果，然后再利用matlab程序对所得针对各种宽度条材的切割方式进行调整，在满足不同宽度的条材总损失最小的前提下，计算出集合中各型号零件需要宽度为30mm的条材为157根，需要宽度为50mm的条材6根，考虑宽度完全利用的组合方式30302020、5050，也应该需要与宽度为30mm相同数目的宽度为20mm的条材进行组合，需要但是组合之后会发现最

33、后需要原材料数目为：157/2+381.5根，这不满足约束条件即不在生产能力的许可范围内，所以必须更改组合方式。通过结合计算机进行试算，将宽度为30mm的条材取出130根进行30302020宽度完全利用的组合方式，可知此种组合需要原材料的数目为130/265根，其余27根进行303030的组合方式，需要27/39根原材料，对6根宽度为50mm的条材进行5050的组合方式，需要原材料6/23根，所有组合完成后可知4天内共需要原材料65+9+377根，每种宽度条材的切割方式如下： 1)宽度为20mm的条材切割方式表6 宽度为20mm的条材切割方式切割方式零件长度(mm)及个数余料(mm)条材数(根

34、)1488(6)7232795(1) 1055(2)9513795(3) 590(1)25114795(3) 488(1)12725184(16)5666275(10)250357420(7)6058578(5)11049665(4) 184(12) 275(3)1152合计1066130如表6可知，宽度为20mm的条材共有10种切割方式，在有时间限制的条件下，需要宽度为20mm的条材130根，总共剩余余料为1066mm。2)宽度为30mm的条材切割方式。表7 宽度为30mm的条材切割方式切割方式零件长度(mm)及个数余料(mm)所需数量(根)1582(5)90992

35、633(2) 582(1) 1105(1)4713633(4) 328(1)14094633(4) 434(1)34135690(4)24036732(4)72177847(2) 328(3) 290(1)3218847(2) 434(1)2569893(3) 290(1)318合计711130如表7可知，宽度为30mm的条材共有9种切割方式，在有时间限制的条件下，需要宽度为30mm的条材130根，总共剩余余料为711mm。3)宽度为50mm的条材切割方式。表8 宽度为50mm的条材切割方式切割方式零件长度(mm)及个数余料(mm)所需数量(根)11046(2) 540(1) 313(1)55

36、6如表8可知，宽度为50mm的条材共有1种切割方式，在有时间限制的条件下，需要宽度为50mm的条材6根，剩余余料为55mm。4)综上，可知4天内集合中零件生产所对应各种宽度条材的组合方式，以及最终的下料方式和原材料数，组合结果如下表：表9 4天内原材料的下料方式下料方式组合方式所需原材料（块）130(1)30(1)20(9)20(9)30230(1)30(1)20(6)20(6)17330(9)30(9)20(8)20(7)4430(8)30(8)20(5)20(5)3530(5)30(5)20(10)20(10)1630(5)30(7)20(7)20(9)1730(1)30(1)20(4)2

37、0(1)2830(4)30(4)20(3)20(3)5930(1)30(4)20(6)20(1)11030(4)30(4)20(3)20(2)11130(6)30(6)30(3)81230(2)30(3)30(6)11350(1)50(1)3合计77由表9可知，考虑优先生产集合中的零件，共有13种下料方式，需要使用原材料的数量为77块。接下来开始生产没有时间限制的零件，因为有时间限制的零件已经生产完毕，故在此不予以考虑，除去生产有时间限制的零件后，利用lingo程序运行得到结果后，再利用matlab程序对所得下料方式进行调整，结合6.2.1的解决问题的思路，然得到的最终结果。1)宽度为20mm

38、的条材切割方式表10 宽度为20mm的条材切割方式切割方式零件长度（mm）及个数余料（mm）所需数量（根）1275（10）184（1）661642405（7）165753414（7）10254455（6）270165455（6） 184（1）86116578（3） 414（3）2417588（5）604168590（1） 184（12）20219590（1） 405（5）385110590（5）509811665（1） 184（12）127112665（4）340613405（4） 275（5）5114882（3）354332151030（2） 882（1）584161030（2） 588（1

39、）3522171030（2） 414（2）1121181030（2） 420（2）1001191030（2） 578（1） 275（1）871201030（2） 665（1） 184（1）911211055（2） 882（1）81221055（2） 882（1）80123420（3）17401合计48641141由表10可知，宽度为20mm的条材共有23种切割方式，在有时间限制的条件下，需要宽度为20mm的条材1141根，总共剩余余料为4864mm。2)宽度为30mm的条材切割方式。表11 宽度为30mm的条材切割方式切割方式零件长度（mm）及个数余料（mm）所需数量（根）1255(11)19

40、5622265(11)85623290(10)100674845(1) 411(5)10015411(7)12316415(7)9537434(4) 265(4)20418434(6) 255(1) 411(1)419434(6) 255(1)141910630(3) 434(1) 411(1)265111630(4) 255(1) 411(1)225112630(4) 411(1)692013745(4)20314830(4) 411(1)992915845(1) 290(7)125116845(1) 830(2) 411(1)84117845(3) 411(1)5434181032(2)

41、411(1)5253191032(2) 434(2)685201032(2) 830(1)1061211032(2) 845(1)913221105(2) 411(1)3792231105(2) 415(1)3752241105(2) 434(1)3565251105(2) 630(1)1603合计4048321由表11可知，宽度为30mm的条材共有25种切割方式，在有时间限制的条件下，需要宽度为30mm的条材321根，总共剩余余料为4048mm。3)宽度为35mm的条材切割方式。表12 宽度为35mm的条材切割方式切割方式零件长度（mm）及个数余料（mm）所需数量（根）1766(2) 600

42、(2)26822600(4)60013600(5)01184766(1) 600(3)43245766(3) 600(1)1022合计1402127由表12可知，宽度为35mm的条材共有5种切割方式，在有时间限制的条件下，需要宽度为35mm的条材127根，剩余余料为1402mm。4)宽度为45mm的条材切割方式。表13 宽度为45mm的条材切割方式切割方式零件长度（mm）及个数余料（mm）所需数量（根）1722(2) 155612722(4)11218合计166819由表13可知，宽度为45mm的条材共有2种切割方式，在有时间限制的条件下，需要宽度为45mm的条材19根，剩余余料为1668mm

43、。5)宽度为50mm的条材切割方式。表14 宽度为50mm的条材切割方式切割方式零件长度（mm）及个数余料（mm）所需数量（根）1155(19)5522714(2) 313(5)7113313(5)143534313(9)18315540(1) 155(14)29016540(5)30017714(4)1441合计241420由表14可知，宽度为50mm的条材共有7种切割方式，在有时间限制的条件下，需要宽度为50mm的条材20根，剩余余料为2414mm。6)宽度为60mm的条材切割方式。表15 宽度为60mm的条材切割方式切割方式零件长度（mm）及个数余料（mm）所需数量（根）1995(3)1

44、519由表15可知，宽度为60mm的条材共有1种切割方式，在有时间限制的条件下，需要宽度为60mm的条材19根，剩余余料为15mm。7)综上，可知其余零件生产所对应各种宽度条材的组合方式，以及最终的下料方式和原材料数，组合结果如下表：表16其余零件生产原材料的下料方式下料方式组合方式所需原材料（块）160(1)20(15)20(15)19245(2)35(3)20(15)18345(1)35(2)20(6)1435(3)35(3)30(1)50535(1)35(5)30(23)2635(4)35(4)30(22)2750(2)50(3)3850(1)50(2)2950(2)50(2)31050

45、(4)50(5)11150(6)50(7)11230(20)30(20)20(10)20(10)11320(1)20(1)30(2)30(3)621420(3)20(12)30(3)30(19)51530(1)30(9)20(4)20(5)91630(1)30(6)20(4)20(4)31730(13)30(18)20(7)20(7)31830(21)30(25)20(10)20(10)31930(14)30(24)20(1)20(1)52030(12)30(14)20(2)20(2)202130(4)30(5)20(11)20(12)12230(7)30(8)20(8)20(9)12330(

46、10)30(11)20(4)20(13)12430(15)30(16)20(17)20(18)12530(14)30(14)20(5)20(16)22630(17)30(17)20(2)20(2)172720(1)20(1)20(1)20(1)20(1)62820(19)20(20)20(21)20(22)20(23)12920(2)20(14)20(14)20(15)20(15)13020(14)20(14)20(14)20(14)20(14)663120(7)20(7)20(7)20(7)20(7)20(7)823220(10)20(10)20(10)20(10)20(10)18合计410

47、由表16可知，考虑优先生产集合中的零件，共有32种下料方式，需要使用原材料的数量为410块。6综上可知，完成所有零件的生产，要采用种下料方式，且共需要块原材料。通过对本文中的一维下料问题建立数学模型，并结合lingo程序计算，得到了完成任务的满意结果。为进一步验证模型的结果，提出利用率这一概念，即理论用料所占实际用料的百分比。首先针对表1，我们可以求出完成这项任务所需要的理论用料数目(即所采用的原材料数目)，建立数学表达式为：其中为每种型号零件要求的长度，为每种型号零件所要求的数量，。代入表1中相关数据进行计算可以得到理论上需要采用的原材料数目为块，由于实际采用原材料的数目为块，所以可得完成任

48、务后的材料利用率为：，可知利用率相对较高，也说明了此模型的可用性。为方便查看，将所得到的结果做成如下表格： 表17 求得完成任务的最终结果原材料总数487块采用下料方式数45种材料利用率92%、改进与推广评价1）对于问题一所建立的多目标整数规划模型，很准确的概括了该问题的所有约束和目标，从理论上讲是一个很严谨的模型。但是对于这一模型的求解却是非常困难的，必须寻找比较好的算法支持它，而文中我们提出优化方法就很好的支持了这个模型，并且有很好的求解效果，材料的利用率很高（废料很少），计算速度快，结果很好。此模型和算法适应能力强，求解结果好，有很强的普遍性和实用性。2）对于问题二所建立的分类逐层分析模

49、型较好的解决了问题二，此方法根据具体问题的具体特点进行分析，找出针对性的解决方案，这样我们同样得到较好的结果，材料利用率高，计算速度快；但此模型有一定的缺陷，没有很强的普遍性，为适应某一特殊问题都需要具体的分析计算，寻求针对性的方案。改进从本文的两个问题的解决可看出，针对本问题将多目标整数规划模型分解为多层整数线性规划模型和分支定界的优化方法是十分有效的。它在大大降低计算复杂度的同时保持了很高的材料利用率和尚可接受的下料方式数。但是简化后的模型与算法在计算结果稳定性方面未来得及分析证明，也就是说此模型用于其它类似问题是否还可以得到和本题两个问题同样高的利用率没有理论基础。改进的模型可以在证明或增加模型稳定性方面作研究。推广前人的研究以及上述算法的评价说明，现有的单一的模型与算法都有自身的缺陷，如常规的整数线性规划求解法计算结果最优，但是NPC问题，随着问题规模的增加，计算量和存储空间的会产生组合爆炸；神经网络法、模拟退火法以及蒙特卡罗法初始收敛速度快，特别适用于优化目标和约束条件复杂的问题，但是为求出精确解付出的机时却特别大。因此接下来可以考虑将蒙特卡罗模拟与我们的方法结合，以期得到一定的稳定性与精确度。本模型在前人研究的