基于线性规划的“多维背包问题”建模与列生成算法求解示例

字数 6008 2025-12-20 07:41:30

好的，根据你的要求，避免重复已讲过的题目，我将为你讲解一个新的线性规划领域算法题目。

基于线性规划的“多维背包问题”建模与列生成算法求解示例

题目描述

多维背包问题是经典背包问题的推广。我们有一个容量有限的背包，但限制条件不止一个（例如，既有重量限制，也有体积限制）。同时，有 \(n\) 件物品可供选择，每件物品 \(j\) 有自己的价值 \(p_j\)，并且会消耗多种资源（如重量 \(w_j\)，体积 \(v_j\) 等）。我们的目标是在不超过所有资源容量限制的前提下，选择若干物品装入背包，使得总价值最大。

形式化定义：

有 \(n\) 件物品，索引为 \(j = 1, 2, ..., n\)。
有 \(m\) 种资源（维度），索引为 \(i = 1, 2, ..., m\)。
第 \(j\) 件物品的价值为 \(p_j\)。
第 \(j\) 件物品消耗第 \(i\) 种资源的量为 \(w_{ij}\)。
第 \(i\) 种资源的总容量为 \(W_i\)。
决策变量：\(x_j \in \{0, 1\}\)，表示是否选择物品 \(j\)。

目标与约束：
最大化总价值：

\[\max \sum_{j=1}^{n} p_j x_j \]

同时满足所有资源限制：

\[\sum_{j=1}^{n} w_{ij} x_j \leq W_i, \quad \forall i = 1, ..., m \]

以及变量的整数性约束：

\[x_j \in \{0, 1\}, \quad \forall j = 1, ..., n \]

这是一个 NP-Hard 的整数规划问题。当物品数量 \(n\) 非常大时（例如数万、数十万），直接建立包含所有物品变量的模型并求解是不现实的。此时，列生成算法 提供了一种高效的求解思路。

解题过程（循序渐进）

列生成算法的核心思想是：不在一开始就考虑所有可能的变量（列），而是从一个小的、容易求解的受限主问题开始，然后通过求解一个子问题（定价问题）来动态地寻找能改善当前解的、有价值的变量（列），将其加入主问题，反复迭代直到找不到能改善解的变量为止。

步骤一：构建限制性主问题

我们首先不从所有 \(n\) 件物品开始，而是随意选择（或根据启发式规则选择）一个物品子集 \(S \subset \{1, ..., n\}\)，构建一个规模较小的线性规划松弛问题，称为 限制性主问题。

限制性主问题：

\[\text{(RMP)} \quad \max \sum_{j \in S} p_j \tilde{x}_j \]

\[ \text{s.t.} \quad \sum_{j \in S} w_{ij} \tilde{x}_j \leq W_i, \quad \forall i = 1, ..., m \]

\[ \tilde{x}_j \geq 0, \quad \forall j \in S \]

注意，我们在这里将原始的0-1变量 \(\boldsymbol{x_j}\) 松弛为了非负变量 \(\boldsymbol{\tilde{x}_j}\)，并且移除了整数约束，但 加入了上界 \(\tilde{x}_j \leq 1\) 吗？不，我们暂时不加。因为列生成通常用于线性规划松弛，但多维背包问题中，物品不能拆分（\(\tilde{x}_j\) 应代表选择物品的比例），所以必须加上上界约束 \(\tilde{x}_j \leq 1\)。然而，在标准的列生成框架中，我们更常处理的是 集合覆盖/划分 或 切割问题，其中变量代表模式或方案。对于多维背包，我们可以将其看作一个“选择模式”问题吗？是的，我们可以。

更巧妙的建模：Dantzig-Wolfe 分解视角
我们可以将原问题重新解释：每个可行的物品选择方案就是一个“列”（模式）。一个列 \(a\) 是一个 \(m+1\) 维向量：\([p^a, w_{1}^a, w_{2}^a, ..., w_{m}^a]^T\)，表示该模式的价值和资源消耗。主问题的变量 \(\lambda_a\) 表示是否采用模式 \(a\)。

