2024年5月19日发(作者：沈慧心)

建模案例：最优截断切割问题

一、 问 题

从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的

对应表面是平行的），通常要经过６ 次截断切割．设水平切割单位面积的费用

是垂直切割单位面积费用的r倍。且当先后两次垂直切割的平面（不管它们之

间是否穿插水平切割）不平行时，因调整刀具需额外费用e.试设计一种安排各

面加工次序（称“切割方式”)的方法,使加工费用最少。

二、 假 设

1、假设水平切割单位面积的费用为r,垂直切割单位面积费用为１;

２、当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，

调整刀具需额外费用ｅ；

3、第一次切割前,刀具已经调整完毕，即第一次垂直切割不加入刀具调整费用；

4 、每个待加工长方体都必须经过6次截断切割．

三、 模型的建立与求解

设待加工长方体的左右面、前后面、上下面间的距离分别为

a0、b０ 、c0

，

六个切割面分别位于左、右、前、后、上、下，将它们相应编号为M1、Ｍ2、M3、

M４、M5、M6，这六个面与待加工长方体相应外侧面的边距分别为

u1、ｕ2、u3、

u4、u5、ｕ6

.这样,一种切割方式就是六个切割面的一个排列，共有

P

6

6

720

种

切割方式。当考虑到切割费用时，显然有局部优化准则:两个平行待切割面中，

边距较大的待切割面总是先加工.

P

6

6

90

种切割方式.即在求最少加工费用 由此准则，只需考虑

2!2!2!

时，只需在９0个满足准则的切割序列中考虑．不失一般性,设

u１≥u2,u3≥u４，

u5≥u6

,故只考虑Ｍ1在M2前、M３在M４前、M5在Ｍ６前的切割方式。

1、 ｅ=0 的情况

1 / 5

为简单起见,先考虑e＝0 的情况．构造如图9—１3的一个有向赋权网络图Ｇ

(V，Ｅ）。为了表示切割过程的有向性，在网络图上加上坐标轴x，y，z．

图9—13 G（V,Ｅ)

图G（V，E)的含义为:

（１)空间网络图中每个结点Ｖi

(ｘi，yi,ｚi）

表示被切割石材所处的一

个状态.顶点坐标

xｉ、yi、ｚi

分别代表石材在左右、前后、上下方向上已被切

割的刀数．例如：V24(2，1,2) 表示石材在左右方向上已被切割两刀，前后方向

上已被切一刀,上下方向上已被切两刀，即面Ｍ1、M2、M3、M5、M6均已被切割．顶

点V1（0，0，０） 表示石材的最初待加工状态,顶点V２7（２，２，２）表示石

材加工完成后的状态．

（2)Ｇ的弧(Vi,Vj)表示石材被切割的一个过程，若长方体能从状态Ｖi经

一次切割变为状态Vj,即当且仅当

xｉ+yi+zi＋１=ｘj＋yj+zj

时，Vi（ｘi，yi，

zｉ)到Vj（ｘｊ，yj,zj）有弧（Vｉ，Vj),相应弧上的权

W(Vi，Ｖj）

即为这一

切割过程的费用。

Ｗ(Ｖi,Vj)＝(xj-xi）



（bｉ



ci）+(yj-yi)



（ai



ci)+(zj—zi)



（ａ

i



bi)



r

其中，

aｉ、ｂi、cｉ

分别代表在状态Vｉ时，长方体的左右面、上下面、

前后面之间的距离.

例如，状态Ｖ5(1，1，0）,

a５ = a0-ｕ1,ｂ5 = b0—u3,c5 = c０;

状态V6（２，1，0）

W（V5,V６) ＝（b0－u3）



c0

