截断切割大学生数学建模论文-毕设论文.doc

截断切割数学建模论文
摘要 本文讨论了将一个待加工长方体经过六次截断切割成一个成品长方体的切割方式问题，利用重心偏移法，考虑了第七及第k+1次切割之间的联系，建立了动态规划的数学模型，并用直接搜索法进行了求解。
本文接着用此模型对某些部门的切割准则作了正确的评价，并给了当e=0时的简明优化准则，最后用具体实例验证了模型的可靠性，并对一些初值进行了详细的讨论，给出了所有的最优解。本文还对模型进行了误差分析，并对模型进行了推广。
关键词 动态规划 切割方式 f-原则
一、问题的提出与分析

某些工业部门（如贵重石材加工等）采用截断切割的加工方式。这里“截断切割”是指将物体沿某个切割平面分成两部分。从一个长方体中加工出一个已知尺寸，位置预定的长方体（这两个长方体的对应表面是平行的），通常要经过6次截断切割。设水平切割单位面积的费用是垂直切割单位面积的费用的r倍，且当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，因调整刀具需额外费用e。
试为这些部门设计一种安排各面加工次序（称“切割方式”）的方法，使加工费用最少。并对某部门用的如下准则作出评论：每次选择一个加工费用最少的待切割面进行切割。
该问题可以采用重心偏移法。在切割之前，长方体的重心是确定的，每切割一次它的重心就偏移一次，而且偏移有一定的规律，它只是沿着长、宽或高的方向偏移。待原长方体加工成成品长方体之后，长方体的重心经过六次偏移已与成品长方体的重心重合了。这就是长方体的重心偏移过程。
该问题是一个动态规划问题，是分级决策方法和最佳化原理的综合应用。首先是建立分级决策的模型。用dk表示第k次决策，Jk表示第k级的级收益，现在一定条件下，寻求一组可行决策变量，使问题的总收益J为最佳。
二、基本假设与符号约定
（一） 基本假设
1． 由工艺要求，与水平工作台接触的待加工长方体底面是事先指定的，成品长方体的尺寸已知，位置预定，且两个长方体和对应表面是平行的。
2． 刀具的磨损情况很小，可忽略不计。
3． 切割热量对长方体所产生的影响很小，可忽略不计。
4． 我们称切割后的那些不含成品长方体的小长方体为切块，考虑切块的可应用性，设切块是带状切块。
5． 在切割过程中，设刀具对切块和待切割长方体不产生任何影响。
6． 设水平切割单位面积费用是垂直切割单位费用的r倍。
7． 设先后两次垂直切割的平面不平行时，不管它们是否穿插水平切割，因调整刀具所需额外费用e。
（二） 符号约定
dk：第k次决策；
J：总收益，即总加工费用；
P：垂直切割单位面积费用；
r：水平切割单位面积费用与垂直切割单位面积费用之比；
e：调整刀具所需额外费用；
δ(k)：第k次切割时垂直待切割平面在水平面上的投影值；
：第k+1次切割后长方体的重心座标；
tk：第k次决策时的状态；
a2,b2,c2：成品长方体的长、宽、高；
a1,a3：成品长方体距待加工长方体左侧面和右侧面的距离；
b1,b3：成品长方体距待加工长方体正前面和正后面的距离；
c1,c3：成品长方体距待加工长方体底面和顶面的距离；
：待加工长方体的长、宽、高；
n：刀具被调整的次数；
：定义了一种运算法则，即x、y同奇同偶时表达式取值为0, x、y奇偶相异时表达式取值为1。
三、模型的建立
（一） 确定切割方式的总数
待加工长方体共需截断切割6次，在横垂直方向、竖垂直方向、水平方向上各两次，其总的不同切割方式的总数为=720种。
下面证明一个定理。
定理 在同一方向上（横垂直方向、竖垂直方向或水平方向），在总收益最小的条件下，先切割下来的应该是切块厚度较大的那块长方体。
证明 如右图所示，长方体高为h，不妨设在竖垂直方向
先后切割两次，在横垂直方向上切割一次，切块T1，T2
的厚度分别为a1和a3，中间那块包着成品长方体，厚度为a2,
,
先切T1时，待切割面积S1 =（a2+a3）h,
先切T2时，待切割面积S2 =（a1+a2）h>S1.
在同种情况下，S2>S1，则切T2比切T1花的费用高，不符合总收益最小的原则。
所以，在同等情况下应切割T1，即先切割厚度较大的那块长方体。证毕。
实际上，切割六次以后，所有切块的总体积是一定的，先把体积大的切块切割下来，后面浪费的面积就少一些，费用也就小一点，这一点与实际情况是相符的。
因此，在这个原则下，不同切割方式的总数为

