天然肠衣搭配问题

刘八平

摘要

“天然肠衣搭配问题”数学模型是通过对原料描述表中的数据进行分析并整理，为改变组装工艺，提高生产效率，而设计原料搭配方案。由于原料长短不一，不同长度区段的肠衣数量不同，需要组装的成品规格有限定要求，利用数学知识联系实际问题，做出相应的解答和处理。结合使用LINGO数学软件对数据进行最优化分析，解决天然肠衣的搭配问题。

根据公司对肠衣搭配方案的具体要求，参照成品规格表（表1），首先对原料描述表（表2）中的数据进行分析，建立纯整数线性规划模型，再把数据用LINGO量化分析。具体分为以下几个步骤：

1、对于给定的一批原料，建立初步的数学模型（考虑总长度允许有±0.5米的误差，总根数允许比标准少1根的情况），把所整理的数据输入LINGO分析并得出各种规格成品捆数最多的最优解并得出下一问的初步解法。

2、对初步解法进行分析，建立成品捆数最多的推广方案。为提高原料使用率，对于剩余原料可以降级使用和成品捆数相同而最短长度最长的成品越多的方案，这就要建立成品捆数最多的推广方案进行LINGO分析计算。

根据LINGO分析的结果，我们选用其中符合所有要求的搭配方案作为模型设计的最后结果，作为该公司设计的最佳原料搭配方案。

本次模型设计在数据编程软件LINGO的支持下，实现了方案的最优化设计，体现的是一种对事物分析和解决问题的一种方式方法和对资源最优化配置的理念。

关键词：数学规划模型，整数线性规划，搭配问题，组合最优化，LINGO软件

一、问题的重述

某公司将经过清洗整理后被分割成长度不等的小段的肠衣原料按照规格要求进行组装生产。传统的生产方式是依靠人工边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）（表1）。为了提高生产效率，公司计划改变组装工艺，先丈量所有原料，建立原料表（表2），设计一个原料搭配方案，工人根据这个方案“照方抓药”进行生产。

公司对搭配方案有以下具体要求：

(1)对于给定的一批原料，装出的成品捆数越多越好；

(2)对于成品捆数相同的方案，最短长度最长的成品越多，方案越好；

(3)为提高原料使用率，总长度允许有±0.5米的误差，总根数允许比标准少1根；

(4)某种规格对应原料如果出现剩余，可以降级使用。如长度为14米的原料可以和长度介于7-13.5米的进行捆扎，成品属于7-13.5米的规格；

(5)为了食品保鲜,要求在30分钟内产生方案。

建立上述问题的数学模型，给出求解方法，并对表1、表2给出的实际数据进行求解，给出搭配方案。

二、问题的分析

由题意可知，目的就是为了建立一种模型，通过计算，按照成品规格表，获得原料的一种最佳搭配方案而使工人能够根据这个方案“按方抓药”进行生产，提高生产效率，实现生产数据化和最大产出率。

分析如下：

1、题中给出两个参考的表格：一个是某批次的原料表格（表2），一个是成品所需要达到要求的规格表格（表1）。

1）原料表格里面有很多不同区间长度和根数，这是给定的。按最小值计算长度，而实际的长度越大越好，譬如3.5-3.9米长的区段，计算时按3.5米计算，而实际长度在允许范围内越长的方案越好。

2）成品表格里面给定了“根数”和“总长度”，“根数”可以有±0.5米的误差，“总长度”允许比标准少1根。

2、两个表格的关系是：批次的原料按照成品表格里面指定的“根数”和“总长度”组装成“捆”。

所组装成品的最优方案是：a、装出来的捆数越多，方案越好；b、且每捆里面单根肠衣在选择时在一个区段里面越长的根数越多越好；c、原料表格里面的材料出现剩余时，可降级使用，不浪费，按降级后的区段计算长度。

3、按照成品规格表，有20根一捆，8根一捆和5根一捆，三种捆类划分。

4、

规格一：3米到6.5米之间有（3-3.4米43根，3.5-3.9米59根，4-4.4米39根，4.5-4.9米41根，5-5.4米27根，5.5-5.9米28根，6-6.4米34根，6.5-6.9米21根）8个可供选择的长度区段，从这8个长度区段里面任意选择，满足两个条件，即总根数为20根，总长为89米即可（考虑允许误差范围）。

同理，

规格二：7-13.5米之间的有14个长度区段，总根数为8根，总长为89米。

规格三：14-26米之间（∞表示没有上限，但实际长度小于26米）有24个长度区段，总根数为5根，总长度为89米。

5、通过初步分析这些问题，可以运用数学规划模型里的整数规划对该问题进行求解。由于肠衣的根数都为整数，因此此题可以用到数学规划模型中的纯整数线性规划来建立相应的数学模型。

三、模型假设

1、假设3-3.4米按3米计算，3.5米-3.9米按3.5米计算，其余的依此类推；

