运 输 问题,(Transportation Problem),例：某运输问题的资料如下：,单位 销地,运价,产地,产量,2,9,10,2,9,1,3,4,2,5,8,4,2,5,7,销量,3,8,4,6,一、运输问题的数学模型,数学模型的一般形式,已知资料如下：,单 销,产 量,产地,产,量,销 量,当产销平衡时，其模型如下：,当产大于销时，其模型是：,当产小于销时，其模型是：,特征：,1、平衡运输问题必有可行解，也必有最优解；,2、运输问题的基可行解中应包括,m+n1,个基变量。,这是平衡的运输问题的数学模型，包含mn个变量，mn个约束方程。系数矩阵如下：,m行,n,行,.重复.，直到找到最优解为止。,步骤：,.找出初始基本可行解（初始调运方案，一般m+n-1个数字格），用西北角法、最小元素法、伏格尔法（Vogel）；,.求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用位势法计算；,.改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；,二、表上作业法,例一、某运输资料如下表所示：,单位 销地,运价,产地,产量,3,11,3,10,7,1,9,2,8,4,7,4,10,5,9,销量,3,6,5,6,1、求初始方案：,此法是纯粹的人为的规定，没有理论依据和实际背景，但它易操作，特别适合在计算机上编程计算，因而受欢迎。,西北角法（或左上角法）,西北角法（或左上角法）,1、先确定左上角变量的值，令它取尽可能的值。将这个值填入该变量对应位置，并在该数字上画上圈。画圈格子的对应的变量是基变量。,2、在画圈格子所在的行或列应取0值的变量处填上号。当画圈格子所在行和列的其余变量都应取0时，则或者只对行打，不能同时对行或列都打。打格子对应的变量是非基变量。,3、对表中尚未画圈和打的部分，重复1、2的手续。若遇左上角变量取0值，则在该位置填0，并且同样画上圈，对应变量仍是基变量。,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,.最小元素法：,基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。,总的运输费用（31）（64）,（43）（12）（310）（35）86元,最小元素法,1、先确定运价最小的格子所对应的变量值。若有几个格子同时达到最小运价，则可任取一个。令该变量取尽可能大的值。将此值填入该变量对应位置并画圈。画圈的格子对应的变量是基变量。,2、在画圈格子所在的行或列应取0值的变量处填上号。当画圈格子所在行和列的其余变量都应取0时，则或者只对行打，不能同时对行或列都打。打格子对应的变量是非基变量。,3、对表中尚未画圈和打的部分，重复1、2的手续。当表剩余部分仅是一行或一列时，确定其最小运价对应变量后，不管其余元素是否取零值，都不能打，应作剩余部分处理。,闭回路,性质：回路中的顶点必是偶数，在运输表中，回路遇到顶点必须转90度与另一顶点连接。,集合中的变量称为闭回路的顶点，相邻两个变量的连线为闭回路的边。,X,43,X,41,A,4,X,33,X,32,A,3,A,2,X,12,X,11,A,1,B,3,B,2,B,1,在运输问题中，若变量组含有闭回路，则变量所对应的列向量线性相关。,m+n-1个变量构成基变量的充要条件是他不包含任何闭回路。,B,1,B,2,产量,A,1,8,5,10,A,2,2,1,20,销量,15,15,最小元素法：,Z,1,=105,另一方案：,Z=85,0,1,1,0,1,2,2,5,1,3,2,-,1,3,0,1,-,2,-,1,2,0,1,-,2,-,1,-,(3)伏格尔法（Vogel）：,基本思想：同时考虑每一产地到每一销地和每一销地来自每一产地的最小运价和次小运价，若两者差额大，说明若不能按最小运价供应，就有可能按次小运价供应，从而运费很高。因此，应先对最大差额所在的行或列，按最小元素确定供销关系。一般讲，按此法所得可行解较最小元素法所得可行解更接近最优解。,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,7,8,1,4,3,A,2,2,6,5,3,5,A,3,1,4,2,7,8,销量,2,1,7,6,ij,0（因为目标函数要求最小化）,表格中有调运量的地方为基变量，空格处为非基变,量。基变量的检验数,ij,0，非基变量的检验数,ij,0。,ij,0 表示运费增加。,2、最优解的判别（检验数的求法）：,.闭合回路法：,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,1,3,4,6,3,（1）,（1）,（1）,（1）,计算如下：空格处（,A,1,B,1,）,(13)(1)3(12)(1)1 1,此数即为该空格处的检验数。,1,检验数就是闭回路中所有增加1个运量处的单位运价之和减去所有减少1个运量处的单位运价之和。（经济解释）,闭回路画法：从某一空格出发，横向或纵向画直线，在适当的数字格转向以回到出发的空格。,从每一个空格出发一定存在和可以找到唯一的闭回路。因（m+n-1）个数字格（基变量）对应的系数向量是一个基。于是，任意一个空格（非基变量）对应系数向量是这个基的线性组合,。,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,1,3,6,3,1,2,4,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,1,3,6,3,1,2,-1,4,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,1,3,6,3,1,2,1,-1,4,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,1,3,6,3,1,2,1,-1,12,4,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,1,3,6,3,1,2,1,-1,12,10,4,检验数中有负数，说明原方案不是最优解。,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,0,0,0,0,0,1,2,1,-1,12,10,0,运输问题的约束条件共有,m+n个，其中：m是产地产量的限制；n是销地销量的限制。,其对偶问题也应有m+n个变量，由对偶性可知,C,B,B,-1,=（u,1,u,2,u,m,;v,1,v,2,v,n,),，于是有,C,B,B,-1,P,ij,=u,i,+v,j,。,又因为,，,ij,=c,ij,-C,B,B,-1,P,ij,=c,ij,(u,i,+v,j,),其中前m个计为u,i,（,i=1.2m,）,后n个计为v,j,（,j=1.2n,）,由单纯形法可知，基变量的,ij,0,c,ij,(u,i,+v,j,)0,因此u,i,v,j,可以求出。,位势法,接上例：,B,1,B,2,B,3,B,4,A,1,3,10,u,1,A,2,1,2,u,2,A,3,4,5,u,3,v,1,v,2,v,3,v,4,B,1,B,2,B,3,B,4,A,1,2,9,3,10,0,A,2,1,8,2,9,1,A,3,3,4,2,5,5,2,9,3,10,u,2,+,v,1,=1,u,2,+,v,3,=2,u,3,+,v,2,=4,u,1,+,v,4,=10,u,1,+,v,3,=3,u,3,+,v,4,=5,令：,u,1,0,u,1,0 v,1,2,u,2,1 v,2,9,u,3,5 v,3,3,v,4,10,(u,i,+v,j,),按,ij,=c,ij,(u,i,+v,j,),计算检验数，并以,ij,0,检验，或用,(u,i,+v,j,),c,ij,0,检验。,B,1,B,2,B,3,B,4,A,1,3,11,3,10,A,2,1,9,2,8,A,3,7,4,10,5,c,ij,B,1,B,2,B,3,B,4,A,1,2,9,3,10,A,2,1,8,2,9,A,3,3,4,-2,5,(u,i,+v,j,),B,1,B,2,B,3,B,4,A,1,1,2,0,0,A,2,0,1,0,1,A,3,10,0,12,0,表中还有负数，说明还未得到最优解，应继续调整。,ij,位势法步骤：,1、确定初始基可行解后，在对应初始方案的数字格处填入单位运价。,2、在表中增加一行一列，在列中填入u,i,（i=1,2，m），在行中填入v,j,（j=1,2,n),先令u,1,=0，接着，通过u,i,+v,j,=c,ij,，i，jB来确定u,i,，v,j,。,3、由 ，计算所有空格的检验数。,闭合回路调整法（原理同单纯形法一样）,接上例：,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,1,3,4,6,3,3、改进的方法,B,1,B,2,B,3,B,4,产量,A,1,5,2,7,A,2,3,1,4,A,3,6,3,9,销量,3,6,5,6,6,5,6,3,销量,9,A,3,4,A,2,7,A,1,产量,B,4,B,3,B,2,B,1,3,1,3,4,6,3,B,1,B,2,B,3,B,4,A,1,0,2,0,0,A,2,0,2,1,0,A,3,9,0,12,0,经检验,所有,ij,0,得到最优解，,最小运费为85元。,0,v,4,v,3,v,2,v,1,u,3,5,4,A,3,u,2,8,1,A,2,u,1,10,3,A,1,B,4,B,3,B,2,B,1,10,3,9,3,5,5,2,4,2,A,3,2,8,1,7,1,A,2,0,10,3,9,3,A,1,B,4,B,3,B,2,B,1,(u,i,+v,j,),闭回路调整法步骤：,1、取非基变量中检验数最小的非基变量为入基变量。,2、从这个非基变量出发，寻求一条以基变量为顶点的闭回路（存在且唯一），并将这条闭回路按顺时针或逆时针依次编号（该非基变量为第一号）。,3、将闭回路中偶序顶点的基变量值最小者取作调整量 ，并将该基变量选取为离基变量。,4、将该闭回路上奇序顶点的值加 ，偶序顶点的值减 ，闭回路外的值一律不变。,.无穷多最优解：产销平衡的运输问题必定存最优解。如果非基变量的,ij,0,，则该问题有无穷多最优解。,.退化：表格中一般要有,(m+n-1),个数字格。但有时，在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有,(m+n-1),个数字格。一般可在划去的行和列的任意空格处加一个 0 即可。,4、表上作业法计算中的问题,1、产大于销：模型,方法是先将原问题变成平衡问题，需假设一个销地,(B,n+1,)(,实际上考虑产地的存量,)，,三、产销不平衡的运输问题及其求解方法,模型为：,2、销大于产：同样假设一个产地即可，变化同上。,单位运价表中的单位运价为,B,1,B,2,B,3,B,4,A,1,2,11,3,4,70,A,2,10,3,5,9,50,A,3,7,8,1,2,70,20,30,40,60,B,1,B,2,B,3,B,4,B,5,A,1,2,11,3,4,0,70,A,2,10,3,5,9,0,50,A,3,7,8,1,2,0,70,20,30,40,60,40,B,1,B,2,B,3,B,4,B,5,A,1,70,A,2,50,A,3,70,20,30,40,60,40,40,30,30,20,30,20,20,用最小元素法求初始方案,例题：,例,如下表所示三个化肥厂供应四个地区的化肥，求运费最省的调拨方案。,已知某运输问题的资料如下表所示,B,1,B,2,B,3,B,4,发量,A,1,2,6,5,3,15,A,2,1,3,2,1,12,A,3,3,2,7,4,13,收量,10,13,12,5,1、表中的发量、收量单位为：吨，运价单位为：元/吨,试求出最优运输方案.,练习：,2、如将,A,2,的发量改为1