第三部分运输问题

3.1运输问题与有关概念3.2运输问题的求解表上作业法,本章主要内容,3.1运输问题模型及有关概念,问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案.,例3.1某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,解：产销平衡问题：总产量=总销量设xij为从产地Ai运往销地Bj的运输量，得到下列运输量表：,minf=6x11+4x12+6x13+6x21+5x22+5x23,s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij0(i=1,2；j=1,2,3）,系数矩阵,模型系数矩阵特征1.共有2+3行，分别表示各产地和销地；23列，分别表示各变量；2.每列只有两个1，其余为0，分别表示只有一个产地和一个销地被使用。,例3.2某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问应如何调运，可使得总运输费最小?,解：这是一个产销平衡的运输问题，设xij为从产地Ai运往销地Bj的运输量（i=1，2，3；j=1，2，3，4）,所以此运输问题的线性规划模型如下：Minf=3x11+11x12+3x13+10 x14+x21+9x22+2x23+8x24+7x31+4x32+10 x33+5x34,s.t.x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x24=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6xij0(i=1,2,3；j=1,2,3),其系数矩阵为：,共有3+4行，分别表示产地和销地；有34列分别表示各变量；每列只有两个1，其余为0。,一般运输问题的提法：假设A1、A2、Am表示某物资的m个产地；B1、B2、Bn表示某物资的n个销地；ai表示产地Ai的产量；bj表示销地Bj的销量；cij表示把物资从产地Ai运往销地Bj的单位运价。如果a1+a2+am=b1+b2+bn，则称该运输问题为产销平衡问题；否则，称产销不平衡。下面，首先讨论一般运输问题。,解：设xij为从产地Ai运往销地Bj的运输量,对于产销平衡问题，可得到下列运输问题的模型：,在实际问题建模时，还会出现如下一些变化：有时目标函数求最大，如求利润最大或营业额最大等；当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束；产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资，这相当于在产量约束条件中加上m个松弛变量；当产量大于销量,时可加入一个虚设的销地去消化多余的物资，这相当于在需求约束条件中减去n个松弛变量。,运输问题求解的有关概念,1、基变量的特点,（1）基变量共有m+n-1个,（2）产销平衡运输问题的m+n-1个变量构成基变量的充分必要条件是不含闭回路.,运输问题是一种特殊的线性规划问题，在求解时依然可以采用单纯形法的思路，如图2-1所示.由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算,则无法利用这些有利条件.人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法.在这里需要讨论基本可行解、检验数以及基的转换等问题.,图2-1运输问题的求解思路,定义3.1决策变量格凡是能够排列成下列形式,xab,xac,xdc，xde,xst,xsb（3.1）或xab,xcb,xcd,xed,xst,xat(3.2),其中，a,d,s各不相同；b,c,t各不相同。我们称之为变量集合的一个闭回路，并将式（3.1）,（3.2）中的变量称为这个闭回路的顶点.,例如，x13,x16,x36,x34,x24,x23；x23,x53,x55,x45,x41,x22；x11,x14,x34,x31等都是闭回路。若把闭回路的各变量格看作节点，在表中可以画出如下形式的闭回路：,闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的；闭回路的每一条边（水平的或垂直的）均有且仅有两个闭回路的顶点（变量格）。,关于闭回路有如下的一些重要结论：,根据定义可以看出闭回路的一些明显特点:：,设xab,xac,xdc,xde,xst,xsb是一个闭回路，那么该闭回路中变量所对应的系数列向量,Pab,pac,pdc,pde,pst,psb线性相关；,若变量组xab,xcd,xef,xst中包含一个部分组构成闭回路，那么该变量组所对应的系数列向量pab,pcd,pef,pst线性相关.,定理3.1变量组xab,xcd,xef,xst所对应的系数列向量pab,pcd,pef,pst线性无关的充分必要条件是这个变量组中不包含闭回路.,推论产销平衡运输问题的m+n-1个变量构成基变量的充分必要条件是它不含闭回路.,3.2运输问题求解表上作业法,步骤如下：,在运输问题求解作业数据表中任选一个单元格xij(Ai行Bj列交叉位置上的格)，令xij=minai,bj,一、初始基本可行解的确定,即考虑从Ai向Bj的最大运输量(使行或列在允许的范围内尽量饱和,即使一个约束方程得以满足)，填入xij的相应位置；,从ai或bj中分别减去xij的值，即调整Ai的拥有量及Bj的需求量；,若ai=0，则划去对应的行（把拥有的量全部运走），若bj=0则划去对应的列（把需要的量全部运来），且每次只划去一行或一列（即每次要去掉,且只去掉一个约束）；,若运输平衡表中所有的行与列均被划去，则转.按照上述方法所产生的一组变量的取值将满足下面条件：所得的变量均为非负，且变量总数恰好为m+n1个；得到了一个初始基本可行解.否则，在剩下的运输平衡表中选下一个变量，,所有的约束条件均得到满足；所得的变量不构成闭回路.因此，根据定理3.1及其推论，所得的解一定是运输问题的基本可行解.一般较常用的方法有西北角法、最小元素法和差额法。下面分别举例予以说明.,1、西北角法（左上角方法）,例3.3考虑例3.2某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示：,问应如何调运，可使得总运输费最小?,3,4,2,2,3,6,产销平衡表,运价表,z=33+411+29+22+310+65=135,2.最小元素法。例34（运价小者先安排）,1,3,2,1,3,4,4,6,5,3,10,3,产销平衡表,运价表,z=43+310+31+12+64+35=86,3.差额法（次小运价与最小运价之差大者先安排）,产销平衡表,运价表,2513,011,6,012,3,212,3,76,5,1,2,z=53+210+31+18+64+35=85,上述计算过程可用流程图描述如下（图2-2）,注：应用西北角法和最小元素法，每次填完数，都只划去一行或一列。当填上一个数后行、列同时饱和时，也应任意划去一行（列）在保留的列（行）任意没被划去的格内标一个0.,例3.5某公司下属有生产一种化工产品的三个产地A1、A2、A3,有四个销售点B1、B2、B3、B4销售这种化工产品.各产地的产量、各销地的销量和各产地运往各销地每吨产品的运费(百元)如下表所示.,产销平衡表,运价表,问应如何调运，可使得总运输费最小?,解：用西北角法求初始基本可行解,产销平衡表,运价表,35,40,0,40,15,65,z=353+408+404+157+655=1015,产销平衡表,运价表,2,35,3,40,4,5,5,50,5,40,9,25,z=505+259+352+54+403+405=885,产销平衡表,运价表,1513,3,40,5,40,3,35,4,40,15,25,z=353+155+259+404+403+405=885,111,练习：求解以下列数据为单位运费的运输问题(1),(2),二、基本可行解的最优性检验,由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案.,1.位势法,首先给出位势概念：设对应m+n-1个基变量xij的系数cij，存在ui,vj满足：,ui+vj=cij，i=1,m；j=1,n.我们称这些ui,vj为该基本可行解对应的位势.,由于有m+n个变量（ui,vj），m+n-1个方程（基变量个数），故该方程组有解。解出ui,vji=1,m；j=1,n。,则检验数为：ij=cij-ui-vji=1,m;j=1,n,例：首先求解方程组,u1+v4=c14=10u1+v3=c13=3u2+v1=c21=1u2+v3=c23=2u3+v2=c32=4u3+v4=c34=5,令u1=5则有v4=5,v3=-2,u2=4,u3=0,v2=4,v1=-3,再求检验数：,11=c11u1-v1=35(-3)=1,12=c12u1v2=1154=2,22=c22u2v2=944=1,24=c24u2v4=845=1,31=c31u3-v1=70(3)=10,33=c33u3v3=100(2)=12,1,2,1,-1,10,12,2.加减法,在运价表中,每行或每列的元素加上或减去一个数,使基变量对应的运价变成零.所得各数即为检验数.,-3,-7,+2,-6,-2,+1,三、求新的基本可行解,(1)找闭回路：以最小的负检验数对应的非基变量为起始顶点寻找一个闭回路.(2)求调整量：闭回路上偶数次顶点运量的最小值为调整量，记作:(3)调整：闭回路上的偶数次顶点的调运量减去；闭回路上的奇数次顶点的调运量加上；非闭回路顶点的其他变量调运量不变；再去掉闭回路上的一个零运量.,24=1，作x24的闭回路，调整数=1，调整得,-3,-7,+2,-6,-1,求调整数得：,所有的检验数均为非负，因此得到最优解：x11=2,x13=5,x21=1,x24=3,x32=6,x34=3,其余的xij=0.,总运费为：f=32+35+11+83+46+53=85.,如果非基变量的检验数有等于零的时候，将出现多解的情况.上面的例题是多解情况.,(或写成)得最优运输方案为:,例3.6已知某运输问题的产销平衡表与单位运价表如下表所示，求最优调运方案.,解：由伏格法：,产销平衡表单位运价表,50,60,30,10,15,65,70,-20,-10,5,-30,-5,5,-10,最优性检验：,所有的检验数都大于等于0，则得到的最优解为如上表所示，没有赋值的变量都取0值.,总运费为z=5015+1020+6015+3030+1530+6515+7025=7225,练习：求最小运费,3,3,4,1,1,2,1,3,5,4,1,2,8,1,1,3,5,2,2,1,5,0,1,1,2,5,最优性检验：,9,2,1,8,+3,10,+3,所有的检验数都大于等于0，所以所得指派方案为最优指派方案，即：,最小运费为：z=212+87+110+59+511+55+59=260,四、产销不平衡问题的处理1、产量大于销量的情况对于产大于销问题，可得到下列运输问题的模型：,例3.7某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,解：这里，总产量为78+45=123；总销量为53+36+25=114.产销不平衡，增加一个虚设的销地，得到下表,计算过程如下：,15,36,0,10,1,11,11,45,25,7,12,1,10,3,+12,2、销量大于产量的情况：可得到下列运输问题的模型：,例3.8某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表，问：应如何调运可使总运输费用最小？,解:这里，总产量小于总销量，产销不平衡，增加一个虚设的产地，得到下表,0,31,2,10,14,15,5,11,45,65,8,12,1,3,10,+3,例3.9有A1、A2、A3三个生产某种物资的产地，五个地区B1、B2、B3、B4、B5对这