天然肠衣搭配问题经典参考模板

1、池州学院天然肠衣搭配问题 组员：陈强 赵晋彪 赵海龙 1 / 31目录一、问题重述41.1问题背景41.2.问题条件41.3.问题要求51.4需要解决的问题5二、问题分析5三、模型假设6四、符号说明6五 模型的建立65.1、模型建立65.2、根据要求模型建立9六、模型求解106.1、问题要求（1）模型求解106.2、问题要求（2）模型求解126.3、问题要求（3）模型求解15七、模型的评价与推广177.1.模型的评价177.1.1模型的优点177.1.2模型的缺点177.2模型的推广17八、参考文献17附录18附录A18附录B20附录C23附录D25天然肠衣搭配问题摘要天然肠衣制作加工是我国的

2、一个传统产业，出口量占世界首位，而天然肠衣传统的人工生产方式已不能满足出口量日益增长的需要。因此，我们从节约生产成本、提高企业生产效率的角度出发，我们结合原料的供给量、长度及成品规格等约束条件进行了模型设计。根据题目中的表1中的成品的规格和表2中的原料，我们所需要解决的问题有：如何搭配才能使得成品的捆数最多？对于针对这一个问题我们采用线性规划建立模型并利用MATLAB以捆数相同，最短长度越长越好的原则，求得模型的最优解。另外，由于所有的原料按长度分档，通常以0.5米为一档，如：3-3.4米按3米计算，3.5米-3.9米按3.5米计算，其余的依此类推。表1是几种常见成品的规格，长度单位为米，表示

3、没有上限，但实际长度小于26米。再把不同档次的原料按照不同的规格进行搭配，分别搭配成三种规格的成品，依次是成品一(36.5米,20根，总长度89米)，成品二(713.5米，8根，总长度89米)，成品三（14米，5根，总长度89米）。运用线性规划分别对成品一、成品二、成品三建立模型，利用LINGO编程进行1步，2步，3步优化筛选，得出方案。并且，对各步筛选所剩余原料再进行优化得出方案，另外，为了提高原材料的使用率，每成品的总长度允许有0.5米的误差，总根数允许比标准少1根，某种成品对应得原材料有剩余，可以降一级使用，这样就会出现每捆总长度88.5米和89.5米，有19根一捆，7根一捆，4根一捆，

4、在满足条件时，计算出最大捆数。关键词：天然肠衣 ； 线性规划 ；MATLAB ;LINGO一、问题重述1.1问题背景天然肠衣制作加工是我国的一个传统产业，出口量占世界首位，而天然肠衣传统的生产依靠工人，边丈量长度，边心算，将原材料按指定根数和总长度组装成捆方式已不能满足出口量日益增长的需要。因此，我们从节约生产成本、提高企业生产效率的角度出发，结合原料的供给量、长度及成品规格等约束条件进行生产模型设计。1.2.问题条件已知某天然肠衣组装的规格表( 见表1) 和某批次原料的描述表( 见表2) 表1 成品规格表成品最短长度/m最长长度/m根数总长度/m成品一成品二 成品三37146.513.520

5、85898989表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.

6、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根数0600011.3.问题要求根据生产规格和原料描述表，设计满足以下要求及允许条件下的组装方案( 即对原料进行打捆的搭配方案) 。1) 对于给定的一批原料，装出的成品时，捆数越多越好；2) 对于成品捆数相同的方案，最短长度最长的成品越多，方案越好；3) 允许成品总长度有±

7、0.5 m 的误差，即总长度88.5米，,89.5米；4) 每捆总根数允许比标准少1 根即每捆可以为19根，7根，4根；5) 某种成品对应原料如果出现剩余，可以降级使；。6）为了食品安全要求在30分钟内完成。1.4需要解决的问题首先我们要考虑原料应该怎样处理，然后考虑各类成品原料的搭配问题以及剩余材料的得搭配问题。二、问题分析 天然肠衣经过人工清理和截取成不等长度，在进行搭配成成品，传统工艺里，工人们边劳作用心丈量，其操作不仅效率差，有时会造成严重资源浪费，为了解决这一问题即做到同等材料中，加工成成品后，剩余材料最少，捆数最多，我们依据表一，表二的生产规格和所拥有的原料进行生产搭配成成品，作出