2、假设原料降级只能从成品规格三向成品规格二或成品规格二向成品规格一降级使用；

3、假设总长度在±0.5米的误差之内，总根数允许比标准少1根不会对结果产生影响；

4、假设工人在肠衣捆绑的过程中不受外界因素干扰，且对肠衣的保鲜度不受影响；

5、假设丈量所有原料时，丈量误差都在误差允许范围之内；

6、假设在每个长度区段选择的根数都非负；

7、忽略在生产过程中对肠衣长度的损耗。

四、符号说明

：成品规格为捆成20根一捆的肠衣成品捆数（规格一成品捆数）

：成品规格为捆成8根一捆的肠衣成品捆数（规格二成品捆数）

：成品规格为捆成5根一捆的肠衣成品捆数（规格三成品捆数）

：不同成品规格装出的成品捆数 =1,2,3

：第i个方案中的j根肠衣数

：可以组装成规格为3-6.5米的成品在第 个长度区段选用的原料根数　　

：可以组装成规格为7-13.5米的成品在第 个长度区段选用的原料根数　　

：可以组装成规格为14~26米的成品在第 个长度区段选用的原料根数　　

(注：文中出现的其他未在此处说明的符号将在后文解释备注)

五、模型的建立与求解

最优化原理：

全过程的最优策略具有这样的性质：不管该最优策略上某状态以前的状态和决策如何，对该状态而言，余下的诸决策必定构成最优子策略。即：最优策略的任一后部子策略都是最优的。

这只是最优性定理的一个推论，即最优策略的必要条件。

整数规划：

当线性规划问题的部分或所有的变量局限于整数值时，我们称这一类问题为整数规划问题。

模型的建立与求解：

对于给定的一批原料，设计一个原料的搭配方案，使这个方案最优

（注：下列模型中表示在i区段原料的总长度，i取1,2,3

其中 表示在i区段成品的根数，i取1,2,3…

决策变量：

，

，

，

模型一：（规格一成品捆数最多优化方案）

目标函数：

（1）

（2）

约束条件：

1）原料供应范围：

（3）

2）每捆的根数：

（4）

3）对于附加约束：

（5）

由以上条件构成数学模型；

4）模型求解

将式(1)~(5)构成的线性整数规划模型输入LINGO软件求解，程序见附录中程序1.1，求解可以得到最优解如下：

VariableValue

X10.000000

X213.00000

X30.000000

X41.000000

X50.000000

X60.000000

X70.000000

X86.000000

即按照模型一所得结果进行原料的搭配，工人可以从3.5-3.9米的长度区段取13根肠衣原料，从4.5-4.9米的长度区段取1根，从6.5-6.9米的长度区段取6根作为成品规格一的最优方案进行原料搭配组装。

为了提高原料使用率，在总长度允许有±0.5米的误差，总根数允许比标准少1根的情况下，改变式（3）和式（4）的条件，程序如附录中程序1.2~1.6,可以解出不同的最佳方案。将以上各程序的数据整理得出不同原料搭配方案，如下表3所示：

表3

模型二：（规格二成品捆数最多优化方案）

目标函数：

