这是 下料问题 的整数规划模型。

$$ \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} $$

接下来对它进行求解。

精确解

最直接的办法，就是用整数规划求解器。但是有个问题，当问题规模较大时，求解器可能算不出来。

简单分析一下。令 $m$ 代表产品类型数量，$n$ 代表可行切割方式的数量。在上面的规划中，约束的个数是 $m$，变量的个数是 $n$。在最坏的情况下，$n$ 随着 $m$ 的增大呈指数增长，即 $n\geq 2^m$。

换句话说，变量的数量以及可行切割的数量随 $m$ 指数增长。即便只是枚举所有的可行切割，需要的时间也随 $m$ 指数增长。

在这个例子中 $m=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 \geq 0, ~\forall j \end{aligned} $$

它的最优解记作 $x^*$。

第二步，向下取整

把最优解 $x^*$ 向下取整，得到整数解记作 $\bar{x}= \lfloor x^* \rfloor$。但是取整后，可能导致需求不满足，即

$$ \sum_{j=1}^n a_{ij}\bar{x}_j < d_i,\quad \exists~ i $$

因此，需要计算没有被满足的需求量。为了方便描述，用 $r_i$ 来表示

$$ r_i = d_i - \sum_{j=1}^n a_{ij}\bar{x}_j, \quad \forall i $$

接下来满足剩余的需求。

第三步，满足需求

考虑所有 $\set{r_i \mid r_i > 0}$，然后满足这些需求。例如每次选一个最大的 $r_i$，从 $\bar{x}$ 对应的基列中选一列，然后满足需求 $r_i$。重复这样的步骤，直到剩余的需求被满足。具体细节这里不多讲，感兴趣可以看 编程实现。

问题

求近似解的过程中，求解松弛问题虽然比整数规划容易，但是仍然不能处理大规模的情形。即，当 $m$ 较大时，$n$ 是 $m$ 的指数关系，导致系数矩阵 $A$ 非常大。在这种情况下，计算系数矩阵 $A$ 就已经超出我们能接受的时间。因此，直接求解的办法不能应对大规模情形。

Edit this page

Last updated 24 Apr 2025, 15:18 +0800 . history