但我们不可能枚举所有模式。在列生成中，我们从一个小的模式集合开始，然后通过求解定价子问题来寻找有“负缩减成本”的新模式加入主问题。为了做到这一点，我们需要获取当前 RMP 解的对偶变量值。

回到标准形式：即使我们直接使用物品变量，列生成依然可行。关键在于，线性规划松弛的 RMP 不需要包含所有物品变量。我们从一个初始的物品子集 \(S\) 开始。为了让松弛有意义，我们 必须加上上界约束 \(\tilde{x}_j \leq 1\)。这样，RMP 就是一个标准的带界约束的线性规划。

初始RMP修正版：
假设初始集合 \(S\) 包含 \(k\) 个物品。

\[\text{(RMP)} \quad \max \sum_{j \in S} p_j \tilde{x}_j \]

\[ \text{s.t.} \quad \sum_{j \in S} w_{ij} \tilde{x}_j \leq W_i, \quad \forall i = 1, ..., m \quad (\text{主约束，对偶变量记为 } \pi_i) \]

\[ \tilde{x}_j \leq 1, \quad \forall j \in S \quad (\text{上界约束，对偶变量记为 } \sigma_j) \]

\[ \tilde{x}_j \geq 0, \quad \forall j \in S \]

步骤二：求解限制性主问题并获取对偶变量

我们使用单纯形法或内点法求解当前的 RMP（它是一个线性规划）。得到最优解 \(\boldsymbol{\tilde{x}^*}\) 和对应的最优对偶变量值。

\(\boldsymbol{\pi_i^*}\)：对应每种资源 \(i\) 的容量约束的影子价格（边际价值）。
\(\boldsymbol{\sigma_j^*}\)：对应每个已考虑物品 \(j \in S\) 的上界约束的影子价格。

这些对偶变量的经济意义是：

\(\pi_i\)：资源 \(i\) 每增加一单位容量所能带来的目标函数（总价值）的增量。
\(\sigma_j\)：物品 \(j\) 的上界约束每放松一单位（即允许选择超过1个）带来的价值增量。对于0-1问题，这通常与物品的“吸引力”有关。

步骤三：构建并求解定价子问题

定价子问题的任务是：在 所有未加入 RMP 的物品（即 \(j \notin S\)）中，找到一个或一组物品，其“加入”到当前 RMP 中能够 改善目标函数值。

在线性规划中，判断一个新变量（列）能否改善当前最优解的标准是看它的 缩减成本。

对于原问题中的任意物品 \(j\)（无论是否在 \(S\) 中），其对应的变量 \(x_j\) 在完整的主问题中，其目标函数系数是 \(p_j\)，在约束矩阵中，它在：

每个资源约束 \(i\) 中的系数是 \(w_{ij}\)。
它自身有一个上界约束 \(x_j \leq 1\)，这个约束在完整问题中也存在，但它是“列的一部分”，更准确地说，在 RMP 中我们显式写出了已考虑物品的上界约束。

对于尚未在 RMP 中的物品 \(t \notin S\)，其缩减成本 \(rc_t\) 的计算公式为：

\[rc_t = p_t - \sum_{i=1}^{m} \pi_i^* w_{it} - \sigma_t \]

等等，这里 \(\sigma_t\) 是什么？\(\sigma_t\) 是变量 \(x_t\) 的上界约束（\(x_t \leq 1\)）对应的对偶变量。关键在于，当物品 \(t\) 还不在 RMP 中时，其上界约束 \(x_t \leq 1\) 也还未加入 RMP，因此它当前没有对应的对偶变量 \(\sigma_t\)。在计算新列的缩减成本时，我们只考虑那些在当前 RMP 中已存在的约束对应的对偶变量。上界约束 \(x_t \leq 1\) 是“伴随”变量 \(x_t\) 出现的，只有当变量被加入时，这个约束才会被“激活”或显式加入。更准确的计算方式是：

