论文部分内容阅读
摘要：设计天然肠衣搭配方案，将提供的原料描述表按规格要求划分为三类区间，由计算机在Excel表中生成模拟数据进行分析处理，建立了0-1规划模型，将每种规格的各区间数据在Excel表中分配，建立分配控件，利用Excel的VBA编程按各规格的每个区间的根数进行分配，给出最终材料搭配方案，得到三种规格的较优搭配方案。
关键词：0-1规划 搭配方案 捆数 长度
1 概述
天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。本文对于给定的一批原料，为提高原料使用率，最短长度最长的成品越多装出的成品捆数越多越好，设计一个原料搭配方案，工人根据这个方案“照方抓药”进行生产。
2 数据分析及处理
我们把天然肠衣几种常见成品规格分为三种规格，见表1（长度单位为米）：
表1 成品规格表
■
根据成品规格要求将原料分档划分为三类区间进行取料组装出成品（捆），规格1对应8个取料样本区间；规格2对应14个取料样本区间；规格3对应24个取料样本区间，将某批次原料描述分类进行数据处理。先由计算机生成一批原料长度模拟数据，对这批数据进行分析处理，为了每次抽取样本个数都为1或0，我们采取一种分配原则：
2.1 计算理论最大捆数
根据每种规格的根数总和可以求出理论最大捆数（我们不考虑长度总和是否合格）。
即Ki=INT■（i=1，2，3，m，n∈Z），取上限①。
规格1中K1=■=14.6捆，最多15捆；规格2中K2=■=44.2捆，最多45捆；规格3中K3=■=135.4捆，最多136捆，这批原料理论上最多可以组装K=15+45+136=196捆。
2.2 将每种规格的各区间原料在Excel表中初次分配
将每个区间原料根数在满足理论最大捆数的原则下尽可能全部分配，也就是说各规格中有K捆就在excel表中设定为K行，将各区间的根数尽可能的均分到K行L列，L列的生成原则是l=INT[■]，取上限；反之再确定mr 能确切分配多少行，h=INT[■]，取下限。例如规格1最多有15捆，那么就在excel表中设定为15行，在a1区间（3-3.4）中有43根原料，则l=INT[■]=INT[2.9]，取上限l为3列，反过来求行数h，h=INT[■]=INT[14.3]，取下限为14行，也就是将43根分配到14行3列中，以此原则类推，将计算机生成的模拟数据在Excel表中设置开始分配控件，用VB程序编写源程序，按各规格的每个区间的原料根数进行第一次K行L列的分配。
2.3 计算每行原料的总长度和根数，及与标准规格的长度差，进行二次调配
在Excel表中进行计算，得到三种规格的数据，二次的搭配原则是定位标记初始调配行，就是说已分配的根数与标准根数之差越小且长度差小于0的那个行数首先开始进行调配，原则上从根数最多的行中挑选样本，使长度在（88.5，89.5）之间，可以有±0.5米的误差，利用计算机编程进行调配，得出各规格组装后的捆数K■■，K■■，K■■，及各规格的剩余根数m■■，m■■，m■■。
2.4 如果某种规格对应原料出现剩余，可以降级使用继续组装捆绑
把规格3的剩余根数m■■降级到规格2搭配，还能组装的捆数K■■=INT[■]且总长度在（88.5，89.5）之间，搭配剩余的规格2根数继续降级按此原则组装捆绑得到捆数K■■。最后得到成品最终捆数K=K■■+K■■+K■■+K■■+K■■及搭配方案。
3 算法步骤
对系统随机生成的原料分配方案，要计算出每一组方案中最佳的原料组合。具体算法为：假设g为每次由0-1模型分配产生的根数总和，c为长度差， bi（i=1，2，3）为标准根数/捆。为提高原料使用率，在总长：89+0.5米的范围内，即c∈（-0.5，0.5）；总根数允许比标准少一根，b或ibi-1都是有效捆法。
Step1：对第i捆数据，计|g-bi+1（i=1，2，3）为N，N为最多筛选数量，统计C■■中的满足条件的筛选元素记录集合，当c最小时，对应区间数据置0，被筛选出数据元素，按各自对应列空间存放。
Step2：当C■■中记录数为0时，N=N+1，N为达到标
准捆数的差值，统计C■■中的满足条件的筛选元素记录集合，当c最小时，对应区间数据置0，被筛选出数据元素，按各自对应列空间存放。
Step3：如果c最小值相同，当C■■中记录数为多个时，根据题目要求2的原则，筛选最短长度较短的肠衣记录。
Step4：重复执行步骤1，2，直至所有数据均被处理完成。
Step5：根据材料降级处理原则，降级处理剩余材料，给出最终材料搭配方案。
4 建立0-1规划模型计算出成品捆数最大值
设置0-1变量aij=1 第i行第j列取走样本原料0 第i行第j列没取样本原料，设mr为第r个区间根数，建立目标函数min=mr-■■aij，（n=8，14，24）。
根据公司对搭配方案的要求，装出的成品捆数越多越好，并且最短长度最长的成品越多越好，总长度允许有± 0.5米的误差，总根数允许比标准少1根，故约束条件如下：s.t88.5≤■aijxij≤89.519≤■aij≤20
我们利用计算机模拟所描述的原料数据，按照建立的模型及算法运行程序数次，运行时间小于30分钟，按要求能快速选出一个较优的搭配方案及捆数。
规格1搭配方案得出K■■=15捆，m■■=2根；规格2搭配方案得出K■■=36捆，剩余根数m■■=66根；规格3搭配方案得出K■■=120捆，剩余根数m■■=80根；规格3的剩余根数m■■降级到规格2搭配，K■■=INT（■）=18捆，剩余2根。
最后得出总捆数：
K=K■■+K■■+K■■+K■■+K■■
=15+36+120+18=189捆。
注释：
①天然肠衣原料规格要求及数据来源于2011全国大学生数学建模D题.
参考文献：
[1]杨启帆，数学建模[M].北京：高等教育出版社，2005.
[2]姜启源，数学建模[M].北京：高等教育出版社，2003.
[3]李秀珍，庞常词.数学实验[M].北京：机械工业出版社，2008.
[4]姜启源，谢金星，叶俊.数学模型.第三版[M].北京：高等级教育出版社，2003.
[5]姜启源等.大学数学实验[M].北京：清华大学出版社，2005.
关键词：0-1规划 搭配方案 捆数 长度
1 概述
天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。本文对于给定的一批原料，为提高原料使用率，最短长度最长的成品越多装出的成品捆数越多越好，设计一个原料搭配方案，工人根据这个方案“照方抓药”进行生产。
2 数据分析及处理
我们把天然肠衣几种常见成品规格分为三种规格，见表1（长度单位为米）：
表1 成品规格表
■
根据成品规格要求将原料分档划分为三类区间进行取料组装出成品（捆），规格1对应8个取料样本区间；规格2对应14个取料样本区间；规格3对应24个取料样本区间，将某批次原料描述分类进行数据处理。先由计算机生成一批原料长度模拟数据，对这批数据进行分析处理，为了每次抽取样本个数都为1或0，我们采取一种分配原则：
2.1 计算理论最大捆数
根据每种规格的根数总和可以求出理论最大捆数（我们不考虑长度总和是否合格）。
即Ki=INT■（i=1，2，3，m，n∈Z），取上限①。
规格1中K1=■=14.6捆，最多15捆；规格2中K2=■=44.2捆，最多45捆；规格3中K3=■=135.4捆，最多136捆，这批原料理论上最多可以组装K=15+45+136=196捆。
2.2 将每种规格的各区间原料在Excel表中初次分配
将每个区间原料根数在满足理论最大捆数的原则下尽可能全部分配，也就是说各规格中有K捆就在excel表中设定为K行，将各区间的根数尽可能的均分到K行L列，L列的生成原则是l=INT[■]，取上限；反之再确定mr 能确切分配多少行，h=INT[■]，取下限。例如规格1最多有15捆，那么就在excel表中设定为15行，在a1区间（3-3.4）中有43根原料，则l=INT[■]=INT[2.9]，取上限l为3列，反过来求行数h，h=INT[■]=INT[14.3]，取下限为14行，也就是将43根分配到14行3列中，以此原则类推，将计算机生成的模拟数据在Excel表中设置开始分配控件，用VB程序编写源程序，按各规格的每个区间的原料根数进行第一次K行L列的分配。
2.3 计算每行原料的总长度和根数，及与标准规格的长度差，进行二次调配
在Excel表中进行计算，得到三种规格的数据，二次的搭配原则是定位标记初始调配行，就是说已分配的根数与标准根数之差越小且长度差小于0的那个行数首先开始进行调配，原则上从根数最多的行中挑选样本，使长度在（88.5，89.5）之间，可以有±0.5米的误差，利用计算机编程进行调配，得出各规格组装后的捆数K■■，K■■，K■■，及各规格的剩余根数m■■，m■■，m■■。
2.4 如果某种规格对应原料出现剩余，可以降级使用继续组装捆绑
把规格3的剩余根数m■■降级到规格2搭配，还能组装的捆数K■■=INT[■]且总长度在（88.5，89.5）之间，搭配剩余的规格2根数继续降级按此原则组装捆绑得到捆数K■■。最后得到成品最终捆数K=K■■+K■■+K■■+K■■+K■■及搭配方案。
3 算法步骤
对系统随机生成的原料分配方案，要计算出每一组方案中最佳的原料组合。具体算法为：假设g为每次由0-1模型分配产生的根数总和，c为长度差， bi（i=1，2，3）为标准根数/捆。为提高原料使用率，在总长：89+0.5米的范围内，即c∈（-0.5，0.5）；总根数允许比标准少一根，b或ibi-1都是有效捆法。
Step1：对第i捆数据，计|g-bi+1（i=1，2，3）为N，N为最多筛选数量，统计C■■中的满足条件的筛选元素记录集合，当c最小时，对应区间数据置0，被筛选出数据元素，按各自对应列空间存放。
Step2：当C■■中记录数为0时，N=N+1，N为达到标
准捆数的差值，统计C■■中的满足条件的筛选元素记录集合，当c最小时，对应区间数据置0，被筛选出数据元素，按各自对应列空间存放。
Step3：如果c最小值相同，当C■■中记录数为多个时，根据题目要求2的原则，筛选最短长度较短的肠衣记录。
Step4：重复执行步骤1，2，直至所有数据均被处理完成。
Step5：根据材料降级处理原则，降级处理剩余材料，给出最终材料搭配方案。
4 建立0-1规划模型计算出成品捆数最大值
设置0-1变量aij=1 第i行第j列取走样本原料0 第i行第j列没取样本原料，设mr为第r个区间根数，建立目标函数min=mr-■■aij，（n=8，14，24）。
根据公司对搭配方案的要求，装出的成品捆数越多越好，并且最短长度最长的成品越多越好，总长度允许有± 0.5米的误差，总根数允许比标准少1根，故约束条件如下：s.t88.5≤■aijxij≤89.519≤■aij≤20
我们利用计算机模拟所描述的原料数据，按照建立的模型及算法运行程序数次，运行时间小于30分钟，按要求能快速选出一个较优的搭配方案及捆数。
规格1搭配方案得出K■■=15捆，m■■=2根；规格2搭配方案得出K■■=36捆，剩余根数m■■=66根；规格3搭配方案得出K■■=120捆，剩余根数m■■=80根；规格3的剩余根数m■■降级到规格2搭配，K■■=INT（■）=18捆，剩余2根。
最后得出总捆数：
K=K■■+K■■+K■■+K■■+K■■
=15+36+120+18=189捆。
注释：
①天然肠衣原料规格要求及数据来源于2011全国大学生数学建模D题.
参考文献：
[1]杨启帆，数学建模[M].北京：高等教育出版社，2005.
[2]姜启源，数学建模[M].北京：高等教育出版社，2003.
[3]李秀珍，庞常词.数学实验[M].北京：机械工业出版社，2008.
[4]姜启源，谢金星，叶俊.数学模型.第三版[M].北京：高等级教育出版社，2003.
[5]姜启源等.大学数学实验[M].北京：清华大学出版社，2005.