(3）根据准则知第一刀有三种选择， 即第一刀应切M1、M3、M5中的某

个面,在图中分别对应的弧为( Ｖ１,Ｖ2），（V1,Ｖ4）,(V1,V10). 图Ｇ中从V1

到Ｖ2７的任意一条有向道路代表一种切割方式.从V１到V２7共有9０条有向道

路，对应着所考虑的９0种切割方式．V1到Ｖ27的最短路即为最少加工费用，该

有向道路即对应所求的最优切割方式。

实例：待加工长方体和成品长方体的长、宽、高分别为1０、14５、1９ 和

3、２、４,两者左侧面、正面、底面之间的距离分别为6、7、9，则边距如下表：

u1

u2

u３

u4

u５

u6

6

１

７

55

6

９

2 / 5

r＝1时，求得最短路为V１－Ｖ１０－V13-V22—V２3－V２6—V27，其权为３７4

对应的最优切割排列为Ｍ５－M3－Ｍ6－M1－M４－Ｍ2,费用为37４元．

2、 e



０的情况

当ｅ



0时,即当先后两次垂直切割的平面不平行时，需加调刀费e。希望在

图９－１３的网络图中某些边增加权来实现此费用增加。在所有切割序列中，四

个垂直面的切割顺序只有三种可能情况：

<情况一＞先切一对平行面，再切另外一对平行面，总费用比e＝0时的费用

增加ｅ。

<情况二＞先切一个，再切一对平行面,最后割剩余的一个,总费用比ｅ=０

时的费用增加2e．

〈情况三>切割面是两两相互垂直，总费用比e＝0时的费用增加３ｅ。

在所考虑的90种切割序列中,上述三种情况下垂直切割面的排列情形，及在

图Ｇ中对应有向路的必经点如下表：

垂直切割面排列情有向路必经点

形

情况一 (一)

M1-M2—M3－M4

(1,0，z）,(2,0，ｚ）,

（2,1,ｚ)

情况一 （二）

Ｍ3－M４－Ｍ1－M2

（0，1,z）,（0,２,ｚ），

(1，２,z）

情况二 （一)

M3—Ｍ1－M2-M4

（0，1,z）,(1，1,ｚ)，

（２，１，z)

情况二 (二）

M1－M3-M4－M2

（1，０，z），(1,1,z），

（1，２，z)

情况三 （一）

M1－M３-M２－M4

(1，0，ｚ)，（１，1，

ｚ)，（2,１，ｚ）

情况三 （二）

M3-M1－M4－M2

(0,1,z)，（1，1，z）,

（１，2,ｚ)

z＝0，1，2

3 / 5

我们希望通过在图9—13的网络图中的某些边上增加权来进行调刀费用增加

的计算，但由于网络图中的某些边是多种切割序列所公用的.对于某一种切割序

列，需要在此边上增加权e,但对于另外一种切割序列, 就有可能不需要在此边上

增加权e,这样我们就不能直接利用图9－１3的网络图进行边加权这种方法来求

出最短路径。

由上表可以看出，三种情况的情形（一)有公共点集{（２，1，z)｜z＝0,1，

２},情形（二)有公共点集｛(1,２，z)|z=0，1，2}.且情形(一)的有向路决不通

