基于线性规划的“最优传输问题”建模与求解示例
字数 4481 2025-12-18 00:19:40

基于线性规划的“最优传输问题”建模与求解示例

我们先从问题背景开始。最优传输问题（Optimal Transport, OT）是运筹学、概率论和计算机视觉等领域的一个重要问题。它研究的是：给定两个概率分布（比如两堆沙子），如何以最小的“搬运成本”将第一个分布变成第二个分布。这里的成本通常用每单位质量从一个位置移动到另一个位置的距离（或更一般地，任意成本）来衡量。

1. 问题描述

我们考虑一个离散形式的最优传输问题，也称为“Earth Mover‘s Distance”或“运输问题”。
假设有 \(m\) 个供应商（供应点），第 \(i\) 个供应商拥有 \(a_i>0\) 单位的某种商品（比如沙子）。
同时有 \(n\) 个消费者（需求点），第 \(j\) 个消费者需要 \(b_j>0\) 单位的该商品。
我们假设总供应等于总需求：\(\sum_{i=1}^{m} a_i = \sum_{j=1}^{n} b_j\)。
从供应商 \(i\) 运输一单位商品到消费者 \(j\) 的成本是 \(c_{ij} \geq 0\)。
我们的目标是找到一个运输计划（一个矩阵 \(X=[x_{ij}]_{m \times n}\)），使得：

  1. 所有供应商的商品都被运出（供应满足）。
  2. 所有消费者的需求都被满足（需求满足）。
  3. 总运输成本最小。

其中，\(x_{ij} \geq 0\) 表示从供应商 \(i\) 运往消费者 \(j\) 的商品数量。

2. 建立线性规划模型

这是一个典型的线性规划问题。我们可以将其形式化地写为：

目标函数（总成本最小化）：

\[\min \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} \]

约束条件：

  1. 供应约束：从每个供应商 \(i\) 运出的总量等于其供应量 \(a_i\)。

\[ \sum_{j=1}^{n} x_{ij} = a_i, \quad \forall i = 1, \dots, m \]

  1. 需求约束：运到每个消费者 \(j\) 的总量等于其需求量 \(b_j\)。

\[ \sum_{i=1}^{m} x_{ij} = b_j, \quad \forall j = 1, \dots, n \]

  1. 非负约束：运输量不能为负。

\[ x_{ij} \geq 0, \quad \forall i, j \]

3. 一个具体的数值例子

假设有2个供应商（\(m=2\)）和3个消费者（\(n=3\)）。
供应量：\(a_1 = 35, a_2 = 25\) 单位。
需求量：\(b_1 = 20, b_2 = 15, b_3 = 25\) 单位。总和为60，供需平衡。
单位运输成本矩阵 \(C = [c_{ij}]\) 如下（从供应商i到消费者j）：

\[C = \begin{bmatrix} 8 & 4 & 6 \\ 5 & 7 & 3 \end{bmatrix} \]

例如，从供应商1运到消费者2的成本是4。

4. 求解过程：运用单纯形法思想循序渐进

第一步：列出完整的线性规划模型

决策变量：\(x_{11}, x_{12}, x_{13}, x_{21}, x_{22}, x_{23}\)。

目标函数：

\[\min Z = 8x_{11} + 4x_{12} + 6x_{13} + 5x_{21} + 7x_{22} + 3x_{23} \]

约束条件：

  1. \(x_{11} + x_{12} + x_{13} = 35\)
  2. \(x_{21} + x_{22} + x_{23} = 25\)
  3. \(x_{11} + x_{21} = 20\)
  4. \(x_{12} + x_{22} = 15\)
  5. \(x_{13} + x_{23} = 25\)
  6. 所有 \(x_{ij} \geq 0\)

第二步：观察与寻找初始可行解

这是一个平衡的运输问题，是线性规划的一种特殊结构。我们可以用更直观的“最小成本法”来找到一个较好的初始基本可行解，这本质上对应了单纯形法的第一阶段。

