列生成算法

1. 问题引入：大规模线性规划的困境
   想象你需要为一家航空公司制定航班人员排班计划。每个可能的“班次”（例如：飞行员A在周一早上8点从北京飞往上海）就是一个决策变量。这个问题的变量数量会轻易达到数百万甚至上亿个。如果我们试图为这个问题建立一个完整的线性规划模型，并直接用单纯形法求解，那么即使是最强大的计算机也无法在合理时间内完成计算，因为需要存储和操作的模型规模太大了。列生成算法就是专门为解决这类“变量极多”的线性规划问题而设计的。

2. 核心思想：主问题与子问题的分解
   列生成算法的精髓在于“按需生成”。它不在一开始就考虑所有天文数字般的变量，而是将原问题分解为两部分：

   • 限制主问题：我们首先只使用一小部分变量（比如，先随机生成一些可行的班次组合）建立一个简化版的线性规划模型。这个简化模型被称为“限制主问题”。因为变量少，它可以被快速求解。
   • 定价子问题：求解完RMP后，我们需要判断：如果现在把那些我们尚未考虑的、数以亿计的变量（在学术上称为“非基变量”）加入到RMP中，能否让目标函数变得更好？（例如，找到一个更省油或更受飞行员欢迎的班次组合）。这个判断工作就交给了“定价子问题”。子问题的核心任务是，在所有未被考虑的变量中，寻找一个“最有潜力”改善当前目标函数的变量。

3. 关键原理：利用对偶理论进行“寻宝”
   我们如何知道哪个未被考虑的变量是“有潜力”的呢？这依赖于你已经学过的对偶理论。

   • 每个线性规划问题（我们的RMP）都有一个对应的对偶问题。
   • 当RMP求解到最优时，我们会得到一组“对偶变量”的值（也称为“影子价格”）。
   • 在单纯形法中，判断一个非基变量是否应该进入基的准则，是计算它的“检验数”（或称“缩减成本”）。对于一个最小化问题，如果某个变量的检验数为负，说明将它引入模型可以降低总成本。
   • 这个检验数的计算公式，可以直接通过对偶变量的值来构造。因此，定价子问题的目标函数，就是去最小化这个“检验数”。如果子问题能找到一个新的变量，其检验数为负（对于最小化问题），那么这个变量就是“有潜力”的，应该被加入到RMP中。如果子问题的最优值表明所有变量的检验数都非负，那么恭喜你，当前RMP的解就是原大规模问题的最优解！

4. 算法流程：一个迭代的循环
   列生成算法遵循一个清晰的迭代步骤：

   • 步骤1：初始化。构造一个初始的RMP，它只需要包含能让问题有可行解的少量变量即可。
   • 步骤2：求解限制主问题。求解当前的RMP，得到最优解和对应的对偶变量的值。
   • 步骤3：求解定价子问题。利用步骤2中获得的对偶变量值，构建并求解定价子问题。子问题的目标是寻找检验数为负最多的变量（即，对目标函数改进最大的变量）。
   • 步骤4：判断收敛。
     • 如果子问题找到了这样的变量（检验数为负），将这个变量（及其在目标函数和约束中的系数，即“列”）加入到RMP中。然后，返回步骤2。
     • 如果子问题找不到检验数为负的变量（即子问题的最优值满足最优性条件），则算法终止。当前RMP的解就是原问题的最优解。

5. 总结与典型应用
   列生成算法是一种非常强大的精确算法框架。它通过巧妙地分解问题，并利用对偶理论来指导搜索方向，避免了直接处理海量变量，从而解决了传统方法无法应对的超大规模优化问题。

   • 切割库存问题：将固定长度的大卷材料切割成不同尺寸的小订单，如何切割使得使用的大卷材料总数最少？每种切割方式就是一个变量，可能的切割方式数量巨大。
   • 车辆路径规划：为车队设计最优的送货路线，使得总行驶距离最短。每条可行的路线就是一个变量。
   • 人员排班：如前所述的航空公司机组人员、司机、客服等的排班问题。

   简而言之，列生成是解决“变量太多，无法枚举”这类组合优化问题的利器。