过情形(二)的公共点集，情形(二）的有向路也不通过情形（一）的公共点集．所

以可判断出这两部分是独立的、互补的。如果我们在图G中分别去掉点集{（1，

2,ｚ)|ｚ=0,１，2｝和｛(2，1，z）|z=0,1，２｝及与之相关联的入弧,就形成

两个新的网络图,如图Ｈ1和H2。这两个网络图具有互补性。对于一个问题来说，

最短路线必存在于它们中的某一个中.

由于调整垂直刀具为3次时，总费用需增加3e， 故我们先安排这种情况的

权增加值e,每次转刀时，给其待切弧上的权增加e．增加e的情况如图9—14中所

示.再来判断是否满足调整垂直刀具为二次、一次时的情况,我们发现所增加的权

满足另外两类切割序列。

综合上述分析,我们将原网络图Ｇ分解为两个网络图Ｈ1和Ｈ2，并在指定边上

的权增加e，然后分别求出图H1和Ｈ2中从V1到Ｖ27的最短路,最短路的权分别为：

d1，d2．则得出整体的最少费用为：d = min(d1，d２) ，最优切割序列即为其

对应的最短路径.

实例:ｒ=1５,e=２时,求得图G1与G2的最短路为Ｇ2的路V１－V4—Ｖ5—Ｖ14

—V17－V26—V２７,权为４435,对应的最优切割序列为Ｍ3-Ｍ1—M6—M4－Ｍ5

—Ｍ2,最优费用为4４35。

图9－1４ H1

4 / 5

图9—15 H

5 / 5

２

2024年5月19日发(作者：沈慧心)

建模案例：最优截断切割问题

一、 问 题

从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的

对应表面是平行的），通常要经过６ 次截断切割．设水平切割单位面积的费用

是垂直切割单位面积费用的r倍。且当先后两次垂直切割的平面（不管它们之

间是否穿插水平切割）不平行时，因调整刀具需额外费用e.试设计一种安排各

面加工次序（称“切割方式”)的方法,使加工费用最少。

二、 假 设

1、假设水平切割单位面积的费用为r,垂直切割单位面积费用为１;

２、当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，

调整刀具需额外费用ｅ；

3、第一次切割前,刀具已经调整完毕，即第一次垂直切割不加入刀具调整费用；

4 、每个待加工长方体都必须经过6次截断切割．

三、 模型的建立与求解

设待加工长方体的左右面、前后面、上下面间的距离分别为

a0、b０ 、c0

，

六个切割面分别位于左、右、前、后、上、下，将它们相应编号为M1、Ｍ2、M3、

M４、M5、M6，这六个面与待加工长方体相应外侧面的边距分别为

u1、ｕ2、u3、

u4、u5、ｕ6

.这样,一种切割方式就是六个切割面的一个排列，共有

P

6

6

720

种

切割方式。当考虑到切割费用时，显然有局部优化准则:两个平行待切割面中，

边距较大的待切割面总是先加工.

P

6

6

90

种切割方式.即在求最少加工费用 由此准则，只需考虑

2!2!2!

时，只需在９0个满足准则的切割序列中考虑．不失一般性,设

u１≥u2,u3≥u４，

u5≥u6

,故只考虑Ｍ1在M2前、M３在M４前、M5在Ｍ６前的切割方式。

1、 ｅ=0 的情况

1 / 5

为简单起见,先考虑e＝0 的情况．构造如图9—１3的一个有向赋权网络图Ｇ

(V，Ｅ）。为了表示切割过程的有向性，在网络图上加上坐标轴x，y，z．

图9—13 G（V,Ｅ)

图G（V，E)的含义为:

（１)空间网络图中每个结点Ｖi

(ｘi，yi,ｚi）

表示被切割石材所处的一

个状态.顶点坐标

xｉ、yi、ｚi

分别代表石材在左右、前后、上下方向上已被切

割的刀数．例如：V24(2，1,2) 表示石材在左右方向上已被切割两刀，前后方向

上已被切一刀,上下方向上已被切两刀，即面Ｍ1、M2、M3、M5、M6均已被切割．顶

点V1（0，0，０） 表示石材的最初待加工状态,顶点V２7（２，２，２）表示石

材加工完成后的状态．

（2)Ｇ的弧(Vi,Vj)表示石材被切割的一个过程，若长方体能从状态Ｖi经

一次切割变为状态Vj,即当且仅当

xｉ+yi+zi＋１=ｘj＋yj+zj

时，Vi（ｘi，yi，

zｉ)到Vj（ｘｊ，yj,zj）有弧（Vｉ，Vj),相应弧上的权

W(Vi，Ｖj）

即为这一

切割过程的费用。

Ｗ(Ｖi,Vj)＝(xj-xi）



（bｉ



ci）+(yj-yi)



（ai



ci)+(zj—zi)



（ａ

i



bi)



r

其中，

aｉ、ｂi、cｉ

分别代表在状态Vｉ时，长方体的左右面、上下面、

前后面之间的距离.

例如，状态Ｖ5(1，1，0）,

a５ = a0-ｕ1,ｂ5 = b0—u3,c5 = c０;

状态V6（２，1，0）

W（V5,V６) ＝（b0－u3）



c0

