《运筹学》胡运权 第4版 第三章 运输问题

1、2本章本章内容内容|运输问题及其数学模型|用表上作业法求解运输问题|运输问题的进一步讨论|应用问题举例问题的提出： 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。1.经典运输问题单一品种物资的运输调度问题由产地Ai运往销地Bj的物品数量Ai到Bj的单位运价网络表示：5,0002,5006,000B2(b2)B1(b1)B3(b3)Bn(bn)销地销地产地产地A2(a2)Am(am)A1(a1)x22x23x21x11x12x13x1nx2nxm3xm1xm2xm

2、nc11c12c13c1nc21c22c23c2ncm1cm2cm3cmn如果运输问题的总产量等于其总销量，即有 则称该运输问题为产销平衡运输问题；反之，称产销不平衡运输问题。mniji=1j=1ab产销平衡运输问题的数学模型可表示如下：34i=1 j=1nij=1mji=1minz =c=(i =1,2,.,m)s.t.=(j=1,2,.,n)0(i =1,2,.,m;j=1,2,.,n)ijijijijijxxaxbx二、运输问题数学模型的特点：二、运输问题数学模型的特点：运输问题一定有最优解；基变量的个数=m+n-11. 运输问题约束条件的系数矩阵：x1mx2mxm1xmm1111111

3、11111111111x11x12x21x22xm2m行n行|运输问题具有下述特点：(1) 约束条件系数矩阵的元素等于0或1；(2) 约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次。|对产销平衡运输问题，除上述两个特点外，还有以下特点：(1) 所有结构约束条件都是等式约束；(2) 各产地产量之和等于各销地销量之和。例1 某部门有3个生产同类产品的工厂(产地)，生产的产品由4个销售点(销地)出售，各工厂的生产量、各销售点的销售量(假定单位均为t)以及各工厂到各销售点的单位运价(元t)示于表3-2中，要求研究产品如何调运才能使总运

4、费最小?表3-2 销地产地B1B2B3B4产量A116A210A322销量8141214484281254101139611该问题的数学模型：mn1112131421i=1j=122232431323334111213142122232431323334112131122232132333142434minz =c4124112103985116=16=10=22=8s.t.=14=12=14ijijixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0 (i = 1,2,.,m; j = 1,2,.,n)j，12本章本章内容内容|运输问题及其数学模型|用表上作业法求

5、解运输问题|运输问题的进一步讨论|应用问题举例一、表上作业法的基本思想和步骤：一、表上作业法的基本思想和步骤：1.1.基本思想：同基本思想：同单纯形法单纯形法的基本思的基本思想想基本可行解是否为最优解换基结束YN2 用用表表上上作作业业法法求求解解运运输输问问题题二、表上作业法的步骤（1）寻找初始基可行解；最小元素法、西北角法、沃格尔法（2）求出非基变量检验数（空格检验数），判断是否为最优解；闭回路法、位势法（3）换基改进，找到新的基可行解闭回路调整法（4 ）重复（2）（3）2 用用表表上上作作业业法法求求解解运运输输问问题题1.1.最小元素法最小元素法 从运价最小的格开始，在格内的右下角标上

6、允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。 销地产地B1B2B3B4产量A1 16A2 10A3 22销量 814 12 14484285101112346911 821014 861.1.最小元素法最小元素法总费用 z= =104+611+82+23+145+86=24634i=1 j=1cijijx寻寻找找初初始始基基可可行行解解2.2.西北角法西北角法 从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（

7、列）的其他格划去。如此进行下去，直至得到一个基本可行解。寻寻找找初初始始基基可可行行解解 销地产地B1B2B3B4产量A1 16A2 10A3 22销量 8 14 12 14484285101112346911 846 14882.2.西北角法西北角法总费用 z= =84+812+610+43+811+146=37234i=1 j=1cijijx寻寻找找初初始始基基可可行行解解3.沃格尔法|罚数=次小费用-最小费用|找出最大的罚数行或列所对应的最小费用优先安排。|重复计算步骤1和23.沃格尔法沃格尔法 销地产地B1B2B3B4产量行罚数12345A116A210A322销量 814121448

8、列罚数123454101211346911285201513221011321148810217062201242总费用 z= =24434i=1 j=1cij ijx寻寻找找初初始始基基可可行行解解 最优性检验就是检查所得到的方案是不是最优方案。检查的方法与单纯形方法中的原理相同，即计算检验数。由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优，需要进行调整。下面介绍两种求检验数的方法：闭回路法和对偶变量法。1.闭回路法| 闭回路：从空格出发，遇到数字格可以旋转90度，最后回到空格所构成的回路；| 原理：利用检验数的经济含义；| 检验数：非基变量增加

9、一个单位引起的成本变化量。| 当所有非基变量的检验数均大于或等于零时，现行的调运方案就是最优方案，因为此时对现行方案作任何调整都将导致总的运输费用增加。| 闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。 销地产地B1B2B3B4产量A116A210A322销量8141214481.1.闭回路法闭回路法（结合最小元素法的初始解）428125410113961181410268检验数11=c11-c21+c23-c13=4-2+3-4=124=c24-c14+c13-c23=9-11+4-3=-10,故知该最小元素法的解不是最优解1211012-1位势：设对应基变量

