B4 9 8
A3
需求 35 40 55 65
80
195
6
3
7
5
问应如何调运，可使得总运输费最小?
31 石家庄经济学院 管理科学与工程学院
解：用西北角法求初始基本可行解
产销平衡表 运价表
销 产 A1 A2 A3 需求
B1
B2
B3
B4
产量 75
B1 3 2 6
B2 8 9 3
B3 5 4 7
B4 9 8 5
第3章 运输问题
学习要点 Sub title
• 1．掌握运输问题的数学模型、系数矩阵特殊形式 • 2．掌握用西北角法、最小元素法求初始基可行解 • 3．掌握位势法求解、牢固掌握三合一表格求解运输 问题过程
1
石家庄经济学院
管理科学与工程学院
第3章 运输问题
本章主要内容
§3.1 运输问题及其数学模型 §3.2 表上作业法 §3.3 产销不平衡的运输问题 §3.4 应用举例
B1
B2
B3
B4
产量 7
B1 3 1 7
B2 11 9 4
B3 3 2 10
B4 10 8 5
3
4
2
3 6
2
3
5
4 9 20
6
6
29
石家庄经济学院
管理科学与工程学院
注：应用西北角法和最小元素法，每次填完数，都
应只划去一行或一列。当填上一个数后行、列同时
饱和时，也应任意划去一行 ( 列 ) ，然后在保留的列 （行）没被划去的格内标一个 0 。 例 3.2 某公司下属有生产一种化工产品的三个产地
13
石家庄经济学院
管理科学与工程学院
若用xij表示从Ai到Bj的运量，那么在产销平衡的条 件下，要求得总运费最小的调运方案，数学模型为：
min z cij xij
i 1 j 1
m
n
14
n xij ai i 1,2,, m j 1 m s.t. xij b j j 1,2,, n i 1 xij 0 石家庄经济学院
pij 0,,0,1,0,,0,1,0,0
T
17
石家庄经济学院
管理科学与工程学院
根据运输问题的数学模型求出的运输问题的解 X xij ，代表着一个运输方案，其中每一个 变量xij的值表示由Ai调运数量为xij的物品给Bj。前已 指出运输问题是一种线性规划问题，可设想用迭代法 进行求解，即先找出它的某一个基可行解，再进行解 的最优性检验，若它不是最优解，就进行迭代调整， 以得到一个新的更好的解 ，继续检验和调整改进，直 至得到最优解为止。
27
石家庄经济学院
管理科学与工程学院
销地 产地 A1 A2 A3 销量
B1 3 1 7 3
B2 11 9 4 6
B3 3 2 10 5
B4 10 8 5 6
产量 7 4 9 20 （产销平衡）
问应如何调运，可使得总运输费最小?
28
石家庄经济学院
管理科学与工程学院
产销平衡表
运价表
销 产 A1 A2 A3 需求
2
石家庄经济学院
管理科学与工程学院
§3.1 运输问题及其数学模型
问题的提出
一般的运输问题就是要解决把某种产品从
若干个产地调运到若干个销地，在每个产地的
供应量与每个销地的需求量已知，并知道各地 之间的运输单价的前提下，如何确定一个使得 总的运输费用最小的方案。
回本章目录
3
石家庄经济学院
管理科学与工程学院
(3 1)
管理科学与工程学院
其中，ai和bj满足：
ai b j
i 1 j 1
m
n
(3-2)
称为产销平衡条件。
15
石家庄经济学院
管理科学与工程学院
将（3-1）的结构约束加以整理，可知其系 数矩阵的结构比较松散，且特殊
x11 x12 x1n x21 x22 x2 n xm1 xm 2 xmn u1 1 1 1 u2 1 1 1 um v1 1 1 v2 1 1 vn 1 1
A1、 A2、 A3 ，有四个销售点 B1、 B2、B3、 B4 销售
这种化工产品。各产地的产量、各销地的销量和各
产地运往各销地每吨产品的运费（百元）如下表所
示。
30 石家庄经济学院 管理科学与工程学院
产销平衡表
运价表
销 产
A1 A2
B1
B2
B3
B4
产量 75 40
B1 3 2
B2 8 9
B3 5 4
x14 + x24 + x34 = 6
xij ≥ 0 ( i = 1、2、3；j = 1、2、3
6 石家庄经济学院 管理科学与工程学院
其系数矩阵为 ：
1 0 0 A 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1
下面分两种情况来讨论：
（1） ai b j 。即运输问题的总产量等于其总
i 1 j 1 m n
销量，这样的运输问题称为产销平衡的运输问题。 m n （2） a b 。即运输问题的总产量不等于总 i j
i 1 j 1
销量，这样的运输问题称为产销不平衡的运输问题。
我们重点讨论产销平衡的运输问题及其求解方法。 然后在此基础上讨论产销不平衡的运输问题应该 如何转化为产销平衡的运输问题。
35
40 0 40 15
40 80 195
65
65
35
40
55
32
石家庄经济学院
管理科学与工程学院
（3）伏格尔法(沃格尔法Vogel)
最小元素法的缺点是：为了节省一处的费用，有时造成 在其它处要多花几倍的运价。伏格尔法考虑到，某产地 的产品假如不能按最小运价就近供应，就考虑次小运价， 这就有一个差额。差额越大，说明不能按最小运价调运 时，运费增加越多。因而对差额最大的行或列，就应当 采用最小运价调运。伏格尔法给出的初始解比用最小元 素法给出的初始解更接近最优解。
销地 产地 A1 A2 ┇ Am 销量 B1 c11 c21 ┇ cm1 b1 B2 „ Bn c12 „ c1n c22 „ c2n ┇ ┇ ┇ 产量 a1 a2 ┇ am
cm2 „ cmn b2 „ bn
10
石家庄经济学院
管理科学与工程学院
表中的 xij (i 1,2, m; j 1,2,, n) 表示由产地Ai 向销地Bj运输物资的数量（即运量）。在产销平衡表 3-1中，去掉最后一行和最后一列余下的部分，称为 一个调运方案，或简称为一个方案。或者将上述两个 表格合在一起，称为运输表（表3-3）。
21
石家庄经济学院
管理科学与工程学院
§3.2.1 初始基本可行解的确定
与一般线性规划问题不同，产销平衡运输问题总是存在 可行解。不难验证
xij ai b j d
≥
0 (i 1,2,, m; j 1,2,, n; d ai b j )
i 1 j 1
m
n
就是模型（3-1）的可行解。又因，目标函数值有下界， 故产销平衡的运输问题必有最优解。
共有 m+n 行，分别表示产地和销地；有 mn 列分别
表示各变量；每列只有两个 1，其余为 0 。
7 石家庄经济学院 管理科学与工程学院
运输问题的一般提法是：设某种物资有m个产地和n个 ,2,, m) ； 销地。产地Ai的产量为 ai (i 1 销地Bj的销量为 b j ( j 1,2,, n) 。从第i个产地向 第j个销地运输每单位物资的运价为Cij，这就是由多个 产地供应多个销地的单品种物资运输问题。问如何调 运这些物资才能使总运费达到最小。
24
石家庄经济学院
管理科学与工程学院
表3-5 运输表（运价小者先安排）
产销平衡表 运价表
销 产 A1 A2 A3 需求
B1
B2
B3
B4
产量 7 4
B1 3 1 7
B2 11 9 4 4
B3
B4
4 3 6
3 6 5
3
3
2
3
10
8 5
10
1 3
6
1
2
9 20
10
5
25
石家庄经济学院
管理科学与工程学院
（2）西北角法
问应如何调运，可使得总运输费最小?
石家庄经济学院 管理科学与工程学院
4
解： 这是一个产销平衡的运输问题，设 xij 为从产 地Ai运往销地Bj的运输量（i = 1，2，3； j = 1，2，
3， 4）
该运输问题的线性规划模型如下： Min f = 3x11+ 11x12+ 3x13+ 10x14+ x21+ 9x22 + 2x23+ 8x24+ 7x31+ 4x32+ 10x33+ 5x34
16 石家庄经济学院
1 1 1 1 1 1
m行 n行
管理科学与工程学院
该系数矩阵中对应于变量xij的系数向量Pij，其分 量中除第i个和第m+j个为1以外，其余的都为零。 即
19