基于线性规划的“最小成本运输问题”的建模与求解示例
我将为你讲解线性规划中的一个经典应用——运输问题，重点是最小成本运输问题。这个题目虽然基础，但能很好地展示线性规划的建模思想和求解方法。
一、 问题描述
考虑一个典型的物流场景：
- 有 \(m\) 个供应点（例如工厂、仓库），每个供应点 \(i\) 的货物供应量为 \(a_i\) 个单位。
- 有 \(n\) 个需求点（例如市场、分销中心），每个需求点 \(j\) 的货物需求量为 \(b_j\) 个单位。
- 假设总供应量等于总需求量，即 \(\sum_{i=1}^{m} a_i = \sum_{j=1}^{n} b_j\)。这是一个平衡运输问题。如果不等，可以通过添加虚拟供应点或需求点来平衡，这是后续的扩展。
- 从供应点 \(i\) 运输一个单位货物到需求点 \(j\) 的成本是 \(c_{ij}\)。
- 目标：在满足所有供应量和需求量的约束下，确定从每个供应点到每个需求点的运输量 \(x_{ij}\)，使得总运输成本最小。
这是一个典型的、可以精确地用线性规划建模和求解的问题。
二、 建立线性规划模型
我们循序渐进地构建数学模型。
步骤1：定义决策变量
设 \(x_{ij} \ge 0\) 表示从供应点 \(i\) 运输到需求点 \(j\) 的货物量。其中 \(i = 1, ..., m\)， \(j = 1, ..., n\)。这是我们要寻找的解。
步骤2：确立目标函数
总成本是每条运输路径 \(i \to j\) 的成本 \(c_{ij}\) 乘以运量 \(x_{ij}\) 的总和。目标是使其最小化。
\[\text{Minimize } Z = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} \]
步骤3：列出约束条件
- 供应约束：从每个供应点 \(i\) 运出的总货物量不能超过其供应量 \(a_i\)。
\[ \sum_{j=1}^{n} x_{ij} = a_i, \quad \forall i = 1,...,m \]
注意这里用等号，因为我们假设在最优方案下，所有供应点的货物都会被运出（平衡条件下，这是合理的，且可避免不必要库存）。
- 需求约束：运到每个需求点 \(j\) 的总货物量必须恰好满足其需求量 \(b_j\)。
\[ \sum_{i=1}^{m} x_{ij} = b_j, \quad \forall j = 1,...,n \]
- 非负约束：运输量不能为负。
\[ x_{ij} \ge 0, \quad \forall i, j \]
步骤4：完整数学模型
将以上整合，得到标准形式的线性规划模型：
\[\begin{aligned} & \underset{x_{ij}}{\text{minimize}} & & Z = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} \\ & \text{subject to} & & \sum_{j=1}^{n} x_{ij} = a_i, \quad i = 1,\ldots,m \quad \text{(供应约束)} \\ & & & \sum_{i=1}^{m} x_{ij} = b_j, \quad j = 1,\ldots,n \quad \text{(需求约束)} \\ & & & x_{ij} \ge 0, \quad i = 1,\ldots,m, \; j = 1,\ldots,n. \quad \text{(非负约束)} \end{aligned} \]
模型特点：这个线性规划模型具有特殊的结构。其约束矩阵的系数全部是0或1，并且每列恰好有两个1（一个在供应约束行，一个在需求约束行）。这个结构保证了它的基本可行解是整数解（当所有 \(a_i, b_j\) 为整数时），这也是运输问题的一个重要性质。
三、 具体算例与求解过程
让我们通过一个具体例子，手把手演示求解。
问题数据：
- 供应点：S1（供应量 20），S2（供应量 30）。总供应=50。
- 需求点：D1（需求量 10），D2（需求量 28），D3（需求量 12）。总需求=50。
- 单位运输成本 \(c_{ij}\)（矩阵）：
| 从\到 | D1 | D2 | D3 |
|---|---|---|---|
| S1 | 4 | 5 | 3 |
| S2 | 6 | 2 | 4 |
步骤1：建立该实例的数学模型
设 \(x_{11}, x_{12}, x_{13}\) 为S1到D1,D2,D3的运量，\(x_{21}, x_{22}, x_{23}\) 为S2到D1,D2,D3的运量。
目标：最小化 \(Z = 4x_{11} + 5x_{12} + 3x_{13} + 6x_{21} + 2x_{22} + 4x_{23}\)
约束：
- S1供应：\(x_{11} + x_{12} + x_{13} = 20\)
- S2供应：\(x_{21} + x_{22} + x_{23} = 30\)
- D1需求：\(x_{11} + x_{21} = 10\)
- D2需求：\(x_{12} + x_{22} = 28\)
- D3需求：\(x_{13} + x_{23} = 12\)
- 非负：\(x_{ij} \ge 0\)
步骤2：寻找初始基本可行解（西北角法）
我们可以用专门针对运输问题的简化单纯形法（表上作业法）。首先找一个初始调运方案。
- 西北角法：从表格的西北角（左上角）开始分配。
- 比较S1供应(20)和D1需求(10)，分配 \(x_{11} = \min(20, 10) = 10\)。D1满足，划去D1列。S1剩余10。
- 移动到右边格子(S1, D2)。比较S1剩余(10)和D2需求(28)，分配 \(x_{12} = \min(10, 28) = 10\)。S1耗尽，划去S1行。D2剩余18。
- 移动到下方格子(S2, D2)。比较S2供应(30)和D2剩余(18)，分配 \(x_{22} = \min(30, 18) = 18\)。D2满足，划去D2列。S2剩余12。
- 移动到右边格子(S2, D3)。比较S2剩余(12)和D3需求(12)，分配 \(x_{23} = \min(12, 12) = 12\)。完成。
得到初始方案：\(x_{11}=10, x_{12}=10, x_{22}=18, x_{23}=12\)，其余为0。总成本 \(Z_0 = 4*10 + 5*10 + 2*18 + 4*12 = 40+50+36+48=174\)。
步骤3：最优性检验（位势法/对偶变量法）
我们计算每个供应点 \(i\) 的对偶变量（位势）\(u_i\) 和每个需求点 \(j\) 的位势 \(v_j\)，使得对于所有有基变量（有运量）的格子 \((i, j)\)，满足 \(c_{ij} = u_i + v_j\)。通常设 \(u_1 = 0\)。
- 基变量 \(x_{11}\): \(4 = u_1 + v_1 = 0 + v_1 \Rightarrow v_1 = 4\)
- 基变量 \(x_{12}\): \(5 = u_1 + v_2 = 0 + v_2 \Rightarrow v_2 = 5\)
- 基变量 \(x_{22}\): \(2 = u_2 + v_2 = u_2 + 5 \Rightarrow u_2 = -3\)
- 基变量 \(x_{23}\): \(4 = u_2 + v_3 = -3 + v_3 \Rightarrow v_3 = 7\)
然后，对每个非基变量（当前运量为0的格子），计算检验数 \(\sigma_{ij} = c_{ij} - (u_i + v_j)\)。在最小化问题中，如果所有 \(\sigma_{ij} \ge 0\)，则当前解最优。
- \(\sigma_{13} = c_{13} - (u_1+v_3) = 3 - (0+7) = -4\) < 0
- \(\sigma_{21} = c_{21} - (u_2+v_1) = 6 - ((-3)+4) = 5 > 0\)
由于 \(\sigma_{13} = -4 < 0\)，将 \(x_{13}\) 引入基中可以降低总成本，当前解非最优。
步骤4：方案改进（闭回路调整法）
找到非基变量 \(x_{13}\) 对应的闭回路。回路是：从 \(x_{13}\) 出发，沿水平或垂直方向，只能拐到有基变量的格子，最后回到起点。这个回路是：\(x_{13} \to x_{12} \to x_{22} \to x_{23} \to x_{13}\)。
在回路的偶数顶点（\(x_{12}, x_{23}\)）中寻找最小的运量：\(\min(x_{12}=10, x_{23}=12) = 10\)。
进行运量调整：回路奇数顶点（\(x_{13}, x_{22}\)）增加调整量 10，偶数顶点减少调整量 10。
得到新方案：
- \(x_{11} = 10\) (不变)
- \(x_{12} = 10 - 10 = 0\) (变为非基变量)
- \(x_{13} = 0 + 10 = 10\) (新基变量)
- \(x_{22} = 18 + 10 = 28\)
- \(x_{23} = 12 - 10 = 2\)
- \(x_{21} = 0\) (不变)
新总成本 \(Z_1 = 4*10 + 3*10 + 2*28 + 4*2 = 40 + 30 + 56 + 8 = 134\)。相比之前的174，成本显著下降。
步骤5：再次检验最优性
重新计算位势（设 \(u_1=0\)）：
- \(x_{11}: 4=0+v_1 \Rightarrow v_1=4\)
- \(x_{13}: 3=0+v_3 \Rightarrow v_3=3\)
- \(x_{22}: 2=u_2+5\)? 等一下，需要先通过其他路径求 \(v_2\)。我们有 \(x_{23}: 4=u_2+3 \Rightarrow u_2=1\)。
- 然后 \(x_{22}: 2=1+v_2 \Rightarrow v_2=1\)。
计算非基变量检验数：
- \(\sigma_{12} = 5 - (0+1) = 4 > 0\)
- \(\sigma_{21} = 6 - (1+4) = 1 > 0\)
- \(\sigma_{23}\) 现在是基变量，不计算。
所有非基变量的检验数 \(\sigma \ge 0\)。因此，当前解为最优解。
步骤6：解读最优方案
最优运输方案为：
- 从S1运输10单位到D1，10单位到D3。
- 从S2运输28单位到D2，2单位到D3。
最小总运输成本为 134。
四、 总结与扩展
这个“最小成本运输问题”完美展示了线性规划从实际问题建模到数学公式表达，再到系统化求解（虽然我们用了其特殊算法，本质仍是单纯形法思想）的全过程。其核心价值在于提供了一个在复杂供需网络中寻找成本最低物流方案的通用框架。
扩展：
- 不平衡问题：若总供应 > 总需求，可添加一个虚拟需求点，其需求量为差额，到各供应点的成本为0（或存储成本）。若总需求 > 总供应，则添加虚拟供应点。
- 最大化利润问题：如果 \(c_{ij}\) 表示利润，则目标函数改为最大化，最优性检验判据变为所有检验数非正。
- 软件求解：对于大规模问题，可以使用线性规划求解器（如Gurobi, CPLEX, 或开源的GLPK, SciPy）直接输入我们建立的模型进行高效求解。
通过这个例子，你应该能理解如何将一个实际的资源分配问题转化为线性规划模型，并掌握其基本的求解逻辑。