8、最有模型。 对于问题要求一，我们运用lingo软件编程求出优化方案，并作出逐步优化，得出最大捆数；对于问题二，利用matlab编程，按照最短长度最长的原则选出最优方案，将选出的方案与lingo结合编程，得出最大捆数，然后在剩余中再按照最短长度最长的原则选择最后所能组成的捆数；对于问题要求三、四、五，对于成品一规格，要求长度满足，或根数满足根； 对于成品二规格，要求长度满足，或+0.5,根数满足根；对于成品三规格，要求长度 满足14m26m，或=+0.5,第三类原料最大长度为，但原料的实际长度小于26米,根数满足5根。在每个档次的原料满足这些约束条件的前提下，建立不定方程组，用lingo软件求解

9、出每种规格产品的最大捆数；为提高原料使用率，总长度允许有±0.5米的误差，总根数允许比标准少1根。因此生产条件将变为每捆天然肠衣成品的总长度为89±0.5m，同时可能会出现成品一每捆十九根，成品二每捆七根，成品三每捆四根，建立不定方程组，用lingo软件求解出每种规格产品的最大捆数。三、模型假设1、 假设题目所给的数据真实可靠；2、 所有原料都是新鲜的，没有腐烂；3、 所有原料都是同种原料，不需要对原料进行分类；4、 厂房的环境、车间和工作人员的卫生等不会对原料产生影响；5、 厂房中的温度，光照等不会对原料的保鲜产生影响。四、符号说明 每个档次在组装中所使用的根数 不同规格

10、成品按某种方案所组装出来的捆数 每种规格所能够组合出来的最大捆数 各规格的最大捆数的总和 各个档次在经过缩小取值范围后的取值 规格的成品第次按照某个方案组装所的捆数 各个档次经过组装的剩余量 档次的原料开始时的数量 每种规格所能取得的最大理想捆数 规格的原料在经过要求（2）的筛选后剩余的总根数五 模型的建立5.1、模型建立成品一成品一要求是选出20根不同肠衣组装成1捆，原料长度按0.5米为一档，如：33.4按3米计算，所选出得肠衣总长度之和为89米，可以得出 其中的限制条件为：按照某个方案组装捆之后，的根数会减少一部分，减少后限制条件变化为 经过次组装之后，规格1的成品的捆数要求最大，可以得出

11、成品二规格2的要求是选出8根不同肠衣组装成1捆，所选出得肠衣总长度之和为89米，可以得出的根数限制条件为 按照某个方案组装捆之后，的根数会减少一部分，减少后限制条件变化为 经过次组装之后，规格2成品的捆数要求最大，可以得出成品三成品3要求是选出5根不同肠衣组装成1捆，所选出得肠衣总长度之和为89米，可以得出的根数限制条件为 按照某个方案组装捆之后，的根数会减少一部分，减少后限制条件变化为 经过次组装之后，成品三成品的产品的捆数要求最大，可以得出最后得出成品的最大捆数为5.2、根据要求模型建立成品一在第一轮筛选后的余量总根数（即满足问题要求2）由于题目要求是20跟一捆，即便充分利用问题要求（3）

12、和（4），也达不到题中的要求，所以成品一不能再搭配出多余的捆数。成品二同样经过要求(2)的筛选后剩下的总根数根数可以达到8根一捆，再考虑一捆的总长度为米和每捆为8根，8根不行，再考虑每捆7根。成品三也是经过要求(2)筛选后剩下的总根数为 按题中5根一捆，根数能够满足要求，再加上每捆总长度在89米，每捆按5或求其次4根计算。目标函数：约束条件： 六、模型求解6.1、问题要求（1）模型求解对于不同规格的成品，会存在一个理想的最大捆数，但是由于实际条件的约束，总捆数不可能超过，其中理想的最大捆数等于此种规格的总根数之和除于此种规格每捆的根数要求成品一的最大理想捆数余下12根成品二的最大理想捆数余下2

