天然肠衣搭配问题

2011高教社杯全国大学生数学建模竞赛

承 诺 书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： D 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 东南大学 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)：

日期： 年 月 日

赛区评阅编号（由赛区组委会评阅前进行编号）：

2011高教社杯全国大学生数学建模竞赛

编 号 专 用 页

评 阅 人 评 分 备 注 赛区评阅编号（由赛区组委会评阅前进行编号）：

赛区评阅记录（可供赛区评阅时使用）：

全国统一编号（由赛区组委会送交全国前编号）：

全国评阅编号（由全国组委会评阅前进行编号）：

天然肠衣搭配问题

【摘要】：

天然肠衣的搭配方案必须通过衡量多个影响因素才能实现成品总捆数的最大化。 本文首先确立了成品总捆数作为一个合理化标准，并基于此标准提出了两个基本模型：单目标等式约束线性规划模型、多目标等式约束线性规划模型，在两种模型的基础上分别对题目进行了解答，在单目标等式约束线性规划模型中，我们暂不考虑成品最短长度最长的规格影响及剩余原料降级使用的影响，得出了最大总捆数为188捆，其中（3，6.5）14捆、（7，13.5）37捆、(14, ?)137捆，但是因为方案所有解的数目非常大，求解时间远超过30分钟，为此，我们添加约束条件，建立了多目标等式约束线性规划模型，针对成品最短长度最长的规格影响及剩余原料降级使用的影响，优先考虑(14, ?)规格的分配情况，将剩余原料降级，依次考虑（7，13.5）、（3，6.5）的分配情况，最终利用LINGO软件得出了最大总捆数为190捆，其中（3，6.5）16捆、（7，13.5）37捆、(14, ?)137捆。

我们简单分析了这两种模型的利弊，在比较了两种基础模型的局限性后，我们提出了化大为小的思想，建立了第三种线性规划模型，将每一种规格下的捆数作为目标函数，分析每种规格中对该规格捆数的影响因素，对模型进行了优化处理，最终得出了最优化搭配方案。

最后，我们根据实际生产情况，讨论了原料数目、时间限制以及离散近似估计对搭配方案的影响并对我们的模型进行了简单的分析和推广。

【关键词】：

搭配 单/多目标等式约束线性规划 化大为小

1

目录

一、 二、

问题重述 ...................................................................................................................... 3 基础模型 ...................................................................................................................... 4 2.1 问题分析 .................................................................................................................. 4

2.1.1 原料规格 ........................................................................................................ 4 2.1.2 成品规格 ........................................................................................................ 4 2.1.3 原料的降级使用情况 .................................................................................... 4 2.2 模型假设 .................................................................................................................. 4 2.3 符号说明 .................................................................................................................. 4 2.4 模型的建立与求解 .................................................................................................. 5

2.4.1模型的分析 ....................................................................................................... 5 2.4.2模型一：单目标等式约束线性规划模型 ....................................................... 5 2.4.3 模型二：多目标等式约束线性规划模型 ...................................................... 6

三、

模型优化 ...................................................................................................................... 8

2.5 模型分析 .................................................................................................................. 8

2.5.1 模型一、二的分析 .......................................................................................... 8 2.6 模型优化 .................................................................................................................. 8 四、

其他因素的进一步讨论 .............................................................................................. 9

4.1原料数目 .................................................................................................................... 10 4.2时间限制 .................................................................................................................... 10 4.3离散近似估计 ............................................................................................................ 10 五、 六、

参考文献 .................................................................................................................... 10 附录 ............................................................................................................................ 11

2

一、 问题重述

天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。

原料按长度分档，通常以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 长10-10.10.5-10度 7-7.4 7.5-7.9 8-8.4 8.5-8.9 9-9.4 9.5-9.9 4 .9 根数 24 24 20 25 21 23 21 18 长11-11.11.5-1112-12.12.5-1213-13.13.5-1314-14.14.5-14度 4 .9 4 .9 4 .9 4 .9 根数 31 23 22 59 18 25 35 29 长15-15.15.5-1516-16.16.5-1617-17.17.5-1718-18.18.5-18度 4 .9 4 .9 4 .9 4 .9 根数 30 42 28 42 45 49 50 64 长19-19.19.5-1920-20.20.5-2021-21.21.5-2122-22.22.5-22度 4 .9 4 .9 4 .9 4 .9 根数 52 63 49 35 27 16 12 2 长23-23.23.5-2324-24.24.5-2425-25.25.5-25度 4 .9 4 .9 4 .9 根数 0 6 0 0 0 1 根据以上成品和原料描述，设计一个原料搭配方案，工人根据这个方案“照方抓药”进行生产。