(6）

（7）

约束条件：

1）原料供应范围：

（8）

2）每捆的根数：

（9）

3）对于附加约束：

（10）

由以上条件构成数学模型；

4）模型求解

将式(6)~(10)构成的线性整数规划模型输入LINGO软件求解，程序见附录中程序2，求解可以得到最优解如下：

VariableValue

Y10.000000

Y20.000000

Y30.000000

Y40.000000

Y51.000000

Y60.000000

Y70.000000

Y84.000000

Y90.000000

Y100.000000

Y110.000000

Y122.000000

Y131.000000

Y140.000000

即按照模型二所得结果进行原料的搭配，工人可以从9-9.4米的长度区段取1根肠衣原料，从10.5-10.9米的长度区段取4根，从12.5-12.9米的长度区段取2根，从13-13.4米的长度区段取1根作为成品规格二的最优方案进行原料搭配组装。

为了提高原料使用率，在总长度允许有±0.5米的误差，总根数允许比标准少1根的情况下，改变式（8）和式（9）的条件，程序与附录中程序1.2~1.6类似,可以解出不同的最佳方案。将各程序的数据整理得出不同原料搭配方案，如下表4所示：

表4

模型三：（规格三成品捆数最多优化方案）

目标函数：

（11）

（12）

约束条件：

1）原料供应范围：

（13）

2）每捆的根数：

（14）

3）对于附加约束：

（15）

由以上条件构成数学模型；

4）模型求解

将式(11)~(15)构成的线性整数规划模型输入LINGO软件求解，程序见附录中程序3，求解可以得到最优解如下：

VariableValue

Z10.000000

Z21.000000

Z32.000000

Z40.000000

Z50.000000

Z60.000000

Z70.000000

Z80.000000

Z90.000000

Z100.000000

Z111.000000

Z120.000000

Z130.000000

Z140.000000

Z150.000000

Z160.000000

Z170.000000

Z180.000000

Z190.000000

Z200.000000

Z210.000000

Z220.000000

Z230.000000

Z241.000000

即按照模型三所得结果进行原料的搭配，工人可以从14.5-14.9米的长度区段取1根肠衣原料，从15-15.4米的长度区段取2根，从19-19.4米的长度区段取1根，从25.5-25.9米的长度区段取1根作为成品规格三的最优方案进行原料搭配组装。

为了提高原料使用率，在总长度允许有±0.5米的误差，总根数允许比标准少1根的情况下，改变式（13）和式（14）的条件，程序与附录中程序1.2~1.6类似,可以解出不同的最佳方案。将各程序的数据整理得出不同原料搭配方案，如下表5所示：

表5

长度	方案1	方案2	方案3	方案4	方案5	方案6
14	0	2	0	0	0	0
14.5	1	1	0	0	0	0
15	2	0	1	0	0	0
15.5	0	0	2	0	0	0
16	0	0	0	0	0	1
16.5	0	0	0	1	0	0
17	0	0	0	0	1	0
17.5	0	0	0	0	0	0
18	0	0	0	0	0	0
18.5	0	0	0	0	0	0
19	1	0	1	0	0	0
19.5	0	0	0	0	0	0
20	0	0	0	0	0	0
20.5	0	0	0	0	0	0
21	0	0	0	0	0	0
21.5	0	0	0	0	0	0
22	0	0	0	0	0	0
22.5	0	0	0	0	0	0
23	0	0	0	0	0	0
23.5	0	2	1	2	2	2
24	0	0	0	0	0	0
24.5	0	0	0	0	0	0
25	0	0	0	0	0	0
25.5	1	0	0	1	1	1

结论：

由附录中的程序1、程序2和程序3分析知，上面建立的三个模型实现的最优化搭配方案只能满足剩余原料在不降级使用情况下的原料搭配方案要求。为充分利用肠衣原料，不造成原料资源浪费，建立推广模型，以实现原料的充分利用，提高产出率。

六、模型的推广与计算

求原料降级使用的最优搭配方案

考虑剩余原料降级使用时肠衣捆数最多的优选方案

目标函数：

max=x+y+z；(16)

max表示考虑剩余原料降级使用时规格一、二、三这三种类别的肠衣的最多捆数；

（ 的取值满足表2）

整理数据，在LINGO软件中运行的结果是193捆，具体的搭配方案及运算程序见附件程序4、5。

七、模型的评价与改进

本文通过对问题的充分分析，用了整数规划模型，使问题的思路清晰明了。创造性的把问题的要求转化为用LINGO数学软件解决的线性规划问题。大大简化了问题讨论过程的复杂程度。分析原料数据的时候，从整体的大的方面开始处理，然后再一步步细化，这种讨论问题的方法简洁易懂，具有很高的可读性。建立纯整数线性规划模型，在理论上有一定的基础，在实际操作中具有一定的可行性。在使用LINGO软件求解的整数线性规划的过程中，有些最优解可能是分数或小数，不符合本文的要求。故模型的结果有一定的误差，但考虑到本问题可以降级使用原料，按需可以获得不同规格的成品，在允许的误差范围内是可以接受的。

因所需设计的搭配方案需要从原料处在不同的长度区段来获取一定长度的成品，决策变量是原料的根数，所求的解必须是整数，为满足整数的要求，化整后的数趋近于最优解。

整数规划的主要缺点是：

没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判断一个问题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析，构造具体的模型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力和灵活的技巧性，这就带来了应用上的局限性。

组合最优化通常都可表述为整数规划问题。两者都是在有限个可供选择的方案中，寻找满足一定约束的最好方案。有许多典型的问题反映整数规划的广泛背景。例如，背袋（或装载）问题、固定费用问题、和睦探险队问题（组合学的对集问题）、有效探险队问题（组合学的覆盖问题）、旅行推销员问题,车辆路径问题等。因此整数规划的应用范围也是极其广泛的。它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。

八、参考文献

【1】 赵静 但琦，数学建模与数学实验（第3版），北京：高等教育出版社，2008.1

【2】 刘来福曾文艺，数学模型与数学建模，北京：北京师范大学出版社，2002

【3】 （美）吉奥丹诺（Giordano,F.R.）；叶其孝译，数学建模（原书第3版），北京：机械工业出版社，2005.1

【4】 赵东方，数学模型与计算，北京：科学出版社，2007

【5】 姚恩瑜 何勇，数学规划与组合优化，杭州：浙江大学出版社，2001.10

【6】 谢金星雪毅，优化建模与LINDO/LINGO软件，北京：清华大学出版社，2005

爱华网本文地址 » http://www.413yy.cn/a/25101017/337042.html