墙纸切割问题数学建模论文-毕业论文.doc

承 诺 书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

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

日期： 2013 年 8 月 17 日

赛区评阅编号（由赛区组委会评阅前进行编号）：
2010高教社杯全国大学生数学建模竞赛

编 号 专 用 页

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

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

评
阅
人

评
分

备
注

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

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

墙纸切割问题

摘要
本着节约环保的宗旨，本文针对如何合理切割墙纸问题做了一定的研究。该问题的关键在于如何合理地安排切割模式，使得在满足客户的需求下，原材料使用最少且原材料的利用率最大。
针对第一问，考虑到符合切割条件的模式有很多种，所以用C语言软件随机选取出材料利用率大于（为）99.88％的200（314选取200种不合理）种切割模式的集合（见附录1），再以所需大卷总量最少为目标函数用Lingo软件建立整型规划模型（建立正数规划模型，用lingo求解），求解得出，所采用组合切割模式中包括10种基本的切割模式（见表格1 ），最适合的切割大卷总卷数为199卷，总毛边余量为1990。
针对问题二，该问题在问题一的基础上加入了时间的限制。考虑到第3、7、9种规格的小卷必须在前七天内完成，所以在前七天切割的168件大卷数中必须将限制完成时间的小卷件数全部切割完成。最后建立整型线性规划模型，求解得出前七天内运用第31、39、55、62、80、82、98、190共八种切割模式（见表格2），切割的大卷总数为199件，完成整个切割任务用时9天。

关键词：整型线性规划模型 最大利用率 切割模式集合 C语言软件 Lingo软件（软件不算关键词）

一、问题重述
1.1背景资料
直接从墙纸厂生产车间生产出来的的墙纸，在墙纸行业称为半成品（大卷），销售部会根据订单情况把相同墙纸类型、相同厚度的需求合在一起，进行组合优化，形成一个切割任务单；最后在切割车间通过机器将大卷切割成客户需要的规格。由此，引出了在满足客户要求的情况下，采取什么切割模式可使公司有较大收益的问题。

1.2待解决问题
（1）为该厂设计一个满意的切割方案送交切割车间，该切割方案须指出切割大卷的总卷数、总毛边余量等数据。
（2）若该厂的切割机每天最多只能处理24大卷的切割任务，3,7,9号订单属于加急订单，必须在一周内完成切割，然后发货，问该怎样调整切割方案，在这种方案下完成整个切割任务需要多少天。

二、问题分析
2.1问题重要性分析
一维切割问题是组合优化中的一个经典问题，要求如何在实现客户要求的前提下，使本公司的收益最大化。一个满意的切割方案要满足以下三点：
1.要求原材料的利用率最大；
2.要求所用的大卷数最少；
3.要求所采取的不同切割模式尽可能少。

2.2问题解决思路
在第一问中，存在一个求解出满意的总大卷切割问题。所谓满意，从公司利益角度出发，即是所切割的总卷数最少且总毛边余量最少。显然，切割模式的组合有很多种。可先通过c语言确定材料利用率大于（为）99.88％的切割模式集合，然后建立以所需总卷数最少为目标函数的整形规划模型，用Lingo语句解出在满足客户要求下所用的组合切割模式及每种切割模式所切割的大卷数，进而求和解出切割的大卷总数和总毛边余量 。
在问题二中，切割大卷受到了时间和工作效率的影响，每天最多切割24卷，而且要求在不大于7天时间里将第3,7,9号订单生产完毕。由于第一问可以解出相对较优的切割方式，所以可以首先考虑将第一问中的切割方式按合理的时间顺序对大卷进行切割，若该切割方式可以将第3,7,9号订单在不大于七天的时间生产完毕，则可采用此种切割方式；若不能实现，则需要在所有利用率大于99.88%的切割方式中，以所需大卷数最少、七日内完成第3,7,9号订单为约束条件进行求解。

三、模型假设与约定
1、每种切割模下毛边余量不超过（为）10
2、假设每次切割都准确无误
3、假设大卷总数足够多
4、假设切割过程中不会出现机器毁损等其他故障
5、假设工人都是按时上下班，每天都是处理24大卷的切割任务。
6. 假设过量生产的产品在之后的时间也可以原件卖出。

四、符号说明

符号
符号说明

切割的总卷数

第i种切割模式

按照第i种切割模式所切割的大卷数

每张大卷按照第i种切割模式所切割第种规格的小卷数

所有切割模式中切割出第种规格的小卷总数

订单中需求第种规格的小卷件数
η
每个大卷的利用率

大卷的总宽度

