天然肠衣搭配问题论文定稿1

1、2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从a/b/c/d中选择一项填写）： d 我们的参赛报名号为（如果赛区设置

2、报名号的话）： 所属学校（请填写完整的全名）： 重庆教育学院 参赛队员 (打印并签名) ：1. 王平 2. 王静 3. 王鸿玫 指导教师或指导教师组负责人 (打印并签名)： 施成湘 日期： 2011年 9 月11日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：论文题目：天然肠衣搭配问题摘 要随着时代的发展，天然肠衣制作加工已经是我国的一个传统产业，在生产中占优很

3、重要的地位。本文就是针对天然肠衣的加工问题展开讨论并建立相应的优化模型，本问题涉及到两方面内容：（一）方案的内容，（二）方案的个数。根据线性规划理论，建立双目标函数模型。从第四个条件肠衣有剩余的角度入题，即剩余的可以降级使用，我们立运筹学中的双目标函数列出了我们最初的模型原型，从而我们可以从中得出的比较合理优化的分配方案577种，在具体解决这个问题的时候，我们从第三种成品开始建立模型，得出初步方案367种，剩余降级使用的数目8根，将剩余的原料归纳到第二种成品中最长的原料中，再利用第二种成品建立模型得出初步方案107种，并得出剩余数目35根，同理降级到第一种成品最长的原料中使用；最终通过筛选得到

4、的最优方案为第一类12种、第二类33种、第三类34种，从捆数上看则是192捆，详见文中总表。对于第三个条件中提出的为了提高利用率而允许有误差，条件是要在30分钟内得出最好的方案，为降低计算复杂度，算法对文中原材料的取定，是要求尽可能的少。通过运行，得出的最优的方案，见下表，总方案数剩余方案数捆数剩余根数第一类产品367341358第二类产品107334135点三类产品1031216-此双目标函数模型很好的解决了天然肠衣的加工分配问题，且方法具有很强的严密性，提高了运算速度，缩短了安排时间，提高效率，能够广泛推广到其他材料的加工安排问题上。关键词： 肠衣加工 多目标线性规划 (一) 问题的提出1

5、.问题的重述天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。原料按长度分档，通常以0.5米为一档，如：3-3.4米按3米计算，3.5米-3.9米按3.5米计算，其余的依此类推。表1是几种常见成品的规格，长度单位为米，表示没有上限，但实际长度小于26米。表1 成品规格表最短长度最大长度根数总长度36.52089713.588914589为了提高生产效率，公司计划改变组装工艺，先丈量所有原料，建立一个原料表。表2为某批次原

6、料描述。表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

7、.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

8、米的误差，总根数允许比标准少1根；(4) 某种规格对应原料如果出现剩余，可以降级使用。如长度为14米的原料可以和长度介于7-13.5米的进行捆扎，成品属于7-13.5米的规格；(5) 为了食品保鲜,要求在30分钟内产生方案。请建立上述问题的数学模型，给出求解方法，并对表1、表2给出的实际数据进行求解，给出搭配方案。2问题的初步分析这是一个典型的优化问题。本问题最终要求给出一个合理的搭配方案，将涉及到两方面内容：（一）方案的内容，（二）为达到尽可能多的使用原材料，如何选择方案，即方案的个数。这两方面将是问题解决的关键。将通过两次建立数学模型，给予求解。对方案的内容，由于要求（2）提到，对成品捆数

9、相同的方案，最短长度最长的方案优先考虑，因此，在同一捆中尽量避免出现相同长度的原材料，即使出现也用于替代下一级中最短的原材料。基于要求（3）提到其总长度允许有 0.5米的误差，那么在考虑约束条件时，便考虑成首选总长度89米的，次而考虑88.5米和89.5的总长度的方案。对方案的个数的求解，很显然这是个线性规划问题。满足一定限额内的资源的最大使用。考虑到要求（5），必须在30分钟内形成方案，即要求模型算法的计算复杂度尽可能的小，计算时间尽量短。故，将原材料根据成品规格的要求分成三大类进行逐层优化，并结合要求（3），提高原材料的使用率，长的原材料可以降级使用，算法将考虑对原材料从长到短的讨论。(二

10、) 模型假设及符号说明1 模型假设1) 假设在丈量所有原料时，原料没有任何损坏；2) 假设原料只有这3种成品规格；3) 假设原料的各种长度的根数如数据所示，没有差错；4) 假设在每种方案中，各种肠衣根数的取值范围为0,1 ；2 符号说明符号表示的意思表示第j种方案下的捆数总捆数第种方案下第种产品的根数第种原材料的限额第种方案下的捆数 (三) 模型建立与求解本问题在求解的过程中要解决两方面内容：（一）方案的内容，（二）方案的个数。为降级计算复杂度，减少计算量，算法首先将原材料按照成品的方案分成三大类，逐类进行计算优化。并且剩余的原材料将遗留到下一类中再次使用。方案内容将由枚举法产生。对方案的个数