13、根成品三的最大理想捆数余下2根成品一利用编程（程序见附录A），对成品一进行最优化筛选，可得方案表3 成品一的原料第1轮筛选的方案选取根数25332131 方案所得捆数：11经过1轮的优化之后，并未达到最优，再进行优化，有方案表4 筛成品一的原料第2筛选的方案选取根数71211503 方案所得捆数：3成品一的实际的总捆数之和， 实际的总捆数之和与最大理想总捆数相等，成品一的优化结束。各个档次剩余根数分别为表5 成品一的原料经过筛选所剩余的原料剩余根数01050211成品二 利用同样的方法对成品二进行优化分配处理表6 成品二的原料第1轮筛选的方案选取根数0101000选取根数0111201 方案所

14、得捆数为：22表7 成品二的原料第2轮筛选的方案 选取根数0000021选取根数1100120 方案所得捆数为：9表8 成品二的原料第3轮筛选的方案选取根数0000012选取根数2000201 方案所得捆数为：3经3轮的筛选之后，各个档次的根数剩余量为表9成品二的原料3轮筛选的剩余量 剩余根数2422032126剩余根数3010000剩余的原料不能再组装出符合要求的成品，优化结束。最后得出成品二的原料所能够组装的最大实际捆数为成品三 成品三的原料采用同样方法，经过九轮筛选之后剩余原料跟数为：表10成品三的原料9轮筛选的剩余量剩余根数000010100001剩余根数2001122060001经过

15、9轮的优化筛选之后，剩余的原料无法再组装出符合要求的成品，最后求得成品三的实际最大捆数为所以，利用对题目中给定的原料求解出最大能够组装出的捆数6.2、问题要求（2）模型求解成品一利用编程（程序见附录B），按照最短长度最长的原则选出如下方案，将选出的方案结合编程（程序见附录C），得出捆数为11表11 成品一的原料按照最短长度最长优化的方案选取根数25332131在剩余中再按照最短长度最长的方案选择3捆，方案如下表12 成品一的原料按照最短长度最长优化的方案选取根数71211503成品二在符合成品二的材料中按照最短长度最长的方案选择22捆，方案如下表13 成品二的原料按照最短长度最长优化的方案选取

16、根数0101000选取根数0111201在剩余中再按照最短长度最长的方案选择9捆，方案如下表14 成品二的原料按照最短长度最长优化的方案选取根数0000021选取根数1100120再在剩余中再按照最短长度最长的方案选择3捆，方案如下表15成品二的原料按照最短长度最长优化的方案选取根数0000012选取根数2000201成品三在符合成品三的材料中按照最短长度最长的方案进行选择42捆，方案如下表16 成品三的原料按照最短长度最长优化的方案选取根数000001101110选取根数000001000000在剩余中再按照最短长度最长的方案选择31捆，方案如下表17 成品三的原料按照最短长度最长优化的方案

17、选取根数100100000002选取根数010000000000在剩余中再按照最短长度最长的方案选择27捆，方案如下表18 成品三的原料按照最短长度最长优化的方案选取根数010010010000选取根数101000000000在剩余中再按照最短长度最长的方案选择15捆，方案如下表19 成品三的原料按照最短长度最长优化的方案选取根数002000010000选取根数100100000000在剩余中再按照最短长度最长的方案选择7捆，方案如下表20 成品三的原料按照最短长度最长优化的方案选取根数000100001300选取根数000000000000在剩余中再按照最短长度最长的方案选择4捆，方案如下表

