基于线性规划的“供应链网络设计中的设施选址与容量规划”建模与求解示例
我将为你讲解一个线性规划在供应链网络设计中的重要应用：设施选址与容量规划问题。这个问题旨在决定在哪些地点建设设施（如工厂、仓库），以及每个设施的产能分配，以最小化总成本（包括建设固定成本和运输可变成本），同时满足客户需求。
问题描述
假设一个公司需要为其产品规划一个从生产工厂到客户的供应链网络。
- 潜在工厂地点集合：有 \(m\) 个潜在的工厂选址点，记作 \(i = 1, 2, ..., m\)。
- 客户需求点集合：有 \(n\) 个客户需求点，记作 \(j = 1, 2, ..., n\)。
- 决策变量：
- \(y_i \in \{0, 1\}\)：二元变量。如果我们在地点 \(i\) 建设工厂，则 \(y_i = 1\)；否则为 0。
- \(x_{ij} \geq 0\)：连续变量。表示从工厂 \(i\) 运往客户 \(j\) 的产品数量。
- 已知参数：
- \(f_i\)：在地点 \(i\) 建设工厂的固定成本（与产量无关，只要建设就发生）。
- \(c_{ij}\)：从工厂 \(i\) 到客户 \(j\) 运输单位产品的可变成本。
- \(d_j\)：客户 \(j\) 的需求量。
- \(p_i\)：如果在地点 \(i\) 建设工厂，其最大产能（生产能力上限）。
- 目标：最小化总成本，包括所有建设工厂的固定成本和所有运输路线的可变成本。
- 约束：
- 每个客户的需求必须被完全满足。
- 从一个工厂运出的产品总量不能超过该工厂的产能（如果该工厂被建设）。
- 只有被建设的工厂才能向客户供货（即如果 \(y_i = 0\)，则从该工厂运出的所有 \(x_{ij}\) 必须为 0）。
解题过程
步骤 1: 建立数学模型（混合整数线性规划模型，MILP）
这是一个经典的带容量限制的固定费用设施选址问题（Capacitated Facility Location Problem, CFLP）。其线性规划模型如下：
目标函数（最小化总成本）：
\[\min \sum_{i=1}^{m} f_i y_i + \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} \]
第一部分是总固定成本，第二部分是总运输成本。
约束条件：
- 需求约束：每个客户 \(j\) 的需求必须被满足。
\[ \sum_{i=1}^{m} x_{ij} = d_j, \quad \forall j = 1, ..., n \]
这保证了所有工厂运往客户 $ j $ 的货物总和等于其需求量 $ d_j $。
- 产能与逻辑耦合约束：这是模型的关键，它同时表达了产能限制和“不开厂就不能发货”的逻辑。
\[ \sum_{j=1}^{n} x_{ij} \leq p_i y_i, \quad \forall i = 1, ..., m \]
* 如果 $ y_i = 1 $（建厂），约束变为 $ \sum_{j} x_{ij} \leq p_i $，即运出总量不超过产能 $ p_i $。
* 如果 $ y_i = 0 $（不建厂），约束变为 $ \sum_{j} x_{ij} \leq 0 $，由于 $ x_{ij} \geq 0 $，这强制所有 $ x_{ij} = 0 $。
- 变量类型约束：
\[ y_i \in \{0, 1\}, \quad \forall i = 1, ..., m \]
\[ x_{ij} \geq 0, \quad \forall i = 1, ..., m, \quad \forall j = 1, ..., n \]
步骤 2: 模型解释与特性分析
这个模型是一个混合整数线性规划，因为变量 \(y_i\) 是二元的（整数），而 \(x_{ij}\) 是连续的。
- 核心耦合：约束
∑_j x_ij ≤ p_i * y_i是非线性的（变量乘积），但由于 \(y_i\) 是二元变量，我们可以将其线性化地表示出来。它本质上是一个“大M”约束，这里的 \(M\) 就是产能 \(p_i\)。 - 权衡决策：模型的核心是权衡固定成本和运输成本。开设更多工厂（高固定成本）可能使工厂离客户更近（低运输成本）；反之，开设较少工厂（低固定成本）可能导致运输距离变长（高运输成本）。模型通过优化自动找到这个平衡点。
步骤 3: 求解方法概述
由于是 MILP 问题，通常不能直接用单纯形法等只适用于连续线性规划的方法求解。标准求解流程如下：
-
松弛与分支定界（Branch and Bound, B&B）：这是商用求解器（如 Gurobi, CPLEX）求解此类问题的核心框架。
- 线性规划松弛：首先，暂时忽略 \(y_i\) 的二元约束，将其松弛为 \(0 \leq y_i \leq 1\)。这样得到一个普通的线性规划问题，可以用单纯形法高效求解。松弛问题的最优解提供了原 MILP 问题的一个下界（对于最小化问题）。
- 分支：如果松弛解中某个 \(y_i^*\) 是分数（比如 0.6），则创建两个子问题：一个强制 \(y_i = 0\)，另一个强制 \(y_i = 1\)。这相当于将原问题的可行域一分为二。
- 定界与剪枝：在每个子节点上继续求解线性规划松弛。整个过程形成一棵搜索树。我们记录当前找到的最好整数可行解的目标值作为上界。如果一个节点的松弛解值已经超过当前上界，则该节点不可能产生更好的整数解，可以“剪枝”掉，停止探索该分支。
- 遍历：系统性地分支、求解、定界、剪枝，直到找到最优的整数解或满足预设的精度/时间限制。
-
启发式与元启发式方法：对于大规模问题，精确的 B&B 可能太慢。常用启发式方法先快速找到一个较好的可行解（为上界提供一个更紧的值，帮助剪枝），例如：
- 贪婪添加法：初始不开放任何设施。依次尝试开放能最大程度降低总成本（固定+运输）的设施，直到成本无法降低为止。
- 贪婪丢弃法：初始开放所有设施。依次尝试关闭能最大程度降低成本（或成本增加最少）的设施。
- 局部搜索/模拟退火：在给定设施开闭组合下，用线性规划（或简单的分配规则）求解运输子问题得到成本，然后通过交换、开/闭单个设施等邻域操作寻找更优解。
步骤 4: 一个简化数值示例
假设有 2 个潜在工厂 (\(i = 1, 2\)) 和 3 个客户 (\(j = A, B, C\))。
- 固定成本: \(f_1 = 100, f_2 = 80\)
- 产能: \(p_1 = 80, p_2 = 70\)
- 需求量: \(d_A = 40, d_B = 30, d_C = 50\)（总计 120）
- 运输成本 \(c_{ij}\)：
从\到 A B C 工厂1 4 5 6 工厂2 7 3 4
问题分析：总需求 120 > 单个工厂最大产能（80或70），所以至少需要开设两个工厂才能满足所有需求。
模型建立：
\[\min 100y_1 + 80y_2 + (4x_{1A}+5x_{1B}+6x_{1C}) + (7x_{2A}+3x_{2B}+4x_{2C}) \]
约束：
- \(x_{1A} + x_{2A} = 40\)
- \(x_{1B} + x_{2B} = 30\)
- \(x_{1C} + x_{2C} = 50\)
- \(x_{1A}+x_{1B}+x_{1C} \leq 80y_1\)
- \(x_{2A}+x_{2B}+x_{2C} \leq 70y_2\)
- \(y_1, y_2 \in \{0,1\}; \quad x_{ij} \geq 0\)
逻辑推理求解：
由于必须开两个厂 (\(y_1 = y_2 = 1\))，固定成本为 \(100 + 80 = 180\)。
剩下是运输分配问题，是一个标准的运输线性规划：
目标：\(\min 4x_{1A}+5x_{1B}+6x_{1C}+7x_{2A}+3x_{2B}+4x_{2C}\)
需求约束 (1)(2)(3) 和产能约束 (4)(5)（此时变为 \(\sum_j x_{1j} \leq 80, \sum_j x_{2j} \leq 70\)）。
观察运输成本：
- 对于客户A，工厂1成本(4) < 工厂2成本(7)，应尽量从工厂1发货：令 \(x_{1A} = 40\)。
- 对于客户B，工厂2成本(3) < 工厂1成本(5)，应尽量从工厂2发货：令 \(x_{2B} = 30\)。
- 对于客户C，工厂2成本(4) < 工厂1成本(6)，应尽量从工厂2发货。但工厂2已发货30给B，剩余产能 \(70-30=40\)，所以 \(x_{2C} = 40\)。
- 客户C还差 \(50-40=10\) 的需求，由工厂1满足：\(x_{1C} = 10\)。
- 工厂1总发货：\(40 + 0 + 10 = 50 \leq 80\)，产能充足。
最优解：
\(y_1=1, y_2=1\)
\(x_{1A}=40, x_{1B}=0, x_{1C}=10\)
\(x_{2A}=0, x_{2B}=30, x_{2C}=40\)
总成本 = 固定成本 180 + 运输成本 \((4*40 + 6*10) + (3*30 + 4*40) = (160+60) + (90+160) = 220 + 250 = 470\)。
因此，最小总成本为 470。
总结
这个例子展示了如何将复杂的供应链战略决策（建不建厂？建多大？如何分配物流？）形式化为一个结构清晰的混合整数线性规划模型。求解过程揭示了 “成本权衡优化” 的本质。对于小规模问题，我们可以通过逻辑分析和求解连续线性规划子问题来得到最优解；对于大规模现实问题，则需要依赖分支定界框架和启发式算法在商业求解器中高效求解。该模型是供应链管理、物流网络设计等领域的基石模型之一。