最小成本法步骤：

  1. 在所有未分配的格子（变量）中，找到单位成本 \(c_{ij}\) 最小的那个。这里，最小值是3，对应变量 \(x_{23}\)。
  2. 尽可能多地分配给它。供应方2有25单位，需求方3需要25单位。所以，令 \(x_{23} = 25\)。这样，供应商2的供应已满足（方程2：\(x_{21}+x_{22}+25=25 \Rightarrow x_{21}=x_{22}=0\)），消费者3的需求也满足（方程5：\(x_{13}+25=25 \Rightarrow x_{13}=0\)）。将第2行和第3列从后续考虑中划去。
  3. 在剩余格子中（第1行和第1、2列），找最小成本。成本为 \(c_{11}=8, c_{12}=4\)，最小是4，对应 \(x_{12}\)。
  4. 分配。供应商1还剩35单位，消费者2需要15单位。所以，令 \(x_{12} = 15\)。消费者2需求满足，划去第2列。供应商1剩余20单位。
  5. 只剩第1行和第1列。将供应商1剩余的20单位全部分配给消费者1。令 \(x_{11} = 20\)。

于是，我们得到初始基本可行解：

\[x_{11}=20, \quad x_{12}=15, \quad x_{13}=0, \quad x_{21}=0, \quad x_{22}=0, \quad x_{23}=25 \]

其他变量为0。

检查所有约束：

  • 行1: 20+15+0=35 ✔
  • 行2: 0+0+25=25 ✔
  • 列1: 20+0=20 ✔
  • 列2: 15+0=15 ✔
  • 列3: 0+25=25 ✔

第三步：检验最优性（计算检验数）

在单纯形法中，我们需要计算非基变量的检验数（Reduced Cost）\(\bar{c}_{ij} = c_{ij} - u_i - v_j\)，其中 \(u_i\) 和 \(v_j\) 是对偶变量（位势），可以通过基变量满足 \(c_{ij} = u_i + v_j\) 来求解。

当前基变量是 \(x_{11}, x_{12}, x_{23}\)。

  1. 令对偶变量 \(u_1 = 0\)（通常设定一个起始值）。
  2. 对于基变量 \(x_{11}\): \(c_{11}=8 = u_1 + v_1 \Rightarrow 0 + v_1 = 8 \Rightarrow v_1 = 8\)
  3. 对于基变量 \(x_{12}\): \(c_{12}=4 = u_1 + v_2 \Rightarrow 0 + v_2 = 4 \Rightarrow v_2 = 4\)
  4. 对于基变量 \(x_{23}\): \(c_{23}=3 = u_2 + v_3\)。我们还没有 \(u_2\) 和 \(v_3\)。我们需要另一个方程。实际上，由于我们划去了行和列，我们需要利用所有基变量。但这里我们只有三个方程，却有四个未知数（\(u_1, u_2, v_1, v_2, v_3\)，但设了\(u_1=0\)）。等等，我们有三行两列，应该有 \(m+n-1=2+3-1=4\) 个基变量。我们只列出了三个。这是因为在运输问题中，当用最小成本法得到一个解时，它可能是一个“退化的”基本可行解（基变量个数少于 m+n-1）。我们需要引入一个“人工基变量”值为0来补足。这里，实际上 \(x_{13}=0\) 也是一个基变量（退化基变量）。所以基变量是 \(\{x_{11}, x_{12}, x_{13}, x_{23}\}\)，其中 \(x_{13}=0\)。

重新计算位势：

  • 设 \(u_1 = 0\)
  • \(x_{11}\): \(8 = u_1 + v_1 \Rightarrow v_1 = 8\)
  • \(x_{12}\): \(4 = u_1 + v_2 \Rightarrow v_2 = 4\)
  • \(x_{13}\): \(6 = u_1 + v_3 \Rightarrow v_3 = 6\)
  • \(x_{23}\): \(3 = u_2 + v_3 = u_2 + 6 \Rightarrow u_2 = -3\)

现在计算非基变量（\(x_{21}, x_{22}\)）的检验数：

  • \(\bar{c}_{21} = c_{21} - u_2 - v_1 = 5 - (-3) - 8 = 0\)
  • \(\bar{c}_{22} = c_{22} - u_2 - v_2 = 7 - (-3) - 4 = 6\)

