Operations Research — Transportation Problem

Loading…

Operations Research — Transportation Problem

问题描述

Problem. 已知运输问题的产销数量与单位运价表如下。试用表上作业法给出最优调运方案和最小运费。

产地 $A_1, A_2, A_3, A_4$ 的产量分别为 $18, 24, 6, 12$ ；销地 $B_1, B_2, B_3, B_4$ 的销量分别为 $6, 14, 35, 5$ 。单位运价如下表所示：

\diagbox{产地}{销地} | $B_1$ | $B_2$ | $B_3$ | $B_4$ | 产量 |

| --- | --- | --- | --- | --- | --- |

A_1

| 9 | 8 | 12 | 13 | 18 |

| $A_2$ | 10 | 10 | 12 | 14 | 24 |

| $A_3$ | 8 | 9 | 11 | 12 | 6 |

| $A_4$ | 10 | 10 | 11 | 12 | 12 |

销量 | 6 | 14 | 35 | 5 | |

| |

\caption{运输问题的产销平衡表与单位运价}

建立数学模型

设 $x_{ij}$ 为从产地 $A_i$ 运往销地 $B_j$ 的运量（单位与产量相同）， $c_{ij}$ 为对应单位运价。

Step. 线性规划模型：

\min\ z = \sum_{i=1}^{4}\sum_{j=1}^{4} c_{ij}\, x_{ij} \text{s.t.} \begin{cases} \sum_{j=1}^{4} x_{ij} = a_i, & i=1,2,3,4 (\text{产量约束})\\[8pt] \sum_{i=1}^{4} x_{ij} = b_j, & j=1,2,3,4 (\text{销量约束})\\[8pt] x_{ij} \geq 0 \end{cases}

Note. 产销平衡验证：

\sum a_i = 18+24+6+12 = 60, \sum b_j = 6+14+35+5 = 60. \sum a_i = \sum b_j = 60，产销平衡，可以直接应用表上作业法。基变量数应为 m+n-1 = 4+4-1 = \mathbf{7} 个。

第一步：用最小元素法确定初始基可行解

Step. 最小元素法的基本思想：

就近优先安排——每次从当前未划去的运价表中找出最小运价 $c_{ij}$ ，尽可能多地给 $x_{ij}$ 分配运量（取 $\min$ 当前剩余产量与剩余销量），然后划去已耗尽的行或列，重复直到全部分配完毕。

分配过程的逐步演示

第①步：

全表最小运价为 $c_{12}=8$ （也有 $c_{31}=8$ ，并列时任选其一，这里先选 $c_{12}$ ）。

x{12} = \min{a1,, b_2} = \min{18,, 14} = \mathbf{14}.

B2 列需求被完全满足，划去 B2 列；A_1 剩余产量为 18-14=4。

第②步：

剩余表中最小运价为 $c_{31}=8$ 。

x_{31} = \min\{a_3,\, b_1\} = \min\{6,\, 6\} = \mathbf{6}.

$A_3$ 行产量和 $B_1$ 列需求同时被满足——这是产生退化的关键时刻。按惯例划去 $A_3$ 行，保留 $B_1$ 列（此时 $B_1$ 已无剩余需求）。

第③步：

剩余表（去掉 $A_3$ 行、 $B_1, B_2$ 列）中最小运价为 $c_{43}=11$ 。

x{43} = \min{a4,, b_3} = \min{12,, 35} = \mathbf{12}.

A4 行产量被满足，划去 A4 行；B_3 剩余需求 35-12=23。

第④步：

剩余表中最小运价为 $c_{13}=12$ （与 $c_{23}=12$ 并列，选 $c_{13}$ ）。

x_{13} = \min{4,, 23} = \mathbf{4}.

A1 剩余产量被耗尽，划去 A1 行；B_3 剩余需求 23-4=19。

第⑤步：

仅剩 $A_2$ 行。 $c_{23}=12$ 。

x_{23} = \min{24,, 19} = \mathbf{19}.

B3 列需求满足，划去 B3 列；A_2 剩余产量 24-19=5。

第⑥步：

仅剩 $(A_2, B_4)$ 一格。

x_{24} = \min\{5,\, 5\} = \mathbf{5}.

至此全部产销均已满足，分配过程结束。

初始方案与退化的处理

Note. 退化判断：

共得到 $6$ 个基变量： $x_{12}, x_{31}, x_{43}, x_{13}, x_{23}, x_{24}$ 。

但是平衡运输问题要求 $m+n-1 = 7$ 个基变量。

