数学建模 D题 肠衣搭配问题.doc

2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： D 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 长春工程学院 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2011 年 9 月 11 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：天然肠衣搭配问题摘要天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。本文对肠衣的搭配进行分析，使用运筹学与最优化方法针对对肠衣搭配问题中的目标、约束条件、决策变量建立一个数学模型，考虑到原料的最大化利用以及食品保鲜，提出运用最优化方法针对所建立的模型，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到原料搭配方案的最优目标。关键词：运筹学与最优学，优化资源分配 一 问题重述这是一个肠衣原料搭配方案设计的问题。天然肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。原料按长度分档，通常以0.5米为一档，如：3-3.4米按3米计算，3.5米-3.9米按3.5米计算，其余的依此类推。表1是几种常见成品的规格，长度单位为米，表示没有上限，但实际长度小于26米。表1 成品规格表最短长度最大长度根数总长度36.52089713.588914589为了提高生产效率，公司计划改变组装工艺，先丈量所有原料，建立一个原料表。表2为某批次原料描述。表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根据以上原料资料运用运筹学与最优化思想，以达到原料优化组合合理分配的效果，最终提高公司效率和资源利用率。公司对搭配方案有以下具体要求：(1) 对于给定的一批原料，装出的成品捆数越多越好；(2) 对于成品捆数相同的方案，最短长度最长的成品越多，方案越好；(3) 为提高原料使用率，总长度允许有 0.5米的误差，总根数允许比标准少1根；(4) 某种规格对应原料如果出现剩余，可以降级使用。如长度为14米的原料可以和长度介于7-13.5米的进行捆扎，成品属于7-13.5米的规格；(5) 为了食品保鲜,要求在30分钟内产生方案。二 问题分析为了方便区分，将三种规格的成品分为成品1、成品2、成品3.搭配方案的选择有如下5个要求：(1) 对于给定的一批原料，装出的成品捆数越多越好；(2) 对于成品捆数相同的方案，最短长度最长的成品越多，方案越好；(3) 为提高原料使用率，总长度允许有 0.5米的误差，总根数允许比标准少1根；(4) 某种规格对应原料如果出现剩余，可以降级使用。如长度为14米的原料可以和长度介于7-13.5米的进行捆扎，成品属于7-13.5米的规格；(5) 为了食品保鲜,要求在30分钟内产生方案。 考虑问题的题设和要求，我们要解决的是关于肠衣搭配的资源优化配置问题，对题目仔细地分析后，我们确定三种不同规格的成品1，成品2，成品3为最终成品数即在成品总长度可以有0.5的误差，总根数可以少一根的情况下，在有限资源下得出最多的最终总成品数资源配置的目标函数。我们分析关系，建立了使效益与效率最大化的模型，寻找到约束条件即成品数以长度长的成品为先，原料优先服务于长长度的成品规格以及总长度允许有 0.5米的误差，总根数允许比标准少1根，原料可降级使用等，利用约束条件起到的有效约束作用，再借助计算机对规划模型进行最优求解。此外，为了目标函数和约束条件的顺利表达，我们在正式模型建立之前，做了大量的完整而系统的的模型准备工作，用量化的语言理清了各部分之间的关系。三 模型假设1. 所有原料都能用于组装成捆，不考虑质量问题。2. 原料资料的统计不在方案产生的时间内。3. 原料在捆绑过程中不损坏。四 符号说明1. a 第一种规格成品中肠衣根数2. b 第二种规格成品中肠衣根数3. c 第一规格成品中肠衣根数4. （i=1，2,3） 各规格成品的捆数5. s 每种规格成品的总长度6. （i=1,2, 42）原料各档使用的根数7. Z 原料总长度五 模型的建立及求解 根据公司给的搭配方案中要求（2）和要求（4），得出以下结论。 即成品3的优先级大于成品2的的优先级大于成品1的优先级，也就是说长度长的原料优先使用，剩余原料降级使用，避免长原料的过多浪费，所以我们先以成品3为例进行方案搭配。 1.成品3的模型建立 决策变量 用（i=23,24,2542）表示各规格成品使用的原料的根数是非负整数。 决策目标 在成品3规格下得出最优搭配方案。 下面进行求解约束条件 为满足搭配要求及成品3规格表，应有 88.5Z89.5 模型求解 将（1），（2），（3）构成的整数线性规划模型（加上整数约束）输入LINGO如下： 88.5=14*x23+14.5*x24+15*x25+15.5*x26+16*x27+16.5*x28+17*x29+17.5*x30+18*x31+18.5*x32+19*x33+19.5*x34+20*x35+20.5*x36+21*x37+21.5*x38+22*x39+22.5*x40+23.5*x41+25.5*x42;14*x23+14.5*x24+15*x25+15.5*x26+16*x27+16.5*x28+17*x29+17.5*x30+18*x31+18.5*x32+19*x33+19.5*x34+20*x35+20.5*x36+21*x37+21.5*x38+22*x39+22.5*x40+23.5*x41+25.5*x42=89.5; x23+x24+x25+x26+x27+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x38+x39+x40+x41+x42=5;a1x23=26;a2x24=27;a3x25=28;a4x26=42;a5x27=28;a6x28=42;a7x29=45;a8x30=49;a9x31=50;a10x32=60;a11x33=52;a12x34=63;a13x35=49;a14x36=35;a15x37=27;a16x38=16;a17x39=12;a18x40=2;a20x41=6;a24x42=1;a27gin(x23);a28gin(x24);a29gin(x25);a30gin(x26);a31gin(x27);a32gin(x28);a33gin(x29);a34gin(x30);a35gin(x31);a36gin(x32);a37gin(x33);a38gin(x34);a39gin(x35);a40gin(x36);a41gin(x37);a42gin(x38);a43gin(x39);a44gin(x40);a45gin(x41);a46gin(x42);求解可以得到最优解如下： Variable Value X23 3.000000 X24 0.000000 X25 0.000000 X26 0.000000 X27 0.000000 X28 0.000000 X29 0.000000 X30 0.000000 X31 0.000000 X32 0.000000 X33 0.000000 X34 0.000000 X35 0.000000 X36 0.000000 X37 0.000000 X38 0.000000 X39 0.000000 X40 0.000000 X41 2.000000 X42 0.000000 Row Slack or Surplus 1 0.5000000 2 0.5000000 3 0.000000 A1 23.00000 A2 27.00000 A3 28.00000 A4 42.00000 A5 28.00000 A6 42.00000 A7 45.00000 A8 49.00000 A9 50.00000 A10 60.00000 A11 52.00000 A12 63.00000 A13 49.00000 A14 35.00000 A15 27.00000 A16 16.00000 A17 12.00000 A18 2.000000 A20 4.000000 A24 1.000000 即按照规格为成品3的搭配方案为：长度为的原料用3根，长度为的原料用2根，根据原料根数的限制，以以上比例出成品3只能出3捆，于是根据原料根数的剩余量，改变约束条件继续对剩余原料进行方案搭配，可得以下数据 表一 成品3搭配方案长度x23 x24x25x26x27x28x29x30X31 X32X33X34X35X36X37X38X39X40X41X42捆数用量3000000000000000002030110000002000000010020030000001000000000110000001040000000000012000200002000000010001003000000000000020005002100000000000110001001000000400000000008000001100300000000009010110000000000200007020000010000001100001010000010030000000001700000004001000000000101010010000000200000100021000000000200000120000100000020000200090000003100000100000011000010000030000000015000101100000200000002200000000000120000005100001010000020000001000102000000110000005000001030000100000005合计76109377116104556546121124剩余00000001000003017000000根据以上表格可知： 出成品3 124捆。（17.5-17.9m）剩余10根，（20-20.4m）剩余30根，（20.5-20.9m）剩余17根。根据要求（4）可将，原料降级使用到成品2的方案搭配中。2.成品2模型建立决策变量 用（i=9,10,1122）表示各规格成品使用的原料的根数是非负整数。 决策目标 在成品2规格下得出最优搭配方案。 下面进行求解约束条件 为满足搭配要求及成品2规格表，应有 88.5Z89.5 模型求解 将（1），（2），（3）构成的整数线性规划模型（加上整数约束）输入LINGO如下： 88.5=7*x9+7.5*x10+8*x11+8.5*x12+9*x13+9.5*x14+10*x15+10.5*x16+11*x17+11.5*x18+12*x19+12.5*x20+13*x21+13.5*x22+17.5*x30+20*x35+20.5*x36;7*x9+7.5*x10+8*x11+8.5*x12+9*x13+9.5*x14+10*x15+10.5*x16+11*x17+11.5*x18+12*x19+12.5*x20+13*x21+13.5*x22+17.5*x30+20*x35+20.5*x36=89.5; x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22+x30+x35+x36=8;x9=24;x10=24;x11=20;x12=25;x13=21;x14=23;x15=21;x16=18;x17=31;x18=23;x19=22;x20=59;x21=18;x22=25;x30=10;x35=30;x36=17;a27gin(x9);a28gin(x10);a29gin(x11);a30gin(x12);a31gin(x13);a32gin(x14);a33gin(x15);a34gin(x16);a35gin(x17);a36gin(x18);a37gin(x19);a38gin(x20);a39gin(x21);a40gin(x22);a41gin(x30);a42gin(x35);a43gin(x36);求解可得最优解如下： Feasible solution found. Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 115 Variable Value X9 4.000000 X10 0.000000 X11 1.000000 X12 0.000000 X13 0.000000 X14 0.000000 X15 0.000000 X16 0.000000 X17 0.000000 X18 0.000000 X19 0.000000 X20 1.000000 X21 0.000000 X22 0.000000 X30 0.000000 X35 1.000000 X36 1.000000 即按照规格为成品2的搭配方案为：长度为的原料用4根，长度为的原料用1根，长度为，的原料各用1根。根据原料根数的限制，以以上比例出成品2只能出1捆，于是根据原料根数的剩余量，改变约束条件继续对剩余原料进行方案搭配，可得以下数据 表二 成品2搭配方案长度x9x10x11x12x13x14x15x16x17x18x19x20x21x22x30x35x36捆数用量5000000000000102043200000000000102010120000020010110010050000001000000112120000000000140001000006000100000015000032000200000101000000200600000002000000103400000001000010200050000004000013200010000011000000230003000003000040012000000012000320000002000011000000042002000001000400010011000101000500000000110103000310020003100011000000000005110003000000000004300003合计910215121191110137217918650剩余000000000008100135 根据以上表格可知： 出成品2 50捆。（12.5-12.9m）剩余8根，（13-13.4m）剩余1根，（20-20.4m）剩余13根，（20.5-20.9m）剩余5根。根据要求（4）可将，原料降级使用到成品1的方案搭配中。3.成品1的模型建立决策变量 用（i=1,2,38）表示各规格成品1使用的原料的根数是非负整数。 决策目标 在成品1规格下得出最优搭配方案。 下面进行求解约束条件 为满足搭配要求及成品1规格表，应有 88.5Z89.5 模型求解 按照成品2，3的计算方法以及模型建立的过程可得成品1的答案方案如下表： 表三 成品1搭配方案长度x1x2x3x4x5X6x7x8x20x21x35x36捆数用量10000019000002010190000000020903080000001010100900000030110008100000111010000800001075022400000100110900000002合计213818221128148000013剩余08007111381135根据以上表格可知： 出成品1 13捆。（3.5-3.9m）剩余8根，（5-5.4m）剩余7根，（5.5-5.9m）剩余1根，（6-6.4m）剩余1根。（6.5-6.9m）剩余13根，（12.5-12.9m）剩余8根，（13-13.4m）剩余1根，（20-20.4m）剩余13根，（20.5-20.9m）剩余5根。总共可生产 如下表R1R2R3总共1350124187整体模型的求解在实际生产实践中，允许一定的误差，就像要求（3），（4），（5）所说，总长度允许有 0.5米的上下浮动，成品中根数可以少一根等等，虽然运用了LINGO软件可以直接求解，但是实际应用中变量可能会改变运行结果。为了得到更优化的结果，可以增加一些显然的约束条件，从而可以放大范围进行优化组合。例如，从要求中可得成品3的优先级高于成品2高于成品1，则在建模时捆数（分别为，）可增加以下约束 下面进行整体模型的建立 决策变量 用（i=1,2,342）表示各规格成品使用的原料的根数，显然是非负整数。 决策目标 以各成品捆数之和最大为目标，则有 Max= + + 根据成品要求，即有 成品长度s 88.5 s89.5 成品1规定根数 a 19a20 成品1规定根数 b 7b8 成品1规定根数 c 4c5 将（10）（11）（12）（13）（14）（15）条件，根据以上模型建立方法，输入lINGO 如下： Model： max=r1+r2+r3;s*(r1+r2+r3)=3*x1+3.5*x2+4*x3+4.5*x4+5*x5+5.5*x6+6*x7+6.5*x8+7*x9+7.5*x10+8*x11+8.5*x12+9*x13+9.5*x14+10*x15+10.5*x16+11*x17+11.5*x18+12*x19+12.5*x20+13*x21+13.5*x22+14*x23+14.5*x24+15*x25+15.5*x26+16*x27+16.5*x28+17*x29+17.5*x30+18*x31+18.5*x32+19*x33+19.5*x34+20*x35+20.5*x36+21*x37+21.5*x38+22*x39+22.5*x40+23.5*x41+25.5*x42;a*r1=x1+x2+x3+x4+x5+x6+x7+x8;b*r2=x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22;c*r3=x23+x24+x25+x26+x27+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x38+x39+x40+x41+x42;s=88.5;a=19;a=7;b=4;c=5;x1=43;x2=59;x3=39;x4=41;x5=27;x6=28;x7=34;x8=21;x9=24;x10=24;x11=20;x12=25;x13=21;x14=23;x15=21;x16=18;x17=31;x18=23;x19=22;x20=59;x21=18;x22=25;x23=35;x24=29;x25=30;x26=42;x27=28;x28=42;x29=45;x30=49;x31=50;x32=64;x33=52;x34=63;x35=49;x36=35;x37=27;x38=16;x39=12;x40=2;x41=6;x42=1;gin(r1);gin(r2);gin(r3);gin(x1);gin(x9);gin(x10);gin(x11);gin(x12);gin(x13