第三章运输问题
一、学习目的与要求
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 cm2 Xm2 b2 … cmn xmn bn am 销量 b1 表中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 B1 4 B2 12 2 8 14 5 10 B3 4 3 11 12 B4 11 产量 16 9 10 6 22 14 8 B1 4 2 8 8 34B2 8 14 14 ijB3 12 10 5 10 2 12 11 3 4 B4 11 6 9 6 8 14 产量 16 A2 A3 销量 总运费（目标函数）：z?m+n-1=3+4-1=6）。 B 西北角法
销地 产地 A1 A2 10 22 ??ci?1j?1xij?246这个解满足约束条件，其非零变量的个数为6（等于
B1 8 2 4 B2 12 8 10 B3 4 3 B4 11 9 产量 16 10 A3 销量 36 8 14 ij4 5 8 12 11 6 14 14 22 8 总运费（目标函数）：z?m+n-1=3+4-1=6）。 C 沃格尔（Vogel）法 销地 产地 A1 A2 A3 销量 1 列罚数 2 3 4 5 总运费（目标函数）：z?
二、解的最优性检验 1、闭回路法
销地 产地 A1 8 8 2 2 2 ??ci?1j?14xij?372这个解满足约束条件，其非零变量的个数为6（等于
B1 4 2 8 B2 12 14 14 5 4ijB3 12 5 12 1 1 1 1 11 4 3 B4 产 量 1 16 10 22 48 行罚数 2 3 0 1 4 7 6 5 1 6 11 4 9 2 6 8 14 3 3 2 2 2 0 0 1 1 1 2 10 ??ci?1j?13xij?244
B1 B2 4 2 8 14 14 5 10 12 B3 4 10 3 2 11 12 B4 11 6 9 6 8 14 产量 16 A2 A3 销量 检验数表
销地 产地 8 8 10 22 B1 B2 B3 B4 产量 A1 A2 A3 销量 1 2 1 12 -1 10 由于?24?0，故知解不是最优解。 2、对偶变量法（也称位势法）
对产销平衡问题，若用u1,u2,?um,v1,v2,?vn分别表示前m个约束条件与后n个约束条件的对偶变量，即有对偶变量
Y?(u1,u2,?um,v1,v2,?vn)
这时对偶问题的对偶规划写成
maxz???aiui??bjuji?1j?1mn?ui?vj?cij??i?1,2,?,ms.t.??j?1,2,?,n?ui,vj的符号不限?由上一章知道，线性规划问题变量xj的检验数可表示为
?j?cj?zj?cj?CBB?1Pj?cj?YPj
由此可写出运输问题某变量xij的检验数如下：
?ij?cij?zij?cij?YPij?cij?(u1,u2,?,um,v1,v2,?,vn)Pij?cij?(ui?vj)
现设我们已得到解到了运输问题的一个基可行解，其基变量是
xi1j1,xi12j2,?xisjs,s?m?n?1
由于基变量的检验数等于零，故对这组基变量可写出方程组
?ui1?vj1?ci11,j1??ui21?vj2?ci2,j2 ????u?v?cjsi1s,js?is1这个方程组有m+n-1个方程。
解以上方程组，可得解（上方程组解不唯一），此方程组解称为位势。 由上章知当每个?ij?cij?(ui?vj)?0达到最优解。 例 用位势法对上例最小元素法有的解作最优性检验。 销地 产地 A1 B1 4 2 8 8 8 B2 12 5 14 14 10 B3 4 10 3 2 11 12 B4 11 6 9 6 8 14 产量 16 ui u1 A2 A3 销量 10 22 48 u2 u3
运筹学课件第三章运输问题