原因：第②步中 $A_3$ 行和 $B_1$ 列同时被划去，导致少算一个基变量。

处理方法：补一个运量为 $0$ 的退化基变量。这里在被划去的 $B_1$ 列里、 $A_1$ 行选 $x_{11}=0$ 作为退化基变量（也可以选其他位置，例如 $x_{34}=0$ ，结果等价）。

\renewcommand{\arraystretch}{1.8}

\diagbox{产地}{销地} | $B_1$ | $B_2$ | $B_3$ | $B_4$ | 产量 |

| --- | --- | --- | --- | --- | --- |

A_1

| \cell{9}{\cellval{[0]}} | \cell{8}{\cellval{14}} | \cell{12}{\cellval{4}} | \cell{13}{} | 18 |

销量 | 6 | 14 | 35 | 5 | |

| |

\caption{初始基可行解（最小元素法），方括号 [0] 为退化基变量}

初始总运费：

\begin{aligned} z_0 &= 0\cdot 9 + 14\cdot 8 + 4\cdot 12 + 19\cdot 12 + 5\cdot 14 + 6\cdot 8 + 12\cdot 11 \\ &= 0 + 112 + 48 + 228 + 70 + 48 + 132 \\ &= \mathbf{638}. \end{aligned}

第二步：用位势法计算检验数（第一次检验）

位势法原理

Step. 位势法（u-v 法）：

为每行 $i$ 设位势 $u_i$ ，为每列 $j$ 设位势 $v_j$ ，要求对所有基变量格 $(i,j)$ 满足

u_i + v_j = c_{ij}.

共 $m+n-1=7$ 个方程， $m+n=8$ 个未知数，自由度为 $1$ ，所以可先令 $u_1=0$ （任意指定一个），其余依次求出。

对所有非基变量格 $(i,j)$ ，计算检验数

\sigma_{ij} = c_{ij} - u_i - v_j.

若所有 $\sigma_{ij} \geq 0$ ，则当前解最优；若存在 $\sigma_{ij} < 0$ ，则当前解非最优，需要调整。

计算位势

基变量集合： $\{(1,1),\,(1,2),\,(1,3),\,(2,3),\,(2,4),\,(3,1),\,(4,3)\}$ 。

\paragraph{从 $u_1 = 0$ 出发：}

\begin{aligned} &\text{由 } (1,1):\ u_1 + v_1 = c_{11} = 9 \ \Rightarrow\ v_1 = 9. \\ &\text{由 } (1,2):\ u_1 + v_2 = c_{12} = 8 \ \Rightarrow\ v_2 = 8. \\ &\text{由 } (1,3):\ u_1 + v_3 = c_{13} = 12 \ \Rightarrow\ v_3 = 12. \\ &\text{由 } (2,3):\ u_2 + v_3 = c_{23} = 12 \ \Rightarrow\ u_2 = 0. \\ &\text{由 } (2,4):\ u_2 + v_4 = c_{24} = 14 \ \Rightarrow\ v_4 = 14. \\ &\text{由 } (3,1):\ u_3 + v_1 = c_{31} = 8 \ \Rightarrow\ u_3 = -1. \\ &\text{由 } (4,3):\ u_4 + v_3 = c_{43} = 11 \ \Rightarrow\ u_4 = -1. \\ \end{aligned}

得位势向量：

(u_1,u_2,u_3,u_4) = (0,\, 0,\, -1,\, -1), (v_1,v_2,v_3,v_4) = (9,\, 8,\, 12,\, 14).

计算非基变量的检验数

对每个非基变量格逐一计算 $\sigma_{ij} = c_{ij} - u_i - v_j$ ：

\begin{aligned} \sigma_{14} &= c_{14} - u_1 - v_4 = 13 - 0 - 14 = -1, \\[2pt] \sigma_{21} &= c_{21} - u_2 - v_1 = 10 - 0 - 9 = 1, \\[2pt] \sigma_{22} &= c_{22} - u_2 - v_2 = 10 - 0 - 8 = 2, \\[2pt] \sigma_{32} &= c_{32} - u_3 - v_2 = 9 - (-1) - 8 = 2, \\[2pt] \sigma_{33} &= c_{33} - u_3 - v_3 = 11 - (-1) - 12 = 0, \\[2pt] \sigma_{34} &= c_{34} - u_3 - v_4 = 12 - (-1) - 14 = -1, \\[2pt] \sigma_{41} &= c_{41} - u_4 - v_1 = 10 - (-1) - 9 = 2, \\[2pt] \sigma_{42} &= c_{42} - u_4 - v_2 = 10 - (-1) - 8 = 3, \\[2pt] \sigma_{44} &= c_{44} - u_4 - v_4 = 12 - (-1) - 14 = -1. \end{aligned}