18、21 成品三的原料按照最短长度最长优化的方案选取根数100100000010选取根数110000000000在剩余中再按照最短长度最长的方案选择2捆，方案如下表22 成品三的原料按照最短长度最长优化的方案选取根数010000010030选取根数000000000000在剩余中再按照最短长度最长的方案选择1捆，方案如下表23 成品三的原料按照最短长度最长优化的方案选取根数000000031100选取根数000000000000在剩余中再按照最短长度最长的方案选择1捆，方案如下表24 成品三的原料按照最短长度最长优化的方案选取根数000000220000选取根数100000000000按照上述成品

19、三选择原材料进行组装，即可使得这批原材料的所组装出来的成品最短长度最长，此时各个规格的捆数之和为178，相比要求1所得的捆数多出了1捆，这是因为成品三在选择最短长度最长的方案组装的时候使得材料能够更加充分利用6.3、问题要求（3）模型求解通过编程求解（程序见附录D），有成品一没有符合要求(3)的方案。成品二8根一捆，选出剩余的最长的8根总长度为米，没有达到最低要求88.5米，每捆减少1根就更不能满足要求，所以没有搭配方案。成品三用lingo软件运行每捆总长度为米，5根一捆的搭配，没有符合的方案，再用4根一捆，结果可以搭配出6捆。在选择4捆时，具体的方案为表25 成品三的原料按照要求(3)的优化

20、方案选取根数000000000000选取根数000030010000在剩余材料按要求(3)选择1捆时，方案为表26 成品三的原料按照要求(3)的优化方案选取根数000000000000选取根数100000020000在剩余材料按要求(3)选择1捆时，方案为表27 成品三的原料按照要求(3)的优化方案选取根数000000000000选取根数010010100001七、模型的评价与推广7.1.模型的评价7.1.1模型的优点 （1）本模型的建立在相应的理论指导下，理论基础较为成熟，并且有相应的专用软件支持，因此可信度较高。（2）利用数学工具，通过，编程的方法，严格地对模型进行求解，具有较高的科学性。

21、（3）模型的建立与实际紧密联系，充分考虑实际情况的多样性，从而使得模型更贴进实际，通用性、推广性较强。7.1.2模型的缺点（1）选取的数据难免在现实生活中存在诸多不协调，带来不可避免误差；（2）在对各档的数据进行处理时，都采用各档的标准值，这样会存在系统误差。（3）在建模的过程中，虽然考虑了很多因素，但仍然忽略了其他不确定因素等次要因素的影响，比如关于原料切割损坏问题等等，在模型假设里都忽略了7.2模型的推广 该模型是一个典型的整数线性规划模型，在实际生活中有着广泛的使用空间。该模型不仅可以对天然肠衣搭配，还可以对类似的问题进行求解。以本模型为基础可以进一步对复杂问题，用类似的方法对模型进行改

22、进，因此模型具有较强的普遍适用性。八、参考文献1万福永 戴浩晖 潘建瑜 数学实验教程（matlab版）北京 科学出版社 20032谢金星、薛毅.优化建模与LINDO软件M.北京：清华大学出版社，2005 3傅远德.线性规划和整数规划M.成都：成都科技大学出版社，1989.12 4卢开澄、卢华明.线性规划M.北京：清华大学出版社，2009 附录附录A、B、C、D每种程序均附上一个模板，后面的采用递减重复运行即可附录A成品一max=y;3*x1+3.5*x2+4*x3+4.5*x4+5*x5+5.5*x6+6*x7+6.5*x8=89;x1+x2+x3+x4+x5+x6+x7+x8=20;y*x1

23、<=43;y*x2<=59;y*x3<=39;y*x4<=41;y*x5<=27;y*x6<=28;y*x7<=34;y*x8<=21;gin(x1);bnd(0,x1,43);gin(x2);bnd(0,x2,59);gin(x3);bnd(0,x3,39);gin(x4);bnd(0,x4,41);gin(x5);bnd(0,x5,27);gin(x6);bnd(0,x6,28);gin(x7);bnd(0,x7,34);gin(x8);bnd(0,x8,21);gin(y);bnd(0,y,14);成品二max=y;7*x9+7.5*x10

