运输单纯形法.ppt

3.3 运输单纯形法,Transportation Simplex Method,Ch3 Transportation Problem,*,Page,*,of 31,设,平衡运输问题的数学模型为：,1/22/2026,运输单纯形法也称为表上作业法，是直接在运价表上求最优解的一种方法，它的步骤是：,第一步：求初始基行可行解（初始调运方案），常用的方法有最小元素法、元素差额法（,Vogel,近似法）、左上角法。,第二步：求检验数并判断是否得到最优解，常用求检验的方法有闭回路法和位势法，当非基变量的检验数,ij,全都非负时得到最优解，若存在检验数,lk,0，,说明还没有达到最优，转第三步。,第三步：调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步。,1/22/2026,3.3.1初始基可行解,1.最小元素法,最小元素法的思想是就近优先运送，即最小运价,C,ij,对应的变量,x,ij,优先赋值,然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后一个初始基可行解。,1/22/2026,【,例3.3】求表,36所示的运输问题的初始基可行解。,表36,销 地,产地,B,1,B,2,B,3,产量,A,1,8,6,7,30,A,2,4,3,5,45,A,3,7,4,8,25,销 量,60,30,10,100,1/22/2026,销 地,产地,B,1,B,2,B,3,产量,A,1,8,6,7,30,A,2,4,3,5,45,A,3,7,4,8,25,销 量,60,30,10,100,【解】,30,15,10,25,20,1/22/2026,【,例3.4】,求表37给出的运输问题的初始基本可行解。,B,1,B,2,B,3,B,4,a,i,A,1,3,11,4,4,7,A,2,7,7,3,8,4,A,3,1,2,10,6,9,b,j,3,6,5,6,20,表37,1/22/2026,【解】,B,1,B,2,B,3,B,4,a,i,A,1,3,11,4,4,7,A,2,7,7,3,8,4,A,3,1,2,10,6,9,b,j,3,6,5,6,20,3,6,0,4,1,6,在,x,12,、,x,22,、x,33,、x,34,中任选一个变量作为基变量，例如选,x,12,表,38,1/22/2026,初始基本可行解可用下列矩阵表示,表38中，标有符号 的变量恰好是3+41=6个且不包含闭回路，,是一组基变量，其余标有符号的变量是非基变量，,1/22/2026,2元素差额法（,Vogel,近似法）,最小元素法只考虑了局部运输费用最小，对整个产销系统的总运输费用来说可能离最优值较远。有时为了节省某一处的运费，而在其它处可能运费很大。元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案，,15 15 15 15,前一种按最小元素法求得，总运费是,Z,1,=108+52+151=105，,后一种方案考虑到,C,11,与,C,21,之间的差额是8,2=6，如果不先调运,x,21,，,到后来就有可能,x,11,0，,这样会使总运费增加较大，从而先调运,x,21,，,再是,x,22,，,其次是,x,12,这时总运费,Z,2,=105+152+51=85,Z,1,。,基于以上想法，元素差额法求初始基本可行解的步骤是：,1/22/2026,基于以上想法，元素差额法求初始基本可行解的步骤是：,第一步：求出每行次小运价与最小运价之差，记为,u,ii,=1,2,m,；,同时求出每列次小运价与最小运价之差，记为,v,j,，,j,=1，2，,n,；,第二步：找出所有行、列差额的最大值，即,L,=max,u,i,，,v,i,，,差额,L,对应行或列的最小运价处优先调运；,第三步：这时必有一列或一行调运完毕，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，就得到一个初始调运方案。,用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。,1/22/2026,【,例5】用元素差额法求表,39运输问题的初始基本可行解。,B,1,B,2,B,3,B,4,a,i,A,1,5,8,9,12,15,A,2,6,72,4,25,A,3,1,10,13,8,20,b,j,20,10,5,25,60,表,39,1/22/2026,销地,产地,B,1,B,2,B,3,B,4,a,i,u,i,A,1,5,8,9,12,15,3,A,2,1,7,2,4,25,1,A,3,6,10,13,8,20,2,b,j,20,10,5,25,60,v,j,4,1,7,4,【,解】,求行差额,u,i,i,=1,2,3,及列差额,v,j,j,=1,2,3,4.,计算公式为,u,i,=,i,行次小运价,i,行最小运价,v,j,=,j,列次小运价,j,例最小运价,5,1/22/2026,销地,产地,B,1,B,2,B,3,B,4,a,i,u,i,A,1,5,8,9,12,15,A,2,1,7,2,4,25,A,3,6,10,13,8,20,b,j,20,10,5,25,60,v,j,5,4,1,4,3,3,2,20,0,1/22/2026,销地,产地,B,1,B,2,B,3,B,4,a,i,u,i,A,1,5,8,9,12,15,A,2,1,7,2,4,25,A,3,6,10,13,8,20,b,j,20,10,5,25,60,v,j,5,20,0,2,4,4,2,20,10,5,1/22/2026,基本可行解为,总运费,Z,=108+201+52+208=270。,求,运输问题的初始方案还有很多方法，如左上角法、右上角法等。常用的方法是,Vogel,近似法、最小元素法。,1/22/2026,3.3.2求检验数,求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记,x,ij,的检验数为,ij,由第一章知，求最小值的运输问题的最优判别准则是：,所有非基变量的检验数都非负，则运输方案最优（即为最优解）。,求检验数的方法有两种，闭回路法和位势法。,1闭回路法求检验数,求某一非基变量的检验数的方法是：在基本可行解矩阵中，以该非基变量为起点，以基变量为其它顶点，找一条闭回路，由起点开始，分别在顶点上交替标上代数符号+、-、+、-、，以这些符号分别乘以相应的运价，其代数和就是这个非基变量的检验数。,1/22/2026,【解】用最小元素法得到下列一组基本可行解,【例7】求下列运输问题的一个初始基本可行解及其检验数。矩阵中的元素为运价,C,ij,，,矩阵右边的元素为产量,a,i,，,下方的元素为销量,b,j,。,10 60 40 30,1/22/2026,矩阵中打“”的位置是非基变量，其余是基变量，这里只求非基变量的检验数。,求,11,，,先找出,x,11,的闭回路 ，对应的运价为,再用正负号分别交替乘以运价有,直接求代数和得,1/22/2026,同理可求出其它非基变量的检验数：,这里,34,0，,说明这组基本可行解不是最优解。,只要求得的基变量是正确的且数目为,m,+,n,1，,则某个非基变量的闭回路存在且唯一，因而检验数唯一。,1/22/2026,2位势法求检验,位势法求检验数是根据对偶理论推导出来的一种方法。,设平衡运输问题为,设前,m,个约束对应的对偶变量为,u,i,i,=1,2,m,，,后,n,个约束对应的对偶变量为,v,j,j,=1,2,n,则运输问题的对偶问题是,1/22/2026,加入松驰变量,ij,将约束化为等式,u,i,+,v,j,+,ij,=,c,ij,记原问题基变量,X,B,的下标集合为,I，,由第二章对偶性质知，原问题,x,ij,的检验数是对偶问题的松弛变量,ij,当（,i,，,j,）,时,ij,=0，,因而有,解,上面第一个方程，将,u,i,、,v,j,代入第二个方程求出,ij,。,1/22/2026,【例8】用位势法求例7给出的初始基本可行解的检验数。,【解】第一步求位势,u,1,、,u,2,、,u,3,及,v,1,、,v,2,、,v,3,、,v,4,。,10 60 40 30,令,u,1,=0,得到位势的解为,1/22/2026,再由公式 求出检验数，其中,C,ij,是非基变量对应的运价。,计算结果与例7结果相同。,1/22/2026,3.3.3调整运量,前面讲过，当某个检验数小于零时，基可行解不是最优解，总运费还可以下降，这时需调整运输量，改进原运输方案，使总运输减少，改进运输方案的步骤是：,第一步：确定进基变量；,第二步：确定出基变量，在进基变量,x,ik,的闭回路中，标有负号的最小运量作为调整量,，,对应的基变量为出基变量，并打上“”以示作为非基变量。,第三步：调整运量。在进基变量的闭回路中标有正号的变量加上调整量,，,标有负号的变量减去调整量,，,其余变量不变，得到一组新的基可行解，然后求所有非基变量的检验数重新检验。,1/22/2026,【例9】求下列运输问题的最优解。,45 65 50 30,销地,产地,B,1,B,2,B,3,B,4,a,i,A,1,5,8,9,2,70,A,2,3,6,4,7,80,A,3,10,12,14,5,40,b,j,45,65,50,30,190,【解】用最小元素法求得初始基本可行解如下：,30,45,35,40,25,15,1/22/2026,销地,产地,B,1,B,2,B,3,B,4,a,i,A,1,5,8,9,2,70,A,2,3,6,4,7,80,A,3,10,12,14,5,40,b,j,45,65,50,30,190,30,45,35,40,25,15,求非基变量的检验数,用闭回路法得：,1/22/2026,销地,产地,B,1,B,2,B,3,B,4,a,i,A,1,5,8,9,2,70,A,2,3,6,4,7,80,A,3,10,12,14,5,40,b,j,45,65,50,30,190,30,45,35,40,25,15,因为有4个检验数小于零，所以这组基本可行解不是最优解。对应的非基变量,x,11,进基.,对应的非基变量,x,11,进基.,x,11,的闭回路是,标负号的变量是,x,12,、,x,33,、,x,21,，,取运量最小值,x,33,最小，,x,33,是出基量，调整量,=15,1/22/2026,销地,产地,B,1,B,2,B,3,B,4,a,i,A,1,5,8,9,2,70,A,2,3,6,4,7,80,A,3,10,12,14,5,40,b,j,45,65,50,30,190,在,x,11,的闭回路上,x,11,、,x,32,、,x,23,分别加上15，,x,12,、,x,33,、,x,21,分别减去15，并且在,x,33,处打上记号“”作为基变量，其余变量不变，调整后得到一组新的基可行解：,30,30,50,25,40,15,1/22/2026,销地,产地,B,1,B,2,B,3,B,4,a,i,A,1,5,8,9,2,70,A,2,3,6,4,7,80,A,3,10,12,14,5,40,b,j,45,65,50,30,190,30,30,50,25,40,15,重新求所有非基变量的检验数得：,13,=3，,22,=0，,24,=7，,31,=1，,33,=4，,34,=1,x,34,进基、,x,14,出基。调整运量得到下表：,1/22/2026,再求非基变量的检验数：,13,=3，,14,=1，,22,=0，,24,=831,=1，,33,=4,所有检验数,ij,0,因而得到最优解,最小运费,销地,产地,B,1,B,2,B,3,B,4,a,i,A,1,5,8,9,2,70,A,2,3,6,4,7,80,A,3,10,12,14,5,40,b,j,45,65,50,30,190,30,30,50,55,10,15,1/22/2026,作业：,P99 T3.3(1)(2)3.4,本节讲解了平衡运输问题的求解方法：运输单纯形法,运输单纯形法主要分三个步骤：,1.求初始运输方案，用最小元素法、元素差额法（,Vogel,近似法）,2.,求检验数，用闭回路法和位势法,3.调整运量，用闭回路法,Exit,运输问题的变体,1/22/2026,