线性规划运输问题

第四章 运输问题

Chapter 4

Transportation Problem

§4.1 运输问题的定义

设有同一种货物从m个发地1，2，…，m运往n个收地1，2，…，n。第i个发地的供应量（Supply）为si（si≥0），第j个收地的需求量（Demand）为dj（dj≥0）。每单位货物从发地i运到收地j的运价为cij。求一个使总运费最小的运输方案。我们假定从任一发地到任一收地都有道路通行。如果总供应量等于总需求量，这样的运输问题称为供求平衡的运输问题。我们先只考虑这一类问题。

图4.1.1是运输问题的网络表示形式。 运输问题也可以用线性规划表示。设xij为从发地i运往收地j的运量，则总运费最小的线性规划问题如下页所示。运输问题线性规划变量个数为nm个，每个变量与运输网络的一条边对应，所有的变量都是非负的。约束个数为m+n个，全部为等式约束。前m个约束是发地的供应量约束，后n个约束是收地的需求量约束。运输问题约束的特点是约束左边所有的系数都是

0或1，而且每一列中恰有两个系数是1，其他都是0。

运输问题是一种线性规划问题，当然可以用第一章中的单纯形法求解。但由于它有特殊的结构，因而有特殊的算法。在本章中，我们将在单纯形法原理的基础上，根据运输问题的特点，给出特殊的算法。

m i 1 c1nci1 cij cin cm1 cmj cmn 图4.1

n j c11 c1j 1 minz?c11x11?c12x12???c1nx1n?c21x21?c22x22???c2nx2n??cm1xm1?cm2xm2??cmnxmns.t.x11?x12???x1nx21?x22??x2n?x11x12?x1nx11x12?x1nx21x22?在运输问题线性规划模型中，令

X=（x11，x12，…，x1n，x21，x22，…，x2n，……，xm1，xm2，…，xmn）T

???xm1?xm2?xm1???xmn??????xmn?xm1xm2?xmn???s1s2smd1d2?dn0?x21?x22???x2nx2n?xm2C=（c11，c12，…，c1n，c21，c22，…，c2n，……，cm1，cm2，…，cmn）T A=[a11，a12，…，a1n，a21，a22，…，a2n，……，am1，am2，…，amn]T

?1???=???1?????1?111?1?11?11?11?1?11??????m行????? ?1???????n行??????1??b=（s1，s2，…，sm，d1，d2，…，dn）T

则运输问题的线性规划可以写成：

min z=CTX s.t. AX=b X≥0

其中A矩阵的列向量

aij=ei+em+j

ei和em+j是m+n维单位向量，元素1分别在在第i个分量和第m+j个分量的位置上。A矩阵中的行与运输网络中的节点对应，前m行对应于发地，后n行对应于收地；A矩阵的列与运输网络中的边对应。

128 / 42

运输问题除了用网络表示及线性规划表示外，还可以用运输表表示：

1

1 c11 x11 c21 2

x21 … …

… cm1 m

xm1 d1 … n … c12 c1n s1

x12 … x1n … c22 c2n s2

x22 … x2n … … … …

… … … … cm2 cmn sm

xm2 … xmn … d2 dn

2 表 4.1

表的行与发地对应，列与收地对应。第i行与第j列交叉的一格与网络的一条边对应（也就是与线性规划约束矩阵的一列对应），每一格的左上角小方格内的数字表明从相应的发地i到收地j的运价cij，每一格右下角表明从相应的发地i到收地j的运量xij。表右方表明各发地的供应量si，表下方表明各需求第的需求量dj。每一行运量之和表示从该发地运往各收地的运量之和，它应该等于该发地的供应量；同样，每一列运量之和表示从各发地运往该收地的运量之和，它应该等于该收地的需求量。

运输问题的网络图、线性规划模型以及运输表之间的关系可以用下表表示： 网络图 节点 边 发点i 收点j 从节点i到节点j 约束 线性规划模型 前m个约束 后n个约束 运输表 表的行 表的列 表中的一格 变量xij，列向量aij 例4.1 以下的运输问题线性规划、网络图和运输表表示同一运输问题。

min s.t.

z=

8x11 x11 x11 x11,

+5x12 +x12

x12 x12,