在最小化问题中，如果所有非基变量的检验数都 \(\geq 0\)，则当前解最优。这里 \(\bar{c}_{21}=0 \geq 0\)，\(\bar{c}_{22}=6 \geq 0\)。所以当前解已经是最优解之一（因为有一个非基变量的检验数为0，可能存在多个最优解）。

第四步：计算最优目标函数值

将最优解代入目标函数：

\[Z^* = 8(20) + 4(15) + 6(0) + 5(0) + 7(0) + 3(25) = 160 + 60 + 0 + 0 + 0 + 75 = 295 \]

5. 结果解释与扩展

我们得到了最优运输计划：

  • 从供应商1运输20单位到消费者1，运输15单位到消费者2，不运到消费者3。
  • 从供应商2运输25单位到消费者3，不运到消费者1和2。
    总最小成本为295。

总结与要点：

  1. 建模核心：最优传输问题（离散形式）可以自然地建模为一个线性规划，其决策变量是运输量，目标是最小化总成本，约束是供应与需求的严格平衡。
  2. 求解特点：虽然可以用通用单纯形法求解，但其特殊的“网络流”结构使得“运输单纯形法”或“位势法”更高效，它通过在表格上操作来寻找改进回路和计算检验数。
  3. 对偶问题：该问题的对偶问题是 \(\max \sum_{i} a_i u_i + \sum_{j} b_j v_j\)，约束为 \(u_i + v_j \leq c_{ij}\)。对偶变量 \(u_i\) 和 \(v_j\) 可以解释为供应商 \(i\) 和消费者 \(j\) 的“影子价格”。我们求解过程中计算的 \(u_i, v_j\) 正是对偶问题的一个可行解。
  4. 应用广泛：除了物流，最优传输问题在图像处理（比较颜色直方图）、统计学（比较概率分布）、机器学习（生成模型）等领域都有重要应用。其连续形式定义了概率分布间的“距离”（Wasserstein距离）。
