关于运输问题的几个注记

Some Notes on Transportation Problem

摘要: 产销平衡的运输问题是《运筹学》课程的重要内容，可采用表上作业法进行求解。在课堂讲解完基本方法后，提出三个问题供学生思考与讨论：1) 利用位势法求解非基变量的检验数时，位势不唯一，为何检验数是唯一的？2) 如果目标函数是一个极大化问题，相应的表上作业法该如何修改？3) 如果用Lagrange乘子法对产销平衡的运输问题进行求解，则Lagrange乘子与位势之间的关系如何？这些问题的讨论，使学生学会思考，融会贯通。

Abstract: Transportation problem with balanced production and marketing is an important part of opera-tions research course. This kind of problem can be solved by table dispatching method on a transportation simplex tableau. After explaining the basic methods in class, three questions are put forward for students to think and discuss. 1) When using the potential method to solve the test number of nonbasic variables, the potentials are not unique. Why is the test number unique? 2) How to modify the table dispatching method on the transportation simplex tableau when we want to maximize the objective function of transportation problem? 3) If we use the Lagrange multiplier method to solve this problem, what is the relationship between Lagrange multiplier and potentials? Through the discussion of these problems, students can learn to think and understand.

1. 运输问题回顾

运输问题是运筹学中的一个重要研究对象。为描述与求解方便，可将产销不平衡的运输问题转化为产销平衡的运输问题进行处理。因此，本文仅对产销平衡的运输问题中学生常提出的几个问题作归纳和总结。

一个产销平衡的运输问题可以描述为 [1] [2] 。

模型1.1： $A_1,A_2,\cdots ,A_m$ 表示某物资的 $m$ 个产地； $B_1,B_2,\cdots ,B_n$ 表示某物质的 $n$ 个销地； $a_i$ 表示产地 $A_i$ 的产量； $b_j$ 表示销地 $B_j$ 的销量； $c_{ij}$ 表示把物资从产地 $A_i$ 运往销地 $B_j$ 的单位运价。假设这是一个产销平衡问题，求一合适的运输方案，使总运输费用最小。

设 $x_{ij}$ 为从产地 $A_i$ 运往销地 $B_j$ 的运输量，得到一般运输量问题的模型：

$\min f={\displaystyle \underset{i=1}{\overset{m}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{c}_{ij}}}{x}_{ij},$ (1)

$\text{s}\text{.t}\text{.}\{\begin{array}{ll}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{x}_{ij}}=a_i,\hfill & i=1,2,\cdots ,m.\hfill \\ {\displaystyle \underset{i=1}{\overset{m}{\sum }}{x}_{ij}}=b_j,\hfill & j=1,2,\cdots ,n\text{.}\hfill \\ x_{ij}\ge 0,\hfill & i=1,2,\cdots ,m,j=1,2,\cdots ,n.\hfill \end{array}$

2. 主要问题讨论

2.1. 采用位势法计算检验数

产销平衡的运输问题可以通过一种特殊的单纯形法——表上作业法进行求解。当非基变量的检验数 ${\sigma }_{ij}\ge 0$ 时，可确定当前基可行解为最优解。非基变量的检验数 ${\sigma }_{ij}$ 可以通过闭回路法或者位势法进行计算。在课程的讲解中，学生经常提出的一个问题是：用位势法计算检验数时，位势是不唯一的，为什么可以用此来计算检验数呢？本文以一个例子来说明：尽管位势不唯一，但是位势法计算得到的检验数和闭回路法计算得到的检验数一定是相同的。

2.1.1. 闭回路与非基变量的检验数

从每一个空格(非基变量)处 $x_{ij}=0$ 出发一定存在且能找到唯一的闭回路。则图1中非基变量 $x_{ij}$ 的检验数为

Figure 1. Closed loop

图1. 闭回路示意

${\sigma }_{ij}=c_{ij}-\left(c_{ik}-c_{lk}+c_{ls}-c_{ts}+c_{tj}\right).$ (2)

