建模案例：最优截断切割问题
一、 问 题
从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的
对应表面是平行的），通常要经过 6 次截断切割.设水平切割单位面积的费用是
垂直切割单位面积费用的 r 倍.且当先后两次垂直切割的平面（不管它们之间是
否穿插水平切割）不平行时，因调整刀具需额外费用 e.试设计一种安排各面加
工次序（称“切割方式”）的方法，使加工费用最少.
二、 假 设
１．假设水平切割单位面积的费用为 r，垂直切割单位面积费用为 1；
２．当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，
调整刀具需额外费用 e；
３．第一次切割前，刀具已经调整完毕，即第一次垂直切割不加入刀具调整费
用；
4．每个待加工长方体都必须经过 6 次截断切割.
三、 模型的建立与求解
设待加工长方体的左右面、前后面、上下面间的距离分别为
b0
、
c0
，六
个切割面分别位于左、右、前、后、上、下，将他们相应编号为
M1
、
M2
、
M3
、
M4
、
M5
、
M6
，这六个面与待加工长方体相应外侧面的边距分
a0
别为
u1
、
u2
、
u3
、
u4
、
u5
、
u6.
这样，一种切割方式就是六个切割面的一个排列，共有
6
6
P 720=
种切割方式
.
当考虑到切割费用时，显然有局部优化准则：两个平行待切割面中，
边距较大的待切割面总是先加工
.
由此准则
,
只需考虑
6
6
P
90
2! 2! 2!
=
´ ´
种切割方式
.
即在求最少加工费用时，
只需在
90
个满足准则的切割序列中考虑
.
不失一般性，设
u1
≥
u2
，
u3
≥
u4
，
u5
≥
u6
，
故只考虑
M1
在
M2
前、
M3
在
M4
前、
M5
在
M6
前的切割方式
.
1.
e=0
的情况
