【数学建模学习】最优截断切割问题

数学建模截断切割问题学号：************* 姓名：杨德升学号：************* 姓名：李春红学号：************* 姓名：杨建明问题描述：某些工业部门（如贵重石材加工等）采用截断切割的加工方式。

这里“截断切割”是指将物体沿某个切割平面分成两部分。

从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的对应表面是平行的），通常要经过6次截断切割。

设水平切割单位面积的费用是垂直切割单位面积费用的r倍，且当先后两次垂直切割的平面(不管它们之间是否穿插水平切割)不平行时，因调整刀具需额外费用e。

试为这些部门设计一种安排各面加工次序（称“切割方式”）的方法，使加工费用最少。

（由工艺要求，与水平工作台接触的长方体底面是事先指定的）详细要求如下：1、需考虑的不同切割方式的总数。

2、给出上述问题的数学模型和求解方法。

3、试对某部门用的如下准则作出评价：每次选择一个加工费用最少的待切割面进行切割。

4、对于e=0的情形有无简明的优化准则。

5、用以下实例数据验证你的方法：待加工长方体和成品长方体的长、宽、高分别为10、14.5、19和3、2、4，二者左侧面、正面、底面之间的距离分别为6、7、9（单位均为厘米）。

垂直切割费用为每平方厘米1元，r和e的数据有以下4组：a r = 1 e = 0;b r = 1.5 e = 0;c r = 8 e = 0;d r = 1.5 2<= e<=15;对最后一组数据应给出所有最优解，并进行讨论。

解：（1）对于计算不同的切割方式总数，经过分析，能够用排列组合的知识来解决这个问题。

我们对分别位于前、后、左、右、上、下的切割面进行编号，其相应的编号分别为1M，2M，M3，M4，M5，M6，然而每一种切割方式都是对这6个切割面的一个排列方式，所以总共就6！=720种排列方式。

但是相继切割一对平行面时，交换切割次序，不影响切割费用，把费用相同的一项归到一类，最终的切割总数为：720-3x5!+3x4!-3!=426种(2)(3)(4)(5)符号说明：a0,b0,c0分别表示待加工长方体的长、宽、高。

五一数学建模竞赛承诺书我们仔细阅读了五一数学建模竞赛的竞赛规则。

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

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

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。

如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。

我们授权五一数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

参赛题号（从A/B/C 中选择一项填写）： B参赛队号：参赛组别（研究生、本科、专科、高中）：所属学校（学校全称）：参赛队员：队员1 姓名：XXX队员2 姓名：XXX队员3 姓名：XXX联系方式：Email：联系电话：日期：年月日（除本页外不允许出现学校及个人信息）五一数学建模竞赛题目：木料切割最优化问题关键词：矩形件下料切割问题guillotine摘要：随着社会的发展、人们对环境资源的重视，提高材料的利用率、获得最大利润就成了不可避免的问题，而解决这个问题的关键就是对产品的生产进行紧凑型的布局。

本文旨在解决家具厂木料的切割问题，由一维问题（或者说是 1.5 维问题）递推到二维问题，通过寻找合适的切割方法（采用guillotine ，贪心启发式算法的多目标二维切割），使得我们从目标木板上切割出的所需产品的面积和最大或者利润最大，后对方案进行优化处理，最终得出最优方案。

问题一用guillotine 方法切割可得一块木板上P1 最多能切割59 个。

问题二在问题一的基础上，通过迭代的方法，分析得出前三甲利用率分别为99.64%，99.23%和99.03%的最佳方案。

问题三又在问题二的基础上，引入了生产任务作为限制因素，并结合贪心启发式算法的多目标二维切割和问题使问题得到解决。

钢管下料
切割模式
按照客户需要在一根原料钢管上安排切割的一种组合。 4米 1根 4米 1根 6米 1根 6米 1根 8米 1根 6米 1根 余料1米 余料3米 余料3米
8米 1根
8米 1根
合理切割模式的余料应小于客户需要钢管的最小尺寸
钢管下料问题1
模式 1 2 3 4 5 6 7 4米钢管根数 4 3 2 1 1 0 0
26 x1 x2 x3 31
x1 x2 x3
模式排列顺序可任定
计算结果
• 模式1：每根原料钢管切割成3根4米和1根6 米钢管，共10根； • 模式2：每根原料钢管切割成2根4米、1根5 米和1根6米钢管，共10根； • 模式3：每根原料钢管切割成2根8米钢管， 共8根。 • 原料钢管总根数为28根。
合理切割模式
6米钢管根数 0 1 0 2 1 3 0 8米钢管根数 0 0 1 0 1 0 2 余料(米) 3 1 3 3 1 1 3
为满足客户需要，按照哪些种合理模式，每种模式 切割多少根原料钢管，最为节省？ 两种 标准 1. 原料钢管剩余总余量最小
2. 所用原料钢管总根数最少
决策 变量 xi ~按第i 种模式切割的原料钢管根数(i=1,2,…7) 目标1（总余量） Min Z1 3x1 x2 3x3 3x4 x5 x6 3x7
钢管下料问题2
增加一种需求：5米10根；切割模式不超过3种。
现有4种需求：4米50根，5米10根，6米20根，8米 15根，用枚举法确定合理切割模式，过于复杂。 对大规模问题，用模型的约束条件界定合理模式
决策变量
xi ~按第i 种模式切割的原料钢管根数(i=1,2,3)
r1i, r2i, r3i, r4i ~ 第i 种切割模式下，每根原料钢管 生产4米、5米、6米和8米长的钢管的数量

