在制造业中，常常要切割原材料，比如把纸卷、布料、钢管等等，切割成不同的长度，以满足生产需求。由于需求的长度和数量是不同的，切割方式可以有很多种。不同的切割方式，消耗的原料总数也不同。

我们的问题是，在满足生产需求的前提下，找到最节省原材料的切割方式。这样的问题称为 下料问题 （The Cutting Stock Problem）。

例子

工厂中有一些材料，每一根的长度都是 1000，原材料的数量没有限制。现在有四种类型的产品要生产。每种类型对应的长度和数量如下表所示。

类型 长度 数量
1 450 97
2 360 610
3 310 395
4 140 211

我们的问题是，最少需要多少原材料才能满足上面四种产品的生产需求。除了计算数量，还要给出对应的切割方式。

说明一下切割方式。例如，可以把一根原材料按类型1的长度 450 切两次，剩下的长度是 1000 - 450 × 2 =100。最小的需求长度是 140，因此这一根原材料就被消耗完了。

或者换一种切割方式，把原材料按类型 1 的长度 450 先切一次，剩余长度 550。接下来再按类型 2 的长度 360 切一次，剩余长度 190。再按类型 4 的长度 140 切一次，剩余长度 50。

还有更多的切割方式，我们不一一列举。这种用文字的方式不适合建立数学模型。接下来我们用数学语言来定义。

可行切割

令 $L$ 代表原材料长度，在这个例子中 $L=1000$。令向量 $s$ 代表四种类型的需求长度，即

$$ s = \begin{bmatrix} s_1\\ s_2\\ s_3\\ s_4 \end{bmatrix}=\begin{bmatrix} 450\\ 360\\ 310\\ 140 \end{bmatrix} $$

给定一根原材料，令向量 $a$ 代表四种类型对应的切割数量。

$$ a = [a_1, a_2, a_3, a_4]^T $$

例如 $[2, 0, 0, 0]^T$ 表示按第 1 种长度为 450 切两次；$[1, 1, 0, 1]$ 表示按第 1 种长度 450 切一次，再按第 2 种长度 350 切一次，再按第 4 种长度 140 切一次。

但是注意，我们还要求

$$ a^T s \leq L $$

换句话说，切割得到的总长度，不能超过原材料的总长度，从而保证切割就是可行的。

因此，我们可以用列向量 $a$ 来描述一种切割方式，如果它满足 $a^T s \leq L$，那么它就是 可行切割。

可行矩阵

我们可以枚举所有的可行切割。假设一种有 $n$ 种方式，记作 $a_1, a_2, …, a_n$。 其中每一个 $a_j$ 是一个列向量，对应每种需求的切割数量。

把它们写成矩阵形式，即

$$ A := \begin{bmatrix} a_1 & a_2 & ... & a_n \end{bmatrix} $$

为了方便描述，我们把矩阵 $A$ 称为 可行矩阵，代表所有可行的切割方式。它的列向量满足如下条件。

$$ a_j^T s \leq L, \quad j=1,2,...,n $$

说一下如何枚举所有可行的切割方式。

考虑一根原材料。令 $k_1, k_2, k_3, k_4$ 代表每一种类型可以切割的数量上限。

$$ k_i = \left\lfloor \frac{L}{s_i}\right\rfloor , \quad i = 1,2,3,4 $$

我们有

$$ k_1 = 2,~ k_2 = 2, ~ k_3 = 3, ~ k_4 = 7 $$

令 $a=[a_1, a_2, a_3, a_4]^T$ 代表一个可行切割，我们有

$$ \begin{aligned} & a_1\in \set{0, 1,2}, ~ a_2\in \set{0, 1, 2}\\ & a_3\in \set{0, ..., 3}, ~ a_4 \in \set{0, ..., 7}\\ \end{aligned} $$

只要枚举 $a$ 的所有取值，如果 $a^T s \leq T$，就把它添加到 $A$ 的列中。

此外，还可以做一些优化，例如 $[0, 0, 0, 0]^T$ 虽然可行，但是在最优解中，显然不会包含这样的切割方式。

具体来说，可以这样做。已知两个可行切割 $a_1, a_2$：

$$ \begin{aligned} & a_1 = [a_{11}, a_{12}, a_{13}, a_{14}]^T \\ & a_2 = [a_{21}, a_{22}, a_{23}, a_{24}]^T \end{aligned} $$

如果 $a_2\geq a_1$，即 $a_{2,i} \geq a_{1,i}$，$i=1,2,3,4$，那么 $a_1$ 就是冗余的。如果存在冗余的可行切割，也可以把它从可行矩阵 $A$ 中删除。

数学模型

接下来把这个问题写成整数规划的形式。

指标

  • $i$ – 产品类型，取值范围 $\set{1,2,3,4}$
  • $j$ – 切割方式，取值范围 $\set{1, …, n}$，其中 $n$ 是可行切割方式的数量

参数

  • $d_i$ – 第 $i$ 种产品的需求量
  • $a_{i,j}$ – 在第 $j$ 种切割方式中，第 $i$ 种需求长度对应的切割数量

决策变量

  • $x_j \in \mathbb{N}$ – 第 $j$ 种切割方式对应的原材料数量

目标函数

  • 最小化总的原材料数量：$\min \sum_{j=1}^n x_j$

约束条件

  • 每种产品的需求量被满足：$\sum_{j=1}^{n} a_{i,j} x_j = d_i, \quad i=1,2,3,4$

综上所述，我们得到如下的整数规划问题。

$$ \begin{aligned} \min ~ & \sum_{j=1}^n x_j \\ \text{ s.t. } & \sum_{j=1}^n a_{i,j} x_j = d_i, ~\forall i \\ & x_j \in \mathbb{N}_+, ~\forall j \end{aligned} $$

写成矩阵形式如下。

$$ \begin{aligned} \min ~ & e^Tx \\ \text{ s.t. } & A x = d \\ & x \in \mathbb{N}^n_+ \end{aligned} $$

其中 $e=[1, 1, …, 1]^T$，$d=[d_1, d_2, d_3, d_4]^T$。

Edit this page

Last updated 22 Apr 2025, 12:44 +0800 . history