广义线性规划
字数 1890 2025-12-18 11:02:52

广义线性规划

第一步：从线性规划到更一般的视角
线性规划（LP）的标准形式是：

\[\min c^T x \quad \text{s.t.} \quad Ax = b,\ x \geq 0, \]

其中目标函数和约束均为线性。广义线性规划（Generalized Linear Programming, GLP） 扩展了这一框架，允许目标函数或约束具有更一般的结构，但保留“线性”的核心思想。其关键特征是通过主问题（master problem） 和列生成（column generation） 来隐式处理可能无限或指数级多的变量，适用于变量维度极高但约束相对较少的场景。

第二步：GLP的问题形式化表述
GLP通常定义为以下形式：

\[\min \sum_{j \in J} c_j \lambda_j \quad \text{s.t.} \quad \sum_{j \in J} A_j \lambda_j = b,\ \lambda_j \geq 0\ (\forall j \in J), \]

其中：

  • 决策变量 \(\lambda_j\) 对应一个决策方案（称为“列”或“活动”），\(j\) 属于指标集 \(J\)，\(J\) 可能非常大（甚至无限）。
  • 每个列 \(j\) 关联一个成本 \(c_j\) 和一个列向量 \(A_j\)（维度等于约束个数）。
  • 约束是这些列的线性组合，右侧为常向量 \(b\)。

关键点：列集 \(J\) 通常不显式列出，而是通过一个生成子问题（subproblem） 动态生成“有益”的列。