Fbest Fmin min {F
1 n 720 (n) knife (n) cut 1 n 720 k 1
(n) ( ( F } min {e f (v ) p (m kn ) )s (v kn ) )}
若 n n 时有
6 ( n ) ( e f (v ) p(mk ) s(vkn ) ) Fmin k 1
h ( h(2), h(1), h(5), h(3), h(4), h(6) ) ( 1, 6, 9, 7, 5.5, 6 ) 则 t1 (a1 , b1 , c1 ) ( 10, 14.5, 19 ) , t2 (a2 , b2 , c2 ) t1 (a1 , b1 , c1 ) ( 9, 14.5, 19 ) t1 h(2)(1,0,0) , t3 (a3 , b3 , c3 ) t2 (a2 , b2 , c2 ) ( 3, 14.5, 19 ) t2 h(1)(1,0,0) , t4 (a4 , b4 , c4 ) t3 (a3 , b3 , c3 ) ( 3, 14.5, 10 ) t3 h(5)(0,0,1) , t5 (a5 , b5 , c5 ) t4 (a4 , b4 , c4 ) ( 3, 7.5, 10 ) t4 h(3)(0,1,0) , t6 (a6 , b6 , c6 ) t5 (a5 , b5 , c5 ) ( 3, 2, 10 ) t5 h(4)(0,1,0) , t6 (a6 , b6 , c6 ) ( 3, 2, 4 ) t6 h(6)(0,0,1) . k 1, 2,3, 4,5 tk 1 tk tk h(vk )em(vk ) ,

平面钢板切割问题【摘要】对于一块钢板，如何切割最经济，需要有最佳切割的方式。

为了找到最优切割方式，首先通过分析及Mathematic软件得到可能的17种下料方法；接着模拟切割操作，得到其中9种可行方法；最后在 Lindo中编程，编写目标函数，寻找最优解。

最终得出在总用量最少目标函数下，即钢板总用量最小为12块，最优解为x1 = 0, x2 = 1, x3 = 0, x4 = 0, x5 = 0, x6 = 0, x7 = 0, x8 = 0, x9 = 6, x10 = 5，其中多余62块1*3的钢板；在总废料的面积最少目标函数下，即钢板总用量最小为13块，最优解为x1 = 0, x2 = 1, x3 = 12, x4 = 0, x5 = 0, x6 = 0, x7 = 0, x8 = 0, x9 = 0, x10 = 0，其中多余91块1*3的钢板和1块5*7的钢板。

【关键词】最佳切割 Mathematic软件 Lindo软件最优解【正文】一、问题重述钢厂有10m×10m 的钢板，需要满足下列订货的切割要求：（1）60 张1m×3m 的小钢板；（2）49 张2m×4m 的小钢板；（3）12 张5m×7m 的小钢板；问题：应该如何切割钢板最经济？二、问题分析（1）算出一块10m×10m 的钢板可以有1m×3m、2m×4m、5m×7m这样的三种小钢板的多少种组合形式（2）根据各种不同的组合，画出下料图（3）根据下料图，利用lindo软件，找出符合要求又废料很少的方式三、建立模型第一步：寻找可能的下料方法钢板总面积100m2，1*3的小钢板面积3m2,2*4的8m2，5*7的35m2，分别最多切割max a 、max b 、max c 块.则max a<=33,max b<=12,max c<=2,又因为下料边长都是整数，于是底料边长不会超过3m，即底料的面积最多是2*2=4m。

————最优切割问题99131059 魏炜一：问题的提出某些工业部门（如贵重石才的加工等）采用截断切割的加工方式。

这里“截断切割”是指将物体沿某个切割平面分成两个部分。

从一个长方体中加工出一个已知尺寸位置预定的长方体（这个长方体的对应表面是平行的），通常要经过6次截断切割。

设水平切割单位面积的费用是垂直切割单位面积的r倍，且当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，因调整刀具需额外费用e。

试为这些部门设计一种安排个面加工次序的方法。

待加工的长方体和成品的长，宽，高分别为10，14.5,19和3,2,4两者左侧面，正面，底面之间的距离分别为6 ,7,9（单位均为厘米）垂直切割的费用为每平方厘米1元。

r和e数据如下(a)r=1,e=0 (b)r=1.5 e=2二：问题的分析刚拿到这个题目时，还是很茫然的，不知应该用什么样的方法进行解答，当学到图与网络分析的时候，突然觉得这道题是不是可以用最短路的来求解呢？抱着试试看的心里，我将问题成功的转换成了求一个图的最短路的问题，而我们要求最短路就是要先求出每一条边所表示的权重。

三：问题的解决设待加工体的长、宽、高分别为a0、b0、c0。

六个切割面分别位于左、右、前后、上下相应为S1、S2、S3、S4、S5、S6。

这六个面与成品的相应外测面的距离分别为d1、d2、d3、d4、d5、d6。

不失一般性设d1>=d2、d3>=d4、d5>=d6。

故可以只考虑S1在S2前、S3在S4前、S5在S6前被切割的方式。

I：e=0 r=1 的情形。

先考虑如何建立图形。

将切割问题转化为求图的最短路径问题。

赋权网络图G*的建立。

由于共计切6刀，因此我们想到要建立一个三维网络图：① 图形的解释。

图中各个点表示每个切割状态。

