【案例04】钢管下料问题返回首页

作者：欧新宇（Xinyu OU）
当前版本：Release v1.0
开发平台：Python3.11
运行环境：Intel Core i7-7700K CPU 4.2GHz, nVidia GeForce GTX 1080 Ti
本教案所涉及的数据集仅用于教学和交流使用，请勿用作商用。

最后更新：2024年3月12日

【知识点】

整数规划

一、提出问题

（问题来源：姜启源-4.6 钢管和易拉罐下料/司守奎-习题4.9）

某钢管零售商从某钢厂购进一批钢管，将钢管按照顾客的要求切割后售出，从钢管厂进货时得到的原料钢管都是19米。
（1）现有一客户需要50根4米、20根6米和15根8米的钢管，应如何下料最节省？
（2）零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过3种。此外客户除需要（1）中的3种钢管外，还需要10根5米的钢管该如何下料最省？

二、问题一的求解

2.1 问题分析

首先，应该确定哪些切割模式是可行的。所谓一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合。例如，可以将 19m 的钢管切割成 3 根 4m 的钢管，余料为 7m；或者将 19m 的钢管切割成 4m、6m 和 8m 的钢管各 1根，余料为 1m。显然可行的切割模式有很多种。
其次，应该确定哪些切割模式是合理的。简单的说就是尽最大可能进行下料，也就是说一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸，即在本题中余料应该小于4m。例如，将 19m 的钢管切割成 3 根 4m 的钢管是可行的，但会有 7m 的余料；此时可以进一步将 7m 的余料切割成 4m 钢管（余料为 3m），或者将 7m 的余料切割成 6m 钢管（余料为 1m）。在这种合理性假设下，切割模式一共有如下7种。

表1 钢管下料的合理切割模式

	4m钢管根数	6m钢管根数	8米钢管根数	余料/m
模式1	0	0	2	3
模式2	0	3	0	1
模式3	1	1	1	1
模式4	1	2	0	3
模式5	2	0	1	3
模式6	3	1	0	1
模式7	4	0	0	3

下面，我们使用python来求解以上7种切割模式。首先，我们定义一个数组变量，用于存储一根原料钢管可以切割出来的4m、6m和8m钢管的数量，以及余料。显然，4m钢管的数量应该不超过4根，即 $n*4m \leq 19m$ 。类似的，6m钢管的数量应该不超过3，8m钢管的数量应该不超过2。

# codes_Project04_01 合理切割模式

import cvxpy as cp
import numpy as np

cutModel = []
for i in range(5):            # 定义4m钢管，取值0~4
    for j in range(4):        # 定义6m钢管，取值0~3
        for k in range(3):    # 定义8m钢管，取值0~2
            used = i*4 + j*6 + k*8
            if used >= 16 and used <= 19:   # 尽最大可能下料，因此取值范围为(19-4+1)~19
                cutModel.append([i, j, k, 19 - used])

print('合理切割模式([4m, 6m, 8m, 余料])：\n', np.array(cutModel))

合理切割模式([4m, 6m, 8m, 余料])：
 [[0 0 2 3]
 [0 3 0 1]
 [1 1 1 1]
 [1 2 0 3]
 [2 0 1 3]
 [3 1 0 1]
 [4 0 0 3]]

基于以上分析，下料问题将转化为在满足客户需要的条件下，按照哪些合理的模式，切割多少根原料钢管，最为节省。所谓最为节省，可以用两种标准进行衡量：

一是切割后剩余的总预料量最小，
二是切割原料钢管的总根数最少。

2.2 模型建立

决策变量：设 $x_i$ 表示按照第 $i, i=(1,..,7)$ 种切割模式下切割原料钢管的根数，显然它应该满足 $x_i \geq 0$ ，即 $x_i$ 是非负整数。

目标函数：根据表1的数据，

以切割后剩余的余量最小为目标，可得优化函数 $z_1$ ：

$\min z_1 = 3x_1 + x_2 + x_3 + 3x_4 + 3x_5 + x_6 + 3x_7 \tag{1}$

以切割原料钢管总根数最少为目标，则可得到优化函数 $z_2$ ：

$\min z_2 = x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 \tag{2}$

约束条件：为满足客户需要，按照表1 应有：

$s.t. \begin{cases} x_3 + x_4 + 2x_5 + 3x_6 + x_7 \geq 50 \\ 3x_2 + 2x_4 + x_6 \geq 20 \\ 2x_1 + x_3 + x_5 \geq 15 \\ x_i \geq 0, 且为整数 (i=1,2,...,7) \end{cases} \tag{3}$

2.3 模型求解

在上面的模型中，目标函数（1）和目标函数（2）是两个不同的优化问题。因此，我们应根据目标函数和约束条件，分别建立两个不同的线性规划模型，然后求解这两个模型。最后再根据求解结果和实际要求，确定最优的切割模式。下面分别给出求解这两个目标函数的Python代码：

# codes_Project04_02 求解目标函数1
a = np.array(cutModel)[:,:3].T
res = np.array(cutModel)[:,-1]

x = cp.Variable(7, integer=True)   # 创建未知变量x
c = np.array([50, 20, 15])
obj1 = cp.Minimize(res@x)
con =[a@x >= c, x >= 0]
prob = cp.Problem(obj1, con)
prob.solve(solver = 'GLPK_MI')

print('以切割后剩余余料最小为目标（目标函数1）：')
print('每种模式钢管数：', np.round(x.value).astype(int))
print('钢管总数为：{:.0f}'.format(prob.value))
print('余料长度为：{:.0f}'.format(res@x.value))
print('实际每类钢管数为：', a@x.value)

