运输问题TransportationProblem.ppt

运 输 问 题 (Transportation Problem),运输问题的数学模型,表上作业法,产销不平衡的运输问题,例：某运输问题的资料如下：,一、运输问题的数学模型,数学模型的一般形式 已知资料如下：,当产销平衡时，其模型如下：,当产大于销时，其模型是：,当产小于销时，其模型是：,运输问题特征： 1、m个供应地，n个需求地的运输问题； 2、决策变量个数为 m*n 个，约束条件个数为 m+n个； 3、系数矩阵中元素为0或1； 4、每个决策变量在 m 个供应量约束和 n 个需求量约束中各出现一次； 5、系数矩阵的秩等于( m+n-1 )个； 6、基本解中基变量个数等于（m+n-1）个； 7、平衡运输问题必有可行解，也必有最优解。,.重复. ，直到找到最优解为止。,步骤：,.找出初始基本可行解（初始调运方案，一般m+n-1个数字格），用最小元素法、西北角法、伏格尔法；,.求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用位势法计算；,.改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；,二、表上作业法,例一、某运输资料如下表所示：,1、求初始方案：,.西北角法（或左上角法）： 此法是纯粹的人为的规定，没有理论依据和实际背景，但它易操作，特别适合在计算机上编程计算，因而受欢迎。方法如下：,3 6 5 6,7 4 9,3,4 4 9,0 6 5 6,4,0 4 9,0 2 5 6,2,0 2 9,0 0 5 6,2,0 0 9,0 0 3 6,3 6,0 0 0 0,0 0 0,3 4 0 0 0 2 2 0 0 0 3 6,总的运费(3×3)(4×11)(2×9)(2×2)(3×10)(6×5)135元,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,.最小元素法： 基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。,总的运输费用（3×1）（6×4） （4×3）（1×2）（3×10）（3×5）86元,（3）伏格尔法 考虑到最小运费与次小运费及相互差额问题。差额最大处应用最小运费调运。,5 2 3 1 6 3,用伏格尔法 得初始调运方案如下： 表1,ij0 （因为目标函数要求最小化） 表格中有调运量的地方为基变量，空格处为非基变 量。基变量的检验数ij0，非基变量的检验数 ij0。,ij 0 表示运费增加。,2、最优解的判别（检验数的求法）： .闭合回路法：,3,1,3,4,6,3,（1）,（1）,（1）,（1）,计算如下：空格处（ A1 B1 ） 3-3+2-11 此数即为该空格处的检验数。,1,3,1,3,6,3,1,2,4,3,1,3,6,3,1,2,-1,4,3,1,3,6,3,1,2,1,-1,4,3,1,3,6,3,1,2,1,-1,12,4,3,1,3,6,3,1,2,1,-1,12,10,4,检验数中有负数，说明原方案不是最优解。,0,0,0,0,0,1,2,1,-1,12,10,0,运输问题的约束条件共有m+n个，其中：m是产地产量的限制；n是销地销量的限制。 其对偶问题也应有m+n个变量，据此： ij=cij(ui+vj) ,其中前m个计为ui（i=1.2m）,前n个计为vj （j=1.2n） 由单纯形法可知，基变量的ij 0 cij(ui+vj) 0 因此ui ,vj可以求出。,.位势法,接上例：,成本表,u2+v1=1 u2+ v3 =2 u3+v2=4 u1+ v4 =10 u1+v3=3 u3+ v4 =5 令： u10,u10 v12 u2 1 v2 9 u3 5 v3 3 v4 10,(ui+vj),按ij=cij(ui+vj) 计算检验数，并以ij0 检验，或用(ui+vj) cij 0 检验。,cij,(ui+vj),表中还有负数，说明还未得到最优解，应继续调整。,ij,闭合回路调整法（原理同单纯形法一样）,接上例：,3,1,3,4,6,3,（1）,（1）,（1）,（1）,3、改进的方法,经检验,所有ij0 得到最优解， 最小运费为85元。,0,.无穷多最优解：产销平衡的运输问题必定存最优解。如果非基变量的ij0，则该问题有无穷多最优解。如上例：（1.1）中的检验数是 0，经过调整，可得到另一个最优解。,.退化：表格中一般要有(m+n-1)个数字格。但有时，在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格。一般可在划去的行和列的任意空格处加一个 0 即可。,4、表上作业法计算中的问题,例1：,2 1 3 5 5 2 6 8 2 1 7 6,例2：,0,0,0,1、产大于销：模型,方法是先将原问题变成平衡问题，需假设一个销地(Bn+1 )(实际上考虑产地的存量)，,三、产销不平衡的运输问题及其求解方法,模型为：,2、销大于产：同样假设一个产地即可，变化同上。,单位运价表中的单位运价为,40,30,30,20,30,20,20,用最小元素法求初始方案,例题：,已知某运输问题的资料如下表所示,1、表中的发量、收量单位为：吨，运价单位为：元/吨 试求出最优运输方案.,练习：,2、如将A2的发量改为17，其它资料不变，试求最优调 运方案。,解：1、用最小元素法求初始方案,运费为108元/吨,2、用位势法判断：,成本表,u1+v3=5 u2+v4 =1 u1+v4 =3 u3+v2=2 u2+v1=1 u3+v4 =4 令： u10,u10 v13 u22 v2 1 u3 1 v3 5 v4 3,(ui+vj),cij,表中还有负数，说明没有得到最优解，调整运输方案。,ij,(ui+vj),2,2,2,2,新的运送方案,新的成本表,(ui+vj)1,总的运费 105元/吨,表中还有负数，说明没有得到最优解，继续调整运输方案。,cij,(ui+vj)1,(ij)1,cij,(ui+vj)2,(ij)2,表中没有负数，说明已经得到最优解。但有无穷多最优解。,0,成本表,u1+v1=2 u2+v4 =1 u1+v3 =5 u3+v2 =2 u2+v1=1 u3+v3 =7 令： u10,u10 v12 u21 v2 0 u3 2 v3 5 v4 2,(ui+vj),cij,ij,成本表,u1+v3=5 u2+v3 =2 u1+v5 =0 u2+v4 =1 u2+v1=1 u3+v2=2 u3+v4=4 令： u10,u10 v14 u2-3 v2 2 u3 0 v3 5 v4 4 v50,(ui+vj),cij,ij,成本表,u1+v1=2 u2+v4 =1 u1+v3 =5 u3+v2 =2 u1+v5=0 u3+v4=4 u2+v3=2 令： u10,u10 v12 u2-3 v2 2 u3 0 v3 5 v4 4 v50,(ui+vj),cij,ij,C =75,已知资料如下表所示，问如何供电能使总的输电费用为最小？,电力供需表,单位输电费用,作业：,初始方案,100,100,50,250,400,100,单位输电费用,电力供需表,ij,成本表,- (ui+vj),=,cij,(ui+vj),成本表,(ui+vj),调运方案,ij,- (ui+vj),=,cij,成本表,调运方案,(ui+vj),ij,- (ui+vj),=,cij,C=5200,试用表上作业法求最优解,最小总费用为945。,