资源描述:
《matlab-最优截断切割问题》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、建模案例:最优截断切割问题一、问题从一个长方体中加工出一个已知尺寸、位置预定的长方体(这两个长方体的对应表面是平行的),通常要经过6次截断切割.设水平切割单位面积的费用是垂直切割单位面积费用的r倍.且当先后两次垂直切割的平面(不管它们之间是否穿插水平切割)不平行时,因调整刀具需额外费用e.试设计一种安排各面加工次序(称“切割方式”)的方法,使加工费用最少.二、假设1、假设水平切割单位面积的费用为r,垂直切割单位面积费用为1;2、当先后两次垂直切割的平面(不管它们之间是否穿插水平切割)不平行时,调整刀具需额外费用e;3、第一次切割前,
2、刀具已经调整完毕,即第一次垂直切割不加入刀具调整费用;4、每个待加工长方体都必须经过6次截断切割.三、模型的建立与求解设待加工长方体的左右面、前后面、上下面间的距离分别为a0、b0、c0,六个切割面分别位于左、右、前、后、上、下,将它们相应编号为M1、M2、M3、M4、M5、M6,这六个面与待加工长方体相应外侧面的边距分别为u1、u2、u3、u4、u5、u6.这样,一种切割方式就是六个切割面的一个排列,共有种切割方式.当考虑到切割费用时,显然有局部优化准则:两个平行待切割面中,边距较大的待切割面总是先加工.由此准则,只需考虑种切割方
3、式.即在求最少加工费用时,只需在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-13G(V,E)图G(V,E)的含义为:(1)空间网络图中每个结点Vi(xi,yi,zi)表示被切割石材所处的一个状态.顶点坐标xi、yi、zi分别代表石材在左右、前后、上下方向上已被切割的刀数.例如:
4、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-x
5、i)(bici)+(yj-yi)(aici)+(zj-zi)(aibi)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条有向道路,对应着所
6、考虑的90种切割方式.V1到V27的最短路即为最少加工费用,该有向道路即对应所求的最优切割方式.实例:待加工长方体和成品长方体的长、宽、高分别为10、145、19和3、2、4,两者左侧面、正面、底面之间的距离分别为6、7、9,则边距如下表:u1u2u3u4u5u66175569r=1时,求得最短路为V1-V10-V13-V22-V23-V26-V27,其权为374对应的最优切割排列为M5-M3-M6-M1-M4-M2,费用为374元.2、e0的情况当e0时,即当先后两次垂直切割的平面不平行时,需加调刀费e.希望在图9-13的网络图中
7、某些边增加权来实现此费用增加.在所有切割序列中,四个垂直面的切割顺序只有三种可能情况:<情况一>先切一对平行面,再切另外一对平行面,总费用比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
8、-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)情况三(一