.
第三章运输问题
一、学习目的与要求
1、掌握表上作业法及其在产销平衡运输问题求解中的应用 2、掌握产销不平衡运输问题求解方法 二、课时 6学时
第一节 运输问题及其数学模型
一、运输问题的数学模型
单一品种运输问题的典型情况：设某种物品有m个产地A1,A2,…,Am，各产地的产量分别是a1,a2,…,am；有N个销地B1,B2,…,Bn，各销地地销量分别为b1,b2,…,bn。假定从产地Ai(i=1,2, …,m)向销地Bj(j=1,2,…,n)运输单位物品的运价是cij，问怎样调运这些物品才能使总运费最小？
为直观清楚起见，列出运输表： 销地 B2 … Bn 产量 B1 产地 A1
c11 x11 c12 x12 c1n x1n a1 A2 c21 x21 c22 x22 c2n x2n a2 … c11 x11 c12 x12 … c1n x1n … Am 销量 cm1 xm1 b1 cm2 Xm2 b2 cmn xmn bn am 表中xij为由产地Ai到销地Bj的物品数量，cij表示产地Ai到销地Bj的单位运价。
如果运输问题的总产量等于其总销量，即有
?a??bii?1j?1mnj
则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。
产销平衡运输问题的数学模型如下：
精品
.
minz???cijxij
i?1j?1
mn?1
?n
??xij?ai
?1?jm?
s.t.??xij?bj
?i?1
?xij?0??
i?1,2,...,m
j?1,2,...,n
这就是运输问题的数学模型，它包含m×n个变量，(n十m)个约束方程．其系数矩阵的结构比较松散，且特殊。
二、运输问题数学模型的特点
1、运输问题有有限最优解，即必有最优基本可行解 2、运输问题约束条件的系数矩阵A的秩为(m+n-1)
该系数矩陈中对应于变量xij的系数向量pij，其分量中除第i个和第m十j个为1以外，其余的都为零．即 Aij＝(0…1…1…0)’=ei+em+j
对产销平衡的运输问题具有以下特点： (1)约束条件系数矩阵的元素等于0或1
(2)约束条件系数矩阵的每一列有两个非零元素，对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次。
此外，对于产销平衡问题，还有以下特点 (3)所有结构约束条件都是等式约束 (4)各产地产量之和等于各销地销量之和
精品
.
第二节 用表上作业法求解运输问题
解题步骤
第1步：确定初始基本可行解。
第2步：最优性判别，若最优准则σij≥0，则当前解最优，计算停止，否则转第3步。 第3步：取一个检验数最小的非基变量做进基变量。 第4步：调整当前基本可行解，转第2步
一、确定初始基本可行解（初始调运方案） 以实例介绍：
例 某部门有3个生产同类产品的工厂(产地),生产的产品由4个销售点(销地)出售，各工厂的生产量、各销点的销售量（假定产位均为t）以及各工厂到各销售点的单位运价（元/t）于下表中，要求研究产品如何调运才能使总运费最小？ 销地 产地 A1 A2 A3 销量
A最小元素法
销地 产地 A1 A2 A3 销量 3B1 4 B2 12 2 8 14 5 10 B3 4 3 11 12 B4 11 9 6 14 产量 16 10 8 22 B1 B2 4 2 8 14 14 ijB3 12 10 5 10 2 12 11 3 4 B4 11 6 9 6 8 14 产量 16 10 22 8 8 总运费（目标函数）：z?m+n-1=3+4-1=6）。 B 西北角法
销地 产地 A1 ??ci?1j?14xij?246这个解满足约束条件，其非零变量的个数为6（等于
B1 8 4 B2 12 8 精品
B3 4 B4 11 产量 16
运筹学课件第三章运输问题