汇总到检验数表中：

\renewcommand{\arraystretch}{1.3}

\sigma_{ij}

| $B_1$ | $B_2$ | $B_3$ | $B_4$ |

| --- | --- | --- | --- | --- |

A_1

| 基 | 基 | 基 | $-1$ |

| $A_2$ | $1$ | $2$ | 基 | 基 |

| $A_3$ | 基 | $2$ | $0$ | $-1$ |

| $A_4$ | $2$ | $3$ | 基 | $-1$ |

| |

\caption{第一次迭代的检验数表}

Note. 存在三个负检验数 $\sigma_{14}=\sigma_{34}=\sigma_{44}=-1$ ，当前解不是最优解，需要调整。

按"取最负"原则任选一个负检验数对应的格作为入基变量。这里我们选 $(A_4, B_4)$ 进基。

第三步：找闭回路并调整（第一次迭代）

闭回路的寻找

Step. 闭回路构造规则：

以入基格 $(A_4,B_4)$ 为起点，沿水平/垂直方向跳跃，只允许在基变量格处转弯，最终回到起点形成一个闭多边形。每个顶点交替标记 $+,-,+,-,\ldots$ ，起点为 $+$ 。

从 $(4,4)$ 出发寻找闭回路：

$(4,4)$
沿第 $4$ 行向左，可到的基变量格只有 $(4,3)$ 。
$(4,3)$
沿第 $3$ 列向上，基变量格有 $(1,3),(2,3)$ 。选 $(2,3)$ 。
$(2,3)$
沿第 $2$ 行向右，基变量格只有 $(2,4)$ 。
$(2,4)$
沿第 $4$ 列回到起点 $(4,4)$ ，闭合。

闭回路：

(4,4)^{+}\ \to\ (4,3)^{-}\ \to\ (2,3)^{+}\ \to\ (2,4)^{-}\ \to\ (4,4)^{+}.

图见 PDF。

闭回路示意： $(4,4)^{+} \to (4,3)^{-} \to (2,3)^{+} \to (2,4)^{-}$

确定调整量 $\theta$

调整量取闭回路上" $-$ "号位置基变量值的最小者：

\theta = \min\{x_{43},\ x_{24}\} = \min\{12,\ 5\} = \mathbf{5}.

出基变量为达到最小值的 $x_{24}=5$ （它将变为 $0$ ）。

执行调整

沿闭回路： $+$ 号位置加 $\theta$ ， $-$ 号位置减 $\theta$ 。

\begin{aligned} x_{44} &= 0 + 5 = 5 (\text{入基}), \\ x_{43} &= 12 - 5 = 7, \\ x_{23} &= 19 + 5 = 24, \\ x_{24} &= 5 - 5 = 0 (\text{出基}). \\ \end{aligned}

其余基变量不变： $x_{11}=0,\ x_{12}=14,\ x_{13}=4,\ x_{31}=6$ 。

调整后的总运费：

z_1 = z_0 + \sigma_{44}\cdot\theta = 638 + (-1)\cdot 5 = \mathbf{633}.

\renewcommand{\arraystretch}{1.8}

\diagbox{产地}{销地} | $B_1$ | $B_2$ | $B_3$ | $B_4$ | 产量 |

| --- | --- | --- | --- | --- | --- |

A_1

| \cell{9}{\cellval{[0]}} | \cell{8}{\cellval{14}} | \cell{12}{\cellval{4}} | \cell{13}{} | 18 |

销量 | 6 | 14 | 35 | 5 | |

| |

\caption{第一次调整后的方案， $z_1 = 633$ }

第四步：第二次检验（最优性验证）

重新计算位势

新的基变量集合： $\{(1,1),(1,2),(1,3),(2,3),(3,1),(4,3),(4,4)\}$ 。

仍取 $u_1 = 0$ ：

\begin{aligned} &(1,1):\ v_1 = c_{11} - u_1 = 9, \\ &(1,2):\ v_2 = c_{12} - u_1 = 8, \\ &(1,3):\ v_3 = c_{13} - u_1 = 12, \\ &(2,3):\ u_2 = c_{23} - v_3 = 0, \\ &(3,1):\ u_3 = c_{31} - v_1 = -1, \\ &(4,3):\ u_4 = c_{43} - v_3 = -1, \\ &(4,4):\ v_4 = c_{44} - u_4 = 12 - (-1) = 13. \end{aligned}

