即
秩A=m+n-1。
在线性规划问题中，约束的系数矩阵要求行满秩的，为了使运输问题系数矩阵行满秩，在A矩阵中增加一个列向量em+n形成增广矩阵
这样增广矩阵的秩就等于m+n，因而是行满秩的。
并且中任何一个基矩阵，都必定包含单位向量em+n。
例4.2.1设一个运输网络如右图，它的系数矩阵为
增广矩阵为
1
2
2
3
1
图4.3
增加的单位列向量em+n=e5相当于在在网络图中增加一条边，它与收点3关联，但不与任何发点关联，这条边称为人工边。
设这条边上的运输量为xa，增广运输问题对应于第三个收点的约束称为
x13+x23+xa=d3
由于
x13+x23=d3
因此，对运输问题的任何一个可行解，都有
xa=0。
4.2.2A矩阵的单位模性质
运输问题的系数矩阵A具有以下性质：
A矩阵中任何一个k阶子矩阵Ak（k=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，这时显然有detAk=0。
3、Ak中至少有一列，其中只有一个1。
这时可以将detAk按这一列展开，设对应于这个1的代数余子式为Ak-1，则有
detAk=±detAk-1
其中Ak-1是k-1阶方阵。
对Ak-1同样有
detAk-1=0
或者
detAk-1=±detAk-2
最后有
detAk=0
或者
detAk=±detAk-1=±detAk-2=…=±detA1=0或±1。
4.2.3基矩阵的三角性
设B是的一个基，B中至少有一列只包含一个1，否则，detB=0不成为一个基。
将B的行列交换，总可以使B成为
其中detBm+n-1≠0，因而Bm+n-1中也至少有一列只有一个1，对Bm+n-1再进行行列交换，得到
依次不断对剩下的方阵进行行列交换，最后可以得到
是一个上三角矩阵。
例4.2设一个运输问题的系数增广矩阵为
=
取其中一个基
对B进行行列交换，成为以下上三角矩阵
求解相应的方程组
由此得到
x12=10，x11=15，x23=20，x13=5，xa=0
由A的基矩阵的三角性以及A矩阵中仅含有元素0和1，可以知道，如果运输问题各发地的供应量和收地的需求量都是整数，运输问题的任何基础可行解都是整数，因而最优解也是整数。
§4.3基在网络图和运输表中的表示
k
j
l
i
图4.4
从前一节已经知道，运输问题的一个基是由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对应的一行全为0，即detB=0。
B不可能成为一个基。
例4.3对于2个发点3个收点的运输问题，网络图如图4.5（a）所示。
图4.5（b）、（c）、（d）都是这个问题的基，这些基都由m+n-1=2+3-1=4条边组成，都不构成回路，并且与每一个节点关联。
正如线性规划矩阵的列向量组成的基一样，一个网络的基的个数是非常多的，以上只是这些基中的几个例子。
（a）网络图 （b）第一个基
（c）第二个基 （d）第三个基
图4.5
§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
j
k
l
图4.6
j
k
i
（i，j）
（i，k）
l
（l，k）
表4.3
如果运输表中有若干个格子，他们中相邻的两个都分别位于同一行或同一列，例如在下表中六个格子（i，j），（i，k），（l，k），（l，n），（m，n）和（m，j），将位于同一行和同一列的两个格子连结起来，在运输表中构成一个闭回路。
在相应的网络图中，这六个格子对应的六条边也组成一个闭回路。
l
n
m
j
k
i
图4.7
j
k
n
i
（i，j）
（i，k）
l
（l，k）
（l，n）
m
（m，j）
（m，n）
表4.4
运输表中的闭回路还可以出现更复杂的情况，如下表和下图所示。
l
n
m
j
k
i
图4.8
j
k
n
i
（i，j）
（i，k）
l
（l，j）
（l，n）
m
（m，k）
（m，n）
表4.5
综上所述，总结运输表中一个基必须具备的特点：
1、一个基应占表中的m+n-1格；
2、构成基的同行同列格子不能构成闭回路；
3、一个基在表中所占的m+n-1个格子应包括表的每一行和每一列。
例4.4在例4.3.1中的运输网络的几个基分别用网络和运输表的表示如下：
1
2
2
3
1
图4.9
（a）系数矩阵、网络图和运输表
1
2
3
1
（1,1）
（1,2）
（1,3）
2
（2,1）
（2,2）
（2,3）
（b）第一个基的矩阵、网络图和运输表
1
2
2
3
1
图4.10
1
2
3
1
（1,1）
（1,2）
（1,3）
2
（2,1）
1
2
2
3
1
图4.11
（c）第二个基的矩阵、网络图和运输表
1
2
3
1
（1,1）
（1,2）
2
（2,2）
（2,3）
1
2
2
3
1
图4.12
（d）第三个基的矩阵、网络图和运输表
1
2
3
1
（1,1）
（1,3）
2
（2,2）
（2,3）
§4.5非基列向量用基向量表示
在线性规划中，设B是A矩阵的一个基，且B=[aB1，aB2，…，aBm]，则A中的任一非基向量aj（j∈R）必定可以用基向量aB1，aB2，…，aBm唯一地线性表出，其线性组合的系数就是Yj，这是因为
Yj=B-1aj
即
这就是说，向量Yj就是用基向量表出一个非基向量aj的系数。
在运输问题中如果确定了一个基，非基向量aij也可以由基向量唯一地表出，由于运输问题的特殊性，表出系数Yij可以很方便地确定。
请看下一例子。
1
2
2
3
1
图4.13
例4.5以具有2个发地，3个收地的运输问题为例子，这个运输问题的网络图和系数矩阵如下：
取基B=[a11，a12，a13，a23，ea]，非基向量为a21，基矩阵、网络图中的非基边（用虚线表示）、基边（用实线表示），并取从发地到收地的方向为各边的方向。
1
2
2
3
1
图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用所有基向量的表出形式为：
2
1
2
3
1
图4.15
由此可以看出
从这个例子可以看出，非基向量由基向量表出的方法和表出的系数可以由该非基向量与有关的基向量形成的回路来确定（见上图）。
选定该非基边的方向作为闭回路的方向，如果一个基边出现在该回路中，并且与回路的方向相同，则表出系数为-1，如果基边的方向和回路的方向相反，则表出系数为+1，如果基边不在回路中，表出系数为0。
从给定非基边的起点（发地）出发，沿着回路方向前进，第一次遇到的基边的方向一定和回路方向相反，第二次遇到的基边方向一定和回路方向相同，同向和反向交替出现，因此，各基边的表出系数一定是+1，-1交替出现。
与网络图对应，在运输表中非基向量用基向量表示的方法也可以相应得到。
例如以上的运输问题，相应的运输表如下左表所示。
1
2
3
1
2
3
1
（1,1）
（1,2）
（1,3）
1
B（+1）
B（0）
B（-1）
2
（2,1）
（2,2）
（2,3）
2
N
B（+1）
表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）不在闭回路的转角处，表出系数为0。
因此，非基向量a21的表出形式为：
例4.6设有4个发地，5个收地的运输问题，运输表和网络图如下：
1
3
4
2
2
3
4
5
1
图4.16
1
2
3
4
5
1
B
B
2
B
3
B
B
B
B
4
N
B
表4.7
1
3
4
2
2
3
4
5
1
y=-1
y=+1
y=+1
y=-1
y=+1
图4.17
取其中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
§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
1
10
11
9
15
30-15
15
2
13
12
16
9
45
3
11
8
7
10
50
4
14
13
12
13
25
15-15
20
31
84
发地1的供应量为15，收地2的需求量为20，在（1，2）上安排运量15，发地1的供应量变为0，收地2的需求量变为5；
1
2
3
4
1
10
11
9
15
15-15
15
15
2
13
12
16
9
45
3
11
8
7
10
50
4
14
13
12
13
25
0
20-15
31
84
收地2的需求量为5，发地2的供应量为45，在（2，2）上安排运量5，发地2的供应量变为40，收地2的需求量变为0；
1
2
3
4
1
10
11
9
15
0
15
15
2
13
12
16
9
45-5
5
3
11
8
7
10
50
4
14
13
12
13
25
0
5-5
31
84
发地2的供应量为40，收地3的需求量为31，在（2，3）上安排运量31，发地3的供应量变为9，收地3的需求量变为0；
1
2
3
4
1
10
11
9
15
0
15
15
2
13
12
16
9
40-31
5
31
3
11
8
7
10
50
4
14
13
12
13
25
0
0
31-31
84
发地2的供应量为9。
收地4的需求量为84，在（2，4）上安排运量9，发地2的供应量变为0，收地4的需求量变为75；
1
2
3
4
1
10
11
9
15
0
15
15
2
13
12
16
9
9-9
5
31
9
3
11
8
7
10
50
4
14
13
12
13
25
0
0
0
84-9
收地4的需求量为75，发地3的供应量为50，安排（3，4）上的运量为50，发地3的供应量0，收地4的需求量25；
1
2
3
4
1
10
11
9
15
0
15
15
2
13
12
16
9
0
5
31
9
3
11
8
7
10
50-50
50
4
14
13
12
13
25
0
0
0
75-50
发地4的供应量为25，收地4的需求量为25，安排（4，4）上的运量25，发地4的供应量为0，收地4的需求量为0，供求和需求都得到满足。
1
2
3
4
1
10
11
9
15
0
15
15
升级会员 