截断切割最优方式Word文件下载.docx
《截断切割最优方式Word文件下载.docx》由会员分享，可在线阅读，更多相关《截断切割最优方式Word文件下载.docx（21页珍藏版）》请在冰点文库上搜索。
：
第i次截断切割的横截面积；
第i次进行切割单位体积的费用（i=1,2,...6）；
待加工长方体的体积；
成品长方体的体积；
第i次切割时切下的体积；
进行第i次切割时的费用；
M：
切割的总费用。
三、模型的分析与建立
（一）离散型线性优化模型：
题目要求从待加工长方体中切割出位置预定的成品长方体，并希望费用尽可能的小。
我们可以这样来考虑：
因为待加工长方体和成品长方体的体积均为定值，因此任何一种切割方式所切割下来的体积之和为定值。
问题要求我们建立模型找出切割费用最少的切割方式。
令e=0时，对切割的费用影响主要是6个面切割的先后次序。
由上述符号约定，任何一种切割方式：
其总切割费用
。
首先我们用
（
=1,2,3,4,5,6）表示第i次可以切割下的所有体积的集合。
即
{第I次可以切割下的所有体积}。
可以算出
中的元素个数
这样我们就可以把元问题归结为离散型线性优化问题：
为了求出这个模型的解，我们首先给出一个定理
定理：
已知
=常数
若
（
）
则
证明：
当
时，不妨设
则
，于是
命题成立。
当
时，
不妨设
则有以下三种情况：
首先对第一种情况进行证明：
有
则
同理：
对于
（2）和（3）的情况命题也成立。
如此类推，可以得出定理的结论。
由此定理，我们得到该模型圆满解答：
每次都沿着“单位体积切割费用最小”的截面进行切割，其切割的总费用最省。
（单位体积切割费用是指截断某一部分所花的费用与该部分体积的比值）。
即按单位体积切割费用大小的先后次序进行切割，为最佳切割方式。
我们可以根据上述结论找到e=0时费用最小的所有最优切割方案。
（二）模型二：
等效变换模型
1、问题分析与记号
在该问题中，难点主要有三个：
1）每次切割面积的变化。
2）切割单位面积费用比例系数r。
3）调整纵向刀具的额外费用e。
下面我们逐个分析这三个难点并给出适当的表示方法。
分析难点
（1）：
每次切割面积的变化。
规定成品的前面、右面、后面、左面、下面、上面分别用代号1、2、3、4、5、6表示。
如右图所示：
大长方体是待加工体，三块阴影是小长方体在大长方体面上的投影。
为便于观察把小长方体取出放在下方，周围的数字是代号，代表各个面。
A0、A1、A2、B0、B1、B2、C0、C1、C2是阴影投影到棱上把棱长分成三段的长度。
C1、A1、B1是小长方体的长、宽、高。
C0、A2、B0是二者左侧面、正面、底面之间的距离。
每切割一面，应抛弃的那一块的厚度变为零（厚度是指该块垂直切割面的棱的长度）。
切割面积记为D。
于是有如下法则：
当沿代号为1的面切割：
令A2=0,D=（C0+C1+C2）（B0+B1+B2）；
当沿代号为2的面切割：
令C2=0,D=（A0+A1+A2）（B0+B1+B2）；
当沿代号为3的面切割：
令A0=0,D=（C0+C1+C2）（B0+B1+B2）；
（2-1）
当沿代号为4的面切割：
令C0=0,D=（A0+A1+A2）（B0+B1+B2）；
当沿代号为5的面切割：
令B0=0,D=（C0+C1+C2）（A0+A1+A2）；
当沿代号为6的面切割：
令B2=0,D=（C0+C1+C2）（A0+A1+A2）；
记向量W=（W1,W2,W3,W4,W5,W6）（Wi=1，2，3，4，5，6且Wi两两不等），W表示按W1,W2,W3,W4,W5,W6顺序切割的一种方式。
如（2，1，4，6，5，3）表示按2,1,4,6,5,3顺序进行切割的一种方式。
记U={W=
}。
＝
=6!
=720。
分析难点
（2）：
切割单位面积费用比例系数r。
当水平切割单位面积的费用是垂直切割单位面积的费用的r倍。
以水平面为基准，而把高化为原来的1/r倍。
这样所得到的新的长方体垂直切割与水平切割的单位面积费用相等。
分析难点（3）：
调整纵向刀具的额外费用。
因为水平切割调整刀具对额外费用没有影响，即Wi=5或6时对调整刀具没影响。
所以把向量W=（W1,W2,W3,W4,W5,W6）中的5和6剔除，把余下四个数按偶数为1奇数为0重新赋值后构成一新向量X=Ｐ（W1,W2,W3,W4,,W5,W6）=（X1,X2,X3,X4）。
显然当奇到偶或偶到奇时需付费用e一次。
举遍X有六种情况，定义：
当X=（0,0,1,1）或X=（1,1,0,0）时需付额外费用e
当X=（0,1,1,0）或X=（1,0,0,1）时需付额外费用2e
当X=（1,0,1,0）或X=（0,1,0,1）时需付额外费用3e
2、建模与求解
1.等效变换优化模型
由上述分析，问题可归结为下面的优化模型：
下面我们给出该模型求解算法和步骤，并编写出程序。
2.等效变换优化模型的求解算法
步骤一：
给A0,A1,A2,B0,B1,B2,C0,C1,C2赋值，并做高的等效变换，例B0=B0/r。
步骤二：
若Ｕ非空，从集合U中取一个元素W=（W1,W2,W3,W4,W5,W6），Ｕ＝Ｕ－｛Ｗ｝；
否则，转步骤八。
步骤三：
若Wi=J,则执行法则（2-1）。
步骤四：
若Wi<
5,则根据其奇偶性依次对向量X=（X
（1）,X
（2）,X（3）,X（4））的分量进行赋0
或1值。
步骤五：
求g（X）值。
步骤六：
如果T=
〈TT（事先把TT定为很大的数便于第一次判断），然后把TT=T.并把T和W1,W2,W3,W4,W5,W6记入QQ,S等数组。
步骤七：
返回步骤二
步骤八：
用QQ数组与TT比较列出所有最优值的方案。
我们编写了一个实现该算法的QuickBasic程序见附录，输入数据只要运行几秒钟就可得出全部最优切割方案，并得到最省的切割费用。
本程序可以求解所有情况。
当运行程序后输入r,e很快就能输出最优值和所有最优切割方案。
3. 实例验证
现在对原问题第5问中所给的四组数据做出解答。
a）.r=1,e=0
最优值是374元，有两种最优切割方式为W=（5,1,4,6,3,2）和W=（5,1,6,4,3,2）。
其文字表述就是：
一种方式是依次切割：
下面、前面、左面、上面、后面、右面；
另一种方式是依次切割：
下面、前面、上面、左面、后面、右面。
b）.r=1.5,e=0
最优值是437.5元，有两种最优切割方式W=（1,4,5,3,6,2）和W=（1,5,4,3,6,2）。
文字表述就是：
前面、左面、下面、后面、上面、右面；
前面、下面、左面、后面、上面、右面。
c）.r=8,e=0
最优值是540.5元，有一种最优的切割方式W=（1,4,3,5,2,6）
文字表述就是：
依次切割：
前面、左面、后面、下面、右面、上面。
从以上的最优切割方案中可以看出：
当e=0时，每次都选取待截断部分的“单位体积切割费用最小”的面进行切割，则切割总费用最省。
正好与前面的结论相吻合。
d）.r=1.5,
设ｅ０<
ｅｒ，若ｅ０，ｅｒ对应的最优切割方案相同，则调刀费用e为ｅ０和ｅｒ之间的任何一个值时，一定会有与其相同的最优方案。
应用计算机模拟，得到如下结论：
（1）ｅ〈2.5时，最优值=437.5+3e，最优方案有两种：
1）W=（1,4,5,3,6,2），即依次切割：
前、左、下、后、上、右面；
2）W=（1,5,4,3,6,2），即依次切割：
前、下、左、后、上、右面。
从而可以看出最优方案调整了三次纵向刀具。
（2）ｅ=2.5时，最优值=437.5+3e，最优方案有三种：
W=（1,4,5,3,6,2）或W=（1,5,4,3,6,2）或W=（1,5,3,4,6,2）。
即依次切割：
或依次切割：
前、下、左、后、上、右面；
前、下、后、左、上、右面。
三种最优方案中调整纵向刀具的次数分别为3，3，1。
（3）ｅ〉2.5时，最优值=442.5+e，最优方案为W=（1,5,3,4,6,2），即依次切割：
最优方案中调整了一次纵向刀具。
从以上结论可以看出，调整刀具的费用e的大小，直接影响最优方案和刀具的调整次数；
并且e有临界值（本例e=2.5）。
（三）动态规划模型
面的代号与模型二相同。
我们“截断切割”的加工方式实际上是一个多阶段决策，属于动态规划问题。
根据原题知“截断切割”的方式共有
种。
用穷举的方法当然可以解决这个问题，不难算出每一种加工方式的费用，进行比较就可以找出最省钱的加工方式。
但这样工作量太大，在实际中是不可取的。
用动态规划解决问题的思路与方法来解决该问题会使计算量远远小于穷举法。
并很快找到最佳的加工方式。
具体实施方案如下：
我们把切割过程分为6个阶段，第一阶段从原长方体切割一个面，.......第k阶段把第
k-1阶段切割后的长方体再切割一个面，第六阶段把第五阶段切割后的长方体切割成品，完成加工任务。
用s=
表示某个阶段长方体，当
0时，
面未切割；
=0时，
面已切割。
其中
为状态变量，
是面的标号。
如s={1，2，0，4，0，0}表示标号为1，2，4的三个面未切割。
加工成品的长方体为
{0，0，0，0，0，0}。
为了方便，原长方体s={1,2,3,4,5,6}叫做第0状态。
不难算出，长方体在加工中共有
=64种状态。
用
表示第k阶段的状态s（长方体）转变（切割i面）成第k+1阶段的状态s-{i}的费用（包括调刀费用），即
用
表示切割i面的切割费用，用
表示第k阶段对s的决策，即从s切割成s-{i},则
.设第k阶段从s切割成品
={0,0,0,0,0,0}的最小费用函数记为
为了方便我们记
则有一般的递推公式：
这样原问题就归结成了一个动态优化模型。
事实上，若我们把每个状态s看成点，用一条线连接有切割关系的两个点，把切割费用看成两点间的距离，把调刀费用看成越过障碍的费用，于是这一问题又转化为“有障碍的最短路问题”。
动态优化模型已有成熟的算法和计算机程序[5]。
由于时间限制，我们不再作进一步讨论。
五、对生产部门使用准则的评价
该部门以每次选择一个加工费用最小的待切割面为准则进行切割，这种方法看起来似乎很合理，但实际上是不能达到使总费用最小的目的。
它虽然使每次切割的费用最小，但总切割费用不一定达到最小。
最优切割方式的准则应该为：
每次选择单位体积切割费用最小的截面进行切割；
特别，当r=1,e=0时，每次选择厚度最大的截面进行切割。
现应用这两种不同的准则以题目中给出的5）a为例找出两种不同的切割方法，并算出这两种方法的总费用M。
（具体细节见表4）
原准则下最小的费用为：
392元
新准则下的最小费用为：
374元
可以看出新准则下的切割费用小于原生产部门所使用准则的切割费用。
我们用题目给出的四组数据验证模型：
模型一只能解决e=0的情况（计算结果见附录一表2至表4），模型二能够解决任意情况（计算结果见模型二）。
六、模型的结果分析与模型的评价
模型的应用价值是评价一个模型好坏的重要依据。
我们的结论正好符合实际生产过程中切割加工时的经验：
就是找较厚的表面进行加工（这实际上就是模型中r=1，e=0时的最优方式）。
至于其它的情况（如
），由于影响费用的因素增加，情况变的复杂，因此一般得不到较直观的经验操作，需要进行数学计算找到最优的加工次序。
我们的模型可以应用于此，且利用模型二的应用程序可以迅速准确地找到总费用最小的加工次序。
根据模型最后得出的结果分析其合理性。
在水平切割单位面积费用比单位面积费用大得很多时（即r较大时，例如r=8），应尽可能把水平切割放在最后进行，这实际上就是问题中要求5）的答案；
当e比较小时，即换因调整刀具（下面均简称为调刀）需要的额外费用比较小时，可以不考虑这部分费用，只需考虑单位体积切割费大小顺序，此时调刀的次数可能比较多；
当e比较大时，即调刀需要的额外费用较大，应采用调刀次数为1的加工方式,如果e介于两者之间，最小费用的加工方式可能出现的调刀次数为1、2、3中之一，在我们的求解中相当于找出了e的临界值。
一般规律是，如果e较小时，换刀次数可以多；
当e较大时，换刀的次数应为1。
这与我们得出的结论是完全一致的。
我们建立的三个模型各有特点，能够相互验证，对于
的情形，模型得出的结论完全一样。
对于
0的情形，模型二更具一般性，有广泛的推广价值，应用计算机求解准确迅速。
模型一可以得到比较直观的准则，易于在实际生产中应用。
七、模型的改进与推广
（1）由于题目的要求，我们所建的模型仅考虑了总费用与切割的方式（水平切割还是垂直）、切割的面积有关。
在实际工作中，总费用还与其它各种因素（例如加工的时间、是顺纹路还是逆纹路加工、工件的重要性、工件表面要求的粗糙程度等）有关，如果在我们所建模型的基础上，再把各种的因素都考虑进去，找到一种总费用最小的方案，这种方案会更符合实际。
（2）动态规划模型需要编出更好的计算机程序。
参考文献
[1]寿纪麟，数学建模—方法与范例，西安交通大学出版社，1993。
[2]钱颂迪等，运筹学（修订版），清华大学出版社，1990。
[3]1992-1995年全国大学生数学建模竞赛优秀论文汇编，全国竞赛组委会，1997.3。
[4]潘正伯等，QuickBASIC结构化程序设计教程，科学出版社，1996。
[5]袁忠良，运筹学应用程序集，清华大学出版社，1989。
附录一：
具体计算：
单位：
费用（元）
面积（cm
）
表1
某部门以每次选择一个加工费用最少的待切割面进行切割为准则，情况a下的切割方法即费用如下：
步骤
第一步
第二步
第三步
第四步
第五步
第六步
切割方法
沿下底面
沿正面
沿上底面
沿右侧面
沿左侧面
沿反面
切割面积
145
100
75
30
12
切割费用
16
8
切割总面积
392
切割总费用
表2
当情况a.r=1,e=0;
第一步
第二步
第三步
第四步
第五步
第六步
沿正面
沿反面
145
100
75
30
16
8
374
表3
当情况b.r=1.5,e=0;
沿上面
190
142.5
40
30×
1.5
8×
418.5
437.5
表4
当情况c.r=8,e=0;
76
20
6
6×
442.5
540.5
附录二：
模型二运用计算机求解的程序清单：
CLS
DIMX（4）
DIMQQ（720）,S1（720）,S2（720）,S3（720）,S4（720）,S5（720）,S6（720）
TT=9999999
INPUT"
R="
;
MR
E="
ME
READMCC,MAA,MBB,MC1,MA1,MB1,MC0,MA2,MB0
DATA10,14.5,19,3,2,4,6,7,9
MA0=MAA-MA1-MA2
MB2=MBB-MB0-MB1
MC2=MCC-MC0-MC1
MB0=MB0/MR
MB1=MB1/MR
MB2=MB2/MR
J=0
FORW1=1TO6
FORW2=1TO6
FORW3=1TO6
FORW4=1TO6
FORW5=1TO6
FORW6=1TO6
IFW1=W2ORW1=W3ORW1=W4ORW1=W5ORW1=W6THEN100
IFW2=W3ORW2=W4ORW2=W5ORW2=W6THEN100
IFW3=W4ORW3=W5ORW3=W6THEN100
IFW4=W5ORW4=W6ORW5=W6THEN100
T=0:
SS=0
A0=MA0:
A1=MA1:
A2=MA2
B0=MB0:
B1=MB1:
B2=MB2
C0=MC0:
C1=MC1:
C2=MC2
R=MR:
E=ME:
D=0
I=1
ONW1GOSUB1,2,3,4,5,6
T=D
IFW1<
5THENGOSUB10
ONW2GOSUB1,2,3,4,5,6
T=T+D
IFW2<
5THENGOSUB20
ONW3GOSUB1,2,3,4,5,6
T=T+D
IFW3<
5THENGOSUB30
ONW4GOSUB1,2,3,4,5,6
IFW4<
5THENGOSUB40
ONW5GOSUB1,2,3,4,5,6
IFW5<
5THENGOSUB50
ONW6GOSUB1,2,3,4,5,6
IFW6<
5THENGOSUB60
IFX
（1）=1ANDX
（2）=1ANDX（3）=0ANDX（4）=0THENT=T*R+E
IFX
（1）=0ANDX
（2）=0ANDX（3）=1ANDX（4）=1THENT=T*R+E
IFX
（1）=1ANDX
（2）=0ANDX（3）=0ANDX（4）=1THENT=T*R+2*E
IFX
（1）=0ANDX
（2）=1ANDX（3）=1ANDX（4）=0THENT=T*R+2*E
IFX
（1）=1ANDX
（2）=0ANDX（3）=1ANDX（4）=0THENT=T*R+3*E
IFX
（1）=0ANDX
（2）=1ANDX（3）=0ANDX（4）=1THENT=T*R+3*E
IFT<
TTTHENTT=T:
M1=W1:
M2=W2:
M3=W3:
M4=W4:
M5=W5:
M6=W6
J=J+1
QQ（J）=T:
S1（J）=W1:
S2（J）=W2:
S3（J）=W3
S4（J）=W4:
S5（J）=W5:
S6（J）=W6
100NEXTW6
NEXTW5
NEXTW4
NEXTW3
NEXTW2
NEXTW1
FORJ=1TO720
IFTT=QQ（J）THENPRINTQQ（J）;
S1（J）;
S2（J）;
S3（J）;
S4（J）;
S5（J）;
S6（J）
NEXTJ
END
1:
A2=0:
D=（C0+C1+C2）*（B0+B1+B2）:
RETURN
2:
C2=0:
D=（A0+A1+A2）*（B0+B1+B2）:
3:
A
升级会员 