建模案例:最优截断切割问题 问题 从一个长方体中加工出一个已知尺寸、位置预定的长方体(这两个长方体的 对应表面是平行的),通常要经过6次截断切割设水平切割单位面积的费用是 垂直切割单位面积费用的r倍且当先后两次垂直切割的平面(不管它们之间是 否穿插水平切割)不平行时,因调整刀具需额外费用e试设计一种安排各面加 工次序(称“切割方式”)的方法,使加工费用最少 二、假设 1、假设水平切割单位面积的费用为r,垂直切割单位面积费用为1; 2、当先后两次垂直切割的平面(不管它们之间是否穿插水平切割)不平行时, 调整刀具需额外费用e; 3、第一次切割前,刀具已经调整完毕,即第一次垂直切割不加入刀具调整费 用 4、每个待加工长方体都必须经过6次截断切割 三、模型的建立与求解 设待加工长方体的左右面、前后面、上下面间的距离分别为m0、b0、c0, 六个切割面分别位于左、右、前、后、上、下,将它们相应编号为M1、M2、 M3、M4、M5、M6,这六个面与待加工长方体相应外侧面的边距分别为ul u2、u3、l4、l5、6这样,一种切割方式就是六个切割面的一个排列,共有P=720 种切割方式当考虑到切割费用时,显然有局部优化准则:两个平行待切割面中 边距较大的待切割面总是先加工 由此准则只需考虑 2!22/90种切割方式即在求最少加工费用时, M5 M4 M6 只需在90个满足准则的切割序列中考虑不失一般性,设ul≥m2,3≥4,u5≥ u6,故只考虑M在M前、M3在M4前、M5在M6前的切割方式 1、e-0的情况
建模案例：最优截断切割问题 一、 问 题 从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的 对应表面是平行的），通常要经过 6 次截断切割.设水平切割单位面积的费用是 垂直切割单位面积费用的 r 倍.且当先后两次垂直切割的平面（不管它们之间是 否穿插水平切割）不平行时，因调整刀具需额外费用 e.试设计一种安排各面加 工次序（称“切割方式”）的方法，使加工费用最少. 二、 假 设 １、假设水平切割单位面积的费用为 r，垂直切割单位面积费用为 1； ２、当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时， 调整刀具需额外费用 e； ３、第一次切割前，刀具已经调整完毕，即第一次垂直切割不加入刀具调整费 用； 4 、每个待加工长方体都必须经过 6 次截断切割. 三、 模型的建立与求解 设待加工长方体的左右面、前后面、上下面间的距离分别为 a0、b0 、c0 ， 六个切割面分别位于左、右、前、后、上、下，将它们相应编号为M1、M2、 M3、M4、M5、M6，这六个面与待加工长方体相应外侧面的边距分别为 u1、 u2、u3、u4、u5、u6.这样，一种切割方式就是六个切割面的一个排列，共有 P6 6 = 720 种切割方式.当考虑到切割费用时，显然有局部优化准则：两个平行待切割面中， 边距较大的待切割面总是先加工. 由此准则,只需考虑 P6 6 2 2 2 90 ! ! ! = 种切割方式.即在求最少加工费用时， 只需在90个满足准则的切割序列中考虑.不失一般性，设u1≥u2，u3≥u4，u5≥ u6，故只考虑M1在M2前、M3在M4前、M5在M6前的切割方式. 1、 e=0 的情况
为简单起见先考虑e=0的情况构造如图913的一个有向赋权网络图G(V,E 为了表示切割过程的有向性,在网络图上加上坐标轴x,y,z 图9-13G(VE) 图G(V,E)的含义为 (1)空间网络图中每个结点 vi(ri,yi,功表示被切割石材所处的一个状态顶点 坐标κiy分别代表石材在左右、前后、上下方向上已被切割的刀数例如: V24(2,1,2)表示石材在左右方向上已被切割两刀,前后方向上已被切一刀,上下 方向上已被切两刀,即面M、M、M3、M5、M6均已被切割顶点v1(0,0,0)表 示石材的最初待加工状态,顶点V27(2,2,2)表示石材加工完成后的状态 (2)G的弧(vj)表示石材被切割的一个过程,若长方体能从状态V经一 次切割变为状态Vj,即当且仅当xi+t+i+l=xy+y+时,Ⅴ i(xi, yi,zi)到vj(xyi) 有弧(vj),相应弧上的权Wv即为这一切割过程的费用 H,功=(xixx(6xc)+y-y× ( CI)+(-动) x(aix bier 其中,m、bic汾别代表在状态V时,长方体的左右面、上下面、前后面 之间的距离 例如,状态V5(1,1,0),a5=a0wl,b5=b043,c5=c0状态6(2,1,0) w(5,v6 b0-u3)×c0 63)根据准则知第一刀有三种选择,即第一刀应切M、M3、M5中的某个 面,在图中分别对应的弧为(V1,V2),(v1,V4),(V1,v10).图G中从V到V27的 任意一条有向道路代表一种切割方式从Ⅵ到v27共有90条有向道路,对应着所 考虑的90种切割方式到V27的最短路即为最少加工费用,该有向道路即对应 所求的最优切割方式 实例:待加工长方体和成品长方体的长、宽、高分别为10、145、19和3、2 两者左侧面、正面、底面之间的距离分别为6、7、9,则边距如下表 u1 3 14 u5 9 r=1时,求得最短路为Ⅴ1-V10—V13-V22-V23-V26-V27,其权为374 对应的最优切割排列为M5-M3-M6-M1-M4-M2,费用为374元 2、e≠0的情况
为简单起见,先考虑e=0 的情况.构造如图9-13的一个有向赋权网络图G(V,E). 为了表示切割过程的有向性，在网络图上加上坐标轴x，y，z. 图 9-13 G(V,E) 图G(V,E)的含义为： (1)空间网络图中每个结点Vi(xi,yi,zi)表示被切割石材所处的一个状态.顶点 坐标xi、yi、zi分别代表石材在左右、前后、上下方向上已被切割的刀数.例如： 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-xi) (bi ci)+(yj-yi) (ai ci)+(zj-zi) (ai bi) 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条有向道路，对应着所 考虑的90种切割方式.V1到V27的最短路即为最少加工费用，该有向道路即对应 所求的最优切割方式. 实例：待加工长方体和成品长方体的长、宽、高分别为10、145、19 和3、2、 4，两者左侧面、正面、底面之间的距离分别为6、7、9，则边距如下表： u1 u2 u3 u4 u5 u6 6 1 7 55 6 9 r=1时，求得最短路为V1－V10－V13－V22－V23－V26－V27，其权为374 对应的最优切割排列为M5－M3－M6－M1－M4－M2，费用为374元. 2、 e 0的情况
当e≠0时,即当先后两次垂直切割的平面不平行时,需加调刀费e希望在图 9-13的网络图中某些边增加权来实现此费用增加在所有切割序列中,四个垂直面 的切割顺序只有三种可能情况: 先切一对平行面,再切另外一对平行面,总费用比e-0时的费用增 加e 先切一个,再切一对平行面,最后割剩余的一个,总费用比e0时 的费用增加2e 切割面是两两相互垂直,总费用比e=0时的费用增加3e. 在所考虑的90种切割序列中,上述三种情况下垂直切割面的排列情形,及在 图G中对应有向路的必经点如下表 垂直切割面排列情有向路必经点 形 情况一 M1—M2一M3-M4(1.0.2)20,z)21,z) 「情况一(二)M3-M4-M-M210,(0,.14,2 情况三(-)|M3-M-M-M4(0,1,,(1,1,21,z) 情况三(二)M-M3-M4-M2|(1,0,z)(1,1,z)(,2,z) 情况三(-)M-M3-M2-M4(1,0z)(1,1,)(21z) 情况三(二)M3-M1-M4-M2(0,1,2)(1,1,(,2z) z=0,1,2 M3-M4-M1-M2M1-M3-M4-M2“M3-M1-M4-M2 Y M1M2-M3-M4 M1-M3-M2-M X 我们希望通过在图9-13的网络图中的某些边上增加权来进行调刀费用增加 的计算,但由于网络图中的某些边是多种切割序列所公用的对于某一种切割序 列,需要在此边上增加权e,但对于另外一种切割序列,就有可能不需要在此边 上增加权e,这样我们就不能直接利用图913的网络图进行边加权这种方法来求 出最短路径 由上表可以看出,三种情况的情形(一)有公共点集(2,,)z=0,1,2},情形 (二)有公共点集(1,2,x)z=0,1,2}.且情形(一)的有向路决不通过情形(二)的
当e 0时，即当先后两次垂直切割的平面不平行时，需加调刀费e.希望在图 9-13的网络图中某些边增加权来实现此费用增加.在所有切割序列中，四个垂直面 的切割顺序只有三种可能情况： 先切一对平行面，再切另外一对平行面，总费用比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－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),(1,1,z),(2,1,z) 情况三 （二） M3－M1－M4－M2 (0,1,z),(1,1,z),(1,2,z) z=0,1,2 我们希望通过在图9-13的网络图中的某些边上增加权来进行调刀费用增加 的计算，但由于网络图中的某些边是多种切割序列所公用的.对于某一种切割序 列，需要在此边上增加权e，但对于另外一种切割序列， 就有可能不需要在此边 上增加权e，这样我们就不能直接利用图9-13的网络图进行边加权这种方法来求 出最短路径. 由上表可以看出，三种情况的情形（一）有公共点集{(2,1,z)|z=0,1,2}，情形 （二）有公共点集{(1,2,z)|z=0,1,2}.且情形（一）的有向路决不通过情形（二）的
公共点集,情形(二)的有向路也不通过情形(一)的公共点集所以可判断出 这两部分是独立的、互补的如果我们在图G中分别去掉点集{(1,2,以=0,1,2}和 (2,1,)z=0,1,2}及与之相关联的入弧,就形成两个新的网络图,如图H1和H2 这两个网络图具有互补性对于一个问题来说,最短路线必存在于它们中的某 个中. 由于调整垂直刀具为3次时,总费用需增加3e,故我们先安排这种情况的权 增加值e,每次转刀时,给其待切弧上的权增加e增加e的情况如图9-14中所示再 来判断是否满足调整垂直刀具为二次、一次时的情况,我们发现所增加的权满足 另外两类切割序列 综合上述分析,我们将原网络图G分解为两个网络图H1和H2,并在指定边 上的权增加e,然后分别求出图H1和H2中从Ⅵl到v27的最短路,最短路的权分 别为:dl,d2则得出整体的最少费用为:d=min(d1,d2),最优切割序列即为其 对应的最短路径 实例:r=15,∈-2时,求得图G与G2的最短路为G2的路ⅤI-Ⅴ4-V5-V14 V17-V26-V27,权为4435,对应的最优切割序列为M-MI-M6-M4-M5 M2,最优费用为4435. u18 图9-14H1 图9-15H2
公共点集，情形（二）的有向路也不通过情形（一）的公共点集.所以可判断出 这两部分是独立的、互补的.如果我们在图G中分别去掉点集{(1,2,z)|z=0,1,2}和 {(2,1,z)|z=0,1,2}及与之相关联的入弧，就形成两个新的网络图，如图Ｈ1和Ｈ2. 这两个网络图具有互补性.对于一个问题来说，最短路线必存在于它们中的某一 个中. 由于调整垂直刀具为3次时，总费用需增加3e， 故我们先安排这种情况的权 增加值e，每次转刀时，给其待切弧上的权增加e.增加e的情况如图9-14中所示.再 来判断是否满足调整垂直刀具为二次、一次时的情况，我们发现所增加的权满足 另外两类切割序列. 综合上述分析，我们将原网络图G分解为两个网络图Ｈ1和Ｈ2，并在指定边 上的权增加e，然后分别求出图Ｈ1和Ｈ2中从V1到V27的最短路，最短路的权分 别为：d1,d2.则得出整体的最少费用为：d = min(d1,d2) ，最优切割序列即为其 对应的最短路径. 实例：r=15,e=2时，求得图G1与G2的最短路为G2的路V1－V4－V5－V14－ V17－V26－V27，权为4435，对应的最优切割序列为M3－M1－M6－M4－M5 －M2，最优费用为4435. 图 9-14 H1 图 9-15 H2