例如)0,0,0(1v 表示最初状态，)2,2,2(27v 表示已经切割完毕。

)0,2,1(8v 表示左前被切一刀，前后各被切一刀，上下没有被切。

截断切割B题截断切割题目某些工业部门（如贵重石材加工等）采用截断切割的加工方式。

这里“截断切割”是指将物体沿某个切割平面分成两部分。

从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长主体的对应表面是平行的）通常要经过6次截断切割。

设水平切割单位面积的费用是垂直切割单位面积费用的r倍，且当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，因调整刀具需额外费用e.试为这些部门设计一种安排各面加工次序（称“切割方式”）的方法，使加工费用最少。

（由工艺要求，与水平工作台接触的长方体底面是事先指定的）详细要求如下：1、需考虑的不同切割方式的总数2、给出上述问题的数学模型和求解方法。

1、试对某部门用的如下准则作出评价：每次选择一个加工费用最少的待切割面进行切割。

2、对于e=0的情形有无简明的优化准则。

3、用以下实例验证你的方法：待加工长方体和成品长方体的长、宽、高分别为10、14.5、19和3、2、4，二者左侧面、正面、底面之间的距离分别为6、7、9（单位均为厘米）。

垂直切割费用为每平方厘米1元，r和e的数据有以下4组：a.r=1 e=0 ;b.r=1.5 e=0 ;c.r=8 ,e=0 ;d.r=1.5;2≤e≤15对最后一组数据应给出所有最优解，并进行讨论。

B题截断切割参考答案（1）需考虑的不同切割方式的总数V中共有6!=720个不同的元素，因此有720种不同的切割方式，注意到相继二次切割一对平行的平面时，交换这二次切割的先后次序不影响对应切割方式的费用，将费用相同的切割方式归成一类，每类取一种切割方式作不代表，此时仅需考虑加工费用可能不同的切割方式426种。

（2）问题归结为求一个定义在6个切割面排列次序的全体或它的一个子集上的函数的最小值。

目标函数应尽量用显式写出。

求解可用枚举法，分支定界法或其它方法，从尽可能简便有效作为评价标准：（3）一种作法如下：在直角坐标系中，表面平行于坐标平面的长方体可表示为{（x,y,z）,(a,b,c)},其中（x,y,z）为长方体某指定角点的坐标，a,b,c分别为它的长、宽、高。

建模案例：最优截断切割问题一、 问 题从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的对应表面是平行的），通常要经过 6 次截断切割.设水平切割单位面积的费用是垂直切割单位面积费用的r 倍.且当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，因调整刀具需额外费用 e.试设计一种安排各面加工次序（称“切割方式”）的方法，使加工费用最少.二、 假 设１、假设水平切割单位面积的费用为r ，垂直切割单位面积费用为1；２、当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，调整刀具需额外费用e ；３、第一次切割前，刀具已经调整完毕，即第一次垂直切割不加入刀具调整费用；4 、每个待加工长方体都必须经过6次截断切割.三、 模型的建立与求解设待加工长方体的左右面、前后面、上下面间的距离分别为 a0、b0 、c0 ，六个切割面分别位于左、右、前、后、上、下，将它们相应编号为M1、M2、M3、M4、M5、M6，这六个面与待加工长方体相应外侧面的边距分别为 u1、u2、u3、u4、u5、u6.这样，一种切割方式就是六个切割面的一个排列，共有P 66720= 种切割方式.当考虑到切割费用时，显然有局部优化准则：两个平行待切割面中，边距较大的待切割面总是先加工.由此准则,只需考虑 P 6622290!!!⨯⨯=种切割方式.即在求最少加工费用时，只需在90个满足准则的切割序列中考虑.不失一般性，设u1≥u2，u3≥u4，u5≥u6，故只考虑M1在M2前、M3在M4前、M5在M6前的切割方式.1、 e=0 的情况为简单起见,先考虑e=0 的情况.构造如图9-13的一个有向赋权网络图G(V,E).为了表示切割过程的有向性，在网络图上加上坐标轴x，y，z.图9-13 G(V,E)图G(V,E)的含义为：(1)空间网络图中每个结点Vi(xi,yi,zi)表示被切割石材所处的一个状态.顶点坐标xi、yi、zi分别代表石材在左右、前后、上下方向上已被切割的刀数.例如：V24(2,1,2) 表示石材在左右方向上已被切割两刀，前后方向上已被切一刀，上下方向上已被切两刀，即面M1、M2、M3、M5、M6均已被切割.顶点V1(0,0,0) 表示石材的最初待加工状态，顶点V27(2,2,2)表示石材加工完成后的状态.(2)G的弧（Vi,Vj）表示石材被切割的一个过程，若长方体能从状态Vi经一次切割变为状态Vj，即当且仅当xi+yi+zi+1=xj+yj+zj时，Vi(xi,yi,zi)到Vj(xj,yj,zj)有弧(Vi,Vj)，相应弧上的权W(Vi,Vj)即为这一切割过程的费用.W(Vi,Vj)=(xj-xi)⨯(bi⨯ci)+(yj-yi)⨯(ai⨯ci)+(zj-zi)⨯(ai⨯bi)⨯r其中，ai、bi、ci分别代表在状态Vi时，长方体的左右面、上下面、前后面之间的距离.例如，状态V5（1，1，0），a5 = a0-u1,b5 = b0-u3,c5 = c0;状态V6（2，1，0）W(V5，V6) ＝（b0-u3)⨯c0(3)根据准则知第一刀有三种选择，即第一刀应切M1、M3、M5中的某个面，在图中分别对应的弧为( V1,V2)，(V1,V4)，(V1,V10). 图G中从V1到V27的任意一条有向道路代表一种切割方式.从V1到V27共有90条有向道路，对应着所考虑的90种切割方式.V1到V27的最短路即为最少加工费用，该有向道路即对应所求的最优切割方式.实例：待加工长方体和成品长方体的长、宽、高分别为10、145、19 和3、2、4，两者左侧面、正面、底面之间的距离分别为6、7、9，则边距如下表：u1 u2 u3 u4 u5u66 1 755 69r=1时，求得最短路为V1－V10－V13－V22－V23－V26－V27，其权为374对应的最优切割排列为M5－M3－M6－M1－M4－M2，费用为374元.2、e≠0的情况当e≠0时，即当先后两次垂直切割的平面不平行时，需加调刀费e.希望在图9-13的网络图中某些边增加权来实现此费用增加.在所有切割序列中，四个垂直面的切割顺序只有三种可能情况：<情况一>先切一对平行面，再切另外一对平行面，总费用比e=0时的费用增加e.<情况二>先切一个，再切一对平行面，最后割剩余的一个，总费用比e=0时的费用增加2e.<情况三>切割面是两两相互垂直，总费用比e=0时的费用增加3e.在所考虑的90种切割序列中，上述三种情况下垂直切割面的排列情形，及在G垂直切割面排列情有向路必经点形情况一（一）M1－M2－M3－M4 (1,0,z),(2,0,z),(2,1,z)情况一（二）M3－M4－M1－M2 (0,1,z),(0,2,z),(1,2,z)情况二（一）M3－M1－M2－M4 (0,1,z),(1,1,z),(2,1,z)情况二（二）M1－M3－M4－M2 (1,0,z),(1,1,z),(1,2,z)情况三（一）M1－M3－M2－M4 (1,0,z),(1,1,z),(2,1,z)情况三（二）M3－M1－M4－M2 (0,1,z),(1,1,z),(1,2,z)我们希望通过在图9-13的网络图中的某些边上增加权来进行调刀费用增加的计算，但由于网络图中的某些边是多种切割序列所公用的.对于某一种切割序列，需要在此边上增加权e，但对于另外一种切割序列，就有可能不需要在此边上增加权e，这样我们就不能直接利用图9-13的网络图进行边加权这种方法来求出最短路径.由上表可以看出，三种情况的情形（一）有公共点集{(2,1,z)|z=0,1,2}，情形（二）有公共点集{(1,2,z)|z=0,1,2}.且情形（一）的有向路决不通过情形（二）的公共点集，情形（二）的有向路也不通过情形（一）的公共点集.所以可判断出这两部分是独立的、互补的.如果我们在图G中分别去掉点集{(1,2,z)|z=0,1,2}和{(2,1,z)|z=0,1,2}及与之相关联的入弧，就形成两个新的网络图，如图Ｈ1和Ｈ2.这两个网络图具有互补性.对于一个问题来说，最短路线必存在于它们中的某一个中.由于调整垂直刀具为3次时，总费用需增加3e，故我们先安排这种情况的权增加值e，每次转刀时，给其待切弧上的权增加e.增加e的情况如图9-14中所示.再来判断是否满足调整垂直刀具为二次、一次时的情况，我们发现所增加的权满足另外两类切割序列.综合上述分析，我们将原网络图G分解为两个网络图Ｈ1和Ｈ2，并在指定边上的权增加e，然后分别求出图Ｈ1和Ｈ2中从V1到V27的最短路，最短路的权分别为：d1,d2.则得出整体的最少费用为：d = min(d1,d2) ，最优切割序列即为其对应的最短路径.实例：r=15,e=2时，求得图G1与G2的最短路为G2的路V1－V4－V5－V14－V17－V26－V27，权为4435，对应的最优切割序列为M3－M1－M6－M4－M5－M2，最优费用为4435.图9-14 H1图9-15 H2。

