列生成算法在设施选址问题中的应用示例 题目描述 考虑一个设施选址问题：某公司需要在全国范围内建立配送中心来服务多个客户点。已知有m个潜在的设施选址点和n个客户点。每个候选设施点i有一个固定的开设成本f_ i，若在该点建设配送中心则需要支付此费用。每个客户点j有需求d_ j。从设施点i到客户点j的单位运输成本为c_ ij。公司的目标是选择开设哪些设施，并决定如何从开设的设施向客户分配需求，使得在满足所有客户需求的前提下，总成本（固定开设成本+运输成本）最小。 解题过程 1. 问题建模 这是一个经典的设施选址问题，可以建立如下整数规划模型： 决策变量： y_ i ∈ {0,1}：是否在位置i开设设施（1表示开设，0表示不开设） x_ ij ≥ 0：从设施i满足客户j的需求量 目标函数：min Σ_ i f_ i y_ i + Σ_ i Σ_ j c_ ij x_ ij 约束条件： 每个客户的需求必须被满足：Σ_ i x_ ij = d_ j, ∀j 只能从已开设的设施提供服务：x_ ij ≤ d_ j y_ i, ∀i,j 变量取值范围：y_ i ∈ {0,1}, x_ ij ≥ 0 2. 列生成方法的应用思路 由于问题规模很大时（设施点和客户点都很多），完整的模型变量和约束数量会非常庞大，直接求解很困难。我们可以采用列生成方法： 将原问题分解为： 主问题（Master Problem）：决定开设哪些设施（y_ i变量） 定价子问题（Pricing Subproblem）：为每个未被考虑的设施配置生成"列"，评估其加入主问题是否能改善目标函数 3. 具体求解步骤 步骤1：构造限制主问题（RMP） 初始时，我们只考虑一个设施子集（比如空集或启发式选择的几个设施），建立限制主问题： min Σ_ {i∈S} f_ i y_ i + Σ_ {i∈S} Σ_ j c_ ij x_ ij s.t. Σ_ {i∈S} x_ ij = d_ j, ∀j x_ ij ≤ d_ j y_ i, ∀i∈S, ∀j y_ i ∈ {0,1}, x_ ij ≥ 0, ∀i∈S, ∀j 其中S是当前考虑的设施子集。 步骤2：求解线性松弛 将y_ i的整数约束松弛为0 ≤ y_ i ≤ 1，求解RMP的线性规划松弛，得到最优解和对应的对偶变量值： π_ j：对应客户需求约束Σ_ i x_ ij = d_ j的对偶变量 μ_ ij：对应容量约束x_ ij ≤ d_ j y_ i的对偶变量 步骤3：定价子问题（寻找可进基列） 对于每个不在当前S中的设施点i，我们需要计算其"降低成本"（reduced cost）： 降低成本 = f_ i - Σ_ j μ_ ij d_ j + min Σ_ j (c_ ij - π_ j) x_ ij s.t. 0 ≤ x_ ij ≤ d_ j, ∀j 这个子问题可以分解为对每个客户j独立求解：实际上就是检查如果开设设施i，运输成本c_ ij - π_ j是否能为负。 更精确地，设施i的降低成本计算为： rc_ i = f_ i - Σ_ j μ_ ij d_ j + Σ_ j min(0, c_ ij - π_ j) d_ j 如果存在某个设施i使得rc_ i < 0（严格负），则将该设施加入S，因为它能改善当前解。 步骤4：迭代过程 重复步骤2-3，直到所有设施的降低成本都非负（即没有能改善目标的设施可加入），此时得到原问题线性松弛的最优解。 步骤5：整数解获取 由于设施选址问题是NP难问题，列生成得到的是线性松弛下界。我们需要在此基础上： 使用分支定界法搜索整数解 或者采用启发式方法（如四舍五入+局部搜索）获得高质量的整数解 4. 算法特点分析 优势：避免一次性考虑所有设施，特别适合大规模问题 关键：定价子问题计算高效，可以并行处理 应用：这种方法可扩展到带容量约束的设施选址、多商品流设施选址等变种问题 通过这种列生成方法，我们能够有效求解大规模设施选址问题，在物流网络设计、供应链优化等领域有重要应用价值。