每个大卷切割出的所有小卷的总宽度

总毛边余量

完成所有切割任务所需天数
（文中提到到时还要说明一下）
五、模型的建立与求解

5.1对多种切割模式的数据处理
本问题的求解目标是在生产力容许的条件下，以最少数量的大卷数尽可能按时完成所需产品的需求任务。由于所需小卷数的规格有10种类型，考虑到切割模型的组合数目十分庞大，难以求解出理论上的最优切割模式的组合。因此，针对本问题，我们用c语言程序获取了毛边余料不超过10的多种切割模式，再从中随机抽取了200组数据作为以下问题的选取范围，以此来简化问题的求解过程。
(具体的200中切割模式的集合见附录1)

5.2基于最小总卷数和最小总毛边余量问题的切割方案
5.2.1模型一的建立
该模型的建立是为了解决采用何种组合的基本切割模式问题。在每种切割模式的墙纸利用率都在99.88％的情况下，我们以大卷的最少使用件数为目标函数来建立了整形规划模型。
确定目标函数：
min=
确定约束条件：
Ⅰ、切割第种规格的小卷总数不小于订货件数，即：

Ⅱ、每个大卷的利用率不低于99.88％，即：
η=>=99.88％

η=>=99.88％
所以，得出目标最优化模型： min=

s.t.

5.2.2模型一的求解
用Lingo软件输入随机抽取的200种切割模式，这200组数据在约束条件的限制下，求解出只有10组数据为有效数据，则此10组有效数据即为所求的基本切割模式。
表1：使用的墙纸切割模式

切割大卷总卷数：=199件 （进行语言描述）
总 毛 边 余 量：=1990

5.3基于在规定天数内完成加急订单问题的切割方案
5.3.1模型二的建立
问题二在原有订单量不变的情况下，增加了3、7、9号订单必须在一周内完成的限制条件，且每天只能处理不超过24大卷的切割任务。分析可知，可以将对时间的限制转化为对切割量的限制，即将7天内对3,7,9号订单的完成转化为前168卷对3,7,9号订单完成，在切到第168大卷时必须完成对上述加急订单的切割，则切割方案存在两种可能：
（1） 第一问中的切割方案按一定的顺序加工可以保证在切割前168卷的过程中完成3,7,9号订单。
（2） 第一问中的切割方案按一定的顺序加工前168卷的过程中不能完成3,7,9号订单，此时要从200种切割方案中筛选出前7天可完成3,7,9号订单的切割模式，同时以所有模式切割的各类小卷数不小于订单数为约束条件，以所需大卷数最少为目标函数建立整形规划模型。（可以放入模型优化中）

由此，可得到一个约束条件：
(Zj为前7天切割量)
目标函数：
min=
所需天数：

所以得出的最优化模型： min=

s.t

5.3.2模型二的求解
对于求解模型二，在模型一的基础上，首先考虑加急订单第3,7,9种规格。在前一周内，即在切割的总大卷数为168件之前，可以完成对加急订单的切割。
最终结果：

表2：使用的墙纸切割模式

小卷一
小卷二
小卷三
小卷四
小卷五
小卷六
小卷七
小卷八
小卷九
小卷十
所需大卷数
总毛边余量
第31种
0
2
2
0
0
2
0
2
0
0
8
80
第39种
2
1
1
1
0
1
0
0
1
1
21
21
第55种
0
0
2
4
3
0
0
0
0
0
1
10
第62种
0
0
0
0
1
0
0
1
2
1
22
220
第80种
2
0
1
4
0
0
1
0
1
0
8
80
第82种
1
0
0
0
2
0
2
1
1
0
45
450
第190种
0
1
5
0
0
0
0
0
2
0
32
320
第98种
1
2
1
4
0
0
0
0
0
1
23
230
第141种
13
3
0
1
0
1
0
0
0
0
2
20
第93种
0
5
0
0
0
3
0
1
0
0
37
370
共计

199
1990

完成切割的天数：
切割大卷总卷数：=199件
总 毛 边 余 量：=1990（文字叙述）