建模案例：最优截断切割问题一、 问 题从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的对应表面是平行的），通常要经过６ 次截断切割．设水平切割单位面积的费用是垂直切割单位面积费用的r 倍。

且当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，因调整刀具需额外费用e.试设计一种安排各面加工次序（称“切割方式”)的方法,使加工费用最少。

二、 假 设1、假设水平切割单位面积的费用为r,垂直切割单位面积费用为１;２、当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，调整刀具需额外费用ｅ；3、第一次切割前,刀具已经调整完毕，即第一次垂直切割不加入刀具调整费用； 4 、每个待加工长方体都必须经过6次截断切割．三、 模型的建立与求解设待加工长方体的左右面、前后面、上下面间的距离分别为 a0、b ０ 、c0 ，六个切割面分别位于左、右、前、后、上、下，将它们相应编号为M1、Ｍ2、M3、M ４、M5、M6，这六个面与待加工长方体相应外侧面的边距分别为 u1、ｕ2、u3、u4、u5、ｕ6.这样,一种切割方式就是六个切割面的一个排列，共有P 66720= 种切割方式。

当考虑到切割费用时，显然有局部优化准则:两个平行待切割面中，边距较大的待切割面总是先加工.由此准则，只需考虑 P 6622290!!!⨯⨯=种切割方式.即在求最少加工费用时，只需在９0个满足准则的切割序列中考虑．不失一般性,设u １≥u2,u3≥u ４，u5≥u6,故只考虑Ｍ1在M2前、M ３在M ４前、M5在Ｍ６前的切割方式。

