基于0―1规划的天然肠衣搭配模型设计.doc

1、1基于 01 规划的天然肠衣搭配模型设计摘要：设计天然肠衣搭配方案，将提供的原料描述表按规格要求划分为三类区间，由计算机在 Excel 表中生成模拟数据进行分析处理，建立了 0-1 规划模型，将每种规格的各区间数据在 Excel 表中分配，建立分配控件，利用 Excel 的 VBA 编程按各规格的每个区间的根数进行分配，给出最终材料搭配方案，得到三种规格的较优搭配方案。 关键词：0-1 规划 搭配方案 捆数 长度 1 概述 天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料） ，进入组装工序。传统的生产方式依靠人工，边丈量原料

2、长度边心算，将原材料按指定根数和总长度组装出成品（捆） 。本文对于给定的一批原料，为提高原料使用率，最短长度最长的成品越多装出的成品捆数越多越好，设计一个原料搭配方案，工人根据这个方案“照方抓药”进行生产。 2 数据分析及处理 我们把天然肠衣几种常见成品规格分为三种规格，见表 1（长度单位为米）： 表 1 成品规格表 根据成品规格要求将原料分档划分为三类区间进行取料组装出成品2（捆） ，规格 1 对应 8 个取料样本区间；规格 2 对应 14 个取料样本区间；规格 3 对应 24 个取料样本区间，将某批次原料描述分类进行数据处理。先由计算机生成一批原料长度模拟数据，对这批数据进行分析处理，为了

3、每次抽取样本个数都为 1 或 0，我们采取一种分配原则： 2.1 计算理论最大捆数 根据每种规格的根数总和可以求出理论最大捆数（我们不考虑长度总和是否合格） 。 即 Ki=INT（i=1，2，3，m，nZ） ，取上限。 规格 1 中 K1=14.6 捆，最多 15 捆；规格 2 中 K2=44.2 捆，最多 45 捆；规格 3 中 K3=135.4 捆，最多 136 捆，这批原料理论上最多可以组装 K=15+45+136=196 捆。 2.2 将每种规格的各区间原料在 Excel 表中初次分配 将每个区间原料根数在满足理论最大捆数的原则下尽可能全部分配，也就是说各规格中有 K 捆就在 exce

4、l 表中设定为 K 行，将各区间的根数尽可能的均分到 K 行 L 列，L 列的生成原则是 l=INT，取上限；反之再确定 mr 能确切分配多少行，h=INT，取下限。例如规格 1 最多有15 捆，那么就在 excel 表中设定为 15 行，在 a1 区间（3-3.4）中有 43根原料，则 l=INT=INT2.9，取上限 l 为 3 列，反过来求行数h，h=INT=INT14.3，取下限为 14 行，也就是将 43 根分配到 14 行3 列中，以此原则类推，将计算机生成的模拟数据在 Excel 表中设置开始分配控件，用 VB 程序编写源程序，按各规格的每个区间的原料根数进行第一次 K 行 L

5、列的分配。 32.3 计算每行原料的总长度和根数，及与标准规格的长度差，进行二次调配 在 Excel 表中进行计算，得到三种规格的数据，二次的搭配原则是定位标记初始调配行，就是说已分配的根数与标准根数之差越小且长度差小于 0 的那个行数首先开始进行调配，原则上从根数最多的行中挑选样本，使长度在（88.5，89.5）之间，可以有0.5 米的误差，利用计算机编程进行调配，得出各规格组装后的捆数 K，K，K，及各规格的剩余根数 m，m，m。 2.4 如果某种规格对应原料出现剩余，可以降级使用继续组装捆绑 把规格 3 的剩余根数 m降级到规格 2 搭配，还能组装的捆数 K=INT且总长度在（88.5，

6、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中的满足条件的筛选元素记录

7、集合，当 c 最小时，对应区间数据置 0，被筛选出数据元素，按各自对应列空间存放。 4Step2：当 C中记录数为 0 时，N=N+1，N 为达到标 准捆数的差值，统计 C中的满足条件的筛选元素记录集合，当 c最小时，对应区间数据置 0，被筛选出数据元素，按各自对应列空间存放。Step3：如果 c 最小值相同，当 C中记录数为多个时，根据题目要求 2 的原则，筛选最短长度较短的肠衣记录。 Step4：重复执行步骤 1，2，直至所有数据均被处理完成。 Step5：根据材料降级处理原则，降级处理剩余材料，给出最终材料搭配方案。 4 建立 0-1 规划模型计算出成品捆数最大值 设置 0-1 变量 a

8、ij=1 第 i 行第 j 列取走样本原料 0 第 i 行第 j 列没取样本原料，设 mr 为第 r 个区间根数，建立目标函数 min=mr-aij， （n=8，14，24） 。 根据公司对搭配方案的要求，装出的成品捆数越多越好，并且最短长度最长的成品越多越好，总长度允许有 0.5 米的误差，总根数允许比标准少 1 根，故约束条件如下：s.t88.5aijxij89.519aij20 我们利用计算机模拟所描述的原料数据，按照建立的模型及算法运行程序数次，运行时间小于 30 分钟，按要求能快速选出一个较优的搭配方案及捆数。 规格 1 搭配方案得出 K=15 捆，m=2 根；规格 2 搭配方案得出

9、 K=36 捆，剩余根数 m=66 根；规格 3 搭配方案得出 K=1205捆，剩余根数 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.