位势更新为：

(u_1,u_2,u_3,u_4) = (0,0,-1,-1), (v_1,v_2,v_3,v_4) = (9,8,12,\mathbf{13}).

（与上一次相比，只有 $v_4$ 由 $14$ 变为 $13$ 。）

重新计算检验数

\begin{aligned} \sigma_{14} &= 13 - 0 - 13 = 0, \\ \sigma_{21} &= 10 - 0 - 9 = 1, \\ \sigma_{22} &= 10 - 0 - 8 = 2, \\ \sigma_{24} &= 14 - 0 - 13 = 1, \\ \sigma_{32} &= 9 - (-1) - 8 = 2, \\ \sigma_{33} &= 11 - (-1) - 12 = 0, \\ \sigma_{34} &= 12 - (-1) - 13 = 0, \\ \sigma_{41} &= 10 - (-1) - 9 = 2, \\ \sigma_{42} &= 10 - (-1) - 8 = 3. \end{aligned}

\renewcommand{\arraystretch}{1.3}

\sigma_{ij}

| $B_1$ | $B_2$ | $B_3$ | $B_4$ |

| --- | --- | --- | --- | --- |

A_1

| 基 | 基 | 基 | $0$ |

| $A_2$ | $1$ | $2$ | 基 | $1$ |

| $A_3$ | 基 | $2$ | $0$ | $0$ |

| $A_4$ | $2$ | $3$ | 基 | 基 |

| |

\caption{第二次迭代的检验数表}

Result. 所有非基变量的检验数 $\sigma_{ij} \geq 0$ ，当前解已达到最优！

另外存在 $\sigma_{14}=\sigma_{33}=\sigma_{34}=0$ ，说明该问题有多个最优解（沿这些零检验数对应格的闭回路调整可得到其它最优方案，但总运费不变）。

最终最优解

Result. 最优调运方案：

\renewcommand{\arraystretch}{1.3}

| \toprule

路线 | 运量 | 单价 | 运费 |

| --- | --- | --- | --- |

| \midrule

A_1 \to B_2

| $14$ | $8$ | $112$ |

| $A_1 \to B_3$ | $4$ | $12$ | $48$ |

| $A_2 \to B_3$ | $24$ | $12$ | $288$ |

| $A_3 \to B_1$ | $6$ | $8$ | $48$ |

| $A_4 \to B_3$ | $7$ | $11$ | $77$ |

| $A_4 \to B_4$ | $5$ | $12$ | $60$ |

| \midrule

\multicolumn{3}{r|}{合计} | $\mathbf{633}$ |

| \bottomrule |

最小总运费：

\boxed{\ z^* = 112 + 48 + 288 + 48 + 77 + 60 = 633\ }

\renewcommand{\arraystretch}{1.8}

\diagbox{产地}{销地} | $B_1$ | $B_2$ | $B_3$ | $B_4$ | 产量 |

| --- | --- | --- | --- | --- | --- |

A_1

| \cell{9}{ $-$ } | \cell{8}{\cellval{14}} | \cell{12}{\cellval{4}} | \cell{13}{ $-$ } | 18 |

销量 | 6 | 14 | 35 | 5 | |

| |

\caption{最优运输方案一览}

求解流程小结

Step. 表上作业法求解运输问题的完整流程：

产销平衡检验： $\sum a_i = \sum b_j = 60$ ，平衡。
最小元素法求初始解：逐次选取最小运价格分配， $x_{12}{=}14, x_{31}{=}6, x_{43}{=}12, x_{13}{=}4, x_{23}{=}19, x_{24}{=}5$ ，初始运费 $z_0 = 638$ 。
处理退化：补退化基变量 $x_{11}=0$ ，使基变量数达 $m+n-1=7$ 。
位势法计算检验数：得最负检验数 $\sigma_{44}=-1$ ，非最优。
找闭回路并调整：闭回路 $(4,4)^+\to(4,3)^-\to(2,3)^+\to(2,4)^-$ ， $\theta=5$ ， $x_{24}$ 出基， $x_{44}$ 入基。新方案 $z_1 = 633$ 。
再次检验：所有 $\sigma_{ij}\geq 0$ ，达到最优。最小运费 $z^*=633$ ，且因存在 $\sigma_{ij}=0$ ，最优解非唯一。

PDF

Download the original write-up here.

问题描述

Problem. 已知运输问题的产销数量与单位运价表如下。试用表上作业法给出最优调运方案和最小运费。