1、 ｅ=0 的情况为简单起见,先考虑e＝0 的情况．构造如图9—１3的一个有向赋权网络图Ｇ(V，Ｅ）。

为了表示切割过程的有向性，在网络图上加上坐标轴x，y，z．图9—13 G（V,Ｅ)图G（V，E)的含义为:（１)空间网络图中每个结点Ｖi(ｘi，yi,ｚi）表示被切割石材所处的一个状态.顶点坐标xｉ、yi、ｚi分别代表石材在左右、前后、上下方向上已被切割的刀数．例如：V24(2，1,2) 表示石材在左右方向上已被切割两刀，前后方向上已被切一刀,上下方向上已被切两刀，即面Ｍ1、M2、M3、M5、M6均已被切割．顶点V1（0，0，０）表示石材的最初待加工状态,顶点V２7（２，２，２）表示石材加工完成后的状态．（2)Ｇ的弧(Vi,Vj)表示石材被切割的一个过程，若长方体能从状态Ｖi经一次切割变为状态Vj,即当且仅当xｉ+yi+zi＋１=ｘj＋yj+zj时，Vi（ｘi，yi，zｉ)到Vj（ｘｊ，yj,zj）有弧（Vｉ，Vj),相应弧上的权W(Vi，Ｖj）即为这一切割过程的费用。

和(0,1,0) → (0,0,1) → (1,0,0) → (0,1,0) → (0,0,1) → (1,0,0)(∗∗) 对应路线为：V1→ V4 → V5(V13) → V14 → V23 → V26 → V27 其中决策方案（*）只符合准则 2，而决策方案（**）不仅符合准则 1，而 且符合准则 2。 （c）r=8,e=0; 求得最小总收益 J=540.5 元，满足最小总收益的只有一种切割方式，在满足 f—原则的前提下，其切割状态向量为： (0,1,0) → (1,0,0) → (0,1,0) → (0,0,1) → (1,0,0) → (0,0,1) 对应路线为：V1→ V4 → V5 → V8 → V17 → V18 → V27 这种决策方案只符合准则 2，但不符合准则 1。 其中决策方案 （*） 只符合准则 2， 而决策方案 （**） 符合准则 1 和准则 从以上结果可看出，模型的可靠性是比较高的，且具有较好的稳定性。 2。
图1 在 M6 前的切割方式. 若用穷举法考虑该问题，所得可能的方法排列如下图
图2 但是由于列举法的计算过程太复杂，故不考虑。
三、基本假设与符号约定
（一）基本假设 1．由工艺要求，与水平工作台接触的待加工长方体底面是事先指定的，成品 长方体的尺寸已知，位置预定，且两个长方体和对应表面是平行的。 2．刀具的磨损情况很小，可忽略不计。 3．切割热量对长方体所产生的影响很小，可忽略不计。 4． 我们称切割后的那些不含成品长方体的小长方体为切块，考虑切块的可应
《数学建模课程设计》
最优截断切割方案
学校 班级 组员
浙江理工大学理学院 11 信息与计算科学（1）班 2011326630108 吴羽桑 2011326630109 余梦颖
2014—6—19

数学建模经典案例最优截断切割问题在我们的日常生活和工业生产中，经常会遇到材料切割的问题。

如何在给定的原材料上，通过合理的切割方式，获得最大的效益或者满足特定的需求，这就是最优截断切割问题所要研究的核心内容。

想象一下，你是一家木材加工厂的老板，手头有一根长长的原木，需要将其切割成不同长度的木板，以满足客户的订单需求。

但原木的长度是有限的，而客户的订单要求各种各样，怎样切割才能最大限度地利用这根原木，减少浪费，提高利润呢？这可不是一件简单的事情，需要运用数学建模的智慧来找到最优解。

为了更好地理解最优截断切割问题，让我们先来看一个具体的例子。

假设有一根长度为 10 米的钢材，需要切割成 2 米、3 米和 4 米三种不同长度的小段，分别需要 10 段、8 段和 5 段。

那么，应该如何切割才能使浪费最少，或者说在满足需求的前提下使用的钢材最少呢？首先，我们可以尝试一些直观的切割方法。

比如说，先把钢材尽可能地切成 4 米长的小段，然后再处理剩下的部分。

但这样做真的是最优的吗？也许在这个例子中是，但如果需求的数量或者钢材的长度发生变化，这种方法可能就不再适用了。

为了解决这个问题，我们可以建立一个数学模型。

假设我们用 x1、x2、x3 分别表示切割成 2 米、3 米和 4 米小段的数量。

那么，我们需要满足以下条件：2x1 ＋ 3x2 ＋ 4x3 ＜＝ 10 （这表示切割出的小段长度总和不能超过原材料的长度）x1 ＞＝ 10 （2 米小段的需求数量）x2 ＞＝ 8 （3 米小段的需求数量）x3 ＞＝ 5 （4 米小段的需求数量）同时，我们的目标是要使切割使用的钢材长度最小，也就是要最小化 2x1 ＋ 3x2 ＋ 4x3 这个目标函数。

接下来，我们可以使用一些数学方法来求解这个模型。

常见的方法有线性规划、动态规划等。

以线性规划为例，我们可以通过软件工具（如 LINGO、Matlab 等）来求解这个问题，得到最优的切割方案。

较了720个加工费后才能达成).理由是: 最佳切割方
式虽然可能不唯一, 但最佳加工费用应是唯一不变的 值. 因此, 若准则选出的不同切割方式有许多, 而 相应的加工费却不全同, 则其至少表明它不具备优 化准则的基本属性．同样，即使精选出的切割方式 唯一, 但加工费却非真正意义上的最佳加工费用， 则准则也无最优性可言。
另外，关于问题4、5的简单分析
计算结果：依准则选出的不同切割方案多达15种，且还表明 了此切割标准一般不可作为优化准则使用. 5.对某部门切割准则的再评价 1） 在切割单价的平竖比r =1与r =1.5且换刀价e =0时, 依 部门准则选出的为数不多的切割方式中包含有最优切割方式(即 切割费最小的方式)；但可能不含有全部可能的最优切割方 式．由于它远比全面搜索的计算量小, 故可用在计算环境差的 现场供手工快速搜索最优切割方式. 2）每次选择加工费最小的待切割面进行切割”虽不可作为优化 准则使用, 但只要其精选出的15种不同切割方式的最小加工费并
这种相互平行的平面一共有3对。其中的1对在 加工顺序中相邻的情况共5!种，有某2对相邻的共4! 模型一、二都没给出总加工费 种，3对都相邻的有3!种。 的就是办法，需要修正模型 根据组合学中的容斥原理便可得到结果：
6! 3 5! 3 4! 3! 426 (种)
五、模型分析与改进
2、重新寻找更好的建模方式、方法
一、模型准备
2、收集资料
方法：可在图书馆、网上查阅、向专家询问、 通过实物切割试验来得到资料，并最好用笔 做好记录。 不过，此问题暂时不需要搜集数据，重 点寻找与之最接近的数学模型资料。
Next：建模，关键是理清不同加工次序下的总加
工费如何计算
3、问题重述（略）
二、模型假设

