运筹学第三章 运输问题

1、|运输问题与有关概念|产销平衡运输问题的求解表上作业法本章内容重点前面讨论了线性规划问题的一般解法，在实际生活中，碰到的线性规划问题的系数矩阵往往具有特殊的结构，这就可能找到比单纯形法更为简单的方法，从而节省计算时间和空间。本章讨论的运输问题就是这样一类特殊的线性规划问题。在经济生活中，常碰到大宗物资的调运问题，如煤、钢铁、木材、粮食等物资，他们在全国有若干生产基地，根据已有的交通网络，制定调运方案，将这些物资运到各个消费地点，而总运费最省。运输问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的产量（供应量）与每个销地的销量(需求量)已知，并知道各地之间的运

2、输单价的前提下，如何确定一个使得总运费用最省的调运方案。确定初始调运方案|例1 某糖果公司下设三个工厂，每日产量分别为：A17吨， A24吨， A39吨。该公司将这些产品运往四个门市部，各门市部每日销量为B13吨， B26吨， B35吨, B46吨。各工厂到各门市部的单位运价见下表，用最小元素法确定一初始调运方案。设某物资有m个产地A1，A2，Am其产量分别是a1,a2, ,am,有n个销地B1，B2， ，Bn,其销量分别是b1,b2, ,bn。已知产地Ai到销地Bj的单位运价是Cij（i=1,2, ,m； j=1,2, ,n ）这些数据可以用运输表表示。若总产量等于总销量（产销平衡）试确定总

3、运费最省调运方案设xij为从产地Ai运往销地Bj的运输量，则此问题的数学模型为： 二、运输问题数学模型的特点：二、运输问题数学模型的特点：1. 运输问题一定有最优解；基变量的个数=m+n-12. 运输问题约束条件的系数矩阵：x1mx2mxm1xmm111111111111111111x11x12x21x22xm2m行n行|运输问题具有下述特点：(1) 约束条件系数矩阵的元素等于0或1；(2) 约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次。(3) 矩阵的秩=m+n-1 (0110)Tijimjpee|对产销平衡运输问题，除上述

4、两个特点外，还有以下特点：(1) 所有结构约束条件都是等式约束；(2) 各产地产量之和等于各销地销量之和。表上作业法产销平衡表单位运价表表上作业法求解思路：初始调运方案初始调运方案是否是是否是最优解最优解结束结束方案调整方案调整NY确定初始调运方案1.最小元素法：这种方法的基本思想是就近供应，从运价表中最小运价开始确定运量，然后次小，一直到给出初始调运方案为止。具体做法为：找出运价表中最小元素CLK，确定xLK=minaL,bk，若xLK=aL,则令划掉运价表中的第L行；反之,若xLK=bL则令 ，划掉运价表中的第K列在运价表中剩余元素中重复，直至运价表中所有的元素全被划掉LkkxbbkLKL

5、Lxaa确定初始调运方案|例1 某糖果公司下设三个工厂，每日产量分别为：A17吨， A24吨， A39吨。该公司将这些产品运往四个门市部，各门市部每日销量为B13吨， B26吨， B35吨, B46吨。各工厂到各门市部的单位运价见下表，用最小元素法确定一初始调运方案。确定初始调运方案得到初始调运方案如下：称上面这个产销平衡表中填有数字的格为数字格，它对应的变量相当于基变量；没填数字的格称为空格，它对应的变量相当于非基变量。上表中共有m+n-1个数字格，即初始调运方案存在m+n-1个基变量。确定初始调运方案特别情况：当最小运价CLK对应的aL和bk相等时，即对应的产量和销量相等时，为保证基变量的

6、个数为m+n-1个，除了在产销平衡表填xLK=aL外，还应在产销平衡表中的第L行或第K列某空格（相应运价未被划掉）处填一个“零”，然后同时划去运价表上的第L行和第K列，该“零”看作是数字格。2.西北角法（左上角法）：这种方法的基本思想是给运输表左上角变量分配运输量，以确定产销关系，依此类推，一直到给出初始可行方案为止。具体做法为：先决定运输表左上角变量xLK，令这个变量取尽可能大的值即xLK=minaL,bk，在这个变量对应的数字格上填上变量所取的值。西北角法：若xLK=aL,则 划去掉运输表的第L行，这些空格不再赋值；若xLK=bk,则 划去第k列，这些空格不再赋值。对表上剩余元素重复，直到

7、所有的格子都有标记。 用西北角法没有考虑单位运费的大小，显然求解结果比较粗糙，收敛速度慢。kkLkbbxLKLLxaa3.沃格尔法|罚数=次小费用-最小费用|找出最大的罚数行或列所对应的最小费用优先安排。|重复计算步骤1和2沃格尔法例题沃格尔法例题 销地产地B1B2B3B4产量行罚数12345A116A210A322销量 814121448列罚数123454101211346911285201513221011321148810217062201242总费用 z= =24434i=1 j=1cij ijx检验数：对于空格（i，j），假定给它一个单位运量，调整其它有关数字格运量，使产销平衡，则这

