第三章运输问题
一、学习目的与要求
1、掌握表上作业法及其在产销平衡运输问题求解中的应用
2、掌握产销不平衡运输问题求解方法 二、课时 6学时
第一节 运输问题及其数学模型
一、运输问题的数学模型
单一品种运输问题的典型情况：设某种物品有m 个产地A 1,A 2,…,A m ，各产地的产量分别是a 1,a 2,…,a m ；有N 个销地B 1,B 2,…,B n ，各销地地销量分别为b 1,b 2,…,b n 。假定从产地A i (i =1,2, …,m )向销地B j (j =1,2,…,n )运输单位物品的运价是c ij ，问怎样调运这些物品才能使总运费最小？
表中x ij i j ij i j
如果运输问题的总产量等于其总销量，即有
∑∑===n
j j
m i i b
a 1
1
则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。
产销平衡运输问题的数学模型如下：
⎪⎪⎪⎩
⎪
⎪⎪⎨⎧≥=====∑∑∑∑===+=0,...,2,1,...,2,1..min 1
111
1
ij m i j
ij n
j i
ij m i n j ij
ij x n
j b x m
i a x t s x c z
这就是运输问题的数学模型，它包含m ×n 个变量，(n 十m)个约束方程．其系数矩阵的结构比较松散，且特殊。
二、运输问题数学模型的特点
1、运输问题有有限最优解，即必有最优基本可行解
2、运输问题约束条件的系数矩阵A 的秩为
(m+n-1)
该系数矩陈中对应于变量x ij 的系数向量p ij ，其分量中除第i 个和第m 十j 个为1以外，其余的都为零．即 A ij ＝(0…1…1…0)’=e i +e m+j
对产销平衡的运输问题具有以下特点： (1)约束条件系数矩阵的元素等于0或1
(2)约束条件系数矩阵的每一列有两个非零元素，对应于每一个变量在前m 个约束方程中出现一次，在后n 个约束方程中也出现一次。
此外，对于产销平衡问题，还有以下特点 (3)所有结构约束条件都是等式约束 (4)各产地产量之和等于各销地销量之和
第二节 用表上作业法求解运输问题
解题步骤
第1步：确定初始基本可行解。
第2步：最优性判别，若最优准则σij ≥0，则当前解最优，计算停止，否则转第3步。 第3步：取一个检验数最小的非基变量做进基变量。 第4步：调整当前基本可行解，转第2步
一、确定初始基本可行解（初始调运方案） 以实例介绍：
例 某部门有3个生产同类产品的工厂(产地),生产的产品由4个销售点(销地)出售，各工厂的生产量、各销点的销售量（假定产位均为t ）以及各工厂到各销售点的单位运价（元/t ）于下表中，要求研究产品如何
A 最小元素法
总运费（目标函数）：24611
==∑∑==i j ij ij
x c
z 这个解满足约束条件，其非零变量的个数为6（等于
m+n-1=3+4-1=6）。 B 西北角法
总运费（目标函数）：37211
==∑∑==i j ij ij
x c
z 这个解满足约束条件，其非零变量的个数为6（等于
m+n-1=3+4-1=6）。 C
总运费（目标函数）：24411
==∑∑==i j ij ij
x c
z
二、解的最优性检验 1、闭回路法
检验数表
由于024<σ，故知解不是最优解。 2、对偶变量法（也称位势法）
对产销平衡问题，若用n m v v v u u u ,,,,,2121分别表示前m 个约束条件与后n 个约束条件的对偶变量，即有对偶变量
),,,,,(2121n m v v v u u u Y =
这时对偶问题的对偶规划写成
⎪⎪⎩
⎪⎪
⎨
⎧==≤++='∑∑==的符号不限j i ij j i j
n
j j i m i i v u n
j m i c v u t s u b u a z ,,,2,1,,2,1..max 1
1
由上一章知道，线性规划问题变量x j 的检验数可表示为
j j j B j j j j YP c P B C c z c -=-=-=-1σ
由此可写出运输问题某变量x ij 的检验数如下：
)(),,,,,,,(2121j i ij ij n m ij ij ij ij ij ij v u c P v v v u u u c YP c z c +-=-=-=-= σ
现设我们已得到解到了运输问题的一个基可行解，其基变量是
1,,,21121-+=n m s x x x s j i j i j i s
由于基变量的检验数等于零，故对这组基变量可写出方程组
⎪⎪⎩⎪⎪
⎨
⎧=+=+=+js s i s j is j i j i j i j i c
v u c v u c v u ,2
,221
,1111
1112
这个方程组有m+n-1个方程。
解以上方程组，可得解（上方程组解不唯一），此方程组解称为位势。 由上章知当每个0)(≥+-=j i ij ij v u c σ达到最优解。 例
⎪⎪⎪⎪⎩⎪⎪⎨
=+=+=+=+6
532
432332
12v u v u v u v u 令02=u 得方程组的解：9,4,10,1,3,2234131=-=====v u v u v v 计算检验数
由于σ24<0
三、解的改进（用闭回路法调整当前基可行解）
解的改进步骤：
（1）以x ij 为换入变量，找出运输表中的闭回路； （2）对顶点进行编号；
（3）确定换出变量：在闭回路上的所有偶数顶点中找出运输量量小的顶点，以该格中的变量为换出变量；
（4）以换出变量值为奇数顶点处的运输量增加值，得新的运输方案； （5）检验新的方案是否为最优，如否则重复以上步骤。