六、模型评价
7.1优点分析
计算结果表明这两种模型对于墙纸的切割问题具有普适性、易操作性、结果可靠等优点。具体可提现在以下几方面：
（1）从很多种切割模式中优化选出了200种高利用率的切割模式，简化了问题，减少了计算量。
（2） 对于模型一，在200种材料利用率都在99.88％的切割模式中，通过整型线性规划，得出10种最佳的基本切割模式，使得切割所需的总卷数最少。这样既提高了墙纸的利用率，又使得切割模式尽可能的少，方便了工人的操作。
（3） 对于模型二，模型具有很好的实适用性，在实际生产中，可以根据原大卷数及生产实际需要和成产能力来选择大卷数及最佳切割模式的组合，从而在满足客户的要求下达到降低成产成本的目的。
7.2缺点分析
（1） 对于模型一，只考虑了使得总卷数最少和总毛边余量最小的问题，导致多生产了一些小卷，且没有将时间问题考虑在内。在这种情况下，工作时间加长了，可能会使客户不满，且工人的工作效率下降，从公司的角度看，这种切割模型显然不是最合适的。
(2) 对于问题二，只保证了第3、7、9种规格的小卷在前七天内完成，没有考虑到其他规格小卷的完成时间，会使工作总时间没有达到最少。
(3) 第二问是在第一问的前提下筛选出来的组合模式，该求解方法不具备普遍性。

七、模型推广
我们建立的切割模型不仅仅适用于墙纸的切割问题，这种模型还可运用到实际生活中的各种切割或下料问题，如，制造业中的各种板材、线材、型材、管材等零件的切割下料，服装业的剪裁问题等；同时，也可用到运输分配问题中，如，一个生产线生产一定量的产品需要固定配比单位的几种原材料，同时存在多种供应原材料的供应线，每个原料供应线只能按照不同且固定比例提供原料，要求解需要哪几个供应线为生产线提供原材料，同时要提供多少原材料，也可用此模型进行求解。

八、参考文献
[1] 赵静，但琦，《数学建模与数学实验》，北京：高等教育出版社，2008.1
[2]佚名，数学建模论文——薄膜切割问题，
[3] 袁月明、龙建成、许鹏，实用一维下料问题模型与求解算法，

九、附录