2.1.2. 位势法计算检验数

满足方程

$u_i+v_j=c_{ij},\left(i=1,2,\cdots ,m;j=1,2,\cdots ,n\right)$ (3)

的解 $u_i,v_j$ 称为基本可行解对应的位势。其中 $c_{ij}$ 为基变量 $x_{ij}$ 对应的单位运价。考虑到产销平衡的运输问题基变量为 $m+n-1$ 个，故位势方程中包含 $m+n-1$ 个方程， $m+n$ 个变量，因此有1个变量为自由未知量，故位势不是唯一的。但是利用

${\sigma }_{ij}=c_{ij}-\left(u_i+v_j\right),$ (4)

计算得到的位势与前面闭回路法得到的位势却是一致的。因为

$\begin{array}{c}{\sigma }_{ij}=c_{ij}-\left(u_i+v_j\right)\\ =c_{ij}-\left(u_i+v_k-v_k-u_l+u_l+v_s-v_s-u_u+u_u+v_j\right)\\ =c_{ij}-\left[\left(u_i+v_k\right)-\left(u_l+v_k\right)+\left(u_l+v_s\right)-\left(u_t+v_s\right)+\left(u_t+v_j\right)\right]\\ =c_{ij}-\left(c_{ik}-c_{lk}+c_{ls}-c_{ts}+c_{tj}\right).\end{array}$ (5)

2.2. 极大化问题与表上作业法

在实际的运输问题中，目标函数可以为求利润最大或营业额最大等问题。其数学模型为

$\max f={\displaystyle \underset{i=1}{\overset{m}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{c}_{ij}}}{x}_{ij},$ (6)

$\text{s}\text{.t}\text{.}\{\begin{array}{ll}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{x}_{ij}}=a_i,\hfill & i=1,2,\cdots ,m.\hfill \\ {\displaystyle \underset{i=1}{\overset{m}{\sum }}{x}_{ij}}=b_j,\hfill & j=1,2,\cdots ,n.\hfill \\ x_{ij}\ge 0,\hfill & i=1,2,\cdots ,m,j=1,2,\cdots ,n.\hfill \end{array}$

实际求解时，将极大化问题转化为极小化问题。设常数M满足 $M\ge \max c_{ij}$ 将目标函数更改为

$\min z={\displaystyle \underset{i=1}{\overset{m}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}\left(M-c_{ij}\right)x_{ij}}}={\displaystyle \underset{i=1}{\overset{m}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}\left(-c_{ij}\right)x_{ij}}}+M{\displaystyle \underset{i=1}{\overset{m}{\sum }}{a}_i}.$ (7)

将 $M-c_{ij}\ge 0$ 作为极小化问题的单位运价，用原有的表上作业法求出最优解。

此外，亦可以直接采用表上作业法对极大化问题进行求解，具体的求解步骤为：

1) 初始化：采用最大元素法或其他方法给出初始可行解；

2) 判断当前可行解是否是最优解；采用闭回路法或是位势法对表上空格处的检验数，当所有空格处的检验数

${\sigma }_{ij}=c_{ij}-C_B{B}^{-1}{P}_{ij}\le 0$

时，当前基可行解为最优解。

3) 更新基变量与基解。

a) 选出 ${\sigma }_{rq}>0$ 中的最大值

${\sigma }_{ij}={\max }_{r,q}\left\{{\sigma }_{rq}|{\sigma }_{rq}>0\right\}.$

则 $x_{ij}$ 为入基变量。

b) 在运输表上找一条包含 $x_{ij}$ 为顶点的闭回路，这条闭回路上的其他顶点皆为基变量(格)。

c) 计算

$\theta =\min \left\{x_{rq}|x_{rq}对应闭回路上的偶点格\right\}=x_{ls}称为\theta 的调整量.$

确定 $x_{ls}$ 为出基变量，所在格子调整为空格。

