文档介绍：运筹学 运输问题
本讲稿第一页，共四十四页
运输问题
运输问题（Transportation Problem，简记为TP）
物资调运工作中提出来的，是物流优化管理的重要的
内每一行（或列）若有闭回路的顶点，则有两个
顶点；
3、每两个顶点格子的连线都是水平的或垂直的；
4、闭回路中顶点的个数必为偶数.
闭回路的几何特征：
1、每一个顶点格子都是 90°转角点；
凡是能排列成
凡是能排列成
本讲稿第十页，共四十四页
§1 运输问题及其数学模型
闭回路的代数性质：
性质 1
构成闭回路的变量组对应的列向量组
必线性相关.
证明
性质 2
分组构成闭回路，则该变量组对应的列向量组
是线性相关的.
推论 1 若变量组对应的列向量组线性无关，则该变
量组一定不包含闭回路.
若变量组 中有一个部
Go on
本讲稿第十一页，共四十四页
性质 1 的证明
Proof :
由直接计算可知
故该向量组线性相关.
本讲稿第十二页，共四十四页
运输问题
在变量组 中，若有某
一个变量 xij 是它所在的行（第 i 行）或列（第 j 列）
中出现于（*）中的唯一变量，则称该变量 xij 是该变量
组的一个孤立点.
定义 2
闭回路的特征
性质 3
没有孤立点
若一变量组中不包含任何闭回路，则该变量组
必有孤立点.
反证
孤立点不会是闭回路上的点
定理 5
变量组 对应的列向量组线性无关的充要
条件是该变量组中不包含任何闭回路.
证明
本讲稿第十三页，共四十四页
定理 5 的证明
Proof :
用反证法
设变量组（*）对应的列向量
组线性无关，但该变量组包含一个以其中某些变量为顶
点的闭回路，
则由性质 2 知，这些变量对应的列向量必
线性相关，与假设矛盾.
定理 5
变量组 对应的列向量组线性无关的充要
条件是该变量组中不包含任何闭回路.
设有一组数 使得
由于变量组（*）中不包含任何闭回路，由性质 3
可知其中必有孤立点，
不妨设 为孤立点，
又不妨设 是（*）在第i1行上唯一的变量，这时由pij
的特征，（1）的左端第i1个分量和为k1，而右端为0，
在第 j1列上的唯一变量如何？
但 仍不包含闭回路，其中还有孤立点,
与前面类似分析可证 k2= 0. 同理得 k3 = k4 =…= kr = 0
这就证明了向量组（*）线性无关.
本讲稿第十四页，共四十四页
§1 运输问题及其数学模型
推论 2 平衡运输问题中的一组 m + n - 1 个变量
能构成基变量的充要条件是它不包含任何闭回路.
该推论给出了运输问题的基可行解中基变量的一
个基本特征：基变量组不含闭回路. 这就是基可行解
在表上的一个表现，利用它来判断 m + n – 1 个变量
是否构成基变量组，就看它是否包含闭回路.
这种方法简便易行，它比直接判断这些变量对应
的列向量是否线性无关要简便得多.
利用基变量的这个特征，将可以导出求平衡运输
问题的初始基可行解的一些简便方法.
本讲稿第十五页，共四十四页
§2 运输问题的表上作业法
§2 运输问题的表上作业法
表上作业法（又称运输单纯形法）是根据单纯形
法的原理和运输问题的特点，设计的一种在表上运算
的求解运输问题的简便而有效的方法.
主要步骤：
1、求一个初始调运方案（初始基可行解）；
2、判别当前方案是否为最优，若是则迭代停止，否则
转下一步；
3、改进当前方案，得到新的方案（新的基可行解），
再返回 2 。
本讲稿第十六页，共四十四页
运输问题
一、初始方案的确定
1、西北角法
Bj
Ai
B1
B2
B3
B4
ai
A1
10
5
2
3
70
A2
4
3
1
2
20
A3
5
6
3
4
10
bj
50
25
10
15
Ex. 1
50
已知某商品有三个产地A1、A2、A3和四个销地
B1、B2、B3、B4 ，产量、
如何调运，在满足各销地需要的情况下，使总的运费
支出为最少？
解：
5
10
10
20
23
5
规则:从运输表的西
北角开始,优先安排
编号小的产地