优化设计方法(Optimization Method)
最优准则法
交通与车辆工程学院 刚宪约 2014年4月24日
截断切割（97年全国数学建模题目）
某些工业部门（如贵重石材加工等）采用截断切割的 加工方式。这里“截断切割”是指将物体沿某个切割平面 分成两部分。从一个长方体中加工出一个已知尺寸、位置 预定的长方体（这两个长方体的对应表面是平行的），通 常要经过6次截断切割。 设水平切割单位面积的费用是垂 直切割单位面积费用的r 倍，且当先后两次垂直切割的平 面(不管它们之间是否穿插水平切割)不平行时，因调整刀 具需额外费用e。 试为这些部门设计一种安排各面加工次 序（称“切割方式”）的方法，使加工费用最少。
T
桁架结构的满应力法(2)
（4）形成应力比列阵。
μ μ1, μ 2 ,, μ n
1 j L


T
式中， μ i max ij ， （5）计算 1 i 。

i 1,2,, n 。
若对于所有 i ，有 1 i （ 为控制精度） ，则停止计算， 取 X* A ；否则，取 Ai i Ai 。 （6） A A ，返回（2）
一个静不定桁架的例子
超静定桁架主要参数： 各杆材料相同， E =常数；
1m B
1m
1m C D ③
=2×107kPa， =－1.5×107kPa。
两种工况： （1） P1 ＝2000kN， P2 ＝0 （2） P1 ＝0， P2 ＝2000kN
①
② A
P 1
P2
交通与车辆工程学院 刚宪约 gangxianyue@
齿行法
交通与车辆工程学院 刚宪约 gangxianyue@

数学建模经典案例最优截断切割问题在日常生活和工业生产中，我们常常会遇到材料切割的问题。

如何在给定的原材料上，通过合理的切割方式，获得最大的效益或者满足特定的需求，这就是最优截断切割问题所要研究的核心内容。

想象一下，你是一家木材加工厂的老板，手里有一根长度固定的原木，而客户向你订购了各种不同长度的木板。

为了最大限度地利用这根原木，减少浪费，同时满足客户的订单需求，你需要思考怎样切割才能达到最优效果。

这不仅仅是简单的切割操作，而是涉及到数学的精确计算和策略规划。

比如说，我们有一根长度为 10 米的原木，而客户需要 2 米长的木板 3 块，3 米长的木板 2 块。

那么，我们应该怎样切割这根原木呢？这就需要用到数学建模的方法来找到最优的切割方案。

首先，我们来分析一下可能的切割方式。

一种方式是直接按照客户的需求进行切割，即先切出 3 段 2 米长的，然后再切出 2 段 3 米长的。

但这样可能会剩下 1 米的废料。

另一种方式是尝试不同的组合，比如先切出 2 段 3 米长的，然后从剩下的 4 米中再切出 3 段 2 米长的，这样就没有废料产生。

但这只是简单的举例，实际情况可能会更加复杂。

为了找到最优的切割方案，我们需要建立一个数学模型。

假设原木的长度为 L，客户需要的木板长度分别为 l1, l2, l3,， ln ，数量分别为n1, n2, n3,， nn 。

我们的目标是在满足客户需求的前提下，使废料最小或者利用率最大。

我们可以定义一个变量 xij 表示第 i 种长度的木板切割 j 段。

那么，我们的约束条件就是：对于每种长度的木板，其切割的数量要满足客户的需求，即∑j xij ＝ni 。

同时，切割的总长度不能超过原木的长度，即∑i j × lij × xij ≤ L 。

接下来，我们的目标函数可以是使废料最小，即 Minimize （L ∑i j × lij × xij) ，或者使利用率最大，即 Maximize （∑i j × lij × xij ／ L) 。