3

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

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

(2) 对于成品捆数相同的方案，最短长度最长的成品越多，方案越好； (3) 为提高原料使用率，总长度允许有± 0.5米的误差，总根数允许比标准少1根； (4) 某种规格对应原料如果出现剩余，可以降级使用。如长度为14米的原料可以和长度介于7-13.5米的进行捆扎，成品属于7-13.5米的规格；

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

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

二、 基础模型

2.1 问题分析

该题目就天然肠衣的成品捆数情况，结合原料规格、成品规格及原料的降级使用情况，考察肠衣原料搭配方案的最优化。

对此，可从以上三个方面分析考虑： 2.1.1 原料规格

题目中所能提供的原料的长度跟根数是有限的，因而各规格的成品捆数也是有上限的，而且，成品各规格捆数受两个影响因素限制：一是原料的总长度与每捆成品的总长度的限制，，二是各规格原料组装成捆后剩余根数的最小总长度不大于各规格原料组装成捆后的剩余长度，因此可从这两个方面估算捆数的上限。

2.1.2 成品规格

根据题目要求，组装成品受单捆总根数与单捆总长度的约束，我们可以建立以成品捆数为目标函数的线性规划模型，同时建立一系列约束条件来求解方案。

2.1.3 原料的降级使用情况

由于原料剩余时可以降级使用，而且最短长度越长的成捆成品越多越好，我们在分析时的优先考虑第三种规格，然后依次是第二、第一种规格。

2.2 模型假设

（1） 假设在方案产生的过程中，天然肠衣的长度不受肠壁脂肪氧化的影响； （2） 在原料捆绑过程中允许折叠捆绑，在降级使用较长原料时，忽略过长肠衣能

否与较短肠衣成捆的问题；

（3） 原料按长度分档，以0.5米为一档，3-3.4米按3米计算，3.5米-3.9米按

3.5米计算，不考虑截断误差，如长度3.3米按3米计算，忽略0.3米的误差，不影响实际生产操作。

（4） 总长度允许有±0.5米的误差，总根数允许比标准少1根；

2.3 符号说明

表1 符号说明 i 成品规格的类型（i=1,2,3） j 第i中成品规格的档数 成品中第i种规格的捆数（i=1,2,3） ni N

成品中三种规格捆数之和 4

nij lij 成品中第i种规格第j档的根数（i=1,2,3） 原料中第i种规格第j档的长度（i=1,2,3） 原料中第i种规格第j档的根数（i=1,2,3） Gij ki ki?N*（i=1,2,3） 2.4 模型的建立与求解

2.4.1模型的分析

针对原料规格、成品规格、原料的降级使用的情况，分别建立两个数学模型分析成品捆数，考察最优化的肠衣原料搭配方案。

2.4.2模型一：单目标等式约束线性规划模型

2.4.2.1 模型建立

该模型忽略成品最短长度最长的规格影响及剩余原料降级使用的影响，分析成品捆数的最大化。为此，建立单目标等式约束线性规划模型。在该问题中，影响成品捆数之和N的因素有肠衣原料第i种规格第j档的长度lij、根数Gij，成品中第i种规格的长度范围、捆数ni，利用以上两个影响因素建立以成品捆数为目标函数的等式约束条件[1]：

maxN??nii?18????88.5k1??n1jl1j?89.5k1j?1??8????19k1??n1j?20k1j?1????n?G1j??1j???14??88.5k2??n2jl2j?89.5k2??j?1??14??7k?n?8k??2?2j2s..t??j?1??n?G2j??2j???24??88.5k?nl?89.5k?33j3j3??j?1??24??4k?n?5k3j3??3?j?1 ????n3j?G3j????*?k?N,i?1,2,3?i35

在(3,6.5)规格中，有8档，j?0,1…，8，根据题目要求，总长度允许有± 0.5米的误差，总根数允许比标准少1根，因此建立如下约束条件：

8??88.5k1??n1jl1j?89.5k1j?1?8??19k1??n1j?20k1

j?1??n?G1j?1j?

在（7,13.5）规格中，有14档，j?0,1…，14，同理，建立如下约束条件：

14??88.5k2??n2jl2j?89.5k2j?1?14??7k2??n2j?8k2

j?1??n?G2j?2j?24，同理，建立如下约束条件： 在(14, ?)规格中，有24档，j?0,1…，24??88.5k3??n3jl3j?89.5k3j?1?24? ?4k3??n3j?5k3j?1??n?G3j?3j?2.4.2.2 模型求解

利用LINGO软件求解得：N?188,n1?14,n2?37,n3?137，即(3,6.5)规格有14捆，

