最优截断切割问题.docx

最优截断切割问题.docx:..建模案例:最优截断切割问题一、 问题从一个长方体中加工出一个已知尺寸、位置预定的长方体(这两个长方体的对应表面是平行的),通常要经过6次截断切割•设水平切割单位面积的费用是垂直切割单位面积费用的r倍•且当先后两次垂直切割的平面(不管它们之间是否穿插水平切割)不平行时,因调整***需额外费用e•试设计一种安排各面加工次序(称“切割方式”)的方法,、假设1、假设水平切割单位面积的费用为「垂直切割单位面积费用为1;2、当先后两次垂直切割的平面(不管它们之间是否穿插水平切割)不平行时,调整***需额外费用e;第一次切割前,***已经调整完毕,即第一次垂直切割不加入***调整费用;4、、模型的建立与求解设待加工长方体的左右面、前后面、、右、前、后、上、下,将它们相应编号为Ml、M2、M3、M4、M5、M6,>u3>u4>u5>,一种切割方式就是六个切割面的一个排列,共有用=720种切割方式•当考虑到切割费用时,显然有局部优化准则:两个平行待切割面中,,只需考虑2!x2!x2!6 =90种切割方式•即在求最少加工费用时,只需在90个满足准则的切割序列中考虑•不失一般性,设u]却,u3^u4,u5^u6,故只考虑Ml在M2前、M3在M4前、=0的情况为简单起见,先考虑e=0的情况胸造如图9・13的一个有向赋权网络图G(V,E)・为了表示切割过程的有向性,在网络图上加上坐标轴x,y,-13G(V,E)图G(V,E)的含义为:⑴空间网络图中每个结点VifxwzO表示被切割石材所处的一个状态•、前后、上下方向上已被切割的刀数•例如:V24(2,l,2)表示石材在左右方向上已被切割两刀,前后方向上已被切一刀,上下方向上已被切两刀,即面Ml、M2、M3、M5、M6均已被切割•顶点Vl(0,0,0)表示石材的最初待加工状态,顶点V27(2,2,2)表示石材加工完成后的状态.⑵G的弧(Vi,Vj)表示石材被切割的一个过程,若长方体能从状态Vi经一次切割变为状态Vj,即当且仅当W+W+N+7呵+刀+力时,Vi(xi,yi,zi倒Vj(xj,yj/j)有弧(Vi,Vj),相应弧上的权W(Vi,Vj)(Vi9Vj)=(xj-xi)x(bixci)+(yj-yi)x(aixci)+(^j-zi)x(aixbi)xr其中,,长方体的左右面、上下面、,状态V5(1,1,0),a5=aOHil,b5=b0-u3,c5=cO;状态V6(2,1,0)W(V5,V6)=(b0・u3)xc0(3)根据准则知第一刀有三种选择,、M5中的某个面,在图中分别对应的弧为(V1,V2),(V1,V4),(V1,V1O)・图G中从VI到V27的任意一条有向道路代表一种切割方式•从VI到V27共有90条有向道路,对应着所考虑的90