运筹学04_运输问题

1,运筹学第五章运输问题TransportationProblems,2,本章内容重点,运输模型数学模型表上作业法运输模型的应用,3,人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。,实际背景,4,运输问题举例,某公司有三个生产设施分别位于杜鲁斯(DL),纳瑞多(LR),和坦帕(TP),三个仓库分别位于摩德斯托(MD),奥玛哈(OM)和波斯顿(BS)。各个工厂的生产能力不同，每个仓库的需求也不同。对于给出的不同的生产和运输成本，如何编制运输方案才能使总成本最小？,5,运输模型方法举例,DL生产能力：100单位,TP生产能力：300单位,LR生产能力：300单位,工厂位置,6,MD需求：300单位,BS需求：200单位,OM需求：200单位,DL生产能力：100单位,LR生产能力：300单位,TP生产能力：300单位,运输模型方法举例,仓库位置,7,DL生产能力：100单位,TP生产能力：300单位,BS需求：200单位,OM需求：200单位,LR生产能力：300单位,运输模型方法举例,从坦帕发货,MD需求：300单位,8,DL生产能力：100单位,MD需求：300单位,TP生产能力：300单位,BS需求：200单位,OM需求：200单位,LR生产能力：300单位,运输模型方法举例,从杜鲁斯发货,9,DL生产能力：100单位,MD需求：300单位,TP生产能力：300单位,BS需求：200单位,OM需求：200单位,LR生产能力：300单位,运输模型方法举例,从纳瑞多发货,10,DL生产能力：100单位,MD需求：300单位,TP生产能力：300单位,BS需求：200单位,OM需求：200单位,1984-1994T/MakerCo.,LR生产能力：300单位,运输模型方法举例,$5,$3,$4,$7,$8,$9,$5,$4,$3,每条路线上应当运多少以实现最低成本?,11,运输问题的表格,12,产销平衡运输问题的一般数学模型,设有m个产地（记作A1，A2，A3,Am），生产某种物资，其产量分别为a1,a2，am；有n个销地（记作B1，B2，Bn），其需要量分别为b1,b2，bn；且产销平衡，即。从第i个产地到j个销地的单位运价为cij，在满足各地需要的前提下，求总运输费用最小的调运方案。设xij(i=1,2,，m；j=1,2,n)为第i个产地到第j个销地的运量，则数学模型为：,13,设平衡运输问题的数学模型为：,运输问题的特点：1.有m+n个约束，mn个变量2.特殊的系数矩阵3.有m+n1个基变量4.运输问题一定存在可行解，也一定存在最优解,14,m行,n行,15,故r(A)=m+n1所以运输问题有m+n1个基变量。,为了在mn个变量中找出m+n1个变量作为一组基变量，就是要在A中找出m+n-1个线性无关的列向量，也即是在运输表格中确定m+n-1个格的运输量不为零，而剩下的(m-1)(n-1)格为零。,16,运输单纯形法表上作业法,17,设平衡运输问题的数学模型为：,18,运输单纯形法也称为表上作业法，是直接在运价表上求最优解的一种方法，它的步骤是：,第一步：求初始基行可行解（初始调运方案）。常用的方法有最小元素法、元素差额法（Vogel近似法）。,第二步：求检验数并判断是否得到最优解。常用求检验的方法有闭回路法和位势法，当非基变量的检验数ij全都非负时得到最优解，若存在检验数lk0，说明还没有达到最优，转第三步。,第三步：调整运量，即换基。选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步。,19,初始基可行解,1.最小元素法最小元素法的思想是就近优先运送，即最小运价Cij对应的变量xij优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后得到一个初始基可行解。,20,【例】求表所示的运输问题的初始基可行解。,21,【解】,30,15,10,25,20,22,【例】求表给出的运输问题的初始基本可行解,23,【解】,5,10,0,15,10,10,24,初始基本可行解可用下列矩阵表示,表511中，基变量恰好是3+41=6个且不包含闭回路，是一组基变量，其余标有符号的变量是非基变量,25,2元素差额法（Vogel法）最小元素法只考虑了局部运输费用最小。有时为了节省某一处的运费，而在其它处可能运费很大。元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案,前一种按最小元素法求得，总运费是Z1=108+52+151=105后一种方案考虑到C11与C21之间的差额是82=6，先调运x21，再是x22，其次是x12这时总运费Z2=105+152+51=85Z1。,26,基于以上思路，元素差额法求初始基本可行解的步骤是：,第一步：求出每行次小运价与最小运价之差，记为ui，i=1,2,m；同时求出每列次小运价与最小运价之差，记为vj，j=1，2，n；,第二步：找出所有行、列差额的最大值，即L=maxui，vi，差额L对应行或列的最小运价处优先调运；,第三步：这时必有一列或一行调运完毕，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，就得到一个初始调运方案。,用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。,27,【例】用元素差额法求表513运输问题的初始基本可行解。,【解】求行差额ui,i=1,2,3及列差额vj,j=1,2,3,4.计算公式为ui=i行次小运价i行最小运价vj=j列次小运价j例最小运价,28,【】,5,29,20,0,【】,30,20,0,【】,10,20,5,31,基本可行解为,总运费Z=108+201+52+208=270。,32,求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记xij的检验数为ij由第一章知，求最小值的运输问题的最优判别准则是：,所有非基变量的检验数都非负，则运输方案最优（即为最优解）。,求检验数的方法有两种，闭回路法和位势法。,1闭回路法求检验数求某一非基变量的检验数的方法是：在基本可行解矩阵中，以该非基变量为起点，以基变量为其它顶点，找一条闭回路，由起点开始，分别在顶点上交替标上代数符号+、-、+、-、，以这些符号分别乘以相应的运价，其代数和就是这个非基变量的检验数。,求检验数,33,为一个闭回路，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。,表中闭回路的变量集合是x11,x12,x42,x43,x23,x25,x35,x31共有8个顶点，这8个顶点间组成一条封闭的回路。,34,闭回路的几何特征：1、相邻两个顶点的连线都是水平的或者竖直的。2、每个顶点都是直角的拐角点。回路遇到顶点必须转90度与另一顶点连接3、每一行每一列只要存在某一闭回路的顶点，则必有该闭回路的两个顶点4、一条回路中的顶点数一定是4或4以上的偶数,35,【定理2】若变量组B包含有闭回路，则B中的变量对应的例向量线性相关。,【证】由线性代数知，向量组中部分向量组线性相关则该向量组线性相关，显然，将C中列向量分别乘以正负号线性组合后等于零，即,因而C中的列向量线性相关，所以B中列向量线性相关。,从每一个空格出发一定存在和可以找到唯一的闭回路,36,【解】用最小元素法得到下列一组基本可行解,【例】求下列运输问题的一个初始基本可行解及其检验数。矩阵中的元素为运价Cij，矩阵右边的元素为产量ai，下方的元素为销量bj。,37,矩阵中打“”的位置是非基变量，其余是基变量，这里只求非基变量的检验数。,求11，先找出x11的闭回路，对应的运价为再用正负号分别交替乘以运价有直接求代数和得,38,8,0,9,6,6,-3,39,同理可求出其它非基变量的检验数：,这里340，说明这组基本可行解不是最优解。,只要求得的基变量是正确的且数目为m+n1，则某个非基变量的闭回路存在且唯一，因而检验数唯一。,40,2位势法求检验位势法求检验数是根据对偶理论推导出来的一种方法。,设平衡运输问题为,设前m个约束对应的对偶变量为ui,i=1,2,m，后n个约束对应的对偶变量为vj,j=1,2,n则运输问题的对偶问题是,41,加入松驰变量ij将约束化为等式,ui+vj+ij=cij,记原问题基变量XB的下标集合为I，由第二章对偶性质知，原问题xij的检验数是对偶问题的松弛变量ij当（i，j）I时ij=0，因而有,解上面第一个方程，将ui、vj代入第二个方程求出ij,42,定理2.5（理论难点）原问题单纯型表的检验数行对应对偶问题的一个基解,43,【例】用位势法求例7给出的初始基本可行解的检验数。,【解】第一步求位势u1、u2、u3及v1、v2、v3、v4。,10604030,令u1=0得到位势的解为,44,再由公式求出检验数，其中Cij是非基变量对应的运价。,45,调整运量,前面讲过，当某个检验数小于零时，基可行解不是最优解，总运费还可以下降，这时需调整运输量，改进原运输方案，使总运费减少，改进运输方案的步骤是：,第一步：确定进基变量,第二步：确定出基变量在进基变量xik的闭回路中，标有负号的最小运量作为调整量，对应的基变量为出基变量，并打上“”以示作为非基变量。,第三步：调整运量在进基变量的闭回路中标有正号的变量加上调整量，标有负号的变量减去调整量，其余变量不变，得到一组新的基可行解，然后求所有非基变量的检验数重新检验。,46,【例】求下列运输问题的最优解,【解】用最小元素法求得初始基本可行解如表,47,求非基变量的检验数,用闭回路法得：,48,因为有4个检验数小于零，所以这组基本可行解不是最优解。对应的非基变量x11进基.,对应的非基变量x11进基.,x11的闭回路是,x33最小，x33是出基量，调整量=15,49,在x11的闭回路上x11、x32、x23分别加上15，x12、x33、x21分别减去15，并且在x33处打上记号“”作为非基变量，其余变量不变，调整后得到一组新的基可行解：,50,重新求所有非基变量的检验数得13=3，22=0，24=7，31=1，33=4，34=134=10,说明还没有得到最优解，x34进基，在x34的闭回路中，标负号的变量x14和x32，调整量为,51,x14出基，调整运量得到：,再求非基变量的检验数：,13=3，14=1，22=0，24=8，31=1，33=4,52,再求非基变量的检验数：,13=3，14=1，22=0，24=8，31=1，33=4,所有检验数ij0因而得到最优解,最小运费,53,解的几种情况,无穷多：某个空格的检验数为0退化解：退化的格中必须要填一个0，表示是数字格,54,当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。,1.当产大于销时,即,数学模型为,不平衡运输问题,55,由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，库存量为xi，n+1（i=1，2，m），总的库存量为,56,bn+1作为一个虚设的销地Bn+1的销量。各产地Ai到Bn+1的运价为零，即Ci，n+1=0,（i=1，m）。则平衡问题的数学模型为：,具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可,57,2.当销大于产时,即,数学模型为,58,由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为,xm+1,j是Am+1运到Bj的运量，也是Bj不能满足需要的数量。Am+1到Bj的运价为零,即Cm+1,j=0(j=1,2,n),59,销大于产平衡问题的数学模型为：,具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。,60,因为有：,【例】求下列表中极小化运输问题的最优解。,所以是一个产大于销的运输问题。,61,表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180160=20的销地B5，Ci5=0，i=1，2，3，4。表的右边增添一列,这样可得新的运价表：,62,下表为计算结果。可看出：产地A4还有20个单位没有运出。,63,上例中，假定B1的需要量是20到60之间，B2的需要量是50到70，试求极小化问题的最优解。,需求量不确定的运输问题,64,先作如下分析：（1）总产量为180，B1，B4的最低需求量20+50+35+45=150，这时属产大于销；,（2）B1，B4的最高需求是60+70+35+45=210，这时属销大于产,（3）虚设一个产地A5，产量是210180=30，A5的产量只能供应B1或B2。,（4）将B1与B2各分成两部分的需求量是20，的需求量是40，的需求量分别是50与20，因此必须由A1，A4供应，可由A1、A5供应。,（5）上述A5不能供应某需求地的运价用大M表示，A5到、的运价为零。得到下表的产销平衡表。,得到这样的平衡表后，计算得到最优方案表5-29。,表5-28,66,表中：x131=0是基变量,说明这组解是退化基本可行解,空格处的变量是非基变量。B1，B2，B3，B4实际收到产品数量分别是50，50，35和45个单位。,67