重庆正大软件职业技术学院黄荣海蒲思琴袁威D.docx
《重庆正大软件职业技术学院黄荣海蒲思琴袁威D.docx》由会员分享,可在线阅读,更多相关《重庆正大软件职业技术学院黄荣海蒲思琴袁威D.docx(37页珍藏版)》请在冰点文库上搜索。
![重庆正大软件职业技术学院黄荣海蒲思琴袁威D.docx](https://file1.bingdoc.com/fileroot1/2023-6/21/4bf19807-dd3f-4c4a-a3d6-ff2a60185f2b/4bf19807-dd3f-4c4a-a3d6-ff2a60185f2b1.gif)
重庆正大软件职业技术学院黄荣海蒲思琴袁威D
2011高教社杯全国大学生数学建模竞赛
承诺书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。
我们知道,抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性。
如有违反竞赛规则的行为,我们将受到严肃处理。
我们参赛选择的题号是(从A/B/C/D中选择一项填写):
D
我们的参赛报名号为(如果赛区设置报名号的话):
所属学校(请填写完整的全名):
重庆正大软件职业技术学院
参赛队员(打印并签名):
1.黄荣海
2.蒲思琴
3.袁威
指导教师或指导教师组负责人(打印并签名):
邓春淘
日期:
2011年9月12日
赛区评阅编号(由赛区组委会评阅前进行编号):
2011高教社杯全国大学生数学建模竞赛
编号专用页
赛区评阅编号(由赛区组委会评阅前进行编号):
赛区评阅记录(可供赛区评阅时使用):
评
阅
人
评
分
备
注
全国统一编号(由赛区组委会送交全国前编号):
全国评阅编号(由全国组委会评阅前进行编号):
天然肠衣搭配优化模型
摘要
本文解决的是天然肠衣搭配的优化问题:
已知肠衣的成品规格参数和原料不同档次对应的长度、根数,根据工厂对搭配方案的要求,设计一个合理的原料搭配方案,在使工厂的收益达到最大的同时简化生产过程中的生产工序。
针对要求
(1)(3),本文采用了线性规划的理论,根据成品规格的不同将原料按三种规格分别列写优化模型,用lingo9.0编程求出符合要求的结果。
针对要求
(2),在要求
(1)(3)的基础上,在lingo9.0编写程序的过程中,将长度最大数据的尽量放在程序中初始数据的前面,这样会使最短长度最长的成品更多,以保证方案更好。
针对要求(4),通过前面的要求逐一满足方案后,为了使成品捆数更多,可以将搭配后剩余的原料降级使用,同时也提高了原料的使用率,以得到更为优化的方案。
针对要求(5)通过讨论并对程序进行调试后,发现方案的优化与数据量有相当大的关系,只要做出了适当的调整(如果数据过多,就可以适当减少部分数据,分两次甚至三次计算),就可在要求的30分钟内产生优化方案,以保证肠衣的新鲜度。
具体的调整求解过程见正文。
本文主要结果如下:
各规格对应的成品捆数以及最终的最大成品捆数,如下表所示(原料搭配的方案的结果请见正文):
规格
最大成品捆数(捆)
最终剩余原料(根)
最终剩余长度(米)
3-6.5
14+2(降级使用)=16
3(3.5-3.9)
10.5
7-13.5
36+9(降级使用)=45
0
0
14-25.5
132
0
0
合计
193
3
10.5
其中,表格中的降级使用根据要求(4)某种规格对应原料如果出现剩余,可以降级使用。
因此,我们将第三种规格剩余的原料进行降级使用可以得到对应于规格二的成品9捆;将第二种规格剩余的原料进行降级使用可以得到对应于规格一的成品2捆。
由以上结果我们可以求解出三种规格的最大总捆数193捆,而且所剩原料很少,仅有10.5米。
最后,对模型进行了检验和进一步讨论,并做出了评价与推广。
关键词:
天然肠衣搭配线性规划LINGO9.0编程求解最大成品捆数
一、问题的提出
1.1背景资料
天然肠衣(以下简称肠衣)制作加工是我国的一个传统产业,出口量占世界首位。
肠衣经过清洗整理后被分割成长度不等的小段(原料),进入组装工序。
传统的生产方式依靠人工,边丈量原料长度边心算,将原材料按指定根数和总长度组装出成品(捆)。
原料按长度分档,通常以0.5米为一档,如:
3-3.4米按3米计算,3.5米-3.9米按3.5米计算,其余的依此类推。
表1是几种常见成品的规格,长度单位为米,∞表示没有上限,但实际长度小于26米。
表1成品规格表
最短长度
最大长度
根数
总长度
3
6.5
20
89
7
13.5
8
89
14
∞
5
89
为了提高生产效率,公司计划改变组装工艺,先丈量所有原料,建立一个原料表。
表2为某批次原料描述。
表2原料描述表
长度
3-3.4
3.5-3.9
4-4.4
4.5-4.9
5-5.4
5.5-5.9
6-6.4
6.5-6.9
根数
43
59
39
41
27
28
34
21
长度
7-7.4
7.5-7.9
8-8.4
8.5-8.9
9-9.4
9.5-9.9
10-10.4
10.5-10.9
根数
24
24
20
25
21
23
21
18
长度
11-11.4
11.5-11.9
12-12.4
12.5-12.9
13-13.4
13.5-13.9
14-14.4
14.5-14.9
根数
31
23
22
59
18
25
35
29
长度
15-15.4
15.5-15.9
16-16.4
16.5-16.9
17-17.4
17.5-17.9
18-18.4
18.5-18.9
根数
30
42
28
42
45
49
50
64
长度
19-19.4
19.5-19.9
20-20.4
20.5-20.9
21-21.4
21.5-21.9
22-22.4
22.5-22.9
根数
52
63
49
35
27
16
12
2
长度
23-23.4
23.5-23.9
24-24.4
24.5-24.9
25-25.4
25.5-25.9
根数
0
6
0
0
0
1
1.2需要解决的问题
根据以上成品和原料描述,设计一个原料搭配方案,工人根据这个方案“照方抓药”进行生产。
公司对搭配方案有以下具体要求:
(1)对于给定的一批原料,装出的成品捆数越多越好;
(2)对于成品捆数相同的方案,最短长度最长的成品越多,方案越好;
(3)为提高原料使用率,总长度允许有±0.5米的误差,总根数允许比标准少1根;
(4)某种规格对应原料如果出现剩余,可以降级使用。
如长度为14米的原料可以和长度介于7-13.5米的进行捆扎,成品属于7-13.5米的规格;
(5)为了食品保鲜,要求在30分钟内产生方案。
请建立上述问题的数学模型,给出求解方法,并对表1、表2给出的实际数据进行求解,给出搭配方案。
二、问题的分析
天然肠衣需要经过一些加工后方能用于一些食品的制作,在加工过程中需要考虑加工时间对其新鲜度的影响,因此,建立一个合理有效地优化方案不仅有益于厂家和加工工人更是有益于消费者本身健康。
这是一个实际生产计划经过简化的加工方案优化设计问题,主要可以利用线性规划的方法来进行研究。
首先,根据题意可知,本文需要求解的是一个线性优化设计方案将该方案运用到实际生产安排之中,由已知规格和原料进行计算,再进行相应的生产加工。
然后,考虑到成品规格中对不同档次肠衣范围不同的确定,每种范围所涉及到的具体肠衣数目以及肠衣形成成品后的总长度。
最后,我们需要对其进行未知化,创建一个合理有效的线性优化方案来合理有效地解决实际存在的问题,同时也能够满足厂家的要求。
三、模型的假设
1、假设肠衣原料均无质量问题。
2、假设搭配出来的成品都符合规格(即总长度89±0.5米处理)。
3、在搭配过程中,不考虑原料的损耗。
4、在降级使用后每种规格对总根数的要求进行放宽要求,如第一种规格根数放宽到16±4根。
5、数据量大时忽略数据“0”对模型的影响,分步编程计算造成的误差不计。
四、符号说明
………………………在理想情况下各种规格成品的肠衣所对应的最大总捆数
………………………各种规格成品的肠衣所对应的第
捆成品
………………………肠衣原料的长度所处的档次
………………………各种规格成品的肠衣所对应的总捆数
………………………各种规格成品的肠衣所对应的最大总捆数
………………………第
捆选用第
档肠衣的数量
………………………第
档肠衣的原料总数量
………………………某批次肠衣原料对应的第
档的长度
五、模型的建立与求解
5.1模型的建立
5.1.1模型的分析
根据题意和问题的分析,可知本文若是要建立一个一步到位的模型是相当困难的,特别是对于要求(4)是很难能够满足的,对于肠衣加工这样一般的工厂是不实用的,由此,我们需要根据题意建立一个简单的优化模型对其进行合适的分类,由此我们想到了由浅入深、由个体到集体的一个计算过程。
通过这样的模型分析求解出来的方案不仅能够满足各个要求,而且能够是原料剩余量最小,使方案求解出来的值能够尽可能的接近理想值(见附录9)。
5.1.2各规格模型
根据题意和前面的相关分析,由要求
(1)(3)建立线性优化模型。
首先,根据已知和假设,我们可以列写出关于规格一中捆数的求解方法,即
然后,根据相应的已知列写约束条件:
在将所有原料都用完的理想情况下,肠衣捆数最大理想值为
捆。
所以,对肠衣捆数有:
各种规格成品的肠衣所对应的最大总捆数
与各种规格成品的肠衣所对应的第
捆成品的关系式如下:
由要求(3)为提高原料使用率,总长度允许有±0.5米的误差,总根数允许比标准少1根,可得:
第
捆选用第
档肠衣的数量
与第
档肠衣的原料总数量
的关系式如下:
综上所述,建立规格一模型如下:
同理,对于规格二有如下模型:
对于规格三有如下模型:
5.2模型求解
在用LINGO9.0编程求解时,由于数据量较大我们将数据按随机抽样的方法进行几组编程求解(见附录1和附录2,附录3和附录4),得出在编写程序的过程中,将长度较大的数据尽量放在程序中初始数据的前面,这样会使最短长度最长的成品更多,从而使得方案能够最大的满足题目中的要求,以得到更优的设计方案。
由于数据量较大,我们适当的减少了部分为“0”的数据,分两次甚至三次编程计算。
这样得到的结果也能够最大的接近理想值,并且满足了题目中的各个要求。
对于规格一,用LINGO9.0编程求解得到搭配方案(见附录2),剩下的原料总长度为63米,已经不能再分配,已经得到最优分配方案。
规格一原料搭配方案如下表5-1所示(根据原料按长度分档,通常以0.5米为一档,因此肠衣原料的长度
所处的档次为第1档,肠衣原料的长度
所处的档次为第2档,依此类推):
表5-1
档次
捆数
1
2
3
4
5
6
7
8
1
1
9
0
0
0
0
7
2
2
0
4
0
0
15
0
0
0
3
7
0
2
0
4
4
3
0
4
0
0
12
1
0
0
6
0
5
0
0
15
0
1
0
4
0
6
0
1
1
18
0
0
0
0
7
0
0
8
3
2
6
0
0
8
0
0
1
19
0
0
0
0
9
1
9
0
0
0
0
9
0
10
0
10
0
0
3
7
0
0
11
11
1
0
0
0
0
0
8
12
0
8
0
0
0
11
0
0
13
10
0
0
0
0
0
0
9
14
0
13
0
0
0
0
5
2
规格一剩余原料如下表5-2所示:
表5-2
本次用去量
1
2
3
4
5
6
7
8
本次用去量
30
55
39
41
25
28
34
21
原料总数量
43
59
39
41
27
28
34
21
本次剩余量
13
4
0
0
2
0
0
0
对于规格二,在用LINGO9.0编程求解的过程之中,由于涉及的数据量较大,我们将数据的顺序以随机的方式进行输入求解,当然不同的数据输入顺序,会对结果的输出有所影响,但是根据我们多次的随机组合数据我们能够得到足以保证最优方案时对于规格二的成品捆数。
与此同时,我们也尽量满足了“对于成品捆数相同的方案,最短长度最长的成品越多,方案越好”这个要求。
规格二的原料搭配方案如下表5-3所示(根据原料按长度分档,通常以0.5米为一档,因此肠衣原料的长度
所处的档次为第1档,肠衣原料的长度
所处的档次为第2档,依此类推):
表5-3
档次
捆数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
0
0
0
1
0
4
0
0
0
0
0
0
3
16
0
0
0
0
1
0
1
0
4
0
1
0
0
1
17
0
0
0
0
3
0
0
0
0
0
3
0
2
0
18
0
2
1
0
0
0
0
0
0
1
0
0
0
4
19
0
0
0
0
0
2
0
0
0
4
2
0
0
0
20
0
0
0
3
0
0
0
0
0
0
1
3
0
1
21
0
0
0
1
0
0
0
0
5
1
0
0
0
1
22
0
0
0
0
4
0
0
0
0
0
0
0
3
1
23
0
0
1
0
0
3
0
0
0
0
0
0
4
0
24
0
0
0
0
1
0
0
1
3
0
3
0
0
0
25
0
0
0
1
1
0
0
0
0
0
6
0
0
0
26
0
0
0
0
4
0
0
0
0
0
0
0
3
1
27
0
0
0
0
0
0
1
1
4
1
0
1
0
0
28
0
0
0
0
0
0
1
0
6
0
0
0
1
0
29
0
0
0
0
0
0
0
6
0
0
0
0
2
0
30
1
0
0
0
0
0
2
0
0
0
0
5
0
0
31
1
0
0
0
0
2
0
0
0
0
0
5
0
0
32
0
0
0
1
1
1
0
0
0
0
0
5
0
0
33
0
0
0
0
0
0
3
3
0
0
0
0
0
2
34
0
0
0
0
0
3
1
1
0
0
0
0
1
2
35
0
0
0
0
0
0
2
0
1
5
0
0
0
0
36
1
1
0
0
0
0
0
0
0
0
0
6
0
0
37
0
0
0
0
2
0
0
0
3
1
0
0
2
0
38
0
0
0
0
0
3
1
0
0
0
0
4
0
0
39
0
1
0
0
3
0
0
0
0
0
0
0
0
4
40
1
0
0
0
0
2
0
0
0
0
0
5
0
0
41
0
0
1
1
0
1
0
0
0
0
0
5
0
0
42
2
0
0
0
0
0
0
0
0
0
0
6
0
0
43
0
0
0
0
0
4
1
0
0
0
0
0
0
3
44
0
0
0
0
0
0
1
0
3
4
0
0
0
0
45
0
0
0
1
0
2
0
0
0
0
3
2
0
0
46
0
0
0
0
0
0
0
5
1
1
0
0
0
1
47
2
0
0
0
0
0
0
0
0
0
1
5
0
0
48
0
1
0
1
0
0
0
1
0
0
0
5
0
0
49
0
0
0
2
0
0
0
0
1
1
2
2
0
0
50
0
0
0
0
0
0
3
0
0
4
0
0
0
1
规格二剩余原料如下表5-4所示:
表5-4
档次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
本次用量
8
5
3
11
21
23
21
18
31
23
22
59
18
25
原料数量
24
24
20
25
21
23
21
18
31
23
22
59
18
25
本次剩余量
16
19
17
14
0
0
0
0
0
0
0
0
0
0
对于规格三可以利用与规格一、二相同的方法进行计算,但是由于其数据量相对较大,一次性能分配的方案只有70捆。
在利用LINGO9.0编程求解的过程之中会遇到很多困难。
因此,我们在编写程序时需要有一些巧妙的设计,对于遇到的困难着手解决以得到最优的方案设计。
首先,我们忽略根数最小的三个档次的肠衣的搭配,并且根数为零的肠衣不代入程序中计算,这样参与搭配的肠衣档次变为17,从而有效地减少数据量,以便能得到理想的结果。
反复改变数据顺序后,求得107捆搭配方案(见附录5)。
然后,用第一次算过之后所剩的原料和根数最小的三个档次的肠衣一起进行再次计算,求得24捆搭配方案(见附录6)。
最后,为了得到更多的搭配方案,把第二次计算后所剩的原料再计算一次(见附录7),得到一套方案。
到这时因为所剩数据已经很小,并且数据量也不大,很明显的看出剩下的原料不能再搭配。
故第三种规格的捆数为132捆.
对于规格三我们对其最优的计算结果方案如下表5-5所示:
表5-5
档次
捆数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
51
0
1
0
0
0
0
1
0
0
0
2
0
1
0
0
0
0
0
0
0
0
0
0
0
52
0
0
0
0
0
0
0
4
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
53
0
0
0
0
0
0
0
4
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
54
0
2
0
0
0
0
0
0
0
1
0
0
0
0
2
0
0
0
0
0
0
0
0
0
55
0
0
1
0
0
0
0
3
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
56
0
0
2
0
0
1
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
57
0
0
0
0
0
3
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
58
0
0
0
0
0
0
0
4
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
59
1
0
0
0
0
0
1
1
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
60
0
0
0
0
0
0
0
4
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
61
0
2
0
0
0
0
0
0
1
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
62
0
0
0
1
0
1
0
0
0
1
2
0
0
0
0
0
0
0
0
0
0
0
0
0
63
0
0
0
0
0
1
0
1
2
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
64
0
0
2
0
0
0
0
0
0
0
0
2
0
1
0
0
0
0
0
0
0
0
0
0
65
1
0
1
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
0
0
0
0
66
0
0
0
0
0
0
0
4
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
67
0
0
0
1
0
1
0
0
0
1
2
0
0
0
0
0
0
0
0
0
0
0
0
0
68
1
0
0
1
0
0
0
0
1
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
69
0
0
1
0
0
0
0
1
0
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
70
0
0
1
0
0
0
0
1
0
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
71
0
0
2
0
0
0
0
0
0
0
0
2
0
1
0
0
0
0
0
0
0
0
0
0
72
2
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
0
0
0
0
0
73
1
0
0
0
0
1
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
74
0
0
0
0
2