工业中截断切割的优化设计一摘要本文评论辩论了加工业中截断切割的优化排序计谋我们对于不合的切割方法总数用穷举法得到720 种所可行解及其费用并对于原问题树立了决议计划并对所给出的算法进行了剖析和磨练1.当e=0时我归纳出解决问题的最优轨则, 从而提出了将面间距同一成断定权重来作为排序准则的算法,同时证实了e = 0 的情况下依据这种最优准则可以或许实现标题所请求的优化目标2.对于e ¹0 时我们提出了实用准则最后我联合现实问题将本问题进行了拓展评论辩论了当最终产品(成品)在毛坯(待加工长方体)中地位不预准时应若何实行加工计划以达到节俭费用和勤俭资本的目标,使我们的计划实用于更为辽阔的范畴二问题的重述.在工业临盆中,常须要采纳将物理一分为二的截断切割方法从一块长方体资估中切出一个小长方体,其加工费用取决于程度切割和垂直切割的截面面积,以及调剂刀具时的额外费用.对本题所给出的问题我们起首面对的对加工次序的排序计谋然后我们斟酌当毛坯和产品地位不预定的时刻若何采纳计谋以达到我们的优化目标问题：1> 需斟酌的不合切割方法的总数.2> 给出上述问题的数学模子和求解办法.3> 试对某部分用的如下准则做出评价,每次选择一个加工费用起码的切割面进行切割.4> 对于 e=0 的情况有无简明的优化准则.5> 用以下实例验证你的办法：待加工长方体和成品长方体的长,宽,高分离为10,14.5,19 和3,2,4,两者左正面,正面,底面之间的距离分离为6,7,5(单位为厘米,垂直切割费用为每平方厘米1 元,r 和e 的数据有4 组：1) r=1,e=0;2) r=1.5,e=0;3) r=8,e=0;4) r=1.5, 2 £e £15 ;三模子的假设和符号解释1 切割刀具为两个一个程度放置一个为垂直放置2 目标长方体地点地位不与毛坯任一概况重合3程度偏向只需平行移动程度刀具垂直偏向只平行移动或调剂后再平行移动刀具是以调剂费用e 是否支付仅取决于先后两次垂直切割是否平行而不记是否穿插着程度切割4毛坯与工作台接触的底面是事先指定的5毛坏.成品均为长方体,且这两个长方体的对应面是平行的,如下图a,b, c 毛坯的长宽高单位厘米aa,b b,c c 最终产品的长宽高单位厘米毛坯的左概况右概况前概况后概况上概况下概况最终产品的左概况右概况前概况后概况上概况下概况(有时我们为了论述问题的便利将其依次记为5,6,3,4,1,2) d j 最终产品与毛坯的对应概况的距离j = 1,2,,,,6r 程度切割单位面积费用与垂直切割单位面积费用之比e 调剂一次垂直刀具的额外费用p 垂直切割单位面积费用ti 加工进程中的第i 刀切割第ti 个面wi 第i 次切割的切割费用单位元vi 第i 次切割被切割失落部分的体积单位立方厘米si 第i 次切割时切割面积分离暗示在切割第正面时的费率,依题意：其它变量假如消失则在应用时另行解释四模子的树立(2,3,4,5,6) (3,4,5,6) (4,5,6) (5,6) (6)(1,3,4,5,6) (2,4,5,6) (3,5,6) (4,6) (5)(1,2,4,5,6) (2,3,5,6) (3,4,6) (4,5) (4)(1,2,3,4,5,6,)(1,2,3,5,6) (2,3,4,6) (3,4,5) (3)(1,2,3,4,6) (2,3,4,5) (2)(1,2,3,4,5) (1,2,3,4) (1,2,3) (1,2) (1)e=0的情况:={1,2,3,4,5,6}暗示初态,即没有进行任何加工;对应一个完全的加工计谋事实上为={1,2,3,4,5,6}的一个全分列;而={1,2,3,4,5,6}的任一子集S应某个计谋在对毛坯加工进程中某个中央状况;3）在对毛坯加工进程中某个中央状况S它仅与在它之前截失落了那些面的组合有关,而与进程(即分列)无关;4）={1,2,3,4,5,6}的64 个子集组成方体切割的所有可能的状况（包含初始状况,终态）：以的64个子集结构有向图G,,以S为起点,认为终点连边,且, 使得对有向图G边赋权：任取有向图G边,不设其以S起点,认为终点,,w (或记为）w（,）暗示在状况S,截去i所需费用这些聚集按照其包含元素数量标若干可分为7组,从多到少排序,相邻两组间组成一个决议计划阶段;1是以得如下“6”阶段动态计划问题：Min ,)S.t ={1,2,3,4,5,6}….为的一全分列=\{}w（,）的表述：记分离暗示方体的长.宽.高（这1面到2面.3到4.5到6的距离）,可得：)=(A,B,C)=w ,)=五．模子求解定理（最优准则）：设e=0,若计谋….知足：,则计谋….必为截断切割的最优计谋.证实：某截断切割计谋….,若知足,且,即称组成计谋….的一逆序对（逆序数？）;（以下证实对任一计谋….,若计谋….中消失逆序对,则总可以结构某截断切割计谋,其逆序数小于计谋….的逆序数,但总的切割费用不比计谋….的多）设某截断切割计谋….的逆序数大于0,则必消失相邻的“两刀”(k,k+1)(成计谋…..的一逆序对,交流.的次序,此时…与…比较,前者的逆序数比后者的削减“1”,而鄙人面证实前者的切割费用不比后者的多：1当面.相对时,仅仅交流相邻两刀(k,k+1)次序对切割费用没有影响;2当面.相邻时,无妨设.此时,…与…切割费用之差等于：=其符号与雷同假设,即…的切割费用比…的少.可用mathematics编程求解,程序见附件.d r=1.5 e=2~15e取值起码费用最优切割计划e=2e=2.1e=2.2 446.3e=2.3 446.7e=2.4 447.1e=2.5e=3 448.5e=3.5e=4 450.5e=4.5 451.5 e=5.5 453.5e=6 454.5e=6.5 455.5e=7 456.5e=7.5 457.5 e=8.5 459.5e=9 460.5e=9.5 461.5 e=10.5 463.5e=11 464.5e=11.5 465.5e=12 466.5e=12.5 467.5 e=13.5 469.5 e=14 470.5e=14.5 471.5 e=15 472.5个中1,2,3,4,5,6,代表切割的面如下图：21,当e 大于2.5用的图像画出 最可能是最优切割方法的三种切割方法切割费用随e 的取值而变更的图像：综上对于e 不合取值时对应的最优计划为对此我们可以提出一个很实用的准则：当e 较小时,换刀的费用很小,对于切割方法可以不斟酌换刀的影响,选择单纯切割费用起码的方法即可;当e ’较大时,则必须重要斟酌换刀的次数,在单纯切割费用尽量小的前提下,尽量选择换刀次数少的切割方法.六成果剖析及评论辩论由以上的盘算与剖析可知,r以及e是在毛坯与成品请求已固定情况下影响费用和切割方法的重要身分,当e=0时,依据优化准则,可以找到最优的切割方法,当e不等于零时,可以依据实用的准则来找到最优切割方法.七模子拓展对于成品地位不固定,成品概况可以无穷接近毛坯概况这个模子,则可以将此问题看做为选择毛坯的八个角中的一个,也即选择通俗模子的六刀中的前三刀的费用,成品未切割的也即接近毛坯概况的三个面的补刀费用,以及换刀的费用,三者之和就是总费用.此模子亦可以用最优准则及实用准则来取得较好的优化后果。

五一数学建模竞赛承诺书我们仔细阅读了五一数学建模竞赛的竞赛规则。

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

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

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。

如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。

我们授权五一数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

参赛题号（从A/B/C中选择一项填写）： B参赛队号：参赛组别（研究生、本科、专科、高中）：所属学校（学校全称）：参赛队员：队员1姓名：XXX队员2姓名：XXX队员3姓名：XXX联系方式：Email：联系电话：日期：年月日（除本页外不允许出现学校及个人信息）五一数学建模竞赛题目：木料切割最优化问题关键词：矩形件下料切割问题guillotine摘要：随着社会的发展、人们对环境资源的重视，提高材料的利用率、获得最大利润就成了不可避免的问题，而解决这个问题的关键就是对产品的生产进行紧凑型的布局。

本文旨在解决家具厂木料的切割问题，由一维问题（或者说是1.5维问题）递推到二维问题，通过寻找合适的切割方法（采用guillotine，贪心启发式算法的多目标二维切割），使得我们从目标木板上切割出的所需产品的面积和最大或者利润最大，后对方案进行优化处理，最终得出最优方案。

问题一用guillotine方法切割可得一块木板上P1最多能切割59个。

问题二在问题一的基础上，通过迭代的方法，分析得出前三甲利用率分别为99.64%，99.23%和99.03%的最佳方案。

问题三又在问题二的基础上，引入了生产任务作为限制因素，并结合贪心启发式算法的多目标二维切割和问题使问题得到解决。

数学建模经典案例最优截断切割问题在我们的日常生活和工业生产中，经常会遇到材料切割的问题。

如何在给定的材料上进行最优的截断切割，以最大程度地提高材料利用率、降低成本，是一个具有实际意义和挑战性的问题。

接下来，让我们深入探讨一下最优截断切割问题的经典案例。

想象一下，有一家家具厂接到了一批订单，需要生产一定数量的桌子和椅子。

而用于制作桌椅的原材料是长度固定的木板。

为了满足订单需求，同时尽可能减少浪费，就需要精心规划木板的切割方式。

假设我们有一块长度为 L 的木板，要将其切割成若干段，用于制作不同长度的零件。

比如，我们需要制作长度分别为 a1, a2, a3,， an 的零件，且每个零件的需求量分别为 b1, b2, b3,， bn 。

首先，我们来考虑一种简单的切割方案。

如果不考虑最优性，只是随意切割，可能会导致大量的材料浪费。

比如，先把木板切割成需要的最长零件长度，然后再用剩余的部分切割较短的零件。

但这样的方法往往不是最优的，因为可能会在最后剩下一些无法有效利用的小段材料。

那么，如何才能找到最优的切割方案呢？这就需要运用数学建模的思想。

我们可以建立一个目标函数，目标是使切割后的剩余材料最少，或者等价地说，使切割出的有用材料最多。

设切割方案为 x1, x2, x3,，xn ，分别表示切割出长度为 a1, a2, a3,， an 的零件的数量。

则我们的目标函数可以表示为：Maximize ∑xi ai （在满足约束条件的情况下）约束条件通常包括：∑xi ai ≤ L （切割出的零件总长度不能超过木板长度）xi ≥ bi （切割出的每种零件数量要满足需求）xi 为整数（因为零件的数量必须是整数）接下来，我们可以使用一些数学优化算法来求解这个模型，比如线性规划、整数规划等方法。

为了更好地理解，让我们来看一个具体的例子。

假设木板长度 L ＝10 米，需要切割出长度为 2 米、3 米和 4 米的零件，需求量分别为 5 个、3 个和 2 个。