第三章 特殊的线性规划
—— 运输问题
& 模型及其特点
& 求解思路及相关理论
& 求解方法 —— 表上作业法
& 运输问题的推广
? 产销不平衡的运输问题
? 转运问题
3.1 运输问题模型与性质
一, 运输问题的数学模型
1,运输问题的一般提法,某种物资有若
干产地和销地, 现在需要把这种物资从各个
产地运到各个销地, 产量总数等于销量总数 。
已知 各产地的 产量 和各销地的 销量 以及各产
地到各销地的 单位运价 （ 或运距 ）, 问应如
何组织调运, 才能使 总运费 （ 或总运输量 ）
最省？
单位 根据具体问题选择确定 。
表 3-1 有关信息
单位 运价 销
或运距 地
产地
B1 B2 … Bn 产 量
A1
A2
┆
Am
c11 c12 … c1 n
c21 c22 … c2n
… … …
cm1 cm2 … cm n
a1
a2
┆
am
销 量 b1 b2 … bn
??
??
?
n
j
j
m
i
i ba
11
2、运输问题的数学模型
设 xij为从产地 Ai运往销地 Bj的物资数量
（ i=1,… m； j=1,… n）, 由于从 Ai
运出的物资总量应等于 Ai的产量 ai,因此
xij应满足：
miax
n
j
iij,,2,1
1
????
?
同理，运到 Bj的物资总量应该等于 Bj
的销量 bj，所以 xij还应满足：
总运费为：
?
?
??
m
i
jij njbx
1
,,1 ?
? ?
? ?
?
m
i
n
j
ijij
xcz
1 1
运输问题的数学模型
?
?
?
?
?
?
?
?
?
???
??
??
?
?
?
? ?
?
?
? ?
njmix
njbx
miax
ts
xcM i n Z
ij
m
i
jij
n
j
iij
m
i
n
j
ijij
,,1;,1,0
,,1
,,1
..
1
1
1 1
??
?
?
（ 3-6）
??
?
?
??
?
?
?? ?
? ?
m
i
n
j
ji ba
1 1
产销平衡条件
二、运输问题的特点与性质
1,约束方程组的系数矩阵具有特殊的结构
写出式 （ 3-1） 的系数矩阵 A,形式如下：
mnmmnn xxxxxxxxx ???????,,,,,,,,,;,,,212222111211
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
111
111
111
111
111
111
?
????
?
?
?
?
?
?
?
m行
n行
?矩阵的元素均为 1或 0；
?每一列只有两个元素为 1，其余元素均为 0；
?列向量 Pij =(0,…, 0,1,0,…,0,1,0,…0) T，
其中两个元素 1分别处于第 i行和第 m+j行。
?将该矩阵分块，特点是,前 m行构成 m个
m× n阶矩阵,而且 第 k个矩阵只有第 k行元素
全为 1，其余元素全为 0（ k=1,…, m） ； 后 n
行构成 m个 n阶单位阵 。
2.运输问题的基变量总数是 m + n -1
写出增广矩阵
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
n
m
b
b
b
a
a
a
A
111
111
111
111
111
111
2
1
2
1
?
?????
?
?
??
??
??
?
?
mnmmnn xxxxxxxxx ???????,,,,,,,,,;,,,212222111211
证明系数矩阵 A及其增广矩阵的秩都是 m+n-1
?前 m行相加之和减去后 n行相加之和结果是
零向量，说明 m+n个行向量线性相关，因此
的秩小于 m+n；？A
A因此 的秩恰好等于 m+n-1，又 D本身就含于
A中，故 A的秩也等于 m+n-1
?由 的第二至 m+n行和前 n列及
对应的列交叉处元素构成 m+n-1阶方阵 D 非奇
异；？
A
13121,,,mxxx ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
n
m
b
b
b
a
a
a
A
111
111
111
111
111
111
2
1
2
1
?
?????
?
?
??
??
??
?
?
mnmmnn xxxxxxxxx ???????,,,,,,,,,;,,,212222111211
0
1
0
1
1
1
1
1
1
1111
1
1
1
1
???
?
?
?
?
?
?
?
m
D ）（
按第一列展开
可以证明, m+n个约束方程中的任意 m+n-1个
都是线性无关的 。
定义 3.1凡是能排成
(3-4)
或 (3-5)
形式的 变量集合 称为一个 闭回路,并称式中 变
量 为该 闭回路的顶点 ；其中 互不
相同,互不相同 。
132222111,,,,,jijijijijiji sss xxxxxx ?
sss jijijijijiji xxxxxx 123221211,,,,,?
siii,,,21 ?
sjjj,,,21 ?
3,m+n-1个变量构成基变量的 充要条件 是
它们不构成 闭回路 。
X11 X13
X21 X24
X33
B1 B2 B3 B4
A1 X12 X14
A2 X22 X23
A3 X31 X32 X34
例 3-1 设 m=3,n=4，决策变量 xij表示从产地
Ai到销地 Bj的调运量，列表如下，给出闭回路
在表中的表示法 ——
用折线连接起来的顶点变量 。
},,,,,{ 212434331311 xxxxxx
练习 3-1 请给出闭回路 和
在表中的表示法 。
},,,{ 14242212 xxxx
},,,,,{ 121131332322 xxxxxx
X11 X13
X21 X24
X33
B1 B2 B3 B4
A1 X12 X14
A2 X22 X23
A3 X31 X32 X34
练习 3-2下面的折线构成的封闭曲线连接的顶
点变量哪些不可能是闭回路？为什麽？
（ a） （ b） （ c） （ d） （ e）
? 表中的折线构成一条封闭曲线, 且所有的
边都是 水平 或 垂直 的；为什麽？
? 表中的 每一行 和 每一列 由折线相连的闭回
路的顶点 只有两个 ；为什麽？
有关闭回路的一些重要结果
定理 3-1 设 是一个闭
回路, 则该闭回路中的变量所对应的系数列
向量 具有下面的
关系：
132222111,,,,,jijijijijiji sss xxxxxx ?
132222111,,,,,jijijijijiji sss PPPPPP ?
0132222111 ??????? jijijijijiji sss PPPPPP ?
注意,列向量 Pij=(0,…,0,1,0,…,0,1,0,…0) T中两
个元素 1分别处于第 i行和第 m+j行，直接计算
即可得到结果。
定理的证明可 借助定理 3-1和高等
代数中, 向量组中, 若 部分向量线性
相关, 则整个向量组就线性相关, 的
定理得到 。
定理 3-2 若变量组
中有一个部分组构成闭回路, 则该变
量组对应的系数列向量线性相关 。
rr jijiji xxx,,,2211 ?
定理 3-3 不包含任何闭回路的变量组中
必有孤立点 。
所谓 孤立点 是指 在所在行或列中出现于该
变量组中的唯一变量 。
可用反证法证明结论成立 。
定理 3-4 r个变量 对应的
系数列向量线性无关 充要条件 是该变量
组 不包含闭回路 。
rr jijiji xxx,,,2211 ?
必要性的证明可考虑用反证法结合定理
3-2的结果进行, 充分性的证明可借助
定理 3-3,根据向量组线性无关的定义
用归纳法得证 。
推论 m+n-1个变量构成基变量的充要
条件是该变量组不含闭回路 。
三、运输问题的求解方法
1、单纯形法（为什麽？）
2、表上作业法
由于问题的特殊形式而采用的
更简洁、更方便的方法
—— 运输问题
& 模型及其特点
& 求解思路及相关理论
& 求解方法 —— 表上作业法
& 运输问题的推广
? 产销不平衡的运输问题
? 转运问题
3.1 运输问题模型与性质
一, 运输问题的数学模型
1,运输问题的一般提法,某种物资有若
干产地和销地, 现在需要把这种物资从各个
产地运到各个销地, 产量总数等于销量总数 。
已知 各产地的 产量 和各销地的 销量 以及各产
地到各销地的 单位运价 （ 或运距 ）, 问应如
何组织调运, 才能使 总运费 （ 或总运输量 ）
最省？
单位 根据具体问题选择确定 。
表 3-1 有关信息
单位 运价 销
或运距 地
产地
B1 B2 … Bn 产 量
A1
A2
┆
Am
c11 c12 … c1 n
c21 c22 … c2n
… … …
cm1 cm2 … cm n
a1
a2
┆
am
销 量 b1 b2 … bn
??
??
?
n
j
j
m
i
i ba
11
2、运输问题的数学模型
设 xij为从产地 Ai运往销地 Bj的物资数量
（ i=1,… m； j=1,… n）, 由于从 Ai
运出的物资总量应等于 Ai的产量 ai,因此
xij应满足：
miax
n
j
iij,,2,1
1
????
?
同理，运到 Bj的物资总量应该等于 Bj
的销量 bj，所以 xij还应满足：
总运费为：
?
?
??
m
i
jij njbx
1
,,1 ?
? ?
? ?
?
m
i
n
j
ijij
xcz
1 1
运输问题的数学模型
?
?
?
?
?
?
?
?
?
???
??
??
?
?
?
? ?
?
?
? ?
njmix
njbx
miax
ts
xcM i n Z
ij
m
i
jij
n
j
iij
m
i
n
j
ijij
,,1;,1,0
,,1
,,1
..
1
1
1 1
??
?
?
（ 3-6）
??
?
?
??
?
?
?? ?
? ?
m
i
n
j
ji ba
1 1
产销平衡条件
二、运输问题的特点与性质
1,约束方程组的系数矩阵具有特殊的结构
写出式 （ 3-1） 的系数矩阵 A,形式如下：
mnmmnn xxxxxxxxx ???????,,,,,,,,,;,,,212222111211
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
111
111
111
111
111
111
?
????
?
?
?
?
?
?
?
m行
n行
?矩阵的元素均为 1或 0；
?每一列只有两个元素为 1，其余元素均为 0；
?列向量 Pij =(0,…, 0,1,0,…,0,1,0,…0) T，
其中两个元素 1分别处于第 i行和第 m+j行。
?将该矩阵分块，特点是,前 m行构成 m个
m× n阶矩阵,而且 第 k个矩阵只有第 k行元素
全为 1，其余元素全为 0（ k=1,…, m） ； 后 n
行构成 m个 n阶单位阵 。
2.运输问题的基变量总数是 m + n -1
写出增广矩阵
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
n
m
b
b
b
a
a
a
A
111
111
111
111
111
111
2
1
2
1
?
?????
?
?
??
??
??
?
?
mnmmnn xxxxxxxxx ???????,,,,,,,,,;,,,212222111211
证明系数矩阵 A及其增广矩阵的秩都是 m+n-1
?前 m行相加之和减去后 n行相加之和结果是
零向量，说明 m+n个行向量线性相关，因此
的秩小于 m+n；？A
A因此 的秩恰好等于 m+n-1，又 D本身就含于
A中，故 A的秩也等于 m+n-1
?由 的第二至 m+n行和前 n列及
对应的列交叉处元素构成 m+n-1阶方阵 D 非奇
异；？
A
13121,,,mxxx ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
n
m
b
b
b
a
a
a
A
111
111
111
111
111
111
2
1
2
1
?
?????
?
?
??
??
??
?
?
mnmmnn xxxxxxxxx ???????,,,,,,,,,;,,,212222111211
0
1
0
1
1
1
1
1
1
1111
1
1
1
1
???
?
?
?
?
?
?
?
m
D ）（
按第一列展开
可以证明, m+n个约束方程中的任意 m+n-1个
都是线性无关的 。
定义 3.1凡是能排成
(3-4)
或 (3-5)
形式的 变量集合 称为一个 闭回路,并称式中 变
量 为该 闭回路的顶点 ；其中 互不
相同,互不相同 。
132222111,,,,,jijijijijiji sss xxxxxx ?
sss jijijijijiji xxxxxx 123221211,,,,,?
siii,,,21 ?
sjjj,,,21 ?
3,m+n-1个变量构成基变量的 充要条件 是
它们不构成 闭回路 。
X11 X13
X21 X24
X33
B1 B2 B3 B4
A1 X12 X14
A2 X22 X23
A3 X31 X32 X34
例 3-1 设 m=3,n=4，决策变量 xij表示从产地
Ai到销地 Bj的调运量，列表如下，给出闭回路
在表中的表示法 ——
用折线连接起来的顶点变量 。
},,,,,{ 212434331311 xxxxxx
练习 3-1 请给出闭回路 和
在表中的表示法 。
},,,{ 14242212 xxxx
},,,,,{ 121131332322 xxxxxx
X11 X13
X21 X24
X33
B1 B2 B3 B4
A1 X12 X14
A2 X22 X23
A3 X31 X32 X34
练习 3-2下面的折线构成的封闭曲线连接的顶
点变量哪些不可能是闭回路？为什麽？
（ a） （ b） （ c） （ d） （ e）
? 表中的折线构成一条封闭曲线, 且所有的
边都是 水平 或 垂直 的；为什麽？
? 表中的 每一行 和 每一列 由折线相连的闭回
路的顶点 只有两个 ；为什麽？
有关闭回路的一些重要结果
定理 3-1 设 是一个闭
回路, 则该闭回路中的变量所对应的系数列
向量 具有下面的
关系：
132222111,,,,,jijijijijiji sss xxxxxx ?
132222111,,,,,jijijijijiji sss PPPPPP ?
0132222111 ??????? jijijijijiji sss PPPPPP ?
注意,列向量 Pij=(0,…,0,1,0,…,0,1,0,…0) T中两
个元素 1分别处于第 i行和第 m+j行，直接计算
即可得到结果。
定理的证明可 借助定理 3-1和高等
代数中, 向量组中, 若 部分向量线性
相关, 则整个向量组就线性相关, 的
定理得到 。
定理 3-2 若变量组
中有一个部分组构成闭回路, 则该变
量组对应的系数列向量线性相关 。
rr jijiji xxx,,,2211 ?
定理 3-3 不包含任何闭回路的变量组中
必有孤立点 。
所谓 孤立点 是指 在所在行或列中出现于该
变量组中的唯一变量 。
可用反证法证明结论成立 。
定理 3-4 r个变量 对应的
系数列向量线性无关 充要条件 是该变量
组 不包含闭回路 。
rr jijiji xxx,,,2211 ?
必要性的证明可考虑用反证法结合定理
3-2的结果进行, 充分性的证明可借助
定理 3-3,根据向量组线性无关的定义
用归纳法得证 。
推论 m+n-1个变量构成基变量的充要
条件是该变量组不含闭回路 。
三、运输问题的求解方法
1、单纯形法（为什麽？）
2、表上作业法
由于问题的特殊形式而采用的
更简洁、更方便的方法
