2021年数学建模经典案例最优截断切割问题.docx

*欧阳光明*创编2021.03.07
*欧阳光明*创编2021.03.07
*欧阳光明*创编
建模案例：最优截断切割问题
2021.03.07
*欧阳光明*创编2021.03.07
*欧阳光明*创编2021.03.07
欧阳光明（2021.03.07）
一、问题
从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的对应表面是平行的），通常要经过6次截断切割.设水平切割单位面积的费用是垂直切割单位面积费用的r倍.且当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，因调整***需额外费用e・试设计一种安排各面加工次序（称“切割方式”）的方法，使加工费用最少.
二、假设
1、假设水平切割单位面积的费用为r,垂直切割单位面积费用为1；
2、当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，调整***需额外费用e；
3、第一次切割前，***已经调整完毕，即第一次垂直切割不加入***调整费用；
4、每个待加工长方体都必须经过6次截断切割・
三、模型的建立与求解
设待加工长方体的左右面、前后面、上下面间的距离分别为a0、
b0、c0,六个切割面分别位于左、右、前、后、上、下，将它们相应编号为M1、M2、M3、M4、M5、M6,这六个面与待加工长方体相应外侧面的边距分别为u1、u2、u3、u4、u5、u6•这样，一种切割方式就是六个切割面的一个排列，共有P6=720种切割方式•当考虑到切割费用时，显然有局部优化准则：两个6平行待切割面中，边距较大的待切割面总是先加工・
P6
由此准则，只需考虑2!x2!x2!=90种切割方式•即在求最少加工费用
u5_
M5
M3
cO
M4
aO
tu3
MIX
ZM6
u5
U4
*欧阳光明*创编2021.03.07
*欧阳光明*创编2021.03.07
01g
时，只需在90个满足准则的切割序列中考虑•不失一般性，设u1>u2,u3>u4,u5>u6,故只考虑M1在M2前、M3在M4前、M5在M6前的切割方式.
1、e=0的情况
为简单起见,先考虑e=0的情况•构造如图9-13的一个有向赋权网络图G(V,E)•为了表示切割过程的有向性，在网络图上加上坐标轴x，yz.
图9-13G(V,E)
图G(V,E)的含义为：
(1)空间网络图中每个结点Vi(瑰嗚②表示被切割石材所处的一个状态•顶点坐标xi^yi^zi分另M弋表石材在左右、前后、上下方向上已被切割的刀数.例如：V24(2,1,2)表示石材在左右方向上已被切割两刀，前后方向上已被切一刀，上下方向上已被切两刀，即面
M1、M2、M3、M5、M6均已被切割•顶点V1(0,0,0)表示石材的最初待加工状态，顶点V27(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)x(bixci)+(yj-yi)x(aixc