产地 $A_1, A_2, A_3, A_4$ 的产量分别为 $18, 24, 6, 12$ ；销地 $B_1, B_2, B_3, B_4$ 的销量分别为 $6, 14, 35, 5$ 。单位运价如下表所示：

\diagbox{产地}{销地} | $B_1$ | $B_2$ | $B_3$ | $B_4$ | 产量 |

| --- | --- | --- | --- | --- | --- |

A_1

| 9 | 8 | 12 | 13 | 18 |

| $A_2$ | 10 | 10 | 12 | 14 | 24 |

| $A_3$ | 8 | 9 | 11 | 12 | 6 |

| $A_4$ | 10 | 10 | 11 | 12 | 12 |

销量 | 6 | 14 | 35 | 5 | |

| |

\caption{运输问题的产销平衡表与单位运价}

建立数学模型

设 $x_{ij}$ 为从产地 $A_i$ 运往销地 $B_j$ 的运量（单位与产量相同）， $c_{ij}$ 为对应单位运价。

Step. 线性规划模型：

\min\ z = \sum_{i=1}^{4}\sum_{j=1}^{4} c_{ij}\, x_{ij} \text{s.t.} \begin{cases} \sum_{j=1}^{4} x_{ij} = a_i, & i=1,2,3,4 (\text{产量约束})\\[8pt] \sum_{i=1}^{4} x_{ij} = b_j, & j=1,2,3,4 (\text{销量约束})\\[8pt] x_{ij} \geq 0 \end{cases}

Note. 产销平衡验证：

\sum a_i = 18+24+6+12 = 60, \sum b_j = 6+14+35+5 = 60. \sum a_i = \sum b_j = 60，产销平衡，可以直接应用表上作业法。基变量数应为 m+n-1 = 4+4-1 = \mathbf{7} 个。

第一步：用最小元素法确定初始基可行解

Step. 最小元素法的基本思想：

分配过程的逐步演示

第①步：

全表最小运价为 $c_{12}=8$ （也有 $c_{31}=8$ ，并列时任选其一，这里先选 $c_{12}$ ）。

x{12} = \min{a1,, b_2} = \min{18,, 14} = \mathbf{14}.

B2 列需求被完全满足，划去 B2 列；A_1 剩余产量为 18-14=4。

第②步：

剩余表中最小运价为 $c_{31}=8$ 。

x_{31} = \min\{a_3,\, b_1\} = \min\{6,\, 6\} = \mathbf{6}.

$A_3$ 行产量和 $B_1$ 列需求同时被满足——这是产生退化的关键时刻。按惯例划去 $A_3$ 行，保留 $B_1$ 列（此时 $B_1$ 已无剩余需求）。

第③步：

剩余表（去掉 $A_3$ 行、 $B_1, B_2$ 列）中最小运价为 $c_{43}=11$ 。

x{43} = \min{a4,, b_3} = \min{12,, 35} = \mathbf{12}.

A4 行产量被满足，划去 A4 行；B_3 剩余需求 35-12=23。

第④步：

剩余表中最小运价为 $c_{13}=12$ （与 $c_{23}=12$ 并列，选 $c_{13}$ ）。

x_{13} = \min{4,, 23} = \mathbf{4}.

A1 剩余产量被耗尽，划去 A1 行；B_3 剩余需求 23-4=19。

第⑤步：

仅剩 $A_2$ 行。 $c_{23}=12$ 。

x_{23} = \min{24,, 19} = \mathbf{19}.

B3 列需求满足，划去 B3 列；A_2 剩余产量 24-19=5。

第⑥步：

仅剩 $(A_2, B_4)$ 一格。

x_{24} = \min\{5,\, 5\} = \mathbf{5}.

至此全部产销均已满足，分配过程结束。

初始方案与退化的处理

Note. 退化判断：

共得到 $6$ 个基变量： $x_{12}, x_{31}, x_{43}, x_{13}, x_{23}, x_{24}$ 。

但是平衡运输问题要求 $m+n-1 = 7$ 个基变量。

原因：第②步中 $A_3$ 行和 $B_1$ 列同时被划去，导致少算一个基变量。

\renewcommand{\arraystretch}{1.8}

\diagbox{产地}{销地} | $B_1$ | $B_2$ | $B_3$ | $B_4$ | 产量 |

| --- | --- | --- | --- | --- | --- |

A_1

| \cell{9}{\cellval{[0]}} | \cell{8}{\cellval{14}} | \cell{12}{\cellval{4}} | \cell{13}{} | 18 |