这比原来缩减了87。5%，大大减少了计算机的工作量。
这条原则我们称之为f—原则。使总收益达到最小时的决策方案总是90种的一种或几种。
（二）模型一
首先，建立一个三维直角坐标系，以待加工长方体的正前左下顶点为原点，长方体长、宽、高方向为x、y、z轴。
上述问题如果用非线性规划解，则其模型为：

可以看出，它有三个约束条件，现转化为动态规划问题，则它是三维的。
用(1,0,0)表示刀具沿垂直于x轴方向（即竖垂直方向）切割；
(0,1,0)表示刀具沿垂直于y轴方向（即横垂直方向）切割；
(0,0,1)表示刀具沿垂直于z轴方向（即水平方向）切割；
第k次切割时刀具方向在水平上的投影值函数定义为：

根据第k次切割及第k+1次切割之间的重心偏移关系，我们得出动态规划的数学模型：
tk+1的状态传递函数为

总收益函数；

；

;
k分别取值0，1，2，3，4，5。
因此，目标函数则为

它必须符合f—原则。
由于没有现成的软件包可以使用，我们自己在LINGO2软件环境下编写了一种实现此动态规划的算法。在程序中，我们把动态规划转化成了一个0—1规划，以判断控制和循环控制为主，采用多层循环，每进入新一层循环，需把总收益与上一层总收益进行比较，如较大则结束循环。最后经过层层比较之后，得到一个最小总收益，并同时得到所有最优决策方案。
（三）模型二
某些部门用以下准则进行工作：每次选择一个加工费用最少的待切割面进行切割。这条准则看起来好象是最优的，每次选一个加工费用最少的待切割面进行切割，最后的总费用还是最少的。实际上并非如此，它只是在其变量参数满足一定条件时才是成立的，其中r在1的范围附近变动，而且e的取值不能很大，这在以后的实例中可以得到。
因此说，这条准则只是一个局部最优准则，而并不是一个整体的最优准则，在此我们称之为准则1。
（四）模型三
当e=0时，垂直方向刀具先后不平行时调整刀具不需要额外费用，这就大大简化了问题的优化模型。
待加工长方体按三个方向切割，每个方向切下两块，我们分别令a1,a3,b1,b3,c1,c3为竖垂直方向、横垂直方向和水平方向的六块切块的厚度。当水平切割单位面积的费用为垂直单位面积的r倍时，除包含底面和顶面的两块切块外，我们分别给其它的四块切块的厚度乘以系数r，则它们的厚度分别由a1,a3,b1,b3变成了泛厚度ra1,ra3,rb1,rb3。
由f—原则得到启示，先切下泛厚度越厚的切块，则后面切割时浪费的面积越少，因此浪费的费用也越少。

即为泛厚度最厚的切块，为除第一个最厚切块外最厚切块的厚度，为泛厚度集合中除了元素外最大者。
因此，e=0时的简化优化准则为每次都切泛厚度最厚的切块。
即依次切割厚度为的切块。
这在以后的实例中可以得到验证。
在此我们称这条优化准则为准则2，它与准则1是不相同的。
四、模型的求解与检验
现有一个待加工长方体和成品长方体，它们的长、宽、高分别为10、14.5 、19和3、2、4，二者左侧面、正面、底面之间的距离分别为6、7、9（单位均为厘米），p=1元/厘米2。
（a）r=1,e=0;
利用上述模型求解，可得
原则的最小总收益J=374元，满足最小总收益的共有两种不同的切割方式，在满足f—原则的前提下，六次切割状态向量分别为：