+6x13 +x13

x13 x13, 129 / 42

+7x21

x21 +x21

x21,

+4x22

+x22

+x22

x22,

+9x23

+x23

+x23 x23

=15 =25 =10 =20 =10

≥0

1 2 3 1

8 5 6 x11 x12 x15

13 2 7 4 9 x21 x22 x25 23 10 20

10

表 4.2

130 / 42

1 10

8 15 1 6 5 7 2 20

25 2 4 9 图4.2 3 10

§4.2 运输问题约束矩阵的性质

4.2.1 约束矩阵的秩

运输问题约束矩阵A的秩为m+n-1。

证明：因为A矩阵的前m行和后n行之和分别等于向量（1，1，…，1），因此秩A

考虑A的一个子矩阵A’=[a1n，a2n，…，amn，a11，a12，…，a1n]，即

11?1??1?1???m行?????1???1A’=?

??1????n行???11?11??m列n列删除A’中的第m+n行和第m+n列，得到

11?1??1?1???m行?????1???1A’’=?

??1????n?1行????1??m列n?1列容易看出，秩A’’=m+n-1。由此

m+n-1=秩A’’≤秩A’≤秩A

131 / 42

即

秩A=m+n-1。

在线性规划问题中，约束的系数矩阵要求行满秩的，为了使运输问题系数矩阵行满秩，在A矩阵中增加一个列向量em+n形成增广矩阵

???A??Aem?n???????必定包含单位向量em+n。

A0?0???? ?0?1??这样增广矩阵A的秩就等于m+n，因而是行满秩的。并且A中任何一个基矩阵，都

例4.2.1 设一个运输网络如右图，它的系数矩阵为

x11x12x13x21x22x23?1?0A???1??0??0增广矩阵为

10010x1110001x1201100x13x01010x0?1??0??0?1??22s1s2d1d2d3x

2123xe?1?0A???1??0??010010100010110001010010010?0??0??0?1??s1s2d1d2d3

增加的单位列向量em+n=e5相当于在在网络图中增加一条边，它与收点3关联，但不与任何发点关联，这条边称为人工边。设这条边上的运输量为xa，增广运输问题对应于第三个收点的约束称为

x13+x23+xa=d3

由于

图4.3 132 / 42

2 1 1 2 3 x13+x23=d3

因此，对运输问题的任何一个可行解，都有

xa=0。

4.2.2 A矩阵的单位模性质

运输问题的系数矩阵A具有以下性质：A矩阵中任何一个k阶子矩阵A（kk=1，2，…m+n），都有detAk=0或±1。

证明：在A中任取一个k阶方阵Ak，有以下三种情况：

1、 Ak中任何一列都有两个1，这时Ak上部的行属于A矩阵的前m行，而下

部的行属于A矩阵的后n行，Ak上部的各行之和以及Ak下部各行之和都等于向量（1，1，…，1），因而Ak的行线性相关，即detAk=0。 2、 Ak 中至少有一列元素全为0，这时显然有det Ak=0。

3、 Ak中至少有一列，其中只有一个1。这时可以将det Ak按这一列展开，设

对应于这个1的代数余子式为Ak-1，则有

det Ak=±det Ak-1

其中Ak-1是k-1阶方阵。对Ak-1同样有

det Ak-1=0 或者

det Ak-1=±det Ak-2

最后有

det Ak=0 或者

det Ak=±det Ak-1=±det Ak-2=…=±det A1=0或±1。

4.2.3基矩阵的三角性

设B是A的一个基，B中至少有一列只包含一个1，否则，det B=0不成为一个基。将B的行列交换，总可以使B成为

133 / 42

?1?0'B??????0再进行行列交换，得到 ?1?0?''B??0????0PT??? Bm?n?1???其中det Bm+n-1≠0，因而Bm+n-1中也至少有一列只有一个1，对Bm+n-1

PT10?0?QT???

Bm?n?2???依次不断对剩下的方阵进行行列交换，最后可以得到

?1?0?B??0?????0是一个上三角矩阵。

10?01?0R?????? ??1??例4.2 设一个运输问题的系数增广矩阵为

x11x12x13x21x22x23xe?1?0A=??1??0??0取其中一个基