以切割后剩余余料最小为目标（目标函数1）：
每种模式钢管数： [ 0  0 15  0  0 12  0]
钢管总数为：27
余料长度为：27
实际每类钢管数为： [51. 27. 15.]

# codes_Project04_03 求解目标函数2
x = cp.Variable(7, integer=True)   # 创建未知变量x
c = np.array([50, 20, 15])
obj2 = cp.Minimize(sum(x))
con =[a@x >= c, x >= 0]
prob = cp.Problem(obj2, con)
prob.solve(solver = 'GLPK_MI')

print('以切割原料钢管总根数最少为目标（目标函数2）：')
print('每种模式钢管数：', np.round(x.value).astype(int))
print('钢管总数为：{:.0f}'.format(prob.value))
print('余料长度为：{:.0f}'.format(res@x.value))
print('实际每类钢管数为：', a@x.value)

以切割原料钢管总根数最少为目标（目标函数2）：
每种模式钢管数： [ 5  0  5  0  0 15  0]
钢管总数为：25
余料长度为：35
实际每类钢管数为： [50. 20. 15.]

2.4 模型分析

根据以上目标函数（1）和目标函数（2），我们可以分别求出 以切割后剩余余料最小为目标 和 以切割原料钢管总根数最少为目标 的两种不同下料方案。这两种求解方案在数学上都属于整数线性规划模型。

根据目标函数（1）的结果可知， $x_3=15, x_6=12$ ，即按照模式3切割15根，按照模式6切割12根，总根数为27根，此时余料为 $15×1+12×1=27m$ 。同理，按照目标函数（2）的结果可知， $x_1=5, x_3=5, x_6=15$ ，总根数为25根，余料为 $5×3+5×1+15+1=35m$ 。

从结果来看，方案一的余料更少，但其消耗的原料却更多。因此，我们最终选择方案的时候需要根据余料的可用性进行判断。若余料没有任何用途，则总根数更少的方案二是更好的选择；而若余料有其他用途，则可以根据余料的利用率进行进一步判断。

三、问题二的求解

问题二的求解留给读者自行完成。

在模型设计和求解过程中，以下有几点是可以加以考虑的：

由于下料需求增加到4种，因此问题一中使用枚举法获得切割模式的可行性，如果使用手工法则工作量会较大，但考虑到可以使用Python编程实现，这种方法依然是可行的。
当变量较多时，模型的解可能并不唯一，因此为了确保模型更加合理，可以考虑增加一些合理性限制条件。例如，钢管原料的上限、或者钢管原料的下限。不难想象钢管原料的总根数应该满足如下条件：

$N_{1钢管数量下限} = \frac{4×50+5×10+6×20+8×15}{19}=26$
$N_{2钢管数量上限} = \leq \lceil 50/(19 \mid 4) \rceil + \lceil 10/(19 \mid 5) \rceil + \lceil 20/(19 \mid 6) \rceil + \lceil 15/(19 \mid 8) \rceil = 31$
$N_1 \leq \sum_{i=1}^n x_i \leq N_2$

下面给出问题二求解的Python代码范例，数学分析及求解过程，请读者自行完成。

# codes_Project04_04 问题二参考代码

import cvxpy as cp
import numpy as np

cutModel = []
for i in range(5):            # 定义4m钢管，取值0~4
    for j in range(4):        # 定义5m钢管，取值0~3
        for k in range(4):        # 定义6m钢管，取值0~3
            for l in range(3):    # 定义8m钢管，取值0~2
                used = i*4 + j*5 + k*6 + l*8
                if used >= 16 and used <= 19:   # 尽最大可能下料，因此取值范围为(19-4+1)~19
                    cutModel.append([i, j, k, l, 19 - used])

# print('合理切割模式([4m, 5m, 6m, 8m, 余料])：\n', np.array(cutModel))

a = np.array(cutModel)[:,:4].T
res = np.array(cutModel)[:,-1]
n = len(cutModel)
x = cp.Variable(n, integer=True)   # 创建未知变量x
y = cp.Variable(n, integer=True)   # 创建未知变量y

c = np.array([50, 20, 15, 10])
obj2 = cp.Minimize(sum(x))
con =[a@x >= c, x >= 0, x<=1000*y, sum(y)<=3, y>=0, y<=1, sum(x)<=31, sum(x)>=26]
prob = cp.Problem(obj2, con)
prob.solve(solver = 'GLPK_MI')

print('以切割原料钢管总根数最少为目标（目标函数2）：')
print('每种模式钢管数：', np.round(x.value).astype(int))
print('钢管总数为：{:.0f}'.format(prob.value))
print('余料长度为：{:.0f}'.format(res@x.value))
print('实际每类钢管数为：', a@x.value)

以切割原料钢管总根数最少为目标（目标函数2）：
每种模式钢管数： [ 0  0  0  0  0  0 10  0  0  0  0  0 10  7  0  0]
钢管总数为：27
余料长度为：27
实际每类钢管数为： [51. 20. 17. 10.]

【拓展练习】钢管下料问题二

（司守奎-习题4.9）

某单位需要加工制作100套钢架，每套用长为2.9m，2.1m和1m的圆钢各一根。已知原料长为6.9m，则（1）如何下料，使用原材料最省；（2）若下料方式不超过3种，应如何下料，使用的原材料最省。

【案例04】钢管下料问题 返回首页