11、的求解，根据线性规划理论求解。1 理论线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。在企业的各项管理活动中,例如计划、生产、运输、技术等问题,线性规划是指从各种限制条件的组合中,选择出最为合理的计算方法,建立线性规划模型从而求得最佳结果。线性规划是运筹学的重要分支，它是一门实用性很强的应用数学学科。随着计算机技术的发展和普及，线性规划的应用越来越广泛。它已成为人们为合理利用有

12、限资源制订最佳决策的有力工具。一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素.从实际问题中建立数学模型一般有以下三个步骤； 1.根据影响所要达到目的的因素找到决策变量； 2.由决策变量和所在达到目的之间的函数关系确定目标函数； 3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。 所建立的数学模型具有以下特点： 1、每个模型都有若干个决策变量（），其中为决策变量个数。决策变量的一组值表示一种方案，同时决策变量一般是非负的。 2、目标函数是决

13、策变量的线性函数，根据具体问题可以是最大化（）或最小化（），二者统称为最优化（opt）。 3、约束条件也是决策变量的线性函数。 当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。线性规划问题建立的最终数学模型包括：决策变量、约束条件和目标函数。建立线性规划问题的方法：设决策变量；列出约束条件；分析目标，列出目标函数。线性规划数学模型的简写： 线性规划的矩阵表示方式： 线性规划的标准形式：目标函数： 约束条件： 线性规划特点：（1）每一个问题都用一组决策变量来表示；（2）用一组不等式或等式来描述有限的资源和决策变量之间的关系（约束）；（3）每一个问

14、题都有一个目标要求，常采用决策变量的函数来表示（目标函数）。2 模型的建立假设各种长度的肠衣为种，成品包装共有种方案，每种方案中的各肠衣的取值为(=1,2,;=1,2,)根,各种肠衣的限额为(=1,2)，(=1,2)表示第j种方案下的捆数，表示总捆数。 1） 方案模型假设每类肠衣取（=1,2,）根，每类肠衣长度为（=1,2,）米，s.t. =1,2,2） 方案选取模型每种方案中的各肠衣的取值为(=1,2,;=1,2,)根,各种肠衣的限额为(=1,2)，(=1,2)表示第j种方案下的捆数，表示总捆数。 s.t. 3 原材料的分类表格第一类第二类第三类3-3.47-7.414-14.43.5-3.

15、97.5-7.914.5-14.94-4.48-8.415-15.44.5-4.98.5-8.915.5-15.95-5.49-9.416-16.45.5-5.99.5-9.916.5-16.96-6.410-10.417-17.46.5-6.910.5-10.917.5-17.911-11.418-18.411.5-11.918.5-18.912-12.419-19.412.5-12.919.5-19.913-13.420-20.413.5-13.920.5-20.921-21.421.5-21.922-22.422.5-22.923-23.423.5-23.924-24.424.5-24.

16、925-25.425.5-25.94. 模型的求解第三类产品： 设：每类肠衣取根(=1,2,320);(注：第三类有四个为零根，所以为1到20) （） s.t. 利用matlab软件计算可以得到367个方案。设： 表示第j种方案下的捆数，表示总捆数； st 利用matlab软件得放入筛选后的方案及方案选取的数量方案；第三类产品分配详见总表一（1）；剩余的根数如下表:长度1415.51717.51818.520212223.5剩余根数1111111184可形成的方案：15.5-15.917-17.418.5-18.919-19.423-23.423.5-23.9方案113方案231方案3112最

17、后余下的根数：长度141820212223.5剩余根数111122将剩余的根数8根降级到第二类的最长长度13.513.9米；第三类总方案详见总表一（2）；原材料的分类表格：第一类第二类3-3.47-7.43.5-3.97.5-7.94-4.48-8.44.5-4.98.5-8.95-5.49-9.45.5-5.99.5-9.96-6.410-10.46.5-6.910.5-10.911-11.411.5-11.912-12.412.5-12.913-13.413.5-13.9 表3 原料描述表长度3-3.43.5-3.94-4.44.5-4.95-5.45.5-5.96-6.46.5-6.9根

18、数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.9根数312322591833第二类产品： 设：每类肠衣取根(=1,2,3，14); （） s.t. 说明：通过matlab软件得出有107种方案。 设： 表示第j种方案下的捆数，表示总捆数； st 利用matlab软件得放入筛选后的方案及方案选取的数量如下表第二类产品分配详见总表二(1)；得出剩余的肠衣根数为35根。剩余

19、的根数如下表：长度99.51010.51111.51212.51313.5剩余根数41322112111可形成的方案：9.51012.5方案134最后余下的根数：长度910.51111.51212.51313.5剩余根数322111711将剩余的根数28/根降级到第一类的最长长度5.55.9米；第二类总方案详见总表二(2)；表4 原料描述表长度3-3.43.5-3.94-4.44.5-4.95-5.45.5-5.96-6.46.5-6.9根数4359394127283456第一类产品： 设：每类肠衣取根(=1,2,3，8); 说明： 得出方案103种 设： 表示第j种方案下的捆数，表示总捆数；