x1310010x10001x1101100x1201010x010010?0??0??0?1???s1??30??s??20??2??? b??d1???15??????d2??10???25???d3???23a?1?0B???0??0??10100110100100100?0??0??0?1??134 / 42

?s1??30??s??20??2??? b??d1???15??????d2??10???25???d3???对B进行行列交换，成为以下上三角矩阵

xax13x23x11x12?1?0B???0??0??0求解相应的方程组

1100011000101001010001010010100?0??0??0?1???d3??25??s??30??1??? b??s2???20??????d1??15???10???d2????1?0??0??0??00??xa??25?1??x13??30??????0??x23???20? ?????0??x11??15?1????10???x12???xa?x13?x23?25x13?x11?x12?30x23?20x11?15x12?10由此得到

x12=10，x11=15， x23=20，x13=5，xa=0

由A的基矩阵的三角性以及A矩阵中仅含有元素0和1，可以知道，如果运输问题各发地的供应量和收地的需求量都是整数，运输问题的任何基础可行解都是整数，因而最优解也是整数。

135 / 42

§4.3 基在网络图和运输表中的表示

从前一节已经知道，运输问题的一个基是由m+n个列向量组成的，其中包括一个单位向量em+n。在网络图上，这m+n个列向量对应m+n条边，其中与单位向量对应的是从最后一个收地出发的人工边。网络图中的一个基具有以下性质：

1、 一个基由m+n条边组成，其中一条是人

工边，其余m+n-1条边是原网络中的边。 2、 组成基的边不能形成闭合回路。若不然，

如果组成一个基的若干条边（i，j），（k，

j），（i，l），（k，l）组成一个闭合回路，则这些边对应的系数矩阵中的列向量aij，akj，ail，akl的线性组合

aij-akj+ail-akl=(ei+em+j)-(ek+em+k)-(ei+em+l)+(ek+em+l)=0

这些列向量线性相关，显然不能包含在一个基中。

3、 组成基的m+n条边必须到达网络的每一个节点。若不然，这m+n条边都不

与某一节点k关联，那么相应的基矩阵

k 图4.4

l

i j???0?B??????????0????0???????????0?节点k???? ????????与节点k对应的一行全为0，即det B=0。B不可能成为一个基。

例4.3 对于2个发点3个收点的运输问题，网络图如图4.5（a）所示。图4.5（b）、（c）、（d）都是这个问题的基，这些基都由m+n-1=2+3-1=4条边组成，都不构成回路，并且与每一个节点关联。

正如线性规划矩阵的列向量组成的基一样，一个网络的基的个数是非常多的，以上只是这些基中的几个例子。

136 / 42

(a)网络图

(c)第二个基

图 4.5

137 / 42

(b)第一个基 (d)第三个基

§4.4 基在运输表中的表示

我们已经知道，运输表中的一行对应于一个发地，一列对应于一个收地，表中i行j列相交的格子表示网络从发地节点i到收地节点j的一条边。运输表中同一行i而不同列j和k的两个格子（i，j）（i，k），分别表示网络中从同一发地节点i出发到达不同收地节点j和节点k的两条边；同样，运输表中位于同一列k而不同行i和l的两个格子（i，k）和（l，k）分别表示从不同的发地节点出发，到达同一收地节点j的两条边（见下表和图）。

i l

j （i，j） 表 4.3

如果运输表中有若干个格子，他们中相邻的两个都分别位于同一行或同一列，例如在下表中六个格子（i，j），（i，k），（l，k），（l，n），（m，n）和（m，j），将位于同一行和同一列的两个格子连结起来，在运输表中构成一个闭回路。在相应的网络图中，这六个格子对应的六条边也组成一个闭回路。

i l m

j （i，j） （m，j）

k （i，k） （l，k） 表 4.4

n （l，n） （m，n） m 图4.7

n l k

i j k （i，k） （l，k） 图4.6 l k

j i 运输表中的闭回路还可以出现更复杂的情况，如下表和下图所示。

138 / 42

i l m

j （i，j） （l，j） k （i，k） （m，k） 表 4.5

n （l，n） （m，n）

i j l k m 图4.8 n 综上所述，总结运输表中一个基必须具备的特点： 1、 一个基应占表中的m+n-1格；