在新变量（列） \(x_t\) 对应的约束系数向量是 \(\mathbf{a_t} = [w_{1t}, w_{2t}, ..., w_{mt}, 1]^T\)，它需要满足前 \(m\) 个资源约束和一个隐含的上界约束。在RMP的对偶视角下，我们已有前 \(m\) 个约束的对偶变量 \(\boldsymbol{\pi}\)。上界约束 \(x_t \leq 1\) 是一个“简单的界”，在单纯形法中，非基变量的缩减成本计算只考虑主约束（资源约束）的对偶价格。实际上，对于一个新变量 \(x_t\)，其缩减成本为：

\[rc_t = p_t - \sum_{i=1}^{m} \pi_i^* w_{it} \]

如果 \(rc_t > 0\)，那么将 \(x_t\) 作为基变量引入（设为一个很小的正数）可以改善目标函数值（因为最大化问题中，检验数为正的非基变量进基会使目标增加）。

因此，定价子问题 就是寻找一个物品 \(j \notin S\)，使得其缩减成本 \(rc_j = p_j - \sum_{i=1}^{m} \pi_i^* w_{ij} > 0\)，并且最大。

子问题数学模型：

\[\text{(Pricing SP)} \quad \max_{j \notin S} \left\{ p_j - \sum_{i=1}^{m} \pi_i^* w_{ij} \right\} \]

等价于：

\[\zeta = \max_{j \notin S} \left\{ p_j - \sum_{i=1}^{m} \pi_i^* w_{ij} \right\} \]

求解：我们只需遍历所有不在 \(S\) 中的物品 \(j\)，计算 \(p_j - \sum_{i=1}^{m} \pi_i^* w_{ij}\)，并找到最大值 \(\zeta\)。这是一个非常简单的计算过程。

步骤四：判断与迭代

判断准则：
- 如果 \(\zeta > 0\)，说明找到了一个缩减成本为正的物品（记为 \(j^*\)）。将这个物品对应的变量（列）加入 RMP 中。具体来说，在 RMP 中新增一个变量 \(\tilde{x}_{j^*}\)，其目标系数为 \(p_{j^*}\)，在第 \(i\) 个资源约束中的系数为 \(w_{i, j^*}\)，并为其新增一个上界约束 \(\tilde{x}_{j^*} \leq 1\)。
- 如果 \(\zeta \leq 0\)，说明对于所有未考虑的物 \(j \notin S\)，都有 \(p_j - \sum_{i=1}^{m} \pi_i^* w_{ij} \leq 0\)。这意味着当前 RMP 的解已经达到了完整线性规划松弛的最优解。因为所有不在基中的变量（包括已考虑的非基变量和未考虑的变量）的检验数都非正（对于最大化问题），满足线性规划的最优性条件。
迭代：
- 如果找到 \(j^*\)，将其加入集合 \(S\)，更新 RMP，返回 步骤二。
- 如果 \(\zeta \leq 0\)，则列生成过程结束。我们得到了原整数规划问题的线性规划松弛最优解 \(\boldsymbol{\tilde{x}_{LP}^*}\) 和最优值 \(Z_{LP}^*\)。

步骤五：获得整数解（分枝定界框架）

列生成通常用于求解线性规划松弛。要得到原0-1整数规划的最优解或高质量可行解，需要将列生成嵌入到 分枝定界 框架中，形成 分枝定价。