20、 st 利用matlab软件得方案如下表第一类产品分配12345678123233303223323213323331313423332123533132313633133123733222223833223033933230323103323113311333121331233320233由于所剩根数少于20根，因此不予考虑。综上所述：方案总表如下：表（b）总方案数剩余方案数捆数剩余根数第一类产品367341358第二类产品107334135点三类产品1031216-六、模型的评价与应用：模型的评价：优点：该模型简便易懂，思路清晰合理；运用线性规划的模型求解相对合理，运用matlab处理数据

21、可以节约运算时间和运算的复杂程度；该模型有一定的推广意义；模型的应用： 在实际生产和一些经济管理以及一些关于合理分配中，我们常常会遇到类似的分配方案的优化问题，而对于现在一切利益化的今天来说，我们如何从各种方案中选取最合理，最优的方案已经越来越重要。我们的模型可以很好的运用于实际产品的生产，一些商品的管理与分配等问题中。（1）总表一 原材料方案1414.51515.51616.51717.51818.51919.52020.52121.52222.523.525.5捆数100000000000000101110220000000000000110100113000001101110000000

22、003400000111010100000000350001000111010000000096000100101011000000007700010010110010000000780001001110000010000059000101000111000000001100001010010101000000041100010101000110000000112001000011011000000002130010000111001000000011400100010011100000000115001000011000110000003160010110000000110000011700

23、110000001110000000118010000010111000000007190100000110101000000012001000010001010000000521010011000000001100003220110000100000101000032301100010000001001000112410000000111100000000525100000010110100000001261000000110011000000082710000001110000100000628100000100100100000001291000010000111000000073010

24、010000001100100000231100100000100101000002（2） 原材料方案1414.51515.51616.51717.51818.51919.52020.52121.52222.523.525.5捆数10000000000000010111022000000000000011010011300000110111000000000340000011101010000000035000100011101000000009600010010101100000000770001001011001000000078000100111000001000005900010100

25、011100000000110000101001010100000004110001010100011000000011200100001101100000000213001000011100100000001140010001001110000000011500100001100011000000316001011000000011000001170011000000111000000011801000001011100000000719010000011010100000001200100001000101000000052101001100000000110000322011000010

26、0000101000032301100010000001001000112410000000111100000000525100000010110100000001261000000110011000000082710000001110000100000628100000100100100000001291000010000111000000073010010000001100100000231100100000100101000002320000000001000000003013300000000000000000310134001100000020000000001总表二：77.588.

27、599.51010.51111.51212.51313.5捆数10000111011110112000101011111001300011010110111140001110010111115001000111111011600100110110111170011000110111118010001011101111901000110101111110010010011011111110101000101111111201100000111111113011101111101001140111111100010111510000011110111116100001011011112171000

28、0110011111118100100001111111191011110011110012010111100000101221110110010101101221101100011010112311011010110101124111001100111001251101101100010112611101010010011127111100101010011281111001101010112911110100101110230111101001101011311111010100111013211111000101101233111110100001111（1）（2）：77.588.599

29、.51010.51111.51212.51313.5捆数10000111011110112000101011111001300011010110111140001110010111115001000111111011600100110110111170011000110111118010001011101111901000110101111110010010011011111110101000101111111201100000111111113011101111101001140111111100010111510000011110111116100001011011112171000011

30、001111111810010000111111119101111001111001201011110000010122111011001010110122110110001101011231101101011010112411100110011100125110110110001011261110101001001112711110010101001128111100110101011291111010010111023011110100110101131111101010011101321111100010110123311111010000111134013000000004000七、附

31、录附一：clear;z=;for a=0:1 for b=0:1 for c=0:1 for d=0:1 for e=0:1 for f=0:1 for g=0:1 for h=0:1 for i=0:1 for j=0:1 for k=0:1 for l=0:1for m=0:1 for n=0:1 for o=0:1 for p=0:1 for q=0:1 for r=0:1 for s=0:1 for t=0:1 if 14*a+14.5*b+15*c+15.5*d+16*e+16.5*f+17*g+17.5*h+18*i+18.5*j+19*k+19.5*l+20*m+20.5*n+2

32、1*o+21.5*p+22*q+22.5*r+23.5*s+25.5*t=89 z=z;a b c d e f g h i j k l m n o p q r s t; end end end end end end end end end end end end end end end end end end end end end hang,lie=size(z); cc=zeros(1,hang); cc(:)=-1; bb=3529304228424549506452634935271612261;v1=zeros(1,hang);int x;int y;x=lp(cc,z,bb,v1);y=-cc*x;xx=round(x); % x 取整zz=z;zzz=zz*xx;zzzz=bb-zzz; % 计算剩余根数附二：z=;for a=0:1 for b=0:1 for c=0:1 for d=0:1 for e=0:1 for f=0:1 for g=0:1 for h=0:1 for i=0:1 for j=0:1 for k=0:1 for l=0:1for