在闭回路上各个奇点变量值均加上 $\theta$ ，各个偶点格均减去 $\theta$ ，而不在闭回路上的各个变量值不变，这样便完成了一次迭代，并保证目标函数上升。

以图1中的闭回路为例，迭代前目标函数

$z^{\text{old}}=\underset{\begin{array}{c}{x}_{rq}为基变量\\ 且不在闭回路上\end{array}}{\sum \sum }{c}_{rq}{x}_{rq}+\left[c_{ik}{x}_{ik}+c_{lk}{x}_{lk}+c_{ls}{x}_{ls}+c_{us}{x}_{us}+c_{uj}{x}_{uj}\right].$

迭代后的目标函数

$\begin{array}{c}{z}^{\text{new}}=\underset{\begin{array}{c}{x}_{rq}为基变量\\ 且不在闭回路上\end{array}}{\sum \sum }{c}_{rq}{x}_{rq}+\left[c_{ik}\left(x_{ik}-\theta \right)+c_{lk}\left(x_{lk}-\theta \right)+c_{ls}\left(x_{ls}-\theta \right)+c_{us}\left(x_{us}+\theta \right)+c_{uj}\left(x_{uj}-\theta \right)+c_{ij}\theta \right]\\ =\underset{\begin{array}{c}{x}_{rq}为基变量\\ 且不在闭回路上\end{array}}{\sum \sum }{c}_{rq}{x}_{rq}+\left[c_{ik}{x}_{ik}+c_{lk}{x}_{lk}+c_{ls}{x}_{ls}+c_{us}{x}_{us}+c_{uj}{x}_{uj}\right]+\left(c_{ij}-c_{ik}+c_{lk}-c_{ls}+c_{ts}-c_{tj}\right)\theta \\ =z^{\text{old}}+{\sigma }_{ij}\theta \ge z^{\text{old}}.\end{array}$

2.3. 表上作业法与Karush-Kuhn-Tucker条件

本文中的运输问题本质上为一个带约束的优化问题，而针对优化问题，学生在“线性规划”，“最优化问题” [3] [4] 等课程中均已接触过相关问题的求解方法，也明白：Karush-Kuhn-Tucker条件是带不等式约束的非线性优化问题取得最优解的必要条件 [5] 。如果考虑用此方法对产销平衡的运输问题进行求解，会得到什么样的结果？我们用以下定理说明Karush-Kuhn-Tucker乘子与运输问题中位势之间的关系。

定理2.1设

$L\left(X;\lambda ,\mu ,d\right)={\displaystyle \underset{i=1}{\overset{m}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{c}_{ij}}}{x}_{ij}+{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\lambda }_i}\left({\displaystyle \underset{j=1}{\overset{n}{\sum }}{x}_{ij}}-a_i\right)+{\displaystyle \underset{j=1}{\overset{n}{\sum }}{\mu }_j}\left({\displaystyle \underset{i=1}{\overset{m}{\sum }}{x}_{ij}}-b_j\right)+{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{d}_{ij}}}\left(-x_{ij}\right).$ (8)

为对模型1.1中的最优化问题对应的Lagrange乘子函数，则运输问题(1)中

1) 等式约束对应的Lagrange乘子为位势的相反数： ${\lambda }_i=-u_i$ ， ${\mu }_j=-v_j$ 。

2) 非负性约束对应的Lagrange乘子为非基变量的检验数： $d_{ij}=c_{ij}+{\lambda }_i+{\mu }_j=c_{ij}-\left(u_i+v_j\right).$

证明：若 $x_{ij}^{*}\left(i=1,2,\cdots ,m,j=1,2,\cdots ,n\right)$ 为运输问题1.1的最优解，则 $x_{ij}^{*}$ 满足对应的Karush-Kuhn-Tucker 条件。

平稳性条件： $\frac{\partial L}{\partial x_{ij}}=c_{ij}+{\lambda }_i+{\mu }_j-d_{ij}=0,$