根节点：我们运行上述列生成过程，得到线性规划松弛最优解 \(Z_{LP}^*\) 和对应的分数解 \(\tilde{x}^*\)。
分枝：如果 \(\tilde{x}^*\) 中所有变量都是0或1，则找到了一个整数最优解。否则，选择一个分数变量 \(\tilde{x}_j\)（其值在0和1之间），创建两个子节点：
- 左子节点：添加约束 \(x_j = 0\)。
- 右子节点：添加约束 \(x_j = 1\)。
定界与剪枝：在每个子节点上，再次运行列生成算法来求解带有新约束（\(x_j = 0\) 或 \(x_j = 1\)）的线性规划松弛。新约束会影响定价子问题：
- 如果 \(x_j = 0\)，则在后续的定价子问题中，简单地禁止物品 \(j\) 被选中。
- 如果 \(x_j = 1\)，则相当于已经选择了物品 \(j\)，需要从资源容量中扣除 \(w_{ij}\)，并在定价子问题中禁止物品 \(j\) 再次被选中。同时，RMP的初始解中可以固定这个变量为1。
继续搜索：在整个分枝定界树中，不断选择节点、分枝、调用列生成求解松弛、更新全局上下界，直到找到最优整数解或满足时间/精度要求。

总结与启示

核心思想：列生成通过解决一个包含少量变量的 主问题 和一个用于生成新变量的 子问题，避免了直接处理大规模变量集，特别适合物品/方案数量巨大的组合优化问题。
关键技术点：
- Dantzig-Wolfe分解：将原问题重构为基于“模式”的主问题。
- 对偶变量：主问题解提供的影子价格是子问题寻找改善方向的“指南针”。
- 定价子问题：通常是一个相对容易的优化问题（本例中是简单的遍历计算），其目标是找到检验数最优的新列。
- 最优性条件：当子问题找不到检验数为正的列时，当前主问题的解就是完整松弛问题的最优解。
应用扩展：本例展示的是最基本的列生成框架。在实际的多维背包问题中，如果物品数量极大（例如上亿），遍历所有物品计算缩减成本可能仍然很慢。此时，定价子问题本身可能就是一个复杂的优化问题（例如一个背包问题），需要设计专门的算法快速求解。此外，分枝定价是获得整数解的标准方法。

通过这个例子，你可以看到列生成算法如何将一个变量规模极大的整数规划问题，转化为一系列规模可控的线性规划子问题和一个简单的定价问题，从而实现了高效求解。