2、 构成基的同行同列格子不能构成闭回路；

3、 一个基在表中所占的m+n-1个格子应包括表的每一行和每一列。 例4.4 在例4.3.1中的运输网络的几个基分别用网络和运输表的表示如下： (a)系数矩阵、网络图和运输表

x11x12x13x21x22x23xa 1 1 ?1?0A???1??0??0 1 2

100101

100012

01100010103

010010?0?? 0??0?1??2 2 图4.9 3 （1,1） （1,2） （1,3） （2,1） （2,2） （2,3） 139 / 42

(b)第一个基的矩阵、网络图和运输表

x11x12x13x21xa?11100??B??00010???10010?? ?01000???00101??? 1

2

3

1 （1,1） （1,2） （1,3） 2

（2,1） (c) 第二个基的矩阵、网络图和运输表

x11x12x22x23xa?11000??

B??00110???10000?? ?01100???00011??? 1

2

3 1 （1,1） （1,2） 2

（2,2） （2,3） (d)第三个基的矩阵、网络图和运输表

x11x13x22x23xa?11000??

B??00110???10000?? ?00100???01011???140 / 42

1 1 2 2 图4.10 3 1 1 2 2 图4.11 3 1 1 2 2 图4.12 3

1 2

1 （1,1） 2 3 （1,3） （2,2） （2,3） 141 / 42

§4.5 非基列向量用基向量表示

在线性规划中，设B是A矩阵的一个基，且B=[aB1，aB2，…，aBm]，则A中的任一非基向量aj（j∈R）必定可以用基向量aB1，aB2，…，aBm唯一地线性表出，其线性组合的系数就是Yj，这是因为

Yj=B-1aj

即

aj?BYj?aB1?aB2?aBm??y1j??y??2j???? ???ymj??y1jaB1?y2jaB2???ymjaBm这就是说，向量Yj就是用基向量表出一个非基向量aj的系数。

在运输问题中如果确定了一个基，非基向量aij也可以由基向量唯一地表出，由于运输问题的特殊性，表出系数Yij可以很方便地确定。请看下一例子。

例4.5 以具有2个发地，3个收地的运输问题为例子，这个运输问题的网络图和系数矩阵如下：

(1,1)(1,2)(1,3)(2,1)(2,2)(2,3)ea1 1 2 2 图4.13 3 ?1?0A???1??0??0

10010100010110001010010010?0?? 0??0?1??取基B=[a11，a12，a13，a23，ea]，非基向量为a21，基矩阵、网络图中的非基边（用虚线表示）、基边（用实线表示），并取从发地到收地的方向为各边的方向。

142 / 42

(1,1)(1,2)(1,3)(2,3)ea?1?0B???1??0??0

1001010001010010?0?? 0??0?1?? 1 1 2 2 3 图4.14 由于任何一个非基向量总是与基向量实线性相关的，因此在网络图中任一条非基边必定与若干条基边形成闭回路。根据运输矩阵的结构，对任何一个列向量aij，有aij=ei+em+j。在上面的问题中，非基向量a21可以表示为：

a21=e2+e2+1=e2+e3

基向量a11，a12，a13，a23可以表示为：

a11=e1+e2+1=e1+e3 a12=e1+e2+2=e1+e4 a13=e1+e2+3=e1+e5 a23=e2+e2+3=e2+e5

因此

a21-a11+a13-a23=(e2+e3)-(e1+e3)+(e1+e5)-(e2+e5)=0

即

a21=a11-a13+a23

由于基向量a12和ea不在这个回路中，它在a12的表达式中的系数是0，因此非基向量a21用所有基向量的表出形式为：

a21?1?a11?0?a12?(?1)?a13?1?a23?0?ea

?1??0?????a11a12a13a23ea???1??By21???1???0??

由此可以看出

1 1 2 2 图4.15 3 143 / 42

?1??0???Y21???1?

???1???0??从这个例子可以看出，非基向量由基向量表出的方法和表出的系数可以由该非基向量与有关的基向量形成的回路来确定（见上图）。选定该非基边的方向作为闭回路的方向，如果一个基边出现在该回路中，并且与回路的方向相同，则表出系数为-1，如果基边的方向和回路的方向相反，则表出系数为+1，如果基边不在回路中，表出系数为0。

