天然肠衣一维下料优化问题.doc

天然肠衣一维下料优化问题 覃亮指导教师：肖华勇（西北工业大学理学院，西安 710072）摘要一维下料问题是指在已知原料数量和顾客所需坯料规格、数量等情况下把一维原材料（如线材、管材、棒材等）按一定要求分割加工成不同长度的产品或零部件，使原材料的利用率达到最大的优化问题，此类问题在工程和工业生产中有着广泛而重要的应用。本文着眼于肠衣下料优化问题的解决，但亦可举一反三将解决该问题的思想、算法应用到其他工业生产中所遇到的一维下料优化问题中。本文首先用Matlab软件求解出满足题意的模式，再在当前可行的下料方式中依次按要求通过Lingo软件筛选出最优模式，不断重复此过程，直至所剩余的坯料数量减少至最少为止。经实际操作，本方法产生方案高效快捷，节材效果显著。关键词：一维下料 线性优化 模式法 lingo 优化问题 matlab1.问题的提出天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。原料按长度分档，通常以0.5米为一档，如：3-3.4米按3米计算，3.5米-3.9米按3.5米计算，其余的依此类推。为了提高生产效率，公司计划改变组装工艺，先丈量所有原料，建立一个原料表。最短长度最大长度根数总长度36.52089713.588914589表1 成品规格表表2为某批次原料描述。长度3-3.43.5-3.94-4.44.5-4.95-5.45.5-5.96-6.46.5-6.9根数4359394127283421长度7-7.47.5-7.98-8.48.5-8.99-9.49.5-9.910-10.410.5-10.9根数2424202521232118长度11-11.411.5-11.912-12.412.5-12.913-13.413.5-13.914-14.414.5-14.9根数3123225918253529长度15-15.415.5-15.916-16.416.5-16.917-17.417.5-17.918-18.418.5-18.9根数3042284245495064长度19-19.419.5-19.920-20.420.5-20.921-21.421.5-21.922-22.422.5-22.9根数526349352716122长度23-23.423.5-23.924-24.424.5-24.925-25.425.5-25.9根数060001表2 原料描述表 根据以上成品和原料描述，设计一个原料搭配方案，工人根据这个方案“照方抓药”进行生产。公司对搭配方案有以下具体要求：(1) 对于给定的一批原料，装出的成品捆数越多越好；(2) 对于成品捆数相同的方案，最短长度最长的成品越多，方案越好；(3) 为提高原料使用率，总长度允许有 0.5米的误差，总根数允许比标准少1根；(4) 某种规格对应原料如果出现剩余，可以降级使用。如长度为14米的原料可以和长度介于7-13.5米的进行捆扎，成品属于7-13.5米的规格；(5) 为了食品保鲜,要求在30分钟内产生方案。2.问题的分析 本文主要考虑在满足各种要求的情况下，解决天然肠衣之间的搭配问题，忽略次要因素，如测量误差、原料意外损耗等，主要考虑使天然肠衣的捆数最大且在捆数相同时最短长度最长的成品最多。在考虑到原料利用率的情况下，首先考虑在总长度和总根数都没有误差的情况，建立模型，求出模式。然后再考虑允许误差的情况，在原有的情况下，放松约束条件，求出模式。考虑到原料可以降级使用，就必须先求原料最长的成品的最大捆数，建立最优模型，求出成品三的最大捆数，接着算出该产品原料的余量。最后考虑成品三的余量，建立成品二的最优模型，求出成品二的最大捆数，算出该产品原料的余量。同理，建立成品一的最优模型，计算出成品一的最大捆数及余量。在捆数达到最大的前提下，使得最短长度最长的成品捆数达到最大，只需要在上述最优模型中，固定捆数为最大值，把目标函数改为最短长度最长的成品捆数最大即可。该问题的求解最终可以使公司获得最大利益，同时该问题所用的模型还可以应用到其它广泛领域，所以对该问题的求解，对国民生产具有很重要的实际意义。 3.符号的约定第种模式的捆数；模式中所选第中原料的根数；第种原料的总根数；上一级产品的余量被当做该级产品的第种原料的根数；第种模式中第种原料的根数；4.模型的假设（1） 假设搭配过程中肠衣不会变质以及受到意外损失或损伤；（2） 假设在对原料长度的测量中没有人为误差；（3） 假设所有坯料均为合格品。5.模型的建立与求解5.1模型的建立5.1.1 求解模式本节主要求解符合题意的模式，根据三种成品的不同规格要求分别对这三种产品求出满足题意的模式。 （一）决策变量:在成品一中，我们假设从33.4米段中选择根，从3.53.9米段中选择根，依此类推，在6.56.9米段中选择根。在成品二中，我们假设从77.4米段中选择根，从7.57.9米段中选择根，依此类推，在13.513.9米段中选择根。在成品三中，我们假设从1414.4米段中选择根，从14.514.9米段中选择根，依此类推，在25.525.9米段中选择根。 （二）约束条件在成品一中，由表二知，它的后一种原料均比前一种原料长0.5米，所以第种原料的长为。考虑到成品总根数可以少一根，总长度可以有米的误差，以及表一，必须满足以下约束条件。同理，在成品二中，第种原料长为同理，在成品二中，第种原料长为5.1.2 求解最大捆数本节主要求解在原料可以降级使用的前提下，求解三种成品的最大捆数。考虑到原料可以降级使用，所以我们先求解第三种成品的最大捆数，计算出余量，然后考虑该成品的余量，求解第二种成品的最大捆数，计算出余量，最后考虑这种成品的余量，求解第一种成品的最大捆数。（一） 成品三的最大捆数求解:（1）决策变量 在成品三中，记为按照该成品的第一种模式所生产的捆数，为按照该成品的第二种模式所生产的捆数，依此类推，为按照该成品的第种产品生产的捆数。（2）决策目标 因为要求的是捆数最大，所以决策目标为 （3）约束条件 记为该成品中第种原料的根数。为改成品中第种模式所用第种材料的根数。则很显然，所用的该种材料总根数不能超过原来该种材料的总根数。约束条件为 （4）余量 求出最优解后，显然第种原料的余量为，则总余量为。 （二）成品二的最大捆数求解: （1）决策变量 在成品二中，记为按照该成品的第一种模式所生产的捆数，为按照该成品的第二种模式所生产的捆数，依此类推，为按照该成品的第种产品生产的捆数。（2）决策目标 因为要求的是捆数最大，所以决策目标为 （3）约束条件 记为该成品中第种原料的根数。为第种模式所用第种材料的根数。为上级成品中余量被当做该级成品中第种原料的根数。则很显然，所用的该种材料总根数不能超过原来该种材料的总根数加上一级被当做该原料的根数。约束条件为 （4）余量 求出最优解后，显然第种原料的余量为，则总余量为。 （三）成品一最大捆数求解: 由于求成品一最大捆数的模型和求成品二的最大捆数的模型相同，所以这里就略去了求成品一最大捆数的模型。（记得余量是第二级和第三级之和）5.1.3 求解最短长度最大的捆数最多 本节主要求解在捆数达到最大的情况下，求解最短长度最大的捆数最多的优化方案。由于最短长度最大的这种模式必然属于成品一的模式，所以我们只需考虑成品一即可。由于要直接用程序找出最短长度最大的那些模式有困难，所以我们人为的从成品一的所有模式中进行观察，找出那些最短长度最长的那些模式。 （一）决策变量： 记为采用最短长度最长的那些模式中的第种模式所生产的捆数，为采用上述模式中第种模式所生产的捆数，依此类推，为采用上述模式中的第种模式所生产的捆数。（1） 决策目标 由于要求的是最短长度最长的那些成品的捆数最多，所以目标函数为（2） 约束条件 记为采用非最短长度最长的那些模式中的第个模式所生产的捆数，为非最短长度最长的那些模式中的第个模式所用的第种原料的根数，为最短长度最长的那些模式中的第个模式所用的第种原料的根数，为该成品中第种原料的根数，为上一级成品中余量被当做该级成品中第种原料的根数，为上一节中计算出的该成品的最大捆数。则显然约束条件为 5.1.4 验证模型的合理性 假设所有的原料或根数均被用完，先检验第三种成品，记为该成品中第种原料的总根数，为第种原料的长度，为该成品中一捆的最少总根数，为该成品中一捆的最短总长度。则最大捆数必须要满足如下条件，如果满足，则证明合理，否则不合理。 然后检验成品二模型的合理性，假设所有的原料或根数均被用完，记为该成品中第种原料的总根数，为第种原料的长度，为该成品中一捆的最少总根数，为该成品中一捆的最短总长度，为上级成品中的总余量。改变该成品中最后一种原料的总根数为则最大捆数必须要满足如下条件，如果满足，则证明合理，否则不合理。 成品一的检验模型同成品二的检验模型，故在这里不再赘言。5.2模型求解 5.2.1 模式求解将上述模式求解的模型用软件编程进行求解，求解程序见附录1，附录2，附录3，运行结果见表3，表4，表5（其中结果均为前面15种结果）。模式原料1原料2原料3原料4原料5原料6原料7原料8100011800020001261003000127000400013420050001350106000135100700013600080001423009000143110100001432001100014400112000144010130001441001400015040015000151210表3 成品一的模式以下模式略（共90849种模式）模式1234567891011121314100000000000340200000000000421300000000000430400000000000502500000000000511600000000000520700000000000601800000000001150900000000001231100000000000124011000000000013121200000000001321130000000000133014000000000014021500000000001411表4 成品二的模式 以下模式略（共10866种模式，第一行的表示原料）模式ABCDEFGHIJKLMNOPQRSTUVWX100000003200000000000000020000001130000000000000003000000023000000000000000400000100400000000000000050000001040000000000000006000000014000000000000000700000004010000000000000080000001211000000000000009000000031100000000000000100000002021000000000000001100000101210000000000000012000000112100000000000000130000000221000000000000001400001000310000000000000015000001003100000000000000表5 成品三的模式 以下模式略（共4286种模式，第一行的表示原料）将模型结果分别保存在文件名为3fangan1、3fangan2、3fangan3的excel文件中。5.2.2 最大捆数求解将上述成品三最大捆数线性规划求解模型用lingo编程进行求解，求解程序见附录4，求的最大捆数为137捆，具体方案及余量见表6。将余量带入成品二最大捆数线性规划求解模型用lingo编程进行求解，求解程序见附录5，求的最大捆数为37捆，求解结果及余量见表7。将余量带入成品一最大捆数线性规划求解模型用lingo编程进行求解，求解程序见附录6，求的最大捆数为18捆。数量ABCDEFGHIJKLMNOPQRSTUVWX根长度10000100002200000000000000588.514001000010210000000000000588.512000000220001000000000000588.55100000100110100000000000588.59001010000011100000000000589.521100100000002100000000000588.56000011100100010000000000588.523010001001010010000000000588.55001100010000110000000000588.57000011101000001000000000588.51000110100010001000000000588.54100010010000101000000000588.55010100000100101000000000589.51100001010000011000000000589.510100110000000020000000005892100002000000001100000000589.52101000100000001100000000588.52000000000000000031000000488.56000000000000000210010000488.51000000000000003000000001488.5余量000000010000000000000000 表6 成品三最优解及其余量（第一行的表示原料，它们的组合为一种模式，数量列为采用该种模式所生产的肠衣捆数，根列表示这种模式总共包含的根数，长度列表示采用该种模式所生产的肠衣总长度，余量行表示该种原料的余量）数量ABCDEFGHIJKLMN根长度100000032000300888.5500000200302100888.5100001004002001888.5300001010230010888.5200001020014000888.5100001110102200888.5200010020300002888.5400011102000003888.5700021000000500888.5400100101030101888.5300101100100301888.5300110020000040888.5120000100000131888.5余量22241020000000000表7 成品二最优解及其余量（第一行的表示原料，它们的组合为一种模式，数量列为采用该种模式所生产的肠衣捆数，根列表示这种模式总共包含的根数，长度列表示采用该种模式所生产的肠衣总长度，余量行表示该种原料的余量）5.2.3最短长度最长且捆数最大的方案求解在第一种成品的模式中观察到最短长度最长的模式为第四种原料的根数不为0，前三种原料的根数均为0的那些模式。把满足以上所述的模式放在文件名为3fangan11的文件中，其余的模式放在文件名为3fangan12的 excel 文件名中。将上述求解最短长度最大的捆数最多的模型用 lingo编程进行求解，求解程序见附录7，求得最终结果见表8。数量12345678根数长度30001180001989.530001504001989.51001201060198910016010032088.5118400070208911900010002089.51192101602088.512730035020891290000081989.5121100010620891560011702088.52901000091989.511000100902088.5余量100-3900-6-14表8 成品一的最终分配方案（第一行的表示原料，它们的组合为一种模式，数量列为采用该种模式所生产的肠衣捆数，根列表示这种模式总共包含的根数，长度列表示采用该种模式所生产的肠衣总长度，余量行表示该种原料的余量）6.模型的优缺点及其推广 先检验成品三模型的合理性，根据上述的成品三检验模型用 excel计算求解得到的该成品的最大捆数137，与用上面模型得到的结果吻合，充分说明得到的是最优方案。再根据上述的成品二检验模型用 excel 计算得到的该成品的最大捆数不超过42，而用上面模型得到的结果是37，吻合得很好，说明该方案合理。最后根据上述的成品一检验模型用 excel计算得到的该成品的最大捆数不超过18，与上面模型结果吻合，说明该方案是最优方案。本文主要应用matlab软件和lingo软件，建立线性规划模型，目标值限定为，满足条件的约束条件均为线性约束， lingo软件对于线性规划模型的运行效率最高，总体来说，这是一个高效率的模型。并且该模型考虑了总长度的误差以及根数的误差，增多了成品的总捆数。使得利益最大化。且对材料进行了降级使用，增加了材料的利用率，使得利益尽可能变大。所以该模型具有结构简明，方便快捷，节材效果显著等优点该模型的唯一缺点就是求得的最终解依然有坯料的剩余，造成了一定程度上的浪费，所以还有继续改进的可能。这种模型适用性广，可以应运到涉及一维下料优化问题的各个生产领域，如：各种管材、线材、棒材以及易拉罐切割问题甚至布料的切割问题等，均可以用上面的模型举一反三地进行解决。参考文献: 1肖华勇.实用数学建模与软件应用M.西安:西北工业大学出版社,2008 2刘勇彪.等界面长条类材料下料方案的最优化设计J.机械设计与制造,1994,5:12-13 3尹泽民等.精通MATLAB6M.北京:清华大学出版社,2002. 4王小东等.一维下料优化的一种新算法J.大连理工大学学报,2004,5,44(3):407-411附录1：num=0;c=3:0.5:6.5;d=;for k1=0:20 for k2=0:(20-k1) for k3=0:(20-k1-k2) for k4=0:(20-k1-k2-k3) for k5=0:(20-k1-k2-k3-k4) for k6=0:(20-k1-k2-k3-k4-k5) for k7=0:(20-k1-k2-k3-k4-k5-k6) for k8=0:(20-k1-k2-k3-k4-k5-k6-k7) if (k1+k2+k3+k4+k5+k6+k7+k8)=19&(k1*c(1)+k2*c(2)+k3*c(3)+k4*c(4)+k5*c(5)+k6*c(6)+k7*c(7)+k8*c(8)=88.5; num=num+1; fprintf(%2d %2d %2d %2d %2d %2d %2d %2d %2d,num,k1,k2,k3,k4,k5,k6,k7,k8) fprintf(n); d(num,1)=k1;d(num,2)=k2;d(num,3)=k3;d(num,4)=k4;d(num,5)=k5;d(num,6)=k6;d(num,7)=k7;d(num,8)=k8; end end end end end end end endEnd附录2：num=0;c=7:0.5:13.5;d=;for k1=0:8 for k2=0:(8-k1) for k3=0:(8-k1-k2) for k4=0:(8-k1-k2-k3) for k5=0:(8-k1-k2-k3-k4) for k6=0:(8-k1-k2-k3-k4-k5) for k7=0:(8-k1-k2-k3-k4-k5-k6) for k8=0:(8-k1-k2-k3-k4-k5-k6-k7) for k9=0:(8-k1-k2-k3-k4-k5-k6-k7-k8) for k10=0:(8-k1-k2-k3-k4-k5-k6-k7-k8-k9) for k11=0:(8-k1-k2-k3-k4-k5-k6-k7-k8-k9-k10) for k12=0:(8-k1-k2-k3-k4-k5-k6-k7-k8-k9-k10-k11) for k13=0:(8-k1-k2-k3-k4-k5-k6-k7-k8-k9-k10-k11-k12) for k14=0:(8-k1-k2-k3-k4-k5-k6-k7-k8-k9-k10-k11-k12-k13) if (k1+k2+k3+k4+k5+k6+k7+k8+k9+k10+k11+k12+k13+k14)=7&(k1*c(1)+k2*c(2)+k3*c(3)+k4*c(4)+k5*c(5)+k6*c(6)+k7*c(7)+k8*c(8)+k9*c(9)+k10*c(10)+k11*c(11)+k12*c(12)+k13*c(13)+k14*c(14)=88.5; num=num+1; fprintf(%2d %2d %2d %2d %2d %2d %2d %2d %2d %2d %2d %2d %2d %2d,num,k1,k2,k3,k4,k5,k6,k7,k8,k9,k10,k11,k12,k13,k14) fprintf(n); d(num,1)=k1;d(num,2)=k2;d(num,3)=k3;d(num,4)=k4;d(num,5)=k5;d(num,6)=k6;d(num,7)=k7;d(num,8)=k8;d(num,9)=k9;d(num,10)=k10;d(num,11)=k11;d(num,12)=k12;d(num,13)=k13;d(num,14)=k14; end end end end end end end end end end end end end endend 附录3：num=0;c=14:0.5:25.5;d=;for k1=0:5 for k2=0:(5-k1) for k3=0:(5-k1-k2) for k4=0:(5-k1-k2-k3) for k5=0:(5-k1-k2-k3-k4) for k6=0:(5-k1-k2-k3-k4-k5) for k7=0:(5-k1-k2-k3-k4-k5-k6) for k8=0:(5-k1-k2-k3-k4-k5-k6-k7) for k9=0:(5-k1-k2-k3-k4-k5-k6-k7-k8) for k10=0:(5-k1-k2-k3-k4-k5-k6-k7-k8-k9) for k11=0:(5-k1-k2-k3-k4-k5-k6-k7-k8-k9-k10) for k12=0:(5-k1-k2-k3-k4-k5-k6-k7-k8-k9-k10-k11) for k13=0:(5-k1-k2-k3-k4-k5-k6-k7-k8-k9-k10-k11-k12) for k14=0:(5-k1-k2-k3-k4-k5-k6-k7-k8-k9-k10-k11-k12-k13) for k15=0:(5-k1-k2-k3-k4-k5-k6-k7-k8-k9-k10-k11-k12-k13-k14) for k16=0:(5-k1-k2-k3-k4-k5-k6-k7-k8-k9-k10-k11-k12-k13-k14-k15) for k17=0:(5-k1-k2-k3-k4-k5-k6-k7-k8-k9-k10-k11-k12-k13-k14-k15-k16) for k18=0:(5-k1-k2-k3-k4-k5-k6-k7-k8-k9-k10-k11-k12-k13-k14-k15-k16-k17) for k19=0:(5-k1-k2-k3-k4-k5-k6-k7-k8-k9-k10-k11-k12-k13-k14-k15-k16-k17-k18) for k20=0:(5-k1-k2-k3-k4-k5-k6-k7-k8-k9-k10-k11-k12-k13-k14-k15-k16-k17-k18-k19) for k21=0:(5-k1-k2-k3-k4-k5-k6-k7-k8-k9-k10-k11-k12-k13-k14-k15-k16-k17-k18-k19-k20) for k22=0:(5-k1-k2-k3-k4-k5-k6-k7-k8-k9-k10-k11-k12-k13