基于线性规划的“最优传输问题”建模与求解示例 我们先从问题背景开始。最优传输问题（Optimal Transport, OT）是运筹学、概率论和计算机视觉等领域的一个重要问题。它研究的是：给定两个概率分布（比如两堆沙子），如何以最小的“搬运成本”将第一个分布变成第二个分布。这里的成本通常用每单位质量从一个位置移动到另一个位置的距离（或更一般地，任意成本）来衡量。 1. 问题描述 我们考虑一个离散形式的最优传输问题，也称为“Earth Mover‘s Distance”或“运输问题”。 假设有 \(m\) 个供应商（供应点），第 \(i\) 个供应商拥有 \(a_ i>0\) 单位的某种商品（比如沙子）。 同时有 \(n\) 个消费者（需求点），第 \(j\) 个消费者需要 \(b_ j>0\) 单位的该商品。 我们假设总供应等于总需求：\(\sum_ {i=1}^{m} a_ i = \sum_ {j=1}^{n} b_ j\)。 从供应商 \(i\) 运输一单位商品到消费者 \(j\) 的成本是 \(c_ {ij} \geq 0\)。 我们的目标是找到一个 运输计划 （一个矩阵 \(X=[ x_ {ij}]_ {m \times n}\)），使得： 所有供应商的商品都被运出（供应满足）。 所有消费者的需求都被满足（需求满足）。 总运输成本最小。 其中，\(x_ {ij} \geq 0\) 表示从供应商 \(i\) 运往消费者 \(j\) 的商品数量。 2. 建立线性规划模型 这是一个典型的线性规划问题。我们可以将其形式化地写为： 目标函数（总成本最小化）： \[ \min \sum_ {i=1}^{m} \sum_ {j=1}^{n} c_ {ij} x_ {ij} \] 约束条件： 供应约束 ：从每个供应商 \(i\) 运出的总量等于其供应量 \(a_ i\)。 \[ \sum_ {j=1}^{n} x_ {ij} = a_ i, \quad \forall i = 1, \dots, m \] 需求约束 ：运到每个消费者 \(j\) 的总量等于其需求量 \(b_ j\)。 \[ \sum_ {i=1}^{m} x_ {ij} = b_ j, \quad \forall j = 1, \dots, n \] 非负约束 ：运输量不能为负。 \[ x_ {ij} \geq 0, \quad \forall i, j \] 3. 一个具体的数值例子 假设有2个供应商（\(m=2\)）和3个消费者（\(n=3\)）。 供应量：\(a_ 1 = 35, a_ 2 = 25\) 单位。 需求量：\(b_ 1 = 20, b_ 2 = 15, b_ 3 = 25\) 单位。总和为60，供需平衡。 单位运输成本矩阵 \(C = [ c_ {ij} ]\) 如下（从供应商i到消费者j）： \[ C = \begin{bmatrix} 8 & 4 & 6 \\ 5 & 7 & 3 \end{bmatrix} \] 例如，从供应商1运到消费者2的成本是4。 4. 求解过程：运用单纯形法思想循序渐进 第一步：列出完整的线性规划模型 决策变量：\(x_ {11}, x_ {12}, x_ {13}, x_ {21}, x_ {22}, x_ {23}\)。 目标函数： \[ \min Z = 8x_ {11} + 4x_ {12} + 6x_ {13} + 5x_ {21} + 7x_ {22} + 3x_ {23} \] 约束条件： \(x_ {11} + x_ {12} + x_ {13} = 35\) \(x_ {21} + x_ {22} + x_ {23} = 25\) \(x_ {11} + x_ {21} = 20\) \(x_ {12} + x_ {22} = 15\) \(x_ {13} + x_ {23} = 25\) 所有 \(x_ {ij} \geq 0\) 第二步：观察与寻找初始可行解 这是一个平衡的运输问题，是线性规划的一种特殊结构。我们可以用更直观的“最小成本法”来找到一个较好的初始基本可行解，这本质上对应了单纯形法的第一阶段。 最小成本法步骤 ： 在所有未分配的格子（变量）中，找到单位成本 \(c_ {ij}\) 最小的那个。这里，最小值是3，对应变量 \(x_ {23}\)。 尽可能多地分配给它。供应方2有25单位，需求方3需要25单位。所以，令 \(x_ {23} = 25\)。这样，供应商2的供应已满足（方程2：\(x_ {21}+x_ {22}+25=25 \Rightarrow x_ {21}=x_ {22}=0\)），消费者3的需求也满足（方程5：\(x_ {13}+25=25 \Rightarrow x_ {13}=0\)）。将第2行和第3列从后续考虑中划去。 在剩余格子中（第1行和第1、2列），找最小成本。成本为 \(c_ {11}=8, c_ {12}=4\)，最小是4，对应 \(x_ {12}\)。 分配。供应商1还剩35单位，消费者2需要15单位。所以，令 \(x_ {12} = 15\)。消费者2需求满足，划去第2列。供应商1剩余20单位。 只剩第1行和第1列。将供应商1剩余的20单位全部分配给消费者1。令 \(x_ {11} = 20\)。 于是，我们得到初始基本可行解： \[ x_ {11}=20, \quad x_ {12}=15, \quad x_ {13}=0, \quad x_ {21}=0, \quad x_ {22}=0, \quad x_ {23}=25 \] 其他变量为0。 检查所有约束： 行1: 20+15+0=35 ✔ 行2: 0+0+25=25 ✔ 列1: 20+0=20 ✔ 列2: 15+0=15 ✔ 列3: 0+25=25 ✔ 第三步：检验最优性（计算检验数） 在单纯形法中，我们需要计算非基变量的检验数（Reduced Cost）\(\bar{c} {ij} = c {ij} - u_ i - v_ j\)，其中 \(u_ i\) 和 \(v_ j\) 是对偶变量（位势），可以通过基变量满足 \(c_ {ij} = u_ i + v_ j\) 来求解。 当前基变量是 \(x_ {11}, x_ {12}, x_ {23}\)。 令对偶变量 \(u_ 1 = 0\)（通常设定一个起始值）。 对于基变量 \(x_ {11}\): \(c_ {11}=8 = u_ 1 + v_ 1 \Rightarrow 0 + v_ 1 = 8 \Rightarrow v_ 1 = 8\) 对于基变量 \(x_ {12}\): \(c_ {12}=4 = u_ 1 + v_ 2 \Rightarrow 0 + v_ 2 = 4 \Rightarrow v_ 2 = 4\) 对于基变量 \(x_ {23}\): \(c_ {23}=3 = u_ 2 + v_ 3\)。我们还没有 \(u_ 2\) 和 \(v_ 3\)。我们需要另一个方程。实际上，由于我们划去了行和列，我们需要利用所有基变量。但这里我们只有三个方程，却有四个未知数（\(u_ 1, u_ 2, v_ 1, v_ 2, v_ 3\)，但设了\(u_ 1=0\)）。等等，我们有三行两列，应该有 \(m+n-1=2+3-1=4\) 个基变量。我们只列出了三个。这是因为在运输问题中，当用最小成本法得到一个解时，它可能是一个“退化的”基本可行解（基变量个数少于 m+n-1）。我们需要引入一个“人工基变量”值为0来补足。这里，实际上 \(x_ {13}=0\) 也是一个基变量（退化基变量）。所以基变量是 \(\{x_ {11}, x_ {12}, x_ {13}, x_ {23}\}\)，其中 \(x_ {13}=0\)。 重新计算位势： 设 \(u_ 1 = 0\) \(x_ {11}\): \(8 = u_ 1 + v_ 1 \Rightarrow v_ 1 = 8\) \(x_ {12}\): \(4 = u_ 1 + v_ 2 \Rightarrow v_ 2 = 4\) \(x_ {13}\): \(6 = u_ 1 + v_ 3 \Rightarrow v_ 3 = 6\) \(x_ {23}\): \(3 = u_ 2 + v_ 3 = u_ 2 + 6 \Rightarrow u_ 2 = -3\) 现在计算非基变量（\(x_ {21}, x_ {22}\)）的检验数： \(\bar{c} {21} = c {21} - u_ 2 - v_ 1 = 5 - (-3) - 8 = 0\) \(\bar{c} {22} = c {22} - u_ 2 - v_ 2 = 7 - (-3) - 4 = 6\) 在最小化问题中，如果所有非基变量的检验数都 \(\geq 0\)，则当前解最优。这里 \(\bar{c} {21}=0 \geq 0\)，\(\bar{c} {22}=6 \geq 0\)。 所以当前解已经是最优解之一 （因为有一个非基变量的检验数为0，可能存在多个最优解）。 第四步：计算最优目标函数值 将最优解代入目标函数： \[ Z^* = 8(20) + 4(15) + 6(0) + 5(0) + 7(0) + 3(25) = 160 + 60 + 0 + 0 + 0 + 75 = 295 \] 5. 结果解释与扩展 我们得到了最优运输计划： 从供应商1运输20单位到消费者1，运输15单位到消费者2，不运到消费者3。 从供应商2运输25单位到消费者3，不运到消费者1和2。 总最小成本为295。 总结与要点 ： 建模核心 ：最优传输问题（离散形式）可以自然地建模为一个线性规划，其决策变量是运输量，目标是最小化总成本，约束是供应与需求的严格平衡。 求解特点 ：虽然可以用通用单纯形法求解，但其特殊的“网络流”结构使得“运输单纯形法”或“位势法”更高效，它通过在表格上操作来寻找改进回路和计算检验数。 对偶问题 ：该问题的对偶问题是 \(\max \sum_ {i} a_ i u_ i + \sum_ {j} b_ j v_ j\)，约束为 \(u_ i + v_ j \leq c_ {ij}\)。对偶变量 \(u_ i\) 和 \(v_ j\) 可以解释为供应商 \(i\) 和消费者 \(j\) 的“影子价格”。我们求解过程中计算的 \(u_ i, v_ j\) 正是对偶问题的一个可行解。 应用广泛 ：除了物流，最优传输问题在图像处理（比较颜色直方图）、统计学（比较概率分布）、机器学习（生成模型）等领域都有重要应用。其连续形式定义了概率分布间的“距离”（Wasserstein距离）。