从给定非基边的起点（发地）出发，沿着回路方向前进，第一次遇到的基边的方向一定和回路方向相反，第二次遇到的基边方向一定和回路方向相同，同向和反向交替出现，因此，各基边的表出系数一定是+1，-1交替出现。

与网络图对应，在运输表中非基向量用基向量表示的方法也可以相应得到。例如以上的运输问题，相应的运输表如下左表所示。

1 2

1

2

3

1 2

1 B(+1) N 2 B(0) 3 B(-1) B(+1) （1,1） （1,2） （1,3） （2,1） （2,2） （2,3） 表 4.6

对应于基B=[a11，a12，a13，a23，ea]的格子为用B表示，非基向量a21相应的格子用N表示，见上面右表。

运输表中非基向量用用基向量表出的系数是这样确定的：（按任一方向）沿着表中的闭回路前进，在第一个转角处基向量的表出系数为+1，下一个转角处基向量的表出系数为-1，以后依次交替变化，由于沿闭回路回到出发的非基向量以前一定要经过奇数次转角，因此最后一个转角处的基向量的表出系数一定也是+1。凡是不在闭回路上或不在闭回路转角处的基向量的表出系数均为0。

在上面的表中，非基向量N（2，1）与基向量B（1，1）、B（1，3）、B（2，3）构成一个闭回路，相应的表出系数依次为+1、-1和+1；基向量B（1，2）不在闭回

144 / 42

路的转角处，表出系数为0。因此，非基向量a21的表出形式为：

a21?1?a11?0?a12?(?1)?a13?1?a23

例4.6 设有4个发地，5个收地的运输问题，运输表和网络图如下： 1 2 3 4 5

1 B B 2 B 3 B B B B 4

N B 表 4.7

取其中m+n-1=4+5=9个基向量a11，a12，a14，a21，a31，a33，a34，a35和a45，非基向量a42与基向量

构成的闭回路

如右图。根据基向量的表出系数

由+1开始，+1、-1交替的原则，以上非基向量用这些基向量表出的形式为：

a42=(+1)a12+(-1)a11+(+1)a31+(-1)a35+(+1)a45+0ea

如果所有基向量按以下次序排列

B=[a11，a12，a21，a31，a33，a34，a35，a45，

ea]

因而a42用这些基向量表示的表出系数

Y42=[-1，+1，0，+1，0，0，-1，+1，0]T

145 / 42

1 1 2 2 3 3 4 4 图4.16 5 y=-1 1 1 y=+1 2 2 y=+1 3 3 y=-1 4 4 y=+1 5 图4.17

§4.6 运输问题单纯形法

运输问题单纯形法的基本步骤和线性规划一样，包括以下步骤，但具体实施是在运输表上实现。

1、 求得一个初始基础可行解；

2、 对非基变量xij计算检验数zij-cij，根据各非基变量的检验数zij-cij值，确定

最优性或选择进基变量；

3、 当进基变量xij进基时，根据基变量的变化，求出最先降为0的基变量确定

为离基变量；

4、 进行基变换，获得新的基础可行解并转步骤2。

4.6.1 确定初始基础可行解

1、 西北角法

西北角法是按发地和收地的编号为序，依次顺序供给的原则获得初始基础可行解的一种方法。它是从确定发地1到收地1的运量开始。这个位置按地图的方位来说是西北角，因而得名。从发地1到收地1的运量取发地1的供应量（30）和收地1的需求量（15）两者中小的一个安排，如果发地1的供应量没有用完，则将剩余的供应量向收地2发送，…，依次类推，直到最后一个发地的供应量全部运出，最后一个收地的需求量全部满足为止。

例4.7 给出运输表如下。发地1的供应量为30，收地1的需求量为15，在（1，1）上安排运量15。发地1和收地1的供应量和需求量分别变为15和0。

1 2 3 4

10 13 11 14 1 15 11 12 8 13 2 9 16 7 12 3 15 9 10 13 4 30-15 45 50 25

15-15 20 31 84

发地1的供应量为15，收地2的需求量为20，在（1，2）上安排运量15，发

146 / 42