其中决策方案（*）只符合准则2，而决策方案（**）不仅符合准则1，而且符合准则2。
（b）r=1.5,e=0;
求得最小总收益J=437.5元，满足最小总收益的共有两种不同的切割方式，在满足f—原则的前提下，六次切割状态向量分别为：

其中决策方案（*）只符合准则2，而决策方案（**）不仅符合准则1，而且符合准则2。
（c）r=8,e=0;
求得最小总收益J=540.5元，满足最小总收益的只有一种切割方式，在满足f—原则的前提下，其切割状态向量为：

这种决策方案只符合准则2，但不符合准则1。
（d）
这种情况比较复杂，需分类讨论。
（ⅰ）当n=1时，这时利用上述模型求解得到最小总收益J=442.5+e，满足最小总收益的只有一种切割方式，在满足f—原则的前提下，其切割状态向量为：

这种决策方案即不符合准则1，也不符合准则2。
（ⅱ）当n=2时，求得最小总收益J=456.5+2e，满足最小总收益的只有一种切割方式，在满足f—原则的前提下，其切割状态向量为：

这种决策方案即不符合准则1，也不符合准则2。
（ⅲ）当n=3时，求得最小总收益J=437.5+3e，它就是状况（b），共有两种不同的切割方式，在满足f—原则的前提下，其状态向量分别为：

其中决策方案（*）只符合准则2，而决策方案（**）符合准则1和准则2。
现，它在一定范围内取值，
令，
则
因此，综合知：有
（A）当共有两种不同的最佳切割方式，在满足f—原则的前提下，其切割状态向量分别为：

此结果与（ⅲ）相同。
（B）当这时只有一种最佳切割方式，在满足f—原则的前提下，其切割状态向量为：

此结果与（ⅰ）相同。
（C）。这时有三种最佳切割方式，在满足f—原则的前提下，其切割状态向量分别为：

和
此结果就是（ⅰ）和（ⅲ）的叠加。
以上结果分别是模型对(a)、(b)、(c)、(d)四种情况的所有的最优解。
从以上结果分析可以得到：准则1的成立是必须满足一定的条件，状态参数变量r在1附近范围内变动，且而当e=0时的简明优化准则2是正确的；同时，上述结果和准则2也可以验证模型的可靠程度是比较高的，且稳定性好。
五、模型的误差分析
模型中的计算误差仅来自算法中的严密性与精确性，由于题目涉及的变量较多，所要求的精度也较高，形式也较繁杂，故可产生一些误差，且能产生一定的局部影响。但本文的基本假设合理，理论可靠，模型结构简单，具有较好的稳定性。
六、模型的评价及改进方向
（一） 模型优缺点
模型一是我们得到了主要结果，它对问题的描述准确、合理，推导理论可靠、严密，模型结构简单，可靠程度高，实用性强，且稳定性好；建模过程中动态规划具有一般性，适用范围广，易于推广。
该模型没有与社会经济联系起来，没有考虑大量加工成品长方体的情形，而这些情况在实际上是出现的。
（二） 模型的改进方向
该模型可推广到其它范围内，如平板车的装货问题、轮船与货车的最大运输量问题、
资源分配问题等。成品长方体也可改成球体、正四面体等其它形体，同样可采用动态规划方法，有时可化为非线性规划问题，变动参数变量使其方案达到最优。
参考文献
[1] 姜衍智，动态规划原理及应用，西安交通大学出版社，1988年。
[2] [英]H。P。Williams著，孟国璧等译，数学规划模型建立与计算机应用，国防工业出版社，1978年。
[3] 李火林等编，数学模型与方法，江西高校出版社，1997年。
[4] [日]中山一雄著，李云芳译，金属切削加工理论，机械工业出版社，1995年。
[5] 丁振明等编，金属切削原理及刀具，国防工业出版社，1985年。
论文点评：
（待写 ）

本篇论文获得1997年数学建模的全国一等奖。