好的，根据你的要求，避免重复已讲过的题目，我将为你讲解一个新的线性规划领域算法题目。基于线性规划的“多维背包问题”建模与列生成算法求解示例题目描述多维背包问题是经典背包问题的推广。我们有一个容量有限的背包，但限制条件不止一个（例如，既有重量限制，也有体积限制）。同时，有 \(n\) 件物品可供选择，每件物品 \(j\) 有自己的价值 \(p_ j\)，并且会消耗多种资源（如重量 \(w_ j\)，体积 \(v_ j\) 等）。我们的目标是在不超过所有资源容量限制的前提下，选择若干物品装入背包，使得总价值最大。形式化定义：有 \(n\) 件物品，索引为 \(j = 1, 2, ..., n\)。有 \(m\) 种资源（维度），索引为 \(i = 1, 2, ..., m\)。第 \(j\) 件物品的价值为 \(p_ j\)。第 \(j\) 件物品消耗第 \(i\) 种资源的量为 \(w_ {ij}\)。第 \(i\) 种资源的总容量为 \(W_ i\)。决策变量：\(x_ j \in \{0, 1\}\)，表示是否选择物品 \(j\)。目标与约束：最大化总价值： \[ \max \sum_ {j=1}^{n} p_ j x_ j \] 同时满足所有资源限制： \[ \sum_ {j=1}^{n} w_ {ij} x_ j \leq W_ i, \quad \forall i = 1, ..., m \] 以及变量的整数性约束： \[ x_ j \in \{0, 1\}, \quad \forall j = 1, ..., n \] 这是一个 NP-Hard 的整数规划问题。当物品数量 \(n\) 非常大时（例如数万、数十万），直接建立包含所有物品变量的模型并求解是不现实的。此时，列生成算法提供了一种高效的求解思路。解题过程（循序渐进）列生成算法的核心思想是：不在一开始就考虑所有可能的变量（列），而是从一个小的、容易求解的受限主问题开始，然后通过求解一个子问题（定价问题）来动态地寻找能改善当前解的、有价值的变量（列），将其加入主问题，反复迭代直到找不到能改善解的变量为止。步骤一：构建限制性主问题我们首先不从所有 \(n\) 件物品开始，而是随意选择（或根据启发式规则选择）一个物品子集 \(S \subset \{1, ..., n\}\)，构建一个规模较小的线性规划松弛问题，称为限制性主问题。限制性主问题： \[ \text{(RMP)} \quad \max \sum_ {j \in S} p_ j \tilde{x} j \] \[ \text{s.t.} \quad \sum {j \in S} w_ {ij} \tilde{x}_ j \leq W_ i, \quad \forall i = 1, ..., m \] \[ \tilde{x}_ j \geq 0, \quad \forall j \in S \] 注意，我们在这里将原始的0-1变量 \(\boldsymbol{x_ j}\) 松弛为了非负变量 \(\boldsymbol{\tilde{x}_ j}\)，并且移除了整数约束，但加入了上界 \(\tilde{x}_ j \leq 1\) 吗？不，我们暂时不加。因为列生成通常用于线性规划松弛，但多维背包问题中，物品不能拆分（\(\tilde{x}_ j\) 应代表选择物品的比例），所以必须加上上界约束 \(\tilde{x}_ j \leq 1\)。然而，在标准的列生成框架中，我们更常处理的是集合覆盖/划分或切割问题，其中变量代表模式或方案。对于多维背包，我们可以将其看作一个“选择模式”问题吗？是的，我们可以。更巧妙的建模：Dantzig-Wolfe 分解视角我们可以将原问题重新解释：每个可行的物品选择方案就是一个“列”（模式）。一个列 \(a\) 是一个 \(m+1\) 维向量：\([ p^a, w_ {1}^a, w_ {2}^a, ..., w_ {m}^a]^T\)，表示该模式的价值和资源消耗。主问题的变量 \(\lambda_ a\) 表示是否采用模式 \(a\)。但我们不可能枚举所有模式。在列生成中，我们从一个小的模式集合开始，然后通过求解定价子问题来寻找有“负缩减成本”的新模式加入主问题。为了做到这一点，我们需要获取当前 RMP 解的对偶变量值。回到标准形式：即使我们直接使用物品变量，列生成依然可行。关键在于，线性规划松弛的 RMP 不需要包含所有物品变量。我们从一个初始的物品子集 \(S\) 开始。为了让松弛有意义，我们必须加上上界约束 \(\tilde{x}_ j \leq 1\)。这样，RMP 就是一个标准的带界约束的线性规划。初始RMP修正版：假设初始集合 \(S\) 包含 \(k\) 个物品。 \[ \text{(RMP)} \quad \max \sum_ {j \in S} p_ j \tilde{x} j \] \[ \text{s.t.} \quad \sum {j \in S} w_ {ij} \tilde{x}_ j \leq W_ i, \quad \forall i = 1, ..., m \quad (\text{主约束，对偶变量记为 } \pi_ i) \] \[ \tilde{x}_ j \leq 1, \quad \forall j \in S \quad (\text{上界约束，对偶变量记为 } \sigma_ j) \] \[ \tilde{x}_ j \geq 0, \quad \forall j \in S \] 步骤二：求解限制性主问题并获取对偶变量我们使用单纯形法或内点法求解当前的 RMP（它是一个线性规划）。得到最优解 \(\boldsymbol{\tilde{x}^* }\) 和对应的最优对偶变量值。 \(\boldsymbol{\pi_ i^* }\)：对应每种资源 \(i\) 的容量约束的影子价格（边际价值）。 \(\boldsymbol{\sigma_ j^* }\)：对应每个已考虑物品 \(j \in S\) 的上界约束的影子价格。这些对偶变量的经济意义是： \(\pi_ i\)：资源 \(i\) 每增加一单位容量所能带来的目标函数（总价值）的增量。 \(\sigma_ j\)：物品 \(j\) 的上界约束每放松一单位（即允许选择超过1个）带来的价值增量。对于0-1问题，这通常与物品的“吸引力”有关。步骤三：构建并求解定价子问题定价子问题的任务是：在所有未加入 RMP 的物品（即 \(j \notin S\)）中，找到一个或一组物品，其“加入”到当前 RMP 中能够改善目标函数值。在线性规划中，判断一个新变量（列）能否改善当前最优解的标准是看它的缩减成本。对于原问题中的任意物品 \(j\)（无论是否在 \(S\) 中），其对应的变量 \(x_ j\) 在完整的主问题中，其目标函数系数是 \(p_ j\)，在约束矩阵中，它在：每个资源约束 \(i\) 中的系数是 \(w_ {ij}\)。它自身有一个上界约束 \(x_ j \leq 1\)，这个约束在完整问题中也存在，但它是“列的一部分”，更准确地说，在 RMP 中我们显式写出了已考虑物品的上界约束。对于尚未在 RMP 中的物品 \(t \notin S\)，其缩减成本 \(rc_ t\) 的计算公式为： \[ rc_ t = p_ t - \sum_ {i=1}^{m} \pi_ i^* w_ {it} - \sigma_ t \] 等等，这里 \(\sigma_ t\) 是什么？\(\sigma_ t\) 是变量 \(x_ t\) 的上界约束（\(x_ t \leq 1\)）对应的对偶变量。关键在于，当物品 \(t\) 还不在 RMP 中时，其上界约束 \(x_ t \leq 1\) 也还未加入 RMP，因此它当前没有对应的对偶变量 \(\sigma_ t\)。在计算新列的缩减成本时，我们只考虑那些在当前 RMP 中已存在的约束对应的对偶变量。上界约束 \(x_ t \leq 1\) 是“伴随”变量 \(x_ t\) 出现的，只有当变量被加入时，这个约束才会被“激活”或显式加入。更准确的计算方式是：在新变量（列） \(x_ t\) 对应的约束系数向量是 \(\mathbf{a_ t} = [ w_ {1t}, w_ {2t}, ..., w_ {mt}, 1]^T\)，它需要满足前 \(m\) 个资源约束和一个隐含的上界约束。在RMP的对偶视角下，我们已有前 \(m\) 个约束的对偶变量 \(\boldsymbol{\pi}\)。上界约束 \(x_ t \leq 1\) 是一个“简单的界”，在单纯形法中，非基变量的缩减成本计算只考虑主约束（资源约束）的对偶价格。实际上，对于一个新变量 \(x_ t\)，其缩减成本为： \[ rc_ t = p_ t - \sum_ {i=1}^{m} \pi_ i^* w_ {it} \] 如果 \(rc_ t > 0\)，那么将 \(x_ t\) 作为基变量引入（设为一个很小的正数）可以改善目标函数值（因为最大化问题中，检验数为正的非基变量进基会使目标增加）。因此，定价子问题就是寻找一个物品 \(j \notin S\)，使得其缩减成本 \(rc_ j = p_ j - \sum_ {i=1}^{m} \pi_ i^* w_ {ij} > 0\)，并且最大。子问题数学模型： \[ \text{(Pricing SP)} \quad \max_ {j \notin S} \left\{ p_ j - \sum_ {i=1}^{m} \pi_ i^* w_ {ij} \right\} \] 等价于： \[ \zeta = \max_ {j \notin S} \left\{ p_ j - \sum_ {i=1}^{m} \pi_ i^* w_ {ij} \right\} \] 求解：我们只需遍历所有不在 \(S\) 中的物品 \(j\)，计算 \(p_ j - \sum_ {i=1}^{m} \pi_ i^* w_ {ij}\)，并找到最大值 \(\zeta\)。这是一个非常简单的计算过程。步骤四：判断与迭代判断准则：如果 \(\zeta > 0\)，说明找到了一个缩减成本为正的物品（记为 \(j^ \)）。将这个物品对应的变量（列）加入 RMP 中。具体来说，在 RMP 中新增一个变量 \(\tilde{x}_ {j^ }\)，其目标系数为 \(p_ {j^ }\)，在第 \(i\) 个资源约束中的系数为 \(w_ {i, j^ }\)，并为其新增一个上界约束 \(\tilde{x}_ {j^* } \leq 1\)。如果 \(\zeta \leq 0\)，说明对于所有未考虑的物 \(j \notin S\)，都有 \(p_ j - \sum_ {i=1}^{m} \pi_ i^* w_ {ij} \leq 0\)。这意味着当前 RMP 的解已经达到了完整线性规划松弛的最优解。因为所有不在基中的变量（包括已考虑的非基变量和未考虑的变量）的检验数都非正（对于最大化问题），满足线性规划的最优性条件。迭代：如果找到 \(j^* \)，将其加入集合 \(S\)，更新 RMP，返回步骤二。如果 \(\zeta \leq 0\)，则列生成过程结束。我们得到了原整数规划问题的线性规划松弛最优解 \(\boldsymbol{\tilde{x} {LP}^* }\) 和最优值 \(Z {LP}^* \)。步骤五：获得整数解（分枝定界框架）列生成通常用于求解线性规划松弛。要得到原0-1整数规划的最优解或高质量可行解，需要将列生成嵌入到分枝定界框架中，形成分枝定价。根节点：我们运行上述列生成过程，得到线性规划松弛最优解 \(Z_ {LP}^ \) 和对应的分数解 \(\tilde{x}^ \)。分枝：如果 \(\tilde{x}^* \) 中所有变量都是0或1，则找到了一个整数最优解。否则，选择一个分数变量 \(\tilde{x}_ j\)（其值在0和1之间），创建两个子节点：左子节点：添加约束 \(x_ j = 0\)。右子节点：添加约束 \(x_ j = 1\)。定界与剪枝：在每个子节点上，再次运行列生成算法来求解带有新约束（\(x_ j = 0\) 或 \(x_ j = 1\)）的线性规划松弛。新约束会影响定价子问题：如果 \(x_ j = 0\)，则在后续的定价子问题中，简单地禁止物品 \(j\) 被选中。如果 \(x_ j = 1\)，则相当于已经选择了物品 \(j\)，需要从资源容量中扣除 \(w_ {ij}\)，并在定价子问题中禁止物品 \(j\) 再次被选中。同时，RMP的初始解中可以固定这个变量为1。继续搜索：在整个分枝定界树中，不断选择节点、分枝、调用列生成求解松弛、更新全局上下界，直到找到最优整数解或满足时间/精度要求。总结与启示核心思想：列生成通过解决一个包含少量变量的主问题和一个用于生成新变量的子问题，避免了直接处理大规模变量集，特别适合物品/方案数量巨大的组合优化问题。关键技术点： Dantzig-Wolfe分解：将原问题重构为基于“模式”的主问题。对偶变量：主问题解提供的影子价格是子问题寻找改善方向的“指南针”。定价子问题：通常是一个相对容易的优化问题（本例中是简单的遍历计算），其目标是找到检验数最优的新列。最优性条件：当子问题找不到检验数为正的列时，当前主问题的解就是完整松弛问题的最优解。应用扩展：本例展示的是最基本的列生成框架。在实际的多维背包问题中，如果物品数量极大（例如上亿），遍历所有物品计算缩减成本可能仍然很慢。此时，定价子问题本身可能就是一个复杂的优化问题（例如一个背包问题），需要设计专门的算法快速求解。此外，分枝定价是获得整数解的标准方法。通过这个例子，你可以看到列生成算法如何将一个变量规模极大的整数规划问题，转化为一系列规模可控的线性规划子问题和一个简单的定价问题，从而实现了高效求解。