第三步：GLP的求解机制——列生成与对偶信息
由于列的数量巨大，直接求解不可行。GLP采用迭代方法：

  1. 限制性主问题（Restricted Master Problem, RMP）：
    初始选取 \(J\) 的一个小子集 \(J' \subset J\)，用这些列构建一个较小的线性规划并求解，得到最优解 \(\lambda^*\) 和对偶变量 \(\pi^*\)（对应约束的乘子）。
  2. 定价子问题（Pricing Subproblem）：
    利用对偶变量 \(\pi^*\)，求解子问题：

\[ \min_{j \in J} (c_j - \pi^* A_j) \quad \text{或等价形式} \quad \min_{y \in Y} (c(y) - \pi^* A(y)), \]

其中 \(Y\) 是列生成的空间（如路径、模式等集合），\(c(y)\) 和 \(A(y)\) 是列参数化表示。
3. 终止条件：
若子问题的最优值 \(\geq 0\)（对最小化问题），则当前RMP的解已是全局最优；否则，将生成的新列（对应负检验数的列）加入 \(J'\)，返回步骤1。

第四步：几何解释与经济学含义

  • 几何视角：可行域是列向量 \(\{A_j\}\) 的凸锥（非负组合）与仿射子空间 \(Ax=b\) 的交集。GLP通过逐步扩展凸锥的生成元（即列）来逼近最优解。
  • 经济学类比：对偶变量 \(\pi\) 可视为资源“影子价格”。子问题寻找“成本低于当前资源估值”的新活动，类似于市场中的套利过程；当无套利机会时达到均衡（最优）。

第五步：典型应用场景

  1. 切割库存问题（Cutting Stock Problem）：
    用标准长度的原材料切割成不同需求的小段，每列对应一种切割模式，列生成动态生成高效模式。
  2. 机组人员排班（Crew Scheduling）：
    每列为一条合法的任务序列（满足工时、休息等规则），列生成枚举可行序列的子集。
  3. 多商品流（Multicommodity Flow）：
    每列对应一种商品的一条路径，主问题分配流量，子问题求最短路（基于边的对偶价格）。

第六步：与相关方法的对比

  • 与Dantzig-Wolfe分解：GLP本质是Dantzig-Wolfe分解在主问题为线性时的特例，将原问题分解为RMP和子问题。
  • 与单纯形法的关系：GLP的列生成可视为单纯形法在变量极多时的实现——单纯形法的“进基变量选择”通过求解子问题完成。
  • 局限性：收敛速度依赖子问题的难易，可能需多次迭代；对偶变量的振荡可能影响效率，常需结合稳定化技术。

总结
广义线性规划通过主问题-子问题的迭代框架，将大规模线性规划中“列”的生成延迟到需要时，适用于组合结构明显、变量呈指数增长的问题。其核心思想是利用对偶信息指导列的生成，兼具线性规划的清晰结构和处理复杂问题的灵活性。

广义线性规划 第一步：从线性规划到更一般的视角 线性规划（LP）的标准形式是： \[ \min c^T x \quad \text{s.t.} \quad Ax = b,\ x \geq 0, \] 其中目标函数和约束均为线性。 广义线性规划（Generalized Linear Programming, GLP） 扩展了这一框架，允许目标函数或约束具有更一般的结构，但保留“线性”的核心思想。其关键特征是通过 主问题（master problem） 和 列生成（column generation） 来隐式处理可能无限或指数级多的变量，适用于变量维度极高但约束相对较少的场景。 第二步：GLP的问题形式化表述 GLP通常定义为以下形式： \[ \min \sum_ {j \in J} c_ j \lambda_ j \quad \text{s.t.} \quad \sum_ {j \in J} A_ j \lambda_ j = b,\ \lambda_ j \geq 0\ (\forall j \in J), \] 其中： 决策变量 \(\lambda_ j\) 对应一个决策方案（称为“列”或“活动”），\(j\) 属于指标集 \(J\)，\(J\) 可能非常大（甚至无限）。 每个列 \(j\) 关联一个成本 \(c_ j\) 和一个列向量 \(A_ j\)（维度等于约束个数）。 约束是这些列的线性组合，右侧为常向量 \(b\)。 关键点 ：列集 \(J\) 通常不显式列出，而是通过一个 生成子问题（subproblem） 动态生成“有益”的列。 第三步：GLP的求解机制——列生成与对偶信息 由于列的数量巨大，直接求解不可行。GLP采用迭代方法： 限制性主问题（Restricted Master Problem, RMP） ： 初始选取 \(J\) 的一个小子集 \(J' \subset J\)，用这些列构建一个较小的线性规划并求解，得到最优解 \(\lambda^ \) 和对偶变量 \(\pi^ \)（对应约束的乘子）。 定价子问题（Pricing Subproblem） ： 利用对偶变量 \(\pi^ \)，求解子问题： \[ \min_ {j \in J} (c_ j - \pi^ A_ j) \quad \text{或等价形式} \quad \min_ {y \in Y} (c(y) - \pi^* A(y)), \] 其中 \(Y\) 是列生成的空间（如路径、模式等集合），\(c(y)\) 和 \(A(y)\) 是列参数化表示。 终止条件 ： 若子问题的最优值 \(\geq 0\)（对最小化问题），则当前RMP的解已是全局最优；否则，将生成的新列（对应负检验数的列）加入 \(J'\)，返回步骤1。 第四步：几何解释与经济学含义 几何视角 ：可行域是列向量 \(\{A_ j\}\) 的凸锥（非负组合）与仿射子空间 \(Ax=b\) 的交集。GLP通过逐步扩展凸锥的生成元（即列）来逼近最优解。 经济学类比 ：对偶变量 \(\pi\) 可视为资源“影子价格”。子问题寻找“成本低于当前资源估值”的新活动，类似于市场中的套利过程；当无套利机会时达到均衡（最优）。 第五步：典型应用场景 切割库存问题（Cutting Stock Problem） ： 用标准长度的原材料切割成不同需求的小段，每列对应一种切割模式，列生成动态生成高效模式。 机组人员排班（Crew Scheduling） ： 每列为一条合法的任务序列（满足工时、休息等规则），列生成枚举可行序列的子集。 多商品流（Multicommodity Flow） ： 每列对应一种商品的一条路径，主问题分配流量，子问题求最短路（基于边的对偶价格）。 第六步：与相关方法的对比 与Dantzig-Wolfe分解 ：GLP本质是Dantzig-Wolfe分解在主问题为线性时的特例，将原问题分解为RMP和子问题。 与单纯形法的关系 ：GLP的列生成可视为单纯形法在变量极多时的实现——单纯形法的“进基变量选择”通过求解子问题完成。 局限性 ：收敛速度依赖子问题的难易，可能需多次迭代；对偶变量的振荡可能影响效率，常需结合稳定化技术。 总结 广义线性规划通过 主问题-子问题 的迭代框架，将大规模线性规划中“列”的生成延迟到需要时，适用于组合结构明显、变量呈指数增长的问题。其核心思想是 利用对偶信息指导列的生成 ，兼具线性规划的清晰结构和处理复杂问题的灵活性。