运筹学课件我的资源3-运输问题

2020/6/10,Copyright2013Czhang.Allrightsreserved.,张冲南京邮电大学经济管理学院Email：zcbling,运输问题,2020/6/10,Copyright2013Czhang.Allrightsreserved.,Chapter3运输规划(TransportationProblem),运输规划问题的数学模型表上作业法产销平衡问题产销不平衡问题（经管）,本章主要内容：,2020/6/10,Copyright2013Czhang.Allrightsreserved.,运输问题的背景,在经济建设中，经常碰到大宗物资调运问题，如煤炭、钢铁、粮食等等。主产区和主销区往往不同，需要大规模的调运，将物资从产地供应到销地。大型企业有多个生产基地，销售遍及全国乃至全世界，如何分配供应计划使经济效益最好。解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，且各地运输单价已知的前提下，如何确定一个使总的运输费用最小的方案。,2020/6/10,Copyright2013Czhang.Allrightsreserved.,运输规划问题的数学模型,例3.1某公司从两个产地A1、A2将物品运往三个销地B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,2020/6/10,Copyright2013Czhang.Allrightsreserved.,运输规划问题的数学模型,解：产销平衡问题：总产量=总销量500设xij为从产地Ai运往销地Bj的运输量，得到下列运输量表：,MinC=6x11+4x12+6x13+6x21+5x22+5x23s.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）,建立线性规划模型：,2020/6/10,Copyright2013Czhang.Allrightsreserved.,运输规划问题的数学模型,运输问题的一般形式：产销平衡（即产地总产量等于销地的总需求量）,A1、A2、Am表示某物资的m个产地；B1、B2、Bn表示某物质的n个销地；ai表示产地Ai的产量；bj表示销地Bj的销量；cij表示把物资从产地Ai运往销地Bj的单位运价。设xij为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：,2020/6/10,Copyright2013Czhang.Allrightsreserved.,运输问题约束条件的系数矩阵,系数列向量：,运输规划问题的数学模型,2020/6/10,Copyright2013Czhang.Allrightsreserved.,第1节运输问题的数学模型,系数矩阵中对应于变量xij的系数向量Pij，其分量中除第i个和第m+j个为1以外，其余的都为零。即Pij=(0,1,0,0,1,0,0)T=ei+em+j对产销平衡的运输问题，由于有以下关系式存在：,2020/6/10,Copyright2013Czhang.Allrightsreserved.,第1节运输问题的数学模型,所以，该模型最多只有m+n-1个独立约束方程，由于有以上特征，求解运输问题时，可用比较简便的计算方法，习惯上称为表上作业法。,2020/6/10,Copyright2013Czhang.Allrightsreserved.,运输规划问题的数学模型,该模型包括mn个变量，（m+n）个约束方程。同时，该模型最多只有m+n-1个独立约束方程，即系数矩阵的秩m+n-1.定理:设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。,2020/6/10,Copyright2013Czhang.Allrightsreserved.,运输规划问题的数学模型,可出现的变化：1）有时目标函数求最大。如求利润最大或营业额最大等；2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)；3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,例3.2某运输资料如下表所示：,问：应如何调运可使总运输费用最小？,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,解：第1步求初始方案给出初始调运方案。初始基可行解：即在(mn)产销平衡表上给出m+n-1个数字格。最小元素法（）伏格尔法,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,方法1：最小元素法用最小元素法给出的初始解是运输问题的基可行解，其理由为：(1)用最小元素法给出的初始解，是从单位运价表中逐次地挑选最小元素，并比较产量和销量。当产大于销，划去该元素所在列。当产小于销，划去该元素所在行。然后在未划去的元素中再找最小元素，再确定供应关系。,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,（2）这样在产销平衡表上每填入一个数字，在运价表上就划去一行或一列。表中共有m行n列，总共可划(n+m)条直线。但当表中只剩一个元素时，这时当在产销平衡表上填这个数字时，而在运价表上同时划去一行和一列。此时把单价表上所有元素都划去了，相应地在产销平衡表上填了(m+n-1)个数字。即给出了(m+n-1)个基变量的值。,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,解：第1步求初始方案,方法1：最小元素法基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。,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元,2020/6/10,Copyright2013Czhang.Allrightsreserved.,最小元素法-注意事项当取定xij的值之后,会出现Ai的产量与Bj的销量都为零的情况,只能划去Ai行或Bj列,不能同时划去用最小元素法时,可能会出现只剩一行或一列的所有格均未填数或未划掉的情况,此时在这一行或这一列中除去已填上的数外均填上零,不能将空格划掉这样可保证填过数或行的格为m+n-1个,即基变量的个数为m+n-1个,表上作业法,2020/6/10,Copyright2013Czhang.Allrightsreserved.,8,2,10,14,8,6,初始基可行解为：目标函数值Z246,二、表上作业法,练习,利用最小元素法求解初始基可行解,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,方法2：伏格尔法（Vogel法）最小元素法的缺点是：为了节省一处的费用，有时造成在其他处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。,用伏格尔法求得的基本可行解更接近最优解，所以也称为近似方案。,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,伏格尔法-步骤,1）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。,3,11,3,10,1,9,2,7,4,10,5,8,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,2）再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应完毕或得到满足时，划去运价表中对应的行或列。重复1)和2)，直到找出初始解为至。,3,11,3,10,1,9,2,7,4,10,5,8,6,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,3,11,3,10,1,9,2,7,4,10,5,8,6,3,3,5,1,2,该方案的总运费:(13)(46)(35)(210)(18)(35)85元。本例用伏格尔法给出的初始解就是最优解。,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,另外一种方法,3,11,3,10,1,9,2,7,4,10,5,8,5,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,7,1,3,5,2,7,5,3,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,1,1,3,5,1,5,3,6,3,1,2,该方案的总运费:(13)(46)(35)(210)(18)(35)85元本例用伏格尔法给出的初始解就是最优解。,2,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,第2步最优解的判别（检验数的求法）,求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记xij的检验数为ij。由第一章知，求最小值的运输问题的最优判别准则是：,所有非基变量的检验数都非负，则运输方案最优,求检验数的方法有两种：闭回路法位势法（）,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,闭回路的概念,方法一：闭回路法,为了求某个空格(非基变量)的检验数，先要找出它在运输表上的闭回路，这个闭回路的顶点，除这个空格外，其它均为填有数字的格(基变量格)，它是由水平线段和竖直线段依次联接这些顶点构成的一封闭多边形。每个空格都唯一存在这样的一条闭回路。,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,例下表中闭回路的变量集合是x11,x12,x42,x43,x23,x25,x35,x31共有8个顶点，这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。,一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一顶点连接，表中的变量x32及x33不是闭回路的顶点，只是连线的交点。,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,例如变量组不能构成一条闭回路，但A中包含有闭回路,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,闭回路,闭回路特征:1.每个顶点都是转角点.2.每一边都是水平或垂直的.3.每一行(或列)若有闭回路的顶点,则必有两个.,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,闭回路的构成在已给出的调运方案的运输表上，从代表非基变量的一个空格出发，沿水平或垂直方向前进，只有碰到代表基变量的有数字的格才能向左或右转，继续前进，直到回到起始出发的空格为止。用闭回路计算检验数在以空格为始点和终点，其他顶点均为数字点的闭回路上将该空格的运输量调整为1，则其他顶点在保持供销平衡的基础上，运输量增加或减少1，计算出该回路的总费用的变化值，该变化值作为该非基变量的检验数，若所有检验数都大于零，则原基可行解为最优解，否则进一步迭代找出最优解。用闭回路法求检验数的缺点要对每一个空格找一条闭回路当产销点多时，较繁杂,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,（1）,x11为非基变量的闭回路,检验数的计算：从（A1，B1）出发，增加一单位调运量（从A1运到B1），为保持产销平衡，依次做调整：在（A1，B3）处减少1吨，（A2，B3）处增加1吨，（A2，B1）处减少1吨。调整方案使运费增加：1*3+（-1）*3+1*2+（-1）*1=1，可见这样调整将每单位增加运费1，将检验数1填入（A1，B1）。,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,（1）,x12为非基变量的闭回路,检验数的计算：1*11+（-1）*10+1*5+（-1）*4=2，可见这样调整将每单位增加运费1，将检验数2填入（A1，B2）。,（2）,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,（1）,x22为非基变量的闭回路,检验数的计算：1*9+（-1）*2+1*3+（-1）*10+1*5+（-1）*4=1，可见这样调整将每单位增加运费1，将检验数1填入（A2，B2）。,（2）,（1）,2020/6/10,Copyright2013Czhang.Allrightsreserved.,所有非基变量的闭回路及检验数,表上作业法,空格,闭回路,检验数,x11,x11-x13-x23-x21-x11,x12-x14-x34-x32-x12,x12,x22,x24,x31,x33,x22-x23-x13-x14-x34-x32-x22,x24-x23-x33-x14-x24,x31-x34-x14-x13-x23-x21-x31,x33-x34-x14-x13-x33,1,2,1,-1,10,12,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,（1）,非基变量的闭回路,（2）,（1）,（-1）,（10）,（12）,2020/6/10,Copyright2013Czhang.Allrightsreserved.,用闭回路法求解检验数,练习,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,方法二：位势法-用位势法对初始方案进行最优性检验：,Step1:由ij=Cij-（Ui+Vj）计算位势Ui，Vj，因对基变量而言有ij=0，即Cij-（Ui+Vj）=0，令U1=0,Step2:再由ij=Cij-（Ui+Vj）计算非基变量的检验如数ij,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表上作业法,3,11,3,10,1,9,2,7,4,10,5,8,4,3,6,3,1,3,0,-1,-5,3,10,2,9,（1）,（2）,（1）,（-1）,（10）,（12）,当存在非基变量的检验数kl0，说明现行方案为最优方案，否则目标成本还可以进一步减小。（本例存在24产”，可虚拟一个产地，让其产量=“销-产”，同时令该虚拟的产地的单位运价为0.,2020/6/10,Copyright2013Czhang.Allrightsreserved.,例1产大于销,2020/6/10,Copyright2013Czhang.Allrightsreserved.,解法：虚设一销地，令其销量为产销量之差。b4=ai-bj=4该列单位运价为0，即可化为产销平衡问题,2020/6/10,Copyright2013Czhang.Allrightsreserved.,例2产小于销,2020/6/10,Copyright2013Czhang.Allrightsreserved.,解法：虚设一销地，令其销量为产销量之差b4=bj-ai=1令该列运价为0，如此可化为产销平衡问题。,2020/6/10,Copyright2013Czhang.Allrightsreserved.,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表3-33产销平衡表,表3-34单位运价表,例：求下面问题最优调运方案,2020/6/10,Copyright2013Czhang.Allrightsreserved.,2020/6/10,Copyright2013Czhang.Allrightsreserved.,解：首先化为产销平衡的运输问题。假设一个库存地B5，产销平衡表如表3-35，其中b5=19-15=4,2020/6/10,Copyright2013Czhang.Allrightsreserved.,4,2,3,3,3,2,2,最小元素法求初始可行解,注意:,在利用最小元素法求初始调运方案时，不将假想的“0”作为最小元素来对待。,2020/6/10,Copyright2013Czhang.Allrightsreserved.,由Vogel法求初始调运方案,2,3,2,2,2,2,4,5,3,3,3,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表3-37Vogel法得运量表,2020/6/10,Copyright2013Czhang.Allrightsreserved.,用位势法求表3-37是否为最优调运方案。其位势表与检验数表如表3-38和3-39表3-38位势表,2020/6/10,Copyright2013Czhang.Allrightsreserved.,ij=cij(ui+vj)=0,u1+v1=2u1+v4=4u1+v5=0u2+v2=3u2+v5=0u3+v3=1u3+v4=2令：u10,2020/6/10,Copyright2013Czhang.Allrightsreserved.,表3-39,所有检验数都大于等于0，所以是最优方案。最优值fmin=22+43+33+41+23=35,2020/6/10,Copyright2013Czhang.Allrightsreserved.,运输问题的应用,短缺资源的分配问题,2020/6/10,Copyright2013Czhang.Allrightsreserved.,必须满足,最高和最低之间差额，不一定全额满足。,问题分析,1、产销量问题。产量160，最低需求110，最高需求无限，但根据现有情况，最高总需求为210（因为销地最多可获得60），属于产销不平衡问题；,2、如何转换成产销平衡问题？增加假想产地。,3、将需求量化成两部分，一部分满足最低需求，一部分满足差额。,2020/6/10,Copyright2013Czhang.Allrightsreserved.,步骤一：转化成产销平衡问题,解：增设产地丁，令其供应量为：最大需求量供应量50,虚拟产地的运价如何确定？,最小需求,最高与最低需求差,2020/6/10,Copyright2013Czhang.Allrightsreserved.,M表示无穷大正数，表示最低需求不能由D产地处供给。,步骤二：虚拟产地的单位运价确定,原则：销地的最小需求必须得到满足，而最高需求不一定得到满足。说明最小销售量的满足不能来源于虚拟的产地。,M,M,M,0,0,0,2020/6/10,Copyright2013Czhang.Allrightsreserved.,2,14,0,19,2,15,3,1,0,0,30,20,3,1,0,0,20,30,2,2,0