10、xij的m+n-1个i、j ，存在ui,vj 满足ui+vj=cij,i=1,2,.,m; j=1,2 , ,n称这些ui , vj 为该基本可行解对应的位势。2.2.对偶变量法（位势法）对偶变量法（位势法）2.对偶变量法（位势法）对偶变量法（位势法）min Z = .111112121n1nm1m1m2m2mnmnc x + c x + +c x + +c x +cx + +cx.11121n 121222n2m1x +x + +x = ax +x + +x = a x+.m2mnm11 21m1 11222 m2x+ +x = ax + x + x =bx +x + x .21n2nmnn

11、ij =b x +x + x=b x 0|设对偶变量向量为设对偶变量向量为12m12nY =(u ,u , .,u , v , v , .,v ). s.t.ijijiju +vci=1,2, ,mj=1, ,nu ,v的符号不限mni 1j 1max z =iijja ub v对偶规划为检验数：目标函数的系数减去对偶变量之和检验数：目标函数的系数减去对偶变量之和原问题检验数：原问题检验数：ij=cij-(ui+vj)特别对于特别对于m+n-1个基变量，有个基变量，有 ij=0 j = C j- CBB-1 Pj = Cj - Y Pj ij = C ij- CBB-1 Pij = Cij -

12、 Y Pij = Cij - (u1,u2, ,um, v1, v2, ,vn) Pij = Cij - ( ui+ vj ) 当xij 为基变量时 ij = Cij - ( ui+ vj )=0 由此，任选一个对偶变量为0，可求出其余所有的ui， vj 。 再根据ij = Cij - ( ui+ vj )求出所有非基变量的检验数。解解的的最最优优性性检检验验 销地产地B1B2B3B4产量uiA116u1(1)A210u2(0)A322u3(-4)销量814121448vjv1(2)v2(9)v3(3)v4(10)4281254101139611表3-91.增加一位势列和位势行并计算位势其中1

13、21421233234u4u11u2u3u5u6vvvvvv8102682解解的的最最优优性性检检验验 销地产地B1B2B3B4产量uiA1161A2100A322-4销量814121448vj293102.计算检验数42812541011396111211012-1检验数13=8-（-4）-2=10；24=9-10=-10,故这个解不是最优解（+2）4.4.解的改进解的改进闭回路调整法闭回路调整法解解的的最最优优性性检检验验 改进的方法是在运输表中找出这个空格对应的闭回路Lij，在满足所有约束条件的前提下，使xij尽量增大并相应调整此闭回路上其他顶点的运输量，以得到另一个更好的基可行解。 销

14、地产地B1B2B3B4产量A1 10 616A28 2 10A314 822销量814121448表表 3-113-114281254101139611（-2）（+2）（-2）5、需要注意的问题 （一）多个空格（非基变量）的检验数为负，任一个都可作为换入变量。一般ij0中最小的对应变量作为换入变量。 （二）最优解时，如果有某非基变量的检验数为0，则说明该运输问题有无穷多最有解。 （三）退化解。解解的的最最优优性性检检验验本章本章内容内容|运输问题及其数学模型|用表上作业法求解运输问题|运输问题的进一步讨论|应用问题举例|产销不平衡的运输问题|有转运的运输问题1.当产大于销时，即njjmiiba

15、11ijminjijxcZ 111min111, (1, 2 , .,), (1, 2 , .,1). .0nijijmijjiijxaimxbjns t x 平衡后的数学模型为：加入假想销地（假想仓库），销量为 ，由于实际并不运送，它们的运费为 = 0；111mnnijijbabi n+1c 2.当销大于产时，即njjmiiba11加入一个虚设的产地去生产不足的物资；它的产量为111nmmjijiaba 接收发送产地销地发送量1mm+1m+n产地1x11x1mx1,m+1x1,m+nQ+a1mxm1xmnxm,m+1xm,m+nQ+am销地m+1xm+1,1xm+1,mxm+1,m+1xm+

16、1,m+nQm+nxm+n,1xm+n,mxm+n,m+1xm+n,m+nQ接收量QQQ+bm+1Q+bm+n表3-15 有转运输问题的运输表表3-16 有转运输问题的运价表 接收发送产地销地发送量1mm+1m+n产地1-c1c1mc1,m+1c1,m+nQ+a1mcm1-cmcm,m+1cm,m+nQ+am销地m+1cm+1,1cm+1,m-cm+1cm+1,m+nQm+ncm+n,1cm+n,mcm+n,m+1-cm+nQ接收量QQQ+bm+1Q+bm+n|例 5图3-3示出了一个运输系统，它包括两个产地(和)、两个销地(和)及一个中间转运站()，各产地的产量和各销地的销量用相应节点处箭线旁的数字表示，节点连线上的数字表示其间的运输单价，节点旁的数字为该地的转运单价，试确定最优运输方案。 接