天然肠衣搭配问题.doc

天然肠衣搭配问题摘要 本文以天然肠衣制作加工产业的组装工序为背景，根据给定的成品规格和原料描述，在一定的限定条件下，设计合理的原料搭配方案，则工人可以根据这个方案“照方抓药”进行生产。本文的主要工作如下：首先对题目给出的限定条件逐条进行分析，将问题分解成两个线性规划问题：（1）求出每种单成品的最大捆数；（2）在捆数为的所有方案中，求出满足限定条件的最优搭配方案。对单成品分配后的剩余原料，本文同样建立了一个线性规划模型求出剩余原料最优搭配方案。其次对模型进行求解。由于限定条件有时间因素，因此模型的求解是本文的难点。在利用LINGO软件求解上述模型时，当原料种类增多、单成品最大捆数增大时，求解时间远远超出30分钟的限定条件，因此本文提出了两种提高求解速度的方法：（1） 通过增加约束条件对模型进行改进；（2） 通过分步求解的方法降低求解时间。通过这两种方法，极大的改进了成品2和成品3以及剩余原料的求解时间。最后，本文将模型进行了推广和扩展。在实际的生产中，各原料的数量并不一定与给出的原料描述一致，考虑到模型的通用性和一般性，本文使用Visual Studio2005设计了图形用户界面，并实现了用C#语言调用LINGO程序进行求解，最终将模型的计算结果即最优搭配方案返回到图形用户界面上。该软件操作简单、使用方便，该软件的建立不仅达到了模型的推广，而且在实际生产中若遇到原料数量发生改变，不需要再重新建立模型，应用软件即可自动得出结果，具有一定的实用性和一般性。关键词：天然肠衣，线性规划，LINGO，求解速度，图形用户界面目录一、问题重述3二、模型假设与符号分析42.1 模型假设42.2 符号说明4三、模型建立与求解43.1 问题分析43.1.1 建模的整体思路43.1.2 模型的扩展VS+LINGO的图形用户界面53.2 模型的建立53.2.1 单成品最大捆数的数学模型53.2.2 单成品搭配方案的数学模型63.2.3 剩余原料搭配方案的数学模型73.3模型的求解73.3.1 数学模型的改进83.3.2 求解方法的改进93.4 结果分析9四、模型的改进与推广104.1 模型的推广104.2 软件的设计思想10五、模型评价11六、参考文献11附录1 Lingo程序清单12附录2 模型计算时间14附录3 最优方案15附录4 C#程序用户图形界面19附录5 C#程序清单20一、问题重述天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。原料按长度分档，通常以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给出的实际数据进行求解，生成最终的优化搭配方案。二、模型假设与符号分析2.1 模型假设（1）天然肠衣加工过程中，成品规格均按照表1所示；（2）总长度 0.5米的误差不影响实际操作；（3）丈量数据与实际数据完全相符；（4）生产中原料没有破损情况；（5）当某种规格出现剩余时，长度降级处理时可以降12级；（6）工人完全按照方案“照方抓药”；2.2 符号说明（1）设分别表示单成品的根数、总长度、原料个数、最大捆数； 分别表示总根数的上限和下限，分别表示总长度的上限和下限，其中。（2）表示生成的搭配方案中，第捆中第个原料的根数，其中，。（3）、分别表示成品所使用的原料的长度和总根数，。（4）表示单成品中每捆成品所需原料的个数，其中，。（5）表示第捆成品中原料的长度，其中，。三、模型建立与求解3.1 问题分析3.1.1 建模的整体思路表1给出的肠衣制作加工的三种规格，是将所有原料按长度在区间3,6.5，7,13.5，14 ,+进行的划分。我们将每一种成品规格简称为成品，每种单成品的根数、总长度、最大捆数分别用表示，它们的取值如表3所示。表3 单成品规格表成品总根数总长度原料个数120898288914358924根据问题的描述，我们将要求（1）（5）称为限制条件，模型的建立和求解应该基于对限制条件的分析。条件（1）和（2）分别要求“成品捆数越多越好”、“最短长度最长的成品越多越好”，如果同时考虑这两个条件，这是一个多目标规划问题1，模型的建立和求解的复杂度较高，因此我们将问题分解成两个线性规划问题2-4：首先，利用线性规划的方法求出每种单成品的最大捆数（详见3.2.1节）；其次，在捆数为的所有方案中，找出满足条件（2）的最优方案（详见3.2.2节）。条件(3)是为了提高原料使用率，单成品的总长度允许有 0.5米的误差，单成品的总根数允许比标准少1根。设、分别表示和的上、下限，则：(1)(2)条件(4)提出了对于剩余原料的降级处理规则，因此可以在单成品生成最优方案后，将所有的剩余材料进行集中处理，以提高材料的使用率（详见3.2.3节）。条件(5)要求在30分钟内产生最优方案。由于本文所建立的数学模型都是线性规划模型，因而使用LINGO软件进行求解5-6。为了确保在30分钟内可以得出所需要的最优搭配方案，必要时还要对模型以及求解方法进行改进（详见3.3节）。3.1.2 模型的扩展VS+LINGO的图形用户界面通过分析可以得出，在实际的肠衣加工制作过程中，原料的长度区间一般不变，但是每种长度的原料个数可以不同。因此，只考虑表2给定的原料数量是不合理的，本文用Visual Studio2005软件设计图形用户界面7，用户只需根据实际的原料数量，即可生成每种单成品的最优搭配方案以及剩余原料的搭配方案（详见4.1节）。3.2 模型的建立3.2.1 单成品最大捆数的数学模型设对于单成品，生成的搭配方案所包含的原料捆数用表示，则目标函数为：设为单成品中每捆成品所需原料的个数，生成的搭配方案中单成品所包含的捆数用表示，则根据表3，成品中每捆成品所包含的原料根数和长度满足如下约束条件：（成品所含原料根数）（成品所含原料长度）其中，成品中每捆成品的原料总根数和总长度的上、下限、由公式（1）、（2）给出，原料个数见表3。综上所述，单成品最大捆数的数学模型由公式（3）表示，模型命名为Model1，程序清单见附录1。（3）其中，成品所需原料的长度、根数的值见表4表6。表4 成品1的、值长度（米）33.544.555.566.5根数（个）4359394127283421表5 成品2的、值长度（米）77.588.599.51010.5根数（个）2424202521232118长度（米）1111.51212.51313.5根数（个）312322591825表6 成品3的、值长度（米）1414.51515.51616.51717.5根数（个）3529304228424549长度（米）1818.51919.52020.52121.5根数（个）5064526349352716长度（米）2222.52323.52424.52525.5根数（个）1220600013.2.2 单成品搭配方案的数学模型在问题的描述中，条件（2）要求对于成品捆数相同的方案，最短长度最长的成品越多，方案越好。设表示第捆成品中原料的长度，则第捆成品的最短长度为，则所求问题为最短长度和的极大化问题，因此目标函数为：除了成品的每捆根数和长度满足表3所示的约束条件外，还需增加原料使用数量的约束条件，设表示生成的搭配方案中，第捆中第个原料的根数，其中，则：因此，单成品搭配方案的数学模型由公式（4）表示，模型命名为Model2-（），程序清单见附录1。（4）3.2.3 剩余原料搭配方案的数学模型当成品分配完成之后，剩余的原料剩余可降级使用。设第种规格产品对应原料剩余，第种规格的剩余原料降为级的原料根数为,则经降级处理后生产某种规格产品的原料根数为自身剩余的根数以及从上一级增加的原料量的和减去将为下级的根数，该数学模型用公式（5）表示（5）3.3模型的求解本文所建立的模型均为线性规划模型，而LINGO软件其特色在于内置建模语言、提供十几个内部函数、可以允许决策变量是整数(即整数规划，包括 0-1 整数规划)、方便灵活、而且执行速度非常快、能方便与EXCEL、数据库等其他软件交换数据，是求解优化问题的最佳选择，因此本文选择LINGO11，根据表2给出的一组原料数据对模型进行编程、求解。程序的运行环境为： 操作系统：Microsoft Window XP CPU：Intel Core Quad CPU Q9550 2.83GHz 内存：3GB（1）单成品最大捆数模型（Model1）程序的运行时间为00:00:00（见附录2），运行结果为：，。（2）单成品搭配方案模型（Model2-1、Model2-2、Model2-3）程序的运行时间（见附录2）如表7所示：表7 单成品搭配方案模型的计算时间Model2-1Model2-2Model2-300:00:003:35:34从表7中可以看出，对于成品1，最优搭配方案的时间满足限制条件（5），而成品2的计算时间已经远远超过30分钟的约束，成品3在运行了24小时后人为终止。从模型的求解时间上可以看出，由于成品2和成品3需要用到的原料数量较大，成品的最大捆数较大，因此求解速度较低。因此，需要对模型以及求解方法进行一定的改进，以提高求解速度。3.3.1 数学模型的改进对于优化问题，增加约束条件可以缩小求解范围，进而降低求解消耗的时间。由于单成品搭配模型对于给定数据的计算时间过长，因此本文采用增加约束条件的方法来提高模型的求解速度。在公式（4）中，表示生成的搭配方案中，第捆中第个原料的根数，其中，。根据表2给出的原料数据，可以得出的上限为： （）将上式作为约束条件加入公式（4）中，得到了改进的单成品搭配模型如公式（4）所示，模型那个命名为Model2-，程序清单见附录1。（4）对于成品2，模型Model2-的运行时间为00:09:08（见附录2），运行速度大幅提升；对于成品3，运行时间仍超过30分钟，因此还需要进一步提升求解速度。3.3.2 求解方法的改进对成品3进行最优搭配方案的求解时，我们发现导致求解速度慢的一个主要原因是成品3最大捆数（）太大。因此需要将最优方案的捆数分若干次求出，则总体的计算时间将会大幅降低。依据3.3.1节对成品2的优化结果，以及多次试验的基础上，如果要在10分钟之内完成成品3的求解，每次计算的最大捆数不应超过15个。因此，根据上述思想对最大捆数进行分割，以提高求解速度。具体步骤如下：设表示第i次求出的最优捆数，表示该成品的最大捆数， （1） 求出该成品最优方案的最大捆数；（2） 对进行划分，先后依次求出捆的最优搭配方案，其中；（3） 给出该成品的最优搭配方案。用分步求解法对成品3进行求解，运行时间为00:02:04（见附录2），满足30分钟的限定条件，但最优方案的最大捆数从137下降到134。应该看到，该方法是在牺牲了全局最优方案的条件下，保证了较少的运行时间。因此该方案是全局最优方案的一个近似解。剩余原料搭配方案的优化模型，由于最大捆数较小，因此直接用LINGO编程求解即可，模型命名为Model3，程序清单见附录1。3.4 结果分析 依据3.3节的求解方法，对表1、表2给定数据进行求解，得到了每种成品的最优搭配方案，如表8所示的成品1的最优方案，成品2、成品3以及剩余原料的最优搭配方案见附录3。表8成品1的最优搭配方案33.544.555.566.5第1捆04732220第2捆04732220第3捆54032204第4捆34232240第5捆24512240第6捆04830212第7捆54130223第8捆54032213第9捆44132222第10捆44132240第11捆44132240第12捆54032222第13捆44132231第14捆14532220（1）模型求解的总时间为00:11:12，满足30分钟的限定条件，即本文所建立的模型及求解方法能够保证食品新鲜的条件下产生最优分配方案；（2）成品1、2、3的理论最大捆数分别为14、37、137，实际生成的最优搭配方案，成品1、2、3包含的捆数分别为14、37、134；这说明用保证较小运行时间的基础上，牺牲了全局最优方案；（3）分步求解法在的优点：节约时间、方便；缺点：很难满足生产的全部最优条件。四、模型的改进与推广4.1 模型的推广在实际的肠衣生产过程中，指定原料的数量是不合理的，因此为了使得模型有一定的通用性，本文引入Visual Studio2005软件设计图形用户界面，并调用LINGO进行求解，最终将最优方案显示在图形界面上。图形用户界面对于制作一个供反复使用且操作简单的专用工具是最好的选择，本文运用图形用户界面编程建立一个自动的方案生成模型，用户只需要根据实际生产情况输入每种长度的原料数量，程序运行相应语句自动得出最优搭配方案。4.2 软件的设计思想软件的设计思想如图1所示，用户在用Visual Studio2005(简称VS)设计的用户界面上，输入每种尺度的原料数量，点击生成方案按钮，调用LINGO软件进行模型的求解，并将生成的最优方案返回给VS，显示在用户界面上。输入原料数量输出最优方案求解Model1求解Model2应用C#求解C#调用lingo解答开始结束图1 软件的设计流程本文采用C#语言进行程序设计，图形用户界面及使用方法见附录4，程序清单见附录5。 五、模型评价本文运用线性规划建立数学模型，利用LINGO软件求解，并设计出一个可以提供反复使用且操作简单的程序，达到模型的推广。我们提出的模型具有如下特点：（1）所得到的模型结果经过与实际生产中的验证符合情况具有实际意义；（2）对于最优方案，我们重新对成品规格表和原料表以及限制条件进行对比，其完全适用于约束条件的限制；（3）经过多组数据以及自编数据的检验，确定模型具有较强的稳定性；（4）在相同组数随机取出数据，所得到的结果与上表结果进行比较确定上表结果为最优结果；（5）我们从实践检验、约束检验、稳定性和最优性四个方面进行对结果数据的分析和检验，使所得结果更具有可靠性，更易于适用实际生产；（6）设计图形用户界面GUI，达到了模型的推广，具有一定的实用性和简洁性。六、参考文献1姜启源，谢金星，叶俊。数学建模M. 北京：高等教育出版社，2003 2宣明.数学建模与数学实验M.杭州：浙江大学出版社.2010.9.3韩中庚.数学建模竞赛获奖论文精选与点评M. 北京：科学出版社，2007.4朱道元等.数学建模案例精选M. 北京：科学出版社，2003 5谢金星，薛毅.优化模型与LINGO软件M. 北京：清华大学出版社，20056袁新生，邵大宏，郁时炼.LINGO和Excel在数学建模中的应用M .北京：科学出版社，2007.7Wei-Meng Lee著.C#2008编程参考手册M.北京：清华大学出版社，2007.附录1 Lingo程序清单程序Model1: 求解最大捆数的LINGO程序model:sets:su1/1.8/:len1,num1,x1;su2/1.14/:len2,num2,x2;su3/1.24/:len3,num3,x3;endsetsdata:len1=3 3.5 4 4.5 5 5.5 6 6.5;num1=43 59 39 41 27 28 34 21;len2=7 7.5 8 8.5 9 9.5 10 10.5 11 11.5 12 12.5 13 13.5;num2=24 24 20 25 21 23 21 18 31 23 22 59 18 25;len3=14 14.5 15 15.5 16 16.5 17 17.5 18 18.5 19 19.5 20 20.5 21 21.5 22 22.5 23 23.5 24 24.5 25 25.5;num3=35 29 30 42 28 42 45 49 50 64 52 63 49 35 27 16 12 2 0 6 0 0 0 1;enddatamax=H1+H2+H3;sum(su1(i):x1)=19*H1;sum(su2(i):x2)=7*H2;sum(su3(i):x3)=4*H3;sum(su1(i):x1*len1)=88.5*H1;sum(su2(i):x2*len2)=88.5*H2;sum(su3(i):x3*len3)=88.5*H3;for(su1(i):x1=num1);for(su2(i):x2=num2);for(su3(i):x3=num3);gin(H1);gin(H2);gin(H3);End程序Model2-1：求解单成品1的LINGO程序model:sets:br1/1.14/:shu;su1/1.8/:len1,num1,z1;tab1(br1,su1):x1;endsetsdata:len1=3 3.5 4 4.5 5 5.5 6 6.5;num1=43 59 39 41 27 28 34 21;enddatamax=sum(br1(i):min(su1(j):if(x1#gt#0,len1,10000);for(su1(j):z1(j)=sum(tab1(i,j):x1);for(br1(i):sum(tab1(i,j):x1*len1(j)=88.5);for(br1(i):sum(tab1(i,j):x1)=19);for(su1(j):sum(tab1(i,j):x1)=num1(j);for(tab1:gin(x1);for(br1(i):shu(i)=sum(tab1(i,j):x1);End程序Model2-2：求解单成品2的LINGO程序model:sets:br2/1.37/:shu;su2/1.14/:len2,num2,z2;tab2(br2,su2):x2;endsetsdata:len2=7 7.5 8 8.5 9 9.5 10 10.5 11 11.5 12 12.5 13 13.5;num2=24 24 20 25 21 23 21 18 31 23 22 59 18 25;enddatamax=sum(br2(i):min(su2(j):if(x2#gt#0,len2,10000);for(su2(j):z2(j)=sum(tab2(i,j):x2);for(br2(i):sum(tab2(i,j):x2*len2(j)=88.5);for(br2(i):sum(tab2(i,j):x2)=7);for(su2(j):sum(tab2(i,j):x2)=num2(j);for(tab2:gin(x2);for(br2(i):shu(i)=sum(tab2(i,j):x2);End程序Model2-3：求解单成品3的LINGO程序model:sets:br3/1.137/:shu;su3/1.20/:len3,num3,z3;tab3(br3,su3):x3;endsetsdata:len3=14 14.5 15 15.5 16 16.5 17 17.5 18 18.5 19 19.5 20 20.5 21 21.5 22 22.5 23.5 25.5;num3=35 29 30 42 28 42 45 49 50 64 52 63 49 35 27 16 12 2 6 1;enddatamax=sum(br3(i):min(su3(j):if(x3#gt#0,len3,10000);for(su3(j):z3(j)=sum(tab3(i,j):x3);for(br3(i):sum(tab3(i,j):x3*len3(j)=88.5);for(br3(i):sum(tab3(i,j):x3)=4);for(su3(j):sum(tab3(i,j):x3)=num3(j);for(tab3:gin(x3);for(br3(i):shu(i)=sum(tab3(i,j):x3);end附录2 模型计算时间Model1求解最大捆数的运行时间Model2-1求解单成品1的运行时间 Model2-2求解单成品2的运行时间 Model2-2求解单成品2的运行时间 Model4修改后求解单成品3的运行时间T=T1*13.7（T1为单个运行时间，T为总时间）附录3 最优方案成品2最优搭配77.588.599.51010.51111.51212.51313.5第1捆00120001000022第2捆00010100210300第3捆00010110101300第4捆00010010110000第5捆00000200400110第6捆00000400000310第7捆00010101200210第8捆00001112000021第9捆00003000020201第10捆00000003310100第11捆00010002112100第12捆00101001110201第13捆00011001101300第14捆00111010001400第15捆00001000331000第16捆00100020030101第17捆00020011001021第18捆00102000101102第19捆00000121101101第20捆00100012002110第21捆00001110110300第22捆00000121110101第23捆00012000011201第24捆00000110230100第25捆00200110000103第26捆00012100000112第27捆00001210100102第28捆00011100100310第29捆00000031020200第30捆00021100000022第31捆00010110200201第32捆00012000001400第33捆00020100001400第34捆00011100110111第35捆00111000100121第36捆00110001012011第37捆00020010002300成品3 最优搭配1414.51515.51616.51717.51818.51919.52020.52121.52222.52323.52424.52525.5第1捆200000000002000100000000第2捆200000000000210000000000第3捆200000000001020000000000第4捆200000000000210000000000第5捆000000000000210030010000第6捆000000000000000030010000第7捆000000130001000000000000第8捆000000040010000000000000第9捆000000040001000000000000第10捆000000310000100000000000第11捆000000000000000030010000第12捆000000101000000000030000第13捆000000040001000000000000第14捆000000300000100000000000第15捆010000010030000000000000第16捆000000040001000000000000第17捆010000030000000100000000第18捆000030000000011000000000第19捆020000000002000100000000第20捆020000000002001000000000第21捆020000000001200000000000第22捆0200