（7,13.5）规格有37捆，(14, ?)规格有137捆，成品总捆数为188捆。具体LINGO代码见附录一。

我们采用遍历的思想，利用LINGO软件[3]求解每捆种第i种规格第j档的根数，发现程序耗时远远超过30分钟，并非优秀的搭配方案，于是我们添加约束条件，于是产生了以下的多目标等式约束线性规划模型。

2.4.3 模型二：多目标等式约束线性规划模型

2.4.3.1 模型建立与求解

在此模型中，综合考虑原料规格、产品规格、最短长度最长的规格影响及剩余原料降级使用的影响。

由题目要求得，对于成品捆数相同的方案，最短长度最长的成品越多，方案越好，因此，我们优先考虑分配第3种规格的原料，根据第三种规格剩余的原料利用降级原理分配（7,13.5）规格的原料，最后根据第二种规格剩余的原料利用降级原理分配（3,6.5）规格的原料，可得最优解。

6

1. 关于第3种成品规格(14, ?)的原料分配方案。 我们依据题意建立如下目标函数与约束条件： maxn324??88.5k3??n3jl3j?89.5k3j?1?24?

s..t?4k3??n3j?5k3j?1??n?G3j?3j?利用LINGO软件，我们求得n3?137，即优先考虑第三种规格，可产生137捆，没

有剩余原料。

2. 关于规格(14, ?)的剩余原料和（7,13.5）规格的分配方案。

将于规格(14, ?)的剩余原料（为0）降级至规格（7,13.5）进行捆扎，建立如下目标函数与约束条件：

maxn214??88.5k2??n2jl2j?89.5k2j?1?14?

s..t?7k2??n2j?8k2j?1??n?G2j?2j?利用LINGO软件，我们求得n2?37，即第二种规格，可产生37捆，剩余原料：

长度 根数 7 3 7.5 14 8 11 3. 关于规格（7,13.5）的剩余原料和（3,6.5）规格的分配方案。

将于规格(14, ?)的剩余原料降级至规格（7,13.5）进行捆扎，建立如下目标函数与约束条件：

maxn18??88.5k1??n1jl1j?89.5k1j?1?8?

s..t?19k1??n1j?20k1j?1??n?G1j?1j?利用LINGO软件，我们求得n1?16，即第一种规格，可产生16捆，剩余原料：

长度 根数

3 8 7.5 1 8 7 7

以上三项讨论的LINGO代码见附录二。

三、 模型优化

2.5 模型分析

2.5.1 模型一、二的分析

本文利用优化模型对天然肠衣的搭配问题进行分析，把复杂的问题简单化，尤其是在处理剩余原料降级时，将剩余原料按下一级的最大长度考虑，既保证了成品的捆数，又简化了模型，有利于在实际中应用。

但是，在两种基础模型求解出的肠衣搭配方案仅仅是对N??ni求得最大值，在上

i?13述分析中，权衡标准仅仅是成品总捆数，而这样的模型在实际应用中很有局限性。

2.6 模型优化

我们采用化大为小的思想[4]，为求得成品捆数最大值，即是求得每一种规格捆数的最大值，取ki为第i种规格下符合题意的搭配方案的种数，xi为在第i种成品规格下第k种搭配方案的捆数，lj为三种原料规格中每一档肠衣的长度，yij为所取的第i种规格中第j档的肠衣的根数，Gij为原料所能提供的第i种规格中第j档的肠衣的根数，a、b为该规格长度的上下限，建立如下目标函数与约束条件：

maxX??xii?1ki?ki??yijxi?Gij,j?1,2…,n?i?1

??s...t?88.5??yijlj?89.5j?1?n??a??yij?b?j?1?根据题目所给的数据，利用LINGO 软件进行求解发现，所用时间不超过10分钟，在题目要求的30 分钟之内，因此所得到的方案具有可行性，第一种规格的方案如表2 所示。

表2 第一种规格原料搭配方案 3 3.5 4 4.5 5 5.5 6 6.5 档/m 0 11 0 2 1 1 4 1 方案1 0 11 0 1 2 0 5 1 方案2 2 1 8 1 0 1 2 4 方案3 3 6 3 1 0 1 4 2 方案4 3 5 4 1 0 3 2 2 方案5 1 7 4 1 0 2 4 1 方案6 0 3 8 4 2 1 1 1 方案7 0 7 4 3 0 1 5 0 方案8 6 1 1 5 1 1 3 2 方案9 6 1 1 2 7 0 1 2 方案10 8

本文来源：https://www.bwwdw.com/article/3scx.html