附录1：lingo求解整型规划程序
model:
sets:
method/1..200/:n;
parts/1..10/:num;
link(method,parts):m;
endsets
data:
m=
3 2 2 2 0 1 1 0 0 0
4 1 5 1 0 0 1 0 0 0
2 3 2 0 1 0 1 0 1 0
1 5 0 1 0 2 0 1 0 0
2 5 0 3 0 0 0 0 1 0
0 4 6 1 0 0 0 0 0 0
1 0 1 2 0 2 1 1 0 0
1 5 0 1 0 2 0 1 0 0
1 1 1 0 0 0 1 2 0 1
6 3 2 2 1 0 0 0 0 0
4 6 4 0 0 0 0 0 0 0
1 0 1 3 0 1 1 0 1 0
0 0 1 0 5 2 0 0 0 0
0 0 0 5 1 0 2 0 0 0
5 3 2 1 1 1 0 0 0 0
1 5 0 1 0 2 0 1 0 0
16 2 0 0 0 0 0 0 1 0
6 1 2 1 0 0 1 0 1 0
10 3 0 0 0 0 1 0 1 0
0 0 1 0 5 2 0 0 0 0
5 3 2 1 0 0 0 0 0 1
6 4 0 0 0 2 1 0 0 0
4 0 0 1 2 0 3 0 0 0
2 0 7 1 1 0 0 0 0 0
4 2 1 0 2 0 0 2 0 0
5 2 1 0 1 0 1 0 0 1
2 0 0 0 2 0 2 2 0 0
2 0 0 1 2 0 0 2 1 0
2 0 1 3 0 0 3 0 0 0
6 1 2 0 0 1 1 1 0 0
0 2 2 0 0 2 0 2 0 0
2 0 0 0 2 0 2 2 0 0
5 1 2 0 0 0 0 3 0 0
5 0 0 1 2 3 0 0 0 0
0 1 1 6 0 0 1 0 0 0
4 0 1 4 0 2 0 0 0 0
3 3 2 0 1 0 1 1 0 0
0 0 0 0 2 1 0 1 2 0
2 1 1 1 0 1 0 0 1 1
1 0 7 0 0 0 0 0 0 1
0 0 0 0 2 1 0 1 2 0
1 1 4 2 1 1 0 0 0 0
0 1 1 0 1 0 0 4 0 0
1 1 5 0 0 0 0 1 1 0
2 1 1 0 1 3 0 1 0 0
9 2 2 0 1 0 0 1 0 0
2 1 1 1 1 0 1 2 0 0
1 2 1 4 0 0 0 0 0 1
11 1 1 0 1 0 0 0 0 1
0 4 0 2 4 0 0 0 0 0
6 1 2 1 0 0 1 0 1 0
6 3 2 2 1 0 0 0 0 0
3 0 0 0 2 2 1 1 0 0
6 0 0 2 0 0 0 0 0 2
0 0 2 4 3 0 0 0 0 0
6 3 2 2 1 0 0 0 0 0
12 3 0 0 0 2 0 0 0 0
14 3 0 2 0 0 0 0 0 0
11 3 0 0 0 0 1 1 0 0
4 2 1 0 2 0 0 2 0 0
0 0 1 2 0 1 0 3 0 0
0 0 0 0 1 0 0 1 2 1
2 3 2 0 1 0 1 0 1 0
1 0 0 6 1 0 0 1 0 0
6 1 0 0 2 0 0 1 0 1
3 4 3 1 0 0 0 1 0 0
0 1 0 2 1 1 1 0 0 1
0 6 0 5 0 0 0 0 0 0
1 1 1 0 0 2 0 0 1 1
6 3 2 2 1 0 0 0 0 0
4 0 0 0 7 0 0 0 0 0
1 0 0 6 1 0 0 1 0 0
0 3 3 0 4 0 0 0 0 0
2 0 0 0 2 1 0 3 0 0
0 3 5 0 1 0 1 0 0 0
1 6 0 0 1 0 0 1 1 0
0 6 0 0 1 0 0 0 2 0
9 0 1 1 0 0 1 0 0 1
0 2 0 1 3 0 1 0 1 0
2 0 1 4 0 0 1 0 1 0
1 0 1 2 0 2 1 1 0 0
1 0 0 0 2 0 2 1 1 0
7 4 0 1 0 1 1 0 0 0
5 3 2 1 1 1 0 0 0 0
0 8 0 0 2 0 1 0 0 0
8 0 1 0 0 1 1 0 0 1
4 4 0 1 0 0 0 0 2 0
3 1 2 0 0 0 0 1 2 0
2 5 0 2 0 1 0 1 0 0
11 1 1 0 1 0 0 0 0 1
0 5 0 0 0 2 2 0 0 0
0 1 1 0 1 0 3 0 1 0
0 5 0 0 0 3 0 1 0 0
2 2 2 1 0 2 1 0 0 0
4 1 1 2 1 0 2 0 0 0
1 0 7 0 1 1 0 0 0 0
8 0 0 4 2 0 0 0 0 0
1 2 1 4 0 0 0 0 0 1
1 0 1 1 5 1 0 0 0 0
5 1 2 0 0 1 1 0 1 0
2 0 0 0 0 0 1 0 1 2
0 0 0 0 2 1 0 1 2 0
3 0 0 0 1 0 3 0 0 1
5 1 0 0 2 0 0 0 1 1
3 1 1 2 1 1 0 0 1 0
3 0 0 0 1 0 3 0 0 1
3 1 1 1 0 1 0 1 0 1
2 0 1 4 0 0 1 0 1 0
8 0 1 0 1 2 1 0 0 0
2 4 3 0 0 1 0 1 0 0
4 3 2 0 1 2 0 0 0 0
3 3 2 0 1 0 1 1 0 0
1 0 3 1 2 1 1 0 0 0
0 5 0 1 0 0 1 2 0 0
8 0 1 1 1 0 0 2 0 0
2 0 1 2 0 4 0 0 0 0
1 2 0 0 2 2 0 0 0 1
3 1 1 1 0 1 0 1 0 1
0 3 3 0 4 0 0 0 0 0
7 1 2 0 0 3 0 0 0 0
1 2 2 2 0 0 0 1 1 0
8 4 0 2 0 0 1 0 0 0
9 0 1 1 1 1 1 0 0 0
5 1 0 0 2 0 0 0 1 1
4 0 0 1 1 0 1 1 0 1
12 3 0 0 0 2 0 0 0 0
3 2 1 0 2 0 0 1 1 0
3 2 2 2 0 1 1 0 0 0
8 1 2 1 0 2 0 0 0 0
8 0 0 4 2 0 0 0 0 0
2 1 1 0 0 1 2 0 0 1
5 0 1 0 1 1 0 0 2 0
6 0 0 2 0 0 0 0 0 2
4 1 3 1 3 0 0 0 0 0
5 3 2 1 1 1 0 0 0 0
1 1 1 0 1 0 3 1 0 0
4 1 1 2 0 0 0 1 0 1
2 6 0 0 1 0 0 2 0 0
0 0 0 0 1 0 0 1 2 1
3 0 0 1 2 0 0 3 0 0
13 3 0 1 0 1 0 0 0 0
0 2 2 0 0 0 4 0 0 0
1 2 2 1 0 1 0 2 0 0
4 6 4 0 0 0 0 0 0 0
10 5 0 1 1 0 0 0 0 0
0 1 1 0 1 1 1 1 1 0
0 1 1 0 1 1 1 1 1 0
12 0 0 0 3 0 1 0 0 0
2 1 1 0 1 2 2 0 0 0
4 0 0 1 1 0 1 1 0 1
5 4 0 0 0 1 0 2 0 0
2 5 0 2 0 1 0 1 0 0
2 3 2 0 1 0 1 0 1 0
1 0 7 0 1 1 0 0 0 0
0 0 0 0 2 0 2 0 2 0
0 5 3 3 0 0 0 0 0 0
0 2 1 3 1 2 0 0 0 0
8 2 2 0 1 0 0 0 1 0
0 0 0 0 1 0 0 1 2 1
5 0 0 1 0 1 0 0 0 2
5 1 0 0 3 1 0 0 1 0
6 4 0 0 0 2 1 0 0 0
3 0 0 1 2 0 0 3 0 0
2 1 1 0 0 1 2 0 0 1
1 0 7 0 1 1 0 0 0 0
0 2 2 1 0 0 2 0 1 0
0 1 0 2 2 2 1 0 0 0
2 0 7 1 1 0 0 0 0 0
2 1 2 0 0 0 0 0 3 0
2 1 5 0 0 0 0 2 0 0
3 0 0 0 1 1 1 1 0 1
4 7 1 2 0 0 0 0 0 0
12 3 0 0 0 2 0 0 0 0
8 1 2 1 0 2 0 0 0 0
3 1 1 1 1 1 2 0 0 0
1 5 2 0 1 0 0 0 0 1
1 0 1 3 0 0 0 3 0 0
6 0 1 6 0 0 0 0 0 0
5 3 2 1 0 0 0 0 0 1
0 1 1 0 1 1 1 1 1 0
2 0 1 2 0 4 0 0 0 0
0 1 0 2 2 2 1 0 0 0
2 2 0 1 1 0 0 0 0 2
6 0 1 0 0 0 0 1 1 1
0 0 1 0 3 0 0 0 0 2
4 0 0 2 2 0 1 0 1 0
0 6 0 0 1 0 0 0 2 0
6 0 1 0 0 0 0 1 1 1
12 0 0 0 3 0 1 0 0 0
0 1 5 0 0 0 0 0 2 0
3 2 0 2 3 1 0 0 0 0
0 2 0 0 3 0 3 0 0 0
0 6 0 5 0 0 0 0 0 0
4 2 2 3 0 0 1 0 0 0
2 1 1 0 0 2 0 1 0 1
0 1 5 0 0 0 0 0 2 0
6 6 1 0 0 0 0 0 1 0
0 1 0 2 1 1 1 0 0 1
3 0 0 1 2 1 1 0 1 0
3 1 5 0 0 1 1 0 0 0;