销量 | 6 | 14 | 35 | 5 | |

| |

\caption{初始基可行解（最小元素法），方括号 [0] 为退化基变量}

初始总运费：

\begin{aligned} z_0 &= 0\cdot 9 + 14\cdot 8 + 4\cdot 12 + 19\cdot 12 + 5\cdot 14 + 6\cdot 8 + 12\cdot 11 \\ &= 0 + 112 + 48 + 228 + 70 + 48 + 132 \\ &= \mathbf{638}. \end{aligned}

第二步：用位势法计算检验数（第一次检验）

位势法原理

Step. 位势法（u-v 法）：

为每行 $i$ 设位势 $u_i$ ，为每列 $j$ 设位势 $v_j$ ，要求对所有基变量格 $(i,j)$ 满足

u_i + v_j = c_{ij}.

共 $m+n-1=7$ 个方程， $m+n=8$ 个未知数，自由度为 $1$ ，所以可先令 $u_1=0$ （任意指定一个），其余依次求出。

对所有非基变量格 $(i,j)$ ，计算检验数

\sigma_{ij} = c_{ij} - u_i - v_j.

若所有 $\sigma_{ij} \geq 0$ ，则当前解最优；若存在 $\sigma_{ij} < 0$ ，则当前解非最优，需要调整。

计算位势

基变量集合： $\{(1,1),\,(1,2),\,(1,3),\,(2,3),\,(2,4),\,(3,1),\,(4,3)\}$ 。

\paragraph{从 $u_1 = 0$ 出发：}

\begin{aligned} &\text{由 } (1,1):\ u_1 + v_1 = c_{11} = 9 \ \Rightarrow\ v_1 = 9. \\ &\text{由 } (1,2):\ u_1 + v_2 = c_{12} = 8 \ \Rightarrow\ v_2 = 8. \\ &\text{由 } (1,3):\ u_1 + v_3 = c_{13} = 12 \ \Rightarrow\ v_3 = 12. \\ &\text{由 } (2,3):\ u_2 + v_3 = c_{23} = 12 \ \Rightarrow\ u_2 = 0. \\ &\text{由 } (2,4):\ u_2 + v_4 = c_{24} = 14 \ \Rightarrow\ v_4 = 14. \\ &\text{由 } (3,1):\ u_3 + v_1 = c_{31} = 8 \ \Rightarrow\ u_3 = -1. \\ &\text{由 } (4,3):\ u_4 + v_3 = c_{43} = 11 \ \Rightarrow\ u_4 = -1. \\ \end{aligned}

得位势向量：

(u_1,u_2,u_3,u_4) = (0,\, 0,\, -1,\, -1), (v_1,v_2,v_3,v_4) = (9,\, 8,\, 12,\, 14).

计算非基变量的检验数

对每个非基变量格逐一计算 $\sigma_{ij} = c_{ij} - u_i - v_j$ ：

\begin{aligned} \sigma_{14} &= c_{14} - u_1 - v_4 = 13 - 0 - 14 = -1, \\[2pt] \sigma_{21} &= c_{21} - u_2 - v_1 = 10 - 0 - 9 = 1, \\[2pt] \sigma_{22} &= c_{22} - u_2 - v_2 = 10 - 0 - 8 = 2, \\[2pt] \sigma_{32} &= c_{32} - u_3 - v_2 = 9 - (-1) - 8 = 2, \\[2pt] \sigma_{33} &= c_{33} - u_3 - v_3 = 11 - (-1) - 12 = 0, \\[2pt] \sigma_{34} &= c_{34} - u_3 - v_4 = 12 - (-1) - 14 = -1, \\[2pt] \sigma_{41} &= c_{41} - u_4 - v_1 = 10 - (-1) - 9 = 2, \\[2pt] \sigma_{42} &= c_{42} - u_4 - v_2 = 10 - (-1) - 8 = 3, \\[2pt] \sigma_{44} &= c_{44} - u_4 - v_4 = 12 - (-1) - 14 = -1. \end{aligned}

汇总到检验数表中：

\renewcommand{\arraystretch}{1.3}

\sigma_{ij}

| $B_1$ | $B_2$ | $B_3$ | $B_4$ |

| --- | --- | --- | --- | --- |

A_1

| 基 | 基 | 基 | $-1$ |

| $A_2$ | $1$ | $2$ | 基 | 基 |

| $A_3$ | 基 | $2$ | $0$ | $-1$ |

| $A_4$ | $2$ | $3$ | 基 | $-1$ |

| |