8、一系列变化导致的总运费变化值称为该空格的检验数，记为 。最优方案的判别准则：如果一个可行方案的所有空格的检验数都大于等于零，则该方案是最优方案。ij以空格为起点的闭回路：它是以空格为起点，沿水平方向或垂直方向前进，碰到合适的数字格后转90，继续前进直至回到起始空格为止。可以证明：在任何可行方案中，以空格（i，j）为顶点，其余顶点全是数字格的闭回路存在且唯一。闭回路示意图检验数：为了确定空格（i，j）的检验数，可以先找出以该空格为一个顶点，其余顶点全是数字格的闭回路，然后假定给空格（i，j）一个单位运量，调整该闭回路上所有数字格顶点的运量，使产销平衡，则闭回路上总运费的变化值就等于空格（i，j）

9、的检验数。判别准则：当所有非基变量的检验数均大于或等于零时，现行的调运方案就是最优方案，因为此时对现行方案作任何调整都将导致总的运输费用增加。闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。对对偶偶变变量量法法对偶变量法（位势法）对偶变量法（位势法）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

10、 + x .21n2nmnnij =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对偶规划为对对偶偶变变量量法法 j = C j- CBB-1 Pj = Cj - Y Pj ij = C ij- CBB-1 Pij = Cij - Y Pij = Cij - (u1,u2, ,um, v1, v2, ,vn) Pij = Cij - ( ui+ vj ) 当x

11、ij 为基变量时 ij = Cij - ( ui+ vj )=0 由此，任选一个对偶变量为0，可求出其余所有的ui， vj 。 再根据ij = Cij - ( ui+ vj )求出所有非基变量的检验数。对对偶偶变变量量法法确定检验数最小的空格（L,K）,即找出以该空格（L,K）为顶点，其余顶点全是数字格得闭回路（该回路存在且唯一），规定该空格（L,K）为闭回路得第一个顶点，闭回路上其它顶点依次为第二个顶点，第三个顶点（顺时针或逆时针排序均可），取闭回路上偶数顶点的最小运量为调整量。min0LKi ji j 闭回路顶点上偶数序号顶点的运量均减，奇数序号顶点的运量均加，不在闭回路上的运量不变。在调

12、整中，如果偶数序号的顶点中仅有一个数字格的运量等于调整数，则调整后，该数字格变为空格；如果偶数序号顶点中两个以上数字格的运量等于调整量，则调整后仅让其中一个数字格为空格，其它调整后要记为“0”，该“0”要看作数字格。调整后，就可以得到一个含有m+n-1个数字格的新的调运方案。产销不平衡运输问题|产大于销情况： 如果总产量大于总销量，就会出现多余物资没地方要的情况，就需要考虑多余物资在哪些产地就地存储的问题。将各地的仓库设成一个假想的销地Bn+1，该销地总需求量:njjmiiba11njjmiinbab111产销不平衡运输问题如果某产地i允许物资就地存储，则Ci,n+1=0因为物资就地存储不存在

13、运输费用问题，运输单价应该是“0”。产销不平衡运输问题如果某产地i不允许物资就地存储，Ci,n+1=M，M 是一个相当大的正数 这样对于某产地i，如果物资就地存储就付出相当大的代价，使得在求解时不得不将产地i的物资都运出去。在最优解中，产地Ai到虚拟销地Bj的运量就是产地Ai就地存储的多余物资的数量。产销不平衡运输问题|销大于产情况（供不应求情况）： 如果总销量大于总产量，必然会出现某销地缺货情况，就需要考虑确定哪些销地缺货多少的问题，为了求解这种问题设虚拟产地Am+1，认为该虚拟产地至各销地的运量为各销地的缺货量。 该产地总产量为： njjmiiba11miinjjmaba111产销不平衡运

14、输问题如果某销地j允许缺货，则Cm+1,j=0 即求解的结果会出现从虚拟产地Am+1向销地Bj运送货物的情况，实际上这部分运量是不可能存在的，是最后分配方案中Bj的缺货量。由于这个产地是不存在的，当然运价为0。产销不平衡运输问题如果某销地j不允许缺货，Cm+1,j=M,M 是一个相当大的正数 从虚拟产地到销地的运价为M，则意味着不可能从虚拟产地Am+1向销地Bj运送货物，则销地Bj的销量bj需要完全是从产地A1 Am运来的，这样就可以保证销地j不缺货。 在最优解中，虚设产地Am+1到销地Bj的运量实际上就是最后分配方案中Bj的缺货量。 产销不平衡运输问题|例2 设有A1、A2和A3三个产地生产

15、某种物资，其产量分别是5，6，8吨， B1、B2和B3三个销地需要该物资，销量分别是4， 8 ，6 吨，又已知各产销地之间的单位运价如下表，试确定总运费最省的调运方案。产销不平衡运输问题 接收发送产地销地发送量1mm+1m+n产地1x11x1mx1,m+1x1,m+nQ+a1mxm1xmnxm,m+1xm,m+nQ+am销地m+1xm+1,1xm+1,mxm+1,m+1xm+1,m+nQm+nxm+n,1xm+n,mxm+n,m+1xm+n,m+nQ接收量QQQ+bm+1Q+bm+n 有转运输问题的运输表有转运输问题的运价表 接收发送产地销地发送量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,