建模案例讲解PPT.pptVIP

从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的对应表面是平行的），通常要经过6 次截断切割.设水平切割单位面积的费用是垂直切割单位面积费用的r倍.且当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，因调整刀具需额外费用e.试设计一种安排各面加工次序（称“切割方式”）的方法，使加工费用最少 4．每个待加工长方体都必须经过6次截断切割. １．假设水平切割单位面积的费用为r，垂直切割单位面积费用为1； ２．当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，调整刀具需额外费用e； ３．第一次切割前，刀具已经调整完毕，即第一次垂直切割不加入刀具调整费用； 设待加工长方体的左右面、前后面、上下面间的距离分别为a0 、b0 、c0 ，六个切割面分别位于左、右、前、后、上、下，将他们相应编号为M1、M2、M3、M4、M5、M6，这六个面与待加工长方体相应外侧面的边距分别为 u1、u2、u3、u4、u5、u6.这样，一种切割方式就是六个切割面的一个排列，共有 种切割方式.当考虑到切割费用时，显然有局部优化准则：两个平行待切割面中，边距较大的待切割面总是先加工. 由此准则,只需考虑 种切割方式.即在求最少加工费用时，只需在90个满足准则的切割序列中考虑. 不失一般性，设u1≥u2，u3≥u4，u5≥u6，故只考虑M1在M2前、M3在M4前、M5在M6前的切割方式. 为简单起见,先考虑e=0 的情况.构造如图的一个有向赋权网络图G(V,E).为了表示切割过程的有向性，在网络图上加上坐标轴 x，y，z，图G(V,E)的含义为： (1)空间网络图中每个结点Vi(xi,yi,zi)表示被切割石材所处的一个状态.顶点坐标xi、yi、zi分别代表石材在左右、前后、上下方向上已被切割的刀数. (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)即为这一切割过程的费用为： 且W(Vi,Vj)=(xj-xi)×(bi×ci)+(yj-yi)×(ai×ci) +(zj-zi)×(ai×bi)×r 其中，ai、bi、ci分别代表在状态Vi时，长方体的左右面、上下面、前后面之间的距离. (3)根据准则知第一刀有三种选择， 即第一刀应切M1、M3、M5中的某个面，在图中分别对应的弧为( V1,V2)，(V1,V4)，(V1,V10). 图G中从V1到V27的任意一条有向道路代表一种切割方式.从V1到V27共有90条有向道路，对应着所考虑的90种切割方式.V1到V27的最短路即为最少加工费用，该有向道路即对应所求的最优切割方式. ∣ ∣ ∣ 实例：待加工长方体和成品长方体的长、宽、高分别为10、14.5、19和3、2、4，两者左侧面、前面、下面之间的距离分别为6、7、9，r＝1，则边距如下表： u1 u1 u3 u4 u5 u6 6 1 7 5.5 6 9 在r=1时，求符合条件的最优切割方案，及此时的最少费用。 选择第一步路径： W（V1,V2）=14.5×19 W（V1,V4）=10×19 W（V1,V10）=10×14.5 故第一步选择V1－V10 r=1时，求得最短路为： V1－V10－V13－V22－V23－V26－V27，其权为374 对应的最优切割排列为： M6－M3－M5－M1－M4－M2，费用为374元. 2． e≠ 0的情况 当e ≠ 0时，即当先后两次垂直切割的平面不平行时，需加调刀费e.希望在图1的网络图中某些边增加权来实现此费用增加.在所有切割序列中，四个垂直面的切割顺序只有三种可能情况： 情况三切割面是两两相互垂直，总费用比e=0时的费用增加3e. 情况二先切一个，再切一对平行面，最后割剩余的一个，总费用比e=0时的费用增加2e. 情况一先切一对平行面，再切另外一对平行面，总费用比e=0时的费用增加e. 垂直切割面排列情形 有向路必经点 情况一 （一） M1－M2－M3－M4 (1,0,z),(2,0,z),(2,1,z) 情况一 （二） M3－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) 情况三 （一） M1－M3－M2－M4 (1,0,z),(