\caption{第一次迭代的检验数表}

Note. 存在三个负检验数 $\sigma_{14}=\sigma_{34}=\sigma_{44}=-1$ ，当前解不是最优解，需要调整。

按"取最负"原则任选一个负检验数对应的格作为入基变量。这里我们选 $(A_4, B_4)$ 进基。

第三步：找闭回路并调整（第一次迭代）

闭回路的寻找

Step. 闭回路构造规则：

从 $(4,4)$ 出发寻找闭回路：

$(4,4)$
沿第 $4$ 行向左，可到的基变量格只有 $(4,3)$ 。
$(4,3)$
沿第 $3$ 列向上，基变量格有 $(1,3),(2,3)$ 。选 $(2,3)$ 。
$(2,3)$
沿第 $2$ 行向右，基变量格只有 $(2,4)$ 。
$(2,4)$
沿第 $4$ 列回到起点 $(4,4)$ ，闭合。

闭回路：

(4,4)^{+}\ \to\ (4,3)^{-}\ \to\ (2,3)^{+}\ \to\ (2,4)^{-}\ \to\ (4,4)^{+}.

图见 PDF。

闭回路示意： $(4,4)^{+} \to (4,3)^{-} \to (2,3)^{+} \to (2,4)^{-}$

确定调整量 $\theta$

调整量取闭回路上" $-$ "号位置基变量值的最小者：

\theta = \min\{x_{43},\ x_{24}\} = \min\{12,\ 5\} = \mathbf{5}.

出基变量为达到最小值的 $x_{24}=5$ （它将变为 $0$ ）。

执行调整

沿闭回路： $+$ 号位置加 $\theta$ ， $-$ 号位置减 $\theta$ 。

\begin{aligned} x_{44} &= 0 + 5 = 5 (\text{入基}), \\ x_{43} &= 12 - 5 = 7, \\ x_{23} &= 19 + 5 = 24, \\ x_{24} &= 5 - 5 = 0 (\text{出基}). \\ \end{aligned}

其余基变量不变： $x_{11}=0,\ x_{12}=14,\ x_{13}=4,\ x_{31}=6$ 。

调整后的总运费：

z_1 = z_0 + \sigma_{44}\cdot\theta = 638 + (-1)\cdot 5 = \mathbf{633}.

\renewcommand{\arraystretch}{1.8}

\diagbox{产地}{销地} | $B_1$ | $B_2$ | $B_3$ | $B_4$ | 产量 |

| --- | --- | --- | --- | --- | --- |

A_1

| \cell{9}{\cellval{[0]}} | \cell{8}{\cellval{14}} | \cell{12}{\cellval{4}} | \cell{13}{} | 18 |

销量 | 6 | 14 | 35 | 5 | |

| |

\caption{第一次调整后的方案， $z_1 = 633$ }

第四步：第二次检验（最优性验证）

重新计算位势

新的基变量集合： $\{(1,1),(1,2),(1,3),(2,3),(3,1),(4,3),(4,4)\}$ 。

仍取 $u_1 = 0$ ：

\begin{aligned} &(1,1):\ v_1 = c_{11} - u_1 = 9, \\ &(1,2):\ v_2 = c_{12} - u_1 = 8, \\ &(1,3):\ v_3 = c_{13} - u_1 = 12, \\ &(2,3):\ u_2 = c_{23} - v_3 = 0, \\ &(3,1):\ u_3 = c_{31} - v_1 = -1, \\ &(4,3):\ u_4 = c_{43} - v_3 = -1, \\ &(4,4):\ v_4 = c_{44} - u_4 = 12 - (-1) = 13. \end{aligned}

位势更新为：

(u_1,u_2,u_3,u_4) = (0,0,-1,-1), (v_1,v_2,v_3,v_4) = (9,8,12,\mathbf{13}).

（与上一次相比，只有 $v_4$ 由 $14$ 变为 $13$ 。）

重新计算检验数

\begin{aligned} \sigma_{14} &= 13 - 0 - 13 = 0, \\ \sigma_{21} &= 10 - 0 - 9 = 1, \\ \sigma_{22} &= 10 - 0 - 8 = 2, \\ \sigma_{24} &= 14 - 0 - 13 = 1, \\ \sigma_{32} &= 9 - (-1) - 8 = 2, \\ \sigma_{33} &= 11 - (-1) - 12 = 0, \\ \sigma_{34} &= 12 - (-1) - 13 = 0, \\ \sigma_{41} &= 10 - (-1) - 9 = 2, \\ \sigma_{42} &= 10 - (-1) - 8 = 3. \end{aligned}