原始可行性： $\frac{\partial L}{\partial {\mu }_j}={\displaystyle \underset{i=1}{\overset{m}{\sum }}{x}_{ij}^{*}}-b_j=0,$

$\frac{\partial L}{\partial {\lambda }_i}={\displaystyle \underset{j=1}{\overset{n}{\sum }}{x}_{ij}^{*}}-a_i=0,$

$x_{ij}\ge 0,$

对偶可行性： $d_{ij}\ge 0,$

互补松弛性： $d_{ij}\left(-x_{ij}^{*}\right)=0.$

为后续描述方便，我们首先考虑运输问题1.1的对偶问题

$\max w={\displaystyle \underset{i=1}{\overset{m}{\sum }}{a}_i}{u}_i+{\displaystyle \underset{j=1}{\overset{n}{\sum }}{b}_j}{v}_j,$ (9)

$\text{s}\text{.t}\text{.}\{\begin{array}{l}{u}_i+v_j\le c_{ij},\\ u_i,v_j无符号限制.\end{array}$

由平稳性条件和对偶可行性条件

$\left(-{\lambda }_i\right)+\left(-{\mu }_j\right)=c_{ij}-d_{ij}\le c_{ij}.$ (10)

则 $-{\lambda }_i$ ， $-{\mu }_j$ 为对偶问题1.1的可行解。

另一方面，由平稳性条件和互补松弛性条件知

$\left(-{\lambda }_i-{\mu }_j\right)x_{ij}^{*}=\left(c_{ij}-d_{ij}\right)x_{ij}^{*}=c_{ij}{x}_{ij}^{*}.$ (11)

从而有

${\displaystyle \underset{i=1}{\overset{m}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}\left(-{\lambda }_i-{\mu }_j\right)x_{ij}^{*}}}={\displaystyle \underset{i=1}{\overset{m}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{c}_{ij}}}{x}_{ij}^{*},$ (12)

即

${\displaystyle \underset{i=1}{\overset{m}{\sum }}\left(-{\lambda }_i\right)}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{x}_{ij}^{*}}+{\displaystyle \underset{j=1}{\overset{n}{\sum }}\left(-{\mu }_j\right)}{\displaystyle \underset{i=1}{\overset{m}{\sum }}{x}_{ij}^{*}}={\displaystyle \underset{i=1}{\overset{m}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{c}_{ij}}}{x}_{ij}^{*}.$ (13)

结合原始可行性条件，我们有

${\displaystyle \underset{i=1}{\overset{m}{\sum }}{a}_i}\left(-{\lambda }_i\right)+{\displaystyle \underset{j=1}{\overset{n}{\sum }}{b}_j}\left(-{\mu }_j\right)={\displaystyle \underset{i=1}{\overset{m}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{c}_{ij}}}{x}_{ij}^{*}.$ (14)

由此，满足Karush-Kuhn-Tucker条件的 $x_{ij}^{*}$ ， $-{\lambda }_i$ ， $-{\mu }_j$ 分别是原问题(1)和对偶问题(9)的可行解，且满足目标函数相等，见等式(14)。则它们分别为原问题和对偶问题的最优解。进一步，结合(10)，我们有：

当 $x_{ij}$ 为基变量时， $d_{ij}=0$ ，则 $-{\lambda }_i-{\mu }_j=c_{ij}$ ，根据位势的定义(3)， $-{\lambda }_i$ ， $-{\mu }_j$ 为位势；

当 $x_{ij}$ 为非基变量时， $d_{ij}=c_{ij}+{\lambda }_i+{\mu }_j$ 恰为检验数。

3. 总结

在课堂讲解运输问题的基本问题后，分别从举例，方法推广，与其他课程相结合等方面设置思考问题，鼓励学生能够对课程内容做进一步探讨，并将研究结果整理成稿。这样的课堂设置，使学生学会思考，融会贯通，也提高了学生对数学类课程的学习热情。