num=145 305 230 151 115 150 98 120 180 65;
end
data
min=@sum(method:n);
@for(parts(j):@sum(method(i):m(i,j)*n(i))>=num(j));
@for(method:@gin(n));
end

附录二：C语言随机抽取200组数据程序
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
main()
{int a,b,c,d,e,f,g,h,i,j,a1[600],b1[600],c1[600],d1[600],e1[600],f1[600],g1[600],h1[600],i1[600],j1[600],k=0,l,m,n,o,p,q,r,s,t,u,v,w;
for(j=0;j<4;j++)
for(i=0;i<5;i++)
for(h=0;h<6;h++)
for(g=0;g<7;g++)
for(f=0;f<7;f++)
for(e=0;e<9;e++)
for(d=0;d<10;d++)
for(c=0;c<11;c++)
for(b=0;b<14;b++)
for(a=0;a<26;a++)
if(330*a+620*b+820*c+920*d+1000*e+1250*f+1360*g+1470*h+1800*i+2250*j>=8320&&330*a+620*b+820*c+920*d+1000*e+1250*f+1360*g+1470*h+1800*i+2250*j<8330)
a1[k]=a,b1[k]=b,c1[k]=c,d1[k]=d,e1[k]=e,f1[k]=f,g1[k]=g,h1[k]=h,i1[k]=i,j1[k]=j,++k;
k-=1;
srand((int)time(0));
for(v=1;v<=200;v++)
{
w=rand()%k;
l=a1[w],m=b1[w],n=c1[w],o=d1[w],p=e1[w],q=f1[w],r=g1[w],s=h1[w],t=i1[w],u=j1[w];
printf("%d %d %d %d %d %d %d %d %d %d\n",l,m,n,o,p,q,r,s,t,u);}
return 0;
}
19