\renewcommand{\arraystretch}{1.3}

\sigma_{ij}

| $B_1$ | $B_2$ | $B_3$ | $B_4$ |

| --- | --- | --- | --- | --- |

A_1

| 基 | 基 | 基 | $0$ |

| $A_2$ | $1$ | $2$ | 基 | $1$ |

| $A_3$ | 基 | $2$ | $0$ | $0$ |

| $A_4$ | $2$ | $3$ | 基 | 基 |

| |

\caption{第二次迭代的检验数表}

Result. 所有非基变量的检验数 $\sigma_{ij} \geq 0$ ，当前解已达到最优！

另外存在 $\sigma_{14}=\sigma_{33}=\sigma_{34}=0$ ，说明该问题有多个最优解（沿这些零检验数对应格的闭回路调整可得到其它最优方案，但总运费不变）。

最终最优解

Result. 最优调运方案：

\renewcommand{\arraystretch}{1.3}

| \toprule

路线 | 运量 | 单价 | 运费 |

| --- | --- | --- | --- |

| \midrule

A_1 \to B_2

| $14$ | $8$ | $112$ |

| $A_1 \to B_3$ | $4$ | $12$ | $48$ |

| $A_2 \to B_3$ | $24$ | $12$ | $288$ |

| $A_3 \to B_1$ | $6$ | $8$ | $48$ |

| $A_4 \to B_3$ | $7$ | $11$ | $77$ |

| $A_4 \to B_4$ | $5$ | $12$ | $60$ |

| \midrule

\multicolumn{3}{r|}{合计} | $\mathbf{633}$ |

| \bottomrule |

最小总运费：

\boxed{\ z^* = 112 + 48 + 288 + 48 + 77 + 60 = 633\ }

\renewcommand{\arraystretch}{1.8}

\diagbox{产地}{销地} | $B_1$ | $B_2$ | $B_3$ | $B_4$ | 产量 |

| --- | --- | --- | --- | --- | --- |

A_1

| \cell{9}{ $-$ } | \cell{8}{\cellval{14}} | \cell{12}{\cellval{4}} | \cell{13}{ $-$ } | 18 |

销量 | 6 | 14 | 35 | 5 | |

| |

\caption{最优运输方案一览}

求解流程小结

Step. 表上作业法求解运输问题的完整流程：

产销平衡检验： $\sum a_i = \sum b_j = 60$ ，平衡。
最小元素法求初始解：逐次选取最小运价格分配， $x_{12}{=}14, x_{31}{=}6, x_{43}{=}12, x_{13}{=}4, x_{23}{=}19, x_{24}{=}5$ ，初始运费 $z_0 = 638$ 。
处理退化：补退化基变量 $x_{11}=0$ ，使基变量数达 $m+n-1=7$ 。
位势法计算检验数：得最负检验数 $\sigma_{44}=-1$ ，非最优。
找闭回路并调整：闭回路 $(4,4)^+\to(4,3)^-\to(2,3)^+\to(2,4)^-$ ， $\theta=5$ ， $x_{24}$ 出基， $x_{44}$ 入基。新方案 $z_1 = 633$ 。
再次检验：所有 $\sigma_{ij}\geq 0$ ，达到最优。最小运费 $z^*=633$ ，且因存在 $\sigma_{ij}=0$ ，最优解非唯一。

PDF

Download the original write-up here.

Operations Research — Transportation Problem

Search

Operations Research — Transportation Problem

问题描述

建立数学模型

第一步：用最小元素法确定初始基可行解

分配过程的逐步演示

初始方案与退化的处理

第二步：用位势法计算检验数（第一次检验）

位势法原理

计算位势

计算非基变量的检验数

第三步：找闭回路并调整（第一次迭代）

闭回路的寻找

确定调整量θ\thetaθ

执行调整

第四步：第二次检验（最优性验证）

重新计算位势

重新计算检验数

最终最优解

求解流程小结

PDF

问题描述

建立数学模型

第一步：用最小元素法确定初始基可行解

分配过程的逐步演示

初始方案与退化的处理

第二步：用位势法计算检验数（第一次检验）

位势法原理

计算位势

计算非基变量的检验数

第三步：找闭回路并调整（第一次迭代）

闭回路的寻找

确定调整量θ\thetaθ

执行调整

第四步：第二次检验（最优性验证）

重新计算位势

重新计算检验数

最终最优解

求解流程小结

PDF

确定调整量 $\theta$

确定调整量 $\theta$