24、+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=89;x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22=8;y*x9<=24;y*x10<=24;y*x11<=20;y*x12<=25;y*x13<=21;y*x14<=23;y*x15<=21; y*x16<=18; y*x17<=31; y*x18<=23; y*x19<=22;

25、y*x20<=59; y*x21<=18; y*x22<=25;gin(x9);bnd(0,x9,24);gin(x10);bnd(0,x10,24);gin(x11);bnd(0,x11,20);gin(x12);bnd(0,x12,25);gin(x13);bnd(0,x13,21); gin(x14);bnd(0,x14,23);gin(x15);bnd(0,x15,21); gin(x16);bnd(0,x16,18); gin(x17);bnd(0,x17,31); gin(x18);bnd(0,x18,23); gin(x19);bnd(0,x19,22); gi

26、n(x20);bnd(0,x20,59); gin(x21);bnd(0,x21,18); gin(x22);bnd(0,x22,25);gin(y);bnd(0,y,44);成品三max=y;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*x41+23.5*x42+24*x43+24.5*x44+25*x45+25.5*x46=89;x1+x2+x3

27、+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22+x23+x24=5;y*x23<=35; y*x24<=29; y*x25<=30; y*x26<=42; y*x27<=28; y*x28<=42; y*x29<=45; y*x30<=49; y*x31<=50; y*x32<=64; y*x33<=52;y*x34<=63; y*x35<=49; y*x36<=35; y*x37<=27; y*x38<=

28、16; y*x39<=12; y*x40<=2; y*x41<=0; y*x42<=6; y*x43<=0; y*x44<=0; y*x45<=0; y*x46<=1;gin(x23);bnd(0,x23,35);gin(x24);bnd(0,x24,29);gin(x25);bnd(0,x25,30);gin(x26);bnd(0,x26,42);gin(x27);bnd(0,x27,28); gin(x28);bnd(0,x28,42);gin(x29);bnd(0,x29,45); gin(x30);bnd(0,x30,49);gin(x3

29、1);bnd(0,x31,50);gin(x32);bnd(0,x32,64);gin(x33);bnd(0,x33,52);gin(x34);bnd(0,x34,63);gin(x35);bnd(0,x35,49);gin(x36);bnd(0,x36,35);gin(x37);bnd(0,x37,27);gin(x38);bnd(0,x38,16);gin(x39);bnd(0,x39,12);gin(x40);bnd(0,x40,2);gin(x41);bnd(0,x41,0);gin(x42);bnd(0,x42,6);gin(x43);bnd(0,x43,0);gin(x44);bn

30、d(0,x44,0);gin(x45);bnd(0,x45,0);gin(x46);bnd(0,x46,1);gin(y);bnd(0,y,136);附录B成品一function yy1c=1;for x1=0:43/11 for x2=0:59/11 for x3=0:39/11 for x4=0:41/11 for x5=0:27/11 for x6=0:28/11 for x7=0:34/11 for x8=0:21/11 k1=x1*3+x2*3.5+x3*4+x4*4.5+x5*5+x6*5.5+x7*6+x8*6.5; k2=x1+x2+x3+x4+x5+x6+x7+x8; if

31、(k1=89)&(k2=20) fprintf('第%d种 n %d,%d,%d,%d,%d,%d,%d,%d n',c,x1,x2,x3,x4,x5,x6,x7,x8) c=c+1; end end end end end end end endend成品二function yy2 c=1;for x9=0:24/22 for x10=0:24/22 for x11=0:20/22 for x12=0:25/22 for x13=0:21/22 for x14=0:23/22 for x15=0:21/22 for x16=0:18/22 for x17=0:31/2

32、2 for x18=0:23/22 for x19=0:22/22 for x20=0:59/22 for x21=0:18/22 for x22=0:25/22 k1=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; k2=x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22; if (k1=89)&(k2=8) fprintf('第%d种 n %d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d n',c,x9,x10,x1