(3）根据准则知第一刀有三种选择， 即第一刀应切M1、M3、M5中的某

个面,在图中分别对应的弧为( Ｖ１,Ｖ2），（V1,Ｖ4）,(V1,V10). 图Ｇ中从V1

到Ｖ2７的任意一条有向道路代表一种切割方式.从V１到V２7共有9０条有向道

路，对应着所考虑的９0种切割方式．V1到Ｖ27的最短路即为最少加工费用，该

有向道路即对应所求的最优切割方式。

实例：待加工长方体和成品长方体的长、宽、高分别为1０、14５、1９ 和

3、２、４,两者左侧面、正面、底面之间的距离分别为6、7、9，则边距如下表：

u1

u2

u３

u4

u５

u6

6

１

７

55

6

９

2 / 5

r＝1时，求得最短路为V１－Ｖ１０－V13-V22—V２3－V２6—V27，其权为３７4

对应的最优切割排列为Ｍ５－M3－Ｍ6－M1－M４－Ｍ2,费用为37４元．

2、 e



０的情况

当ｅ



0时,即当先后两次垂直切割的平面不平行时，需加调刀费e。希望在

图９－１３的网络图中某些边增加权来实现此费用增加。在所有切割序列中，四

个垂直面的切割顺序只有三种可能情况：

<情况一＞先切一对平行面，再切另外一对平行面，总费用比e＝0时的费用

增加ｅ。

<情况二＞先切一个，再切一对平行面,最后割剩余的一个,总费用比ｅ=０

时的费用增加2e．

〈情况三>切割面是两两相互垂直，总费用比e＝0时的费用增加３ｅ。

在所考虑的90种切割序列中,上述三种情况下垂直切割面的排列情形，及在

图Ｇ中对应有向路的必经点如下表：

垂直切割面排列情有向路必经点

形

情况一 (一)

M1-M2—M3－M4

(1,0，z）,(2,0，ｚ）,

（2,1,ｚ)

情况一 （二）

Ｍ3－M４－Ｍ1－M2

（0，1,z）,（0,２,ｚ），

(1，２,z）

情况二 （一)

M3—Ｍ1－M2-M4

（0，1,z）,(1，1,ｚ)，

（２，１，z)

情况二 (二）

M1－M3-M4－M2

（1，０，z），(1,1,z），

（1，２，z)

情况三 （一）

M1－M３-M２－M4

(1，0，ｚ)，（１，1，

ｚ)，（2,１，ｚ）

情况三 （二）

M3-M1－M4－M2

(0,1,z)，（1，1，z）,

（１，2,ｚ)

z＝0，1，2

3 / 5

我们希望通过在图9—13的网络图中的某些边上增加权来进行调刀费用增加

的计算，但由于网络图中的某些边是多种切割序列所公用的.对于某一种切割序

列，需要在此边上增加权e,但对于另外一种切割序列, 就有可能不需要在此边上

增加权e,这样我们就不能直接利用图9－１3的网络图进行边加权这种方法来求

出最短路径。

由上表可以看出，三种情况的情形（一)有公共点集{（２，1，z)｜z＝0,1，

２},情形（二)有公共点集｛(1,２，z)|z=0，1，2}.且情形(一)的有向路决不通

过情形(二)的公共点集，情形(二）的有向路也不通过情形（一）的公共点集．所

以可判断出这两部分是独立的、互补的。如果我们在图G中分别去掉点集{（1，

2,ｚ)|ｚ=0,１，2｝和｛(2，1，z）|z=0,1，２｝及与之相关联的入弧,就形成

两个新的网络图,如图Ｈ1和H2。这两个网络图具有互补性。对于一个问题来说，

最短路线必存在于它们中的某一个中.

由于调整垂直刀具为3次时，总费用需增加3e， 故我们先安排这种情况的

权增加值e,每次转刀时，给其待切弧上的权增加e．增加e的情况如图9—14中所

示.再来判断是否满足调整垂直刀具为二次、一次时的情况,我们发现所增加的权

满足另外两类切割序列。

综合上述分析,我们将原网络图Ｇ分解为两个网络图Ｈ1和Ｈ2，并在指定边上

的权增加e，然后分别求出图H1和Ｈ2中从V1到Ｖ27的最短路,最短路的权分别为：

d1，d2．则得出整体的最少费用为：d = min(d1，d２) ，最优切割序列即为其

对应的最短路径.

实例:ｒ=1５,e=２时,求得图G1与G2的最短路为Ｇ2的路V１－V4—Ｖ5—Ｖ14

—V17－V26—V２７,权为４435,对应的最优切割序列为Ｍ3-Ｍ1—M6—M4－Ｍ5

—Ｍ2,最优费用为4４35。

图9－1４ H1

4 / 5

图9—15 H

5 / 5

２