3. 运输问题的特征
特征1：运输问题一定有可行解； 特征2：运输问题一定有最优解； 特征3：运输问题每一组基对应 m+n-1个基变量； 特征4：运输问题的 m+n-1个基变量构成的变量组不含 闭回路； 特征5：任意一个非基变量和 m+n-1个基变量组成的变 量组中必定存在一条并且只存在唯一一条闭回路； 特征6：如果运输问题中的供应量和需求量都是整数， 则任一基解中各变量的取值也都是整数。
1. 运输问题的定义
例1： 某集团新购进一批钢材，分别存储在三个仓库，现在 要将这批钢材运到分布在各地的四个工厂。各仓库的库存量、 各工厂的需求量以及从各仓库往各个工厂每运送一吨钢材所 需的费用见下表，问如何调运才能使总运费降到最低？
仓库A1
工厂 B1 2
仓库A2 1
仓库A3 8
需求量 3
工厂 B2 9
北京物资学院运筹学教学课件
第三章 运输问题
北京物资学院信息学院 2010年11月
本章主要内容
第一节 运输问题的数学模型及其特征 第二节 运输问题的求解—表上作业法 第三节 产销不平衡的运输问题及应用
第一节 运输问题的数学模型及其特征
1. 运输问题的定义 2. 运输问题的数学模型 3. 运输问题的特征
第一步：编制初始调运方案
要求得运输问题的初始基可行解，必须保证找到 m+n–1 个基变量. 运输问题的任意m+n-1个变量构成一组基变量的充要条 件是变量组中不含闭回路.
关键:找出m+n-1个不含闭回路的变量。 问题：如何使得一个选定的变量不包含在闭回路中？
1 西北角法（左上角法） 2 最小元素法 3 Vogel 法
i1
xij
0,
i 1,
2, ......m, j 1,
2, ......n
m
n
（其中
ai
b
）
j
i 1
j 1
运输问题的约束方程组系数矩阵及特征
x11 x12 ....x1n
1 1.......1
A
1
1
1
x21 x22 ....x2n ...... xm1 xm2 ....xmn
1 1.......1
3
4
8
工厂 B3 10
4
2
4
工厂 B4 7
2
5
6
库存量
9 5 7
运输问题：有m个供应点向n个需求点供应某种物资，这m
个供应点A1、A2、…...Am的供应量分别为a1、a2、…...am；n 个 需 求 点 B1、B2、…...Bn 的 需 求 量 分 别 为 b1、b2、…...bn；
已知从任一供应点Ai向任一需求点Bj运输一个单位物资的费 用为cij。问采取什么样的物资调运方案才能使总运费最省？
A2
A3
X31
X35
A4
X41
X43
B1
B2
B3
B4
B5Βιβλιοθήκη A1X11X12A2
X21
X22
X24
A3
A4
X42
X44
（1）每个顶点都是转折点；
（2）闭回路是一条闭合的折线，每一条边都是水 平或垂直的；
（3）闭回路上同一行（列）的顶点有偶数个。
闭回路上的点对应的系数列向量线性相关。
Plk
Pls
Pij
2
A3
1
需求量 2
-2
B2 8
并称集合中每一个变量为此闭回路的一个顶点；称连 接相邻两个变量（顶点）以及连接最后一个顶点和第 一个顶点的线段为此闭回路的边。
B1
B2
B3
B4
B5
A1
X13
X15
A2
A3
X31
X33
A4
X41
X45
B1
B2
B3
B4
B5
A1
X12
X14
A2
A3
X32
X34
A4
B1
B2
B3
B4
B5
A1
X13
X15
2
9
10
3
5
7
1
9 -3 -1 -5
A2
1
A3
8
3
4
3
4
2
4
2
5
5
5 -5 7 -4 -3
需求量 3
8
4
6
-3
-3
-4
-5
-1
-5
对应的总运费为
C 2= 2×3 + 9×5 + 7×1 + 2×5 + 4×3 + 2×4 =88
退化情况的处理 用西北角法求下列运输问题的第一个基可行解
B1
A1
7
2
A2
B1
B2
…
Bn 供应量
A1
c11
c12
…
c1n
a1
A2
c21
c22
…
c2n
a2
…
…
…
…
…
…
Am
cm1
需求量
b1
cm2
…
cmn
am
b2
…
bn
2. 运输问题的数学模型
mn
min z
cij xij
i 1 j1
n
xij ai
(i 1,
2, ......m)
j1
m
s.t. xij bj ( j 1, 2, ......n)
西北角法(左上角法)
B1
A1
2
3
A2
1
A3
8
需求量 3
-3
B2
B3
9
10
6
3
4
2
3
4
2
1
8
4
-6
-3
-2
-1
B4 7
2
5
6
6
-6
库存量 9 -3 -6 5 -2 -3
7 -1 -6
对应的总运费为
C 1= 2×3 + 9×6 + 3×2 + 4×3 + 2×1 + 5×6 = 110
最小元素法
B1
1 1 1
......... ..........
1 1.......1
1
1
1
m行 n行
1. 矩阵A是一个m+n行mn列的矩阵，它的秩为m+n-1。 2. 运输问题应该有m+n-1个基变量。 3. 系数矩阵非常稀疏。 4. xij的系数列向量为：
Pij (0....1...0....1...0)T ei em j
闭回路
定义：凡是能够排列成下列序列的一组变量的集合就 称为运输问题的一个闭回路。
x , x , x , x , , x , x i1 j1 i1 j2 i2 j2 i2 j3
is js is j1
或
x , x , x , x , , x , x i1 j1 i2 j1 i2 j2 i3 j2
is js i1 js
Pik
Puj
Pus
由于 Pij ei em j
容易证明 Pij Pik Plk Pls Pus Puj 0
第二节 运输问题的求解--表上作业法
表上作业法的基本步骤：
第一步：编制初始调运方案，即寻找第一个基可行解；
第二步：计算各非基变量的检验数； 第三步：判断当前的调运方案是否是最优方案，如果已经 是最优，则算法结束，问题已经解决；否则，转第四步； 第四步：确定进基变量和出基变量，调整非最优的调运 方案，获得更好的调运方案；转第二步。
A1
2
A2
1
3
A3
8
需求量 3
-3
B2
B3
9
10
5
3
4
4
3
8
-3 -5
2
4
4
-4
B4 7
4
2
2
5
库存量 9 -4 -5
5 -3-2 7 -4 -3
6
-2
-4
对应的总运费为
C 2= 9×5 + 7×4 + 1×3 + 2×2 + 4×3 + 2×4 = 100
Vogel 法
B1
B2
B3
B4 库存量
A1