运筹学运输与指派问题.ppt

制作与教学,武汉,理工大学,管理学院 熊伟,xiongw,Page,*,Chapter 5,运输与指派问题,T&,A,Problem,运筹学,Operations Research,Chapter 5,运输与指派问题,Transportationand,Assignment,Problem,5.1,运输问题的数学模型,及其特征,5.2,运输单纯形法,5.3,运输模型的应用,5.4,指派问题,5.1,运输问题的数学模型及其特征,Mathematical Model of,Transportation Problems,人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的,生产量,和,需要量,及各地之间的,运输费用,，如何制定一个运输方案，使总的运输费用最小。这样的问题称为,运输问题,。,5.1,运输模型,Model of,Transportation Problems,5.1.1,数学模型,产地,销地,A,1,10,A,2,8,A,3,5,B,4,3,B,3,8,B,2,7,B,1,5,3,5,4,2,3,1,6,8,2,3,2,9,图,5.1,【,例,5-1】,现有,A,1,，,A,2,，,A,3,三个产粮区，可供应 粮食分别为,10,，,8,，,5,（万吨），现将粮食运往,B,1,，,B,2,，,B,3,，,B,4,四个地区，其需要量分别为,5,，,7,，,8,，,3,（万吨）。产粮地到需求地的运价（元,/,吨）如表,5-1,所示，问如何安排一个运输计划，使总的运输费用最少。,需求地,产粮地,B,1,B,2,B,3,B,4,供给量,A,1,3,2,6,3,10,A,2,5,3,8,2,8,A,3,4,1,2,9,5,需求量,5,7,8,3,23,运价表（元,/,吨）,表,5-1,5.1,运输模型,Model of,Transportation Problems,设,x,ij,(,i,=1,2,3,；,j,=1,2,3,4),为,i,个产粮地运往第,j,个需求地的运量，这样得到下列运输问题的数学模型：,运量应大于或等于零（非负要求），即,5.1,运输模型,Model of,Transportation Problems,有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型,看一个例子：,【,例,5-2】,有三台机床加工三种零件，计划第,i,台的生产任务为,a,i,(,i,=1,2,3),个零件，第,j,种零件的需要量为,b,j,(,j,=1,2,3),，第,i,台机床加工第,j,种零件需要的时间为,c,ij,，如表,5,2,所示。问如何安排生产任务使总的加工时间最少？,零件,机床,B1,B2,B3,生产任务,A1,5,2,3,50,A2,6,41,60,A3,7,3,4,40,需要量,70,30,50,150,表,5,2,5.1,运输模型,Model of Transportation Problems,【,解,】,设,x,i j,(,i,=1,2,3,；,j,=1,2,3,),为第,i,台机床加工第,j,种零件的数量，则此问题的数学模型为,5.1,运输模型,Model of Transportation Problems,5.1.2,模型特征,运输问题的一般数学模型,设有,m,个产地（记作,A,1,，,A,2,，,A,3,A,m,），生产某种物资，其产量分别为,a,1,a,2,，,，,a,m,；有,n,个销地（记作,B,1,，,B,2,，,，,B,n,），其需要量分别为,b,1,b,2,，,，,b,n,；且产销平衡，即 。从第,i,个产地到,j,个销地的单位运价为,c,ij,，在满足各地需要的前提下，求总运输费用最小的调运方案。,5.1,运输模型,Model of Transportation Problems,销地,产地,产量,销量,设,xij,(,i,=1,2,，,m,；,j,=1,2,n,),为第,i,个产地到第,j,个销地的运量，,则数学模型为：,5.1,运输模型,Model of,Transportation Problems,m,行,n,行,5.1,运输模型,Model of,Transportation Problems,运输问题具有如下特点,:,1.,运输问题存在可行解，也一定存在最优解,2.,当供应量和需求量都是整数时，则一定存在整数最优解,3.,有,m+n,个约束，,mn,个变量,4.,约束条件系数矩阵的元素等于,0,或,1,5.,约束条件系数矩阵的每一列有两个非零元素,这对应于每一个变量在前,m,个约束方程中出现一次,在后,n,个约束方程中也出现一次,6.,所有约束方程都是等式方程,7.,各产地产量之和等于各销地销量之和,8.,有,m+n,1,个基变量,因为产销平衡,所以模型最多只有,m+n-1,个独立约束方程,即系数矩阵的秩最多为,m+n-1.,5.2,运输单纯形法,Transportation Simplex Method,设平衡运输问题的数学模型为：,5.2,运输单纯形法,Transportation Simplex Method,运输单纯形法也称为表上作业法，是直接在运价表上求最优解的一种方法，它的步骤是：,第一步：,求初始基本可行解（初始调运方案）。常用的方法有最小元素法、元素差额法（,Vogel,近似法）、左上角法。,第二步：,求检验数并判断是否得到最优解。常用求检验的方法有闭回路法和位势法，当非基变量的检验数,ij,全都非负时得到最优解，若存在检验数,lk,0,，说明还没有达到最优，转第三步。,第三步：,调整运量，即换基。选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步。,5.2,运输单纯形法,Transportation Simplex Method,5.2.1,初始基可行解,1.,最小元素法,最小元素法的思想是就近优先运送，即最小运价,C,ij,对应的变量,x,ij,优先赋值,然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后得到一个初始基可行解。,5.2,运输单纯形法,Transportation Simplex Method,【,例,5-3】,求表,5,6,所示的运输问题的初始基可行解。,表,5,6,销 地,产地,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,9,7,2,3,6,10,85,9,4,1,2,70,50,20,销 量,10,60,40,30,140,5.2,运输单纯形法,Transportation Simplex Method,B,j,A,i,B,1,B,2,B,3,B,4,产 量,A,1,9,3,8,4,70,A,2,7,6,5,1,50,A,3,2,10,9,2,20,销 量,10,60,40,30,140,表,5,7,5,9,【,解,】,30,10,10,60,5.2,运输单纯形法,Transportation Simplex Method,20,10,到一组基可行解可用矩阵,表示，矩阵,X,中空白处对应的变量是非基变量，运量等于零，这组解就是初始调运方案总运费,Z,=360+810+520+130+210+910=500,【,例,5-4】,求表,5-10,给出的运输问题的初始基本可行解,B,1,B,2,B,3,B,4,a,i,A,1,4,10,4,4,20,A,2,7,7,3,8,15,A,3,1,2,10,6,15,b,j,5,10,25,10,50,表,5-10,5.2,运输单纯形法,Transportation Simplex Method,表,5-11,B,j,A,i,B,1,B,2,B,3,B,4,a,i,A,1,4,10,4,4,20,A,2,7,7,3,8,15,A,3,1,2,10,6,15,b,j,5,10,25,10,50,【,解,】,5,10,0,15,10,10,5.2,运输单纯形法,Transportation Simplex Method,初始基本可行解可用下列矩阵表示,5.2,运输单纯形法,Transportation Simplex Method,2,元素差额法（,Vogel,近似法）,最小元素法只考虑了局部运输费用最小。有时为了节省某一处的运费，而在其它处可能运费很大。元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案,前一种按最小元素法求得，总运费是,Z,1,=108+52+151=105后一种方案考虑到,C,11,与,C,21,之间的差额是,8,2=6,，先调运,x,21,，再是,x,22,，其次是,x,12,这时总运费,Z,2,=105+152+51=85,Z,1,。,5.2,运输单纯形法,Transportation Simplex Method,基于以上思路，元素差额法求初始基本可行解的步骤是：,第一步,：求出每行次小运价与最小运价之差，记为,u,i,，,i,=1,2,m,；同时求出每列次小运价与最小运价之差，记为,v,j,，,j,=1,，,2,，,，,n,；,第二步,：找出所有行、列差额的最大值，即,L,=max,u,i,，,v,i,，差额,L,对应行或列的最小运价处优先调运；,第三步,：这时必有一列或一行调运完毕，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，就得到一个初始调运方案。,用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。,5.2,运输单纯形法,Transportation Simplex Method,表,5-6,【,例,5-5】,用元素差额法求表,56,运输问题的初始基本可行解。,【,解,】,求行差额,u,i,i,=1,2,3,及列差额,v,j,j,=1,2,3,4.,计算公式为,u,i,=,i,行次小运价,i,行最小运价,v,j,=,j,列次小运价,j,例最小运价,5.2,运输单纯形法,Transportation Simplex Method,销 地,产地,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,9,7,2,3,6,10,8,5,9,4,1,2,70,50,20,销 量,10,60,40,30,140,表,512,B,j,A,i,B,1,B,2,B,3,B,4,a,i,u,i,A,1,9,3,8,4,70,1,A,2,7,6,5,1,50,4,A,3,2,10,9,2,20,7,b,j,10,60,40,30,140,v,j,5,3,3,1,【】,10,5.2,运输单纯形法,Transportation Simplex Method,表,5-13,10,5.2,运输单纯形法,Transportation Simplex Method,B,j,A,i,B,1,B,2,B,3,B,4,a,i,u,i,A,1,9,3,8,4,70,1,A,2,7,6,5,1,50,4,A,3,2,10,9,2,20,7,10,b,j,10,60,40,30,140,v,j,3,3,1,【】,5.2,运输单纯形法,Transportation Simplex Method,B,j,A,i,B,1,B,2,B,3,B,4,a,i,u,i,A,1,9,3,8,4,70,1,A,2,7,6,5,1,50,4,A,3,2,10,9,2,20,10,10,b,j,10,60,40,30,140,v,j,3,3,3,表,5-14,【】,20,表,5-15,【】,60,30,10,5.2,运输单纯形法,Transportation Simplex Method,B,j,A,i,B,1,B,2,B,3,B,4,a,i,u,i,A,1,9,3,8,4,70,5,A,2,7,6,5,1,50,1,20,A,3,2,10,9,2,20,10,10,b,j,10,60,40,30,140,v,j,3,3,基本可行解为,总运费,Z,=360+810,530+120+210+210=470,比最小元素法的总运费（,500,）要小,30,5.2,运输单纯形法,Transportation Simplex Method,3.,左上角法,。左上角法,(,亦称西北角法,),是优先从运价表的左上角的变量赋值，当行或列分配完毕后，再在表中余下部分的左上角赋值，依次类推，直到右下角元素分配完毕当出现同时分配完一行和一列时，仍然应在打“,”,的位置上选一个变量作基变量，以保证最后的基变量数等于,m,+,n,1,【,例,5-6】,用左上角法求例,5-3,中表,5-6,的初始基本可行解,表,5-16,10,60,0,10,20,5.2,运输单纯形法,Transportation Simplex Method,B,j,A,i,B,1,B,2,B,3,B,4,产 量,A,1,9,3,8,4,70,A,2,7,6,5,1,50,A,3,2,10,9,2,20,销 量,10,60,40,30,40,基本可行解为,用左上角法求得的基本可行解对应的目标函数值（总运费）是,Z,910,360,80,540,110+220=520,求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记,x,ij,的检验数为,ij,由第一章知，求最小值的运输问题的最优判别准则是：,所有非基变量的检验数都非负，则运输方案最优（即为最优解）。,求检验数的方法有两种，闭回路法和位势法。,1,闭回路法求检验数,求某一非基变量的检验数的方法是：在单位运价表中，以该非基变量为起点，以基变量为其它顶点，找一条闭回路，由起点开始，分别在顶点上交替标上代数符号,+,、,-,、,+,、,-,、,，以这些符号分别乘以相应的运价，其代数和就是这个非基变量的检验数。,5.2,运输单纯形法,Transportation Simplex Method,5.2.2,求检验数,【,解,】,用最小元素法 求得的初始基可行解,【,例,5-7】,用闭回路法求例,5,3,表,5,9,的检验数。,5.2,运输单纯形法,Transportation Simplex Method,B,j,A,i,B,1,B,2,B,3,B,4,产 量,A,1,9,3,8,4,70,A,2,7,6,5,1,50,A,3,2,10,9,2,20,销 量,1060,40,30,140,30,10,10,60,20,10,矩阵中打“,”,的位置是非基变量，其余是基变量，这里只求非基变量的检验数。,求,11,，先找出,x,11,的闭回路 ，对应的运价为,再用正负号分别交替乘以运价有,直接求代数和得,5.2,运输单纯形法,Transportation Simplex Method,B,j,A,i,B,1,B,2,B,3,B,4,a,i,A,1,9,3,8,4,70,8(+),60,10(-),0,A,2,7,6,5,1,50,9,6,20,30,A,3,2,10,9,2,20,10(-),6,10(+),-3,b,j,10,60,40,30,5.2,运输单纯形法,Transportation Simplex Method,同理可求出其它非基变量的检验数：,这里,34,0,，说明这组基本可行解不是最优解。,只要求得的基变量是正确的且数目为,m,+,n,1,，则某个非基变量的闭回路存在且唯一，因而检验数唯一。,5.2,运输单纯形法,Transportation Simplex Method,2,位势法求检验,位势法求检验数是根据对偶理论推导出来的一种方法。,设平衡运输问题为,设前,m,个约束对应的对偶变量为,u,i,i,=1,2,m,，后,n,个约束对应的对偶变量为,v,j,j,=1,2,n,则运输问题的对偶问题是,5.2,运输单纯形法,Transportation Simplex Method,加入松驰变量,ij,将约束化为等式,u,i,+v,j,+,ij,=,c,ij,记原问题基变量,X,B,的下标集合为,I,，由第二章对偶性质知，原问题,x,ij,的检验数是对偶问题的松弛变量,ij,，,当（,i,，,j,）,I,时,ij,=0,，因而有,解上面第一个方程，将,u,i,、,v,j,代入第二个方程求出,ij,5.2,运输单纯形法,Transportation Simplex Method,【,例,5-8】,用位势法求例,5-3,表,5,9,给出的初始基本可行解的检验数。,【,解,】,第一步求位势,u,1,、,u,2,、,u,3,及v,1,、,v,2,、,v,3,、,v,4,。,10 60 40 30,令,u,1,=0,得到位势的解为,5.2,运输单纯形法,Transportation Simplex Method,再由公式 求出检验数，其中,C,ij,是非基变量对应的运价。,计算结果与例,5-7,结果相同。,5.2,运输单纯形法,Transportation Simplex Method,销地,产地,B1,B2,B3,B4,产量,ui,A1,9,8,3,60,8,10,4,0,70,0,A2,7,9,6,6,5,20,1,30,50,-3,A3,2,10,10,6,9,10,2,-3,9,1,销量,10,60,40,30,140(,产销平衡,vj,1,3,8,4,5.2.3,调整运量,前面讲过，当某个检验数小于零时，基可行解不是最优解，总运费还可以下降，这时需调整运输量，改进原运输方案，使总运费减少，改进运输方案的步骤是：,第一步：确定进基变量,第二步：确定出基变量,在进基变量,x,ik,的闭回路中，标有负号的最小运量作为调整量,，,对应的基变量为出基变量，并打上“,”,以示作为非基变量。,第三步：调整运量,在进基变量的闭回路中标有正号的变量加上调整量,，标有负号的变量减去调整量,，其余变量不变，得到一组新的基可行解，然后求所有非基变量的检验数重新检验。,5.2,运输单纯形法,Transportation Simplex Method,销地,产地,B1,B2,B3,B4,产量,ui,A1,9,8,3,60,8,10,4,0,70,0,A2,7,9,6,6,5,20(+),1,30(-),50,-3,A3,2,10,10,6,9,10(-),2,-3(+),9,1,销量,10,60,40,30,140(,产销平衡,vj,1,3,8,4,因为有一个检验数小于零，所以这组基本可行解不是最优解。对应的非基变量,x,34,进基,.,x,34,的闭回路是,x,33,最小，,x,33,是出基量，调整量,=10,5.2,运输单纯形法,Transportation Simplex Method,在,x,34,的闭回路上,x,34,、,x,23,分别加上,10,，,x,33,、,x,24,分别减去,10,，其余变量不变，调整后得到一组新的基可行解：,销地,产地,B1,B2,B3,B4,产量,ui,A1,9,5,3,60,8,10,4,0,70,0,A2,7,6,6,6,5,30,1,20,50,-3,A3,2,10,10,9,9,3,2,10,9,-2,销量,10,60,40,30,140(,产销平衡,vj,4,3,8,4,非基变量的检验数：,11,=5,，,14,=0,，,21,=6,，,22,=6,，,32,=9,，,33,=3,所有检验数,ij,0,因而得到最优解,最小运费,5.2,运输单纯形法Transportation Simplex Method,销地,产地,B1,B2,B3,B4,产量,ui,A1,9,5,3,60,8,10(-),4,0(+),70,0,A2,7,6,6,6,5,30(+),1,20(-),50,-3,A3,2,10,10,9,9,3,2,10,9,-2,销量,10,60,40,30,140(,产销平衡,vj,4,3,8,4,销地,产地,B1,B2,B3,B4,产量,ui,A1,9,5,3,60,8,0,4,10,70,0,A2,7,6,6,6,5,40,1,10,50,-3,A3,2,10,10,9,9,3,2,10,9,-2,销量,10,60,40,30,140(,产销平衡,vj,4,3,8,4,B,j,A,i,B,1,B,2,B,3,B,4,a,i,A,1,5,8,9,2,70,40,30,A,2,3,6,4,7,80,45,35,A,3,10,12,14,5,40,25,15,b,j,45,65,50,30,190,【,例,5-9】,求下列运输问题的最优解,表,5-19,5.2,运输单纯形法,Transportation Simplex Method,【,解,】,用最小元素法求得初始基本可行解如表,5-19,Bj,Ai,B1,B2,B3,B4,ai,ui,A1,5,-4(+),8,40(-),9,-1,2,30,70,0,A2,3,45),6,4,4,35(+),7,11,80,-6,A3,10,-3,12,25(+),14,15(-),5,-1,40,4,bj,45,65,50,30,190(,产销平衡,vj,9,8,10,2,因为有,4,个检验数小于零，所以这组基本可行解不是最优解。对应的非基变量,x,11,进基,.,对应的非基变量,x,11,进基,.,x,11,的闭回路是,x,33,最小，,x,33,是出基量，调整量,=15,5.2,运输单纯形法,Transportation Simplex Method,在,x,11,的闭回路上,x,11,、,x,32,、,x,23,分别加上,15,，,x,12,、,x,33,、x,21,分别减去,15,，并且在,x,33,处打上记号“,”,作为基变量，其余变量不变，调整后得到一组新的基可行解：,Bj,Ai,B1,B2,B3,B4,ai,ui,A1,5,15,8,25(+),9,3,2,30,(-),70,0,A2,3,30,6,0,4,50,7,7,80,-2,A3,10,1,12,40(-),14,4,5,-1(+),40,4,bj,45,65,50,30,190(,产销平衡,vj,5,8,6,2,Bj,Ai,B1,B2,B3,B4,ai,ui,A1,5,15,8,55,9,3,2,1,70,0,A2,3,30,6,0,4,50,7,8,80,-2,A3,10,1,12,10,14,4,5,30,40,4,bj,45,65,50,30,190(,产销平衡,vj,5,8,6,1,非基变量的检验数：,13,=3,，,14,=1,，,22,=0,，,24,=8,，,31,=1,，,33,=4,所有检验数,ij,0,因而得到最优解,最小运费,5.2,运输单纯形法,Transportation Simplex Method,【,例,5-10】,有四项工作指派给甲、乙两人完成，每人完成两项工作两人完成各项工作的时间（小时）见表,5-18,，怎样安排工作使总时间最少,A,B,C,D,甲,15,20,9,10,乙,12,16,10,12,表,5-18,【,解,】,设x,ij,(,i,=1,2,；,j,=1,2,3,4),为第,i,人完成第,j,项工作的状态,数学模型为,5.2,运输单纯形法,Transportation Simplex Method,写出表,5-18,的平衡运输表,5-19,用运输单纯形法求解得到最优表,5-20,A,B,C,D,产量,甲,15,20,9,10,2,乙,12,16,10,12,2,销量,1,1,1,1,A,B,C,D,产量,甲,0,0,1,1,2,乙,1,1,0,0,2,销量,1,1,1,1,表,5-19,表,5-20,最优的工作分配是：甲完成工作,C,和,D,，乙完成工作,A,和,B,，总时间,Z,47,（小时）,5.2,运输单纯形法,Transportation Simplex Method,设数学模型为,5.2.4,最大值问题,5.2,运输单纯形法,Transportation Simplex Method,第一种方法：将极大化问题转化为极小化问题。设极大化问题的运价表为,C,=,（,C,ij,）,mn,，用一个较大的数,M,（,M,max,C,ij,）去减每一个,C,ij,得到矩阵,C,=,（,C,ij,）,m,n,，其中,C,/,ij,=,M,C,ij,0,将,C,/,作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为,例如，下列矩阵,C,是,A,i,（,I=1,，,2,，,3,）到,B,j,的单位货物利润,运输部门如何安排运输方案使总利润最大,.,8 14 9,5.2,运输单纯形法,Transportation Simplex Method,用最小元素法求初始方案得,11,=8,12,=4,21,=2,23,=2,全部非负,得到最优运输方案,X,最大利润,Z=89+1010+68+54=240,第二种方法,:,所有非基变量的检验数,ij,0,时最优,.,求初始运输方案可采用最大元素法,.,如上例,用最大元素得到 的初始运输方案,:,8 14 9,求检验数,:,11,=,8,12,=,4,21,=,2,23,=,2,全部非正,得到最优解运输方案,结果与第一种方法相同,.,5.2运输单纯形法,Transportation Simplex Method,当总产量与总销量不相等时,称为不平衡运输问题,.,这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。,1.,当产大于销时,即,数学模型为,5.2.5,不平衡运输问题,5.2,运输单纯形法,Transportation Simplex Method,由于总产量大于总销量，必有部分产地的产量不能全部,运送完，必须就地库存，即每个产地设一个仓库，库存量,为,x,i,，,n+,1,（,i,=1,，,2,，,，,m,），总的库存量为,5.2,运输单纯形法,Transportation Simplex Method,b,n+,1,作为一个虚设的销地,B,n,+1,的销量。各产地,A,i,到,B,n,+1,的运价为零，即,C,i,，,n,+1,=0,（,i=,1,，,，,m,）。则平衡问题的数学模型为：,具体求解时,只在运价表右端增加一列,B,n,+1,，运价为零,销量为,b,n,+1,即可,5.2,运输单纯形法,Transportation Simplex Method,2.,当销大于产时,即,数学模型为,5.2,运输单纯形法,Transportation Simplex Method,由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地,A,m,+,1,，产量为,x,m,+1,j,是,A,m,+1,运到,B,j,的运量，也是,B,j,不能满足需要的数量。,A,m,+1,到,B,j,的运价为零,即,C,m,+1,j,=0(,j,=1,2,n,),5.2,运输单纯形法,Transportation Simplex Method,销大于产平衡问题的数学模型为,：,具体计算时，在运价表的下方增加一行,A,m,+1,，运价为零。产量为,a,m+1,即可。,5.2,运输单纯形法,Transportation Simplex Method,B1,B2,B3,B4,a,i,A1,5,9,2,3,60,A2,-,4,7,8,40,A3,3,6,4,2,30,A4,4,8,10,11,50,b,j,20,60,35,45,180,160,因为有,：,【,例,5-11】,求下列表中极小化运输问题的最优解。,所以是一个产大于销的运输问题。,5.2,运输单纯形法,Transportation Simplex Method,表,5-21,表中,A,2,不可达,B,1,，用一个很大的正数,M,表示运价,C,21,。虚设一个销量为,b,5,=180,160=20,的销地,B,5,，,C,i,5,=0,，,i,=1,，,2,，,3,，,4,。表的右边增添一列,这样可得新的运价表：,B1,B2,B3,B4,B5,a,i,A1,5,9,2,3,0,60,A2,M,4,7,8,0,40,A3,3,6,4,2,0,30,A4,4,8,10,11,0,50,b,j,20,60,35,45,20,180,5.2,运输单纯形法,Transportation Simplex Method,B1,B2,B3,B4,B5,Ai,A1,35,25,60,A2,40,40,A3,10,20,30,A4,20,10,20,50,Bj,20,60,35,45,20,180,下表为计算结果。可看出：产地,A4,还有,20,个单位没有运出。,5.2,运输单纯形法,Transportation Simplex Method,【,例,5-12】,在例,5-11,中，假定,B,1,的需要量是,20,到,60,之间，,B,2,的需要量是,50,到,70,，试求极小化问题的最优解。,B1,B2,B3,B4,a,i,A1,5,9,2,3,60,A2,-,4,7,8,40,A3,3,6,4,2,30,A4,4,8,10,11,50,b,j,20,60,50,70,35,45,180,150,210,5.2.6,需求量不确定的运输问题,5.2,运输单纯形法,Transportation Simplex Method,先作如下分析：（,1,）总产量为,180,，,B,1,，,，,B,4,的最低需求量,20+50+35+45=150,，这时属产大于销；,（,2,）,B,1,，,，,B,4,的最高需求是,60+70+35+45=210,，这时属销大于产,（,3,）虚设一个产地,A,5,，产量是,210,180=30,，,A,5,的产量只能供应,B,1,或,B,2,。,（,4,）将,B,1,与,B,2,各分成两部分 的需求量是,20,，的需求量是,40,，的需求量分别是,50,与,20,，因此,必须由,A,1,，,，,A,4,供应，可由,A,1,、,、,A,5,供应。,（,5,）上述,A,5,不能供应某需求地的运价用大,M,表示，,A,5,到 、的运价为零。得到下表的产销平衡表。,5.2,运输单纯形法,Transportation Simplex Method,B,3,B,4,a,i,A1,5,59,9,2,3,60,A2,M,M,4,4,7,8,40,A3,3,3,6,6,4,2,30,A4,4,4,8,8,10,11,50,A5,M,0,M,0,M,M,30,b,j,20,40,50,20,35,45,210,得到这样的平衡表后，计算得到最优方案表,5-23,。,5.2,运输单纯形法,Transportation Simplex Method,表,5-22,B,3,B,4,a,i,A,1,35,25,60,A,2,40,40,A,3,0,10,20,30,A,4,20,30,50,A,5,10,20,30,b,j,20,40,50,20,35,45,210,表中：,x,1,31,0,是基变量,说明这组解是退化基本可行解,空格处的变量是非基变量。,B,1,，,B,2,，,B,3,，,B,4,实际收到产品数量分别是,50,，,50,，,35,和,45,个单位。,5.2,运输单纯形法,Transportation Simplex Method,表,5-23,5.2.7,中转问题,产地,销地,A,1,20,A,2,30,A,3,50,A,9,20,A,8,15,A,7,20,A,6,45,3,5,4,2,3,1,6,8,2,3,2,9,图,5.2,A,4,A,5,2,2,7,15,中转地,3,4,1,3,5.2,运输单纯形法,Transportation Simplex Method,A1,A2,A3,A4,A5,A6,A7,A8,A9,ai,A1,0,M,M,2,5,3,2,M,M,120,A2,M,0,1,4,2,M,M,M,M,130,A3,M,M,0,8,7,M,M,M,15,150,A4,M,3,M,0,3,4,3,6,M,100,A5,M,M,M,M,0,M,1,2,9,100,A6,M,M,M,M,M,0,2,M,M,100,A7,M,M,M,M,M,M,0,M,M,100,A8,M,M,M,M,M,M,M,0,3,100,A9,M,M,M,M,M,M,M,M,0,100,bj,100,100,100,100,100,145,120,115,120设,x,ij,为,A,i,到,A,j,的运量，,i,，,j,=1,，,2,，,，,m+n+r,则中转运输问题的数学模型为,产大于销时将式,(5-3,a,),改为“”约束，销大于产时将式,(5-3,c,),改为“”约束,5.2,运输单纯形法,Transportation Simplex Method,5.4,指派问题,assignment problem,5.4.1,问题的提出与数学模型,指派问题也称分配问题,是一种特殊的整数规划问题,是,0-1,整数线性规划问题,.,在生活中经常会遇到这样的问题,某单位需要指派,m,个人去完成,m,项任务,每个人只做一工作,同时,每项工作只由一个人完成,.,由于各人的专长不同,每个人完成各项任务的效率也不同,.,于是产生了应指派哪一个人去完成哪一项任务,使完成项任务的总效率最高,(,如所用的时间为最少,),的问题,.,这类问题为指派问题或分配问题,.,5.4,指派问题,assignment problem,【,例,5-15】,人事部门欲安排四人到四个不同的岗位工作，每个岗位一个人经考核四人在不同岗位的成绩（百分制）如表,5-28,所示，如何安排他们的工作使总成绩最好。类似的有,m,项加工任务，怎样指派到,m,台机床上分别完成的问题；,m,条航线，怎样指定,m,艘船去航行的问题等,.,表,5-28,工作,人员,A,B,C,D,甲,85,92,73,90,乙,95,87,78,95,丙,82,83,79,90,丁,86,90,80,88,数学模型为：,甲,乙,丙,丁,A,B,C,D,图,5.3,5.4,指派问题,assignment problem,【,例,5-15】,某汽车公司拟将四种新产品配置到四个工厂生产，四个工厂的单位产品成本（元,/,件）如表,5-29,所示求最优生产配置方案,表,5-29,产品,1,产品,2,产品,3,产品,4,工厂,1,58,69,180,260,工厂,2,75,50,150,230,工厂,3,65,70,170,250,工厂,4,82,55,200,280,【,解,】,问题求最小值。,第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有,5.4,指派问题,assignment problem,第二步,：找出矩阵每列的最小元素，再分别从每列中减去，有,5.4,指派问题,assignment problem,第六步,:,回到第三步,反复进行,一直到找到了最优分配方案,.,得到两个最优解,有两个最优方案,第一种方案,：第一个工厂加工产品,1,，第二工厂加工产品,3,，第三个工厂加工产品,4,，第四个工厂加工产品,2,；,第二种方案,：第一个工厂加工产品,1,，第二工厂加工产品,4,，第三个工厂加工产品,3,，第四个工厂加工产品,2,；,单件产品总成本,Z,58,150,250,55,513,5.4,指派问题,assignment problem,B1,B2,B3,B4,B5,A1,4,8,7,15,12,A2,7,9,17,14,10,A3,6,9,12,8,7,A4,6,7,14,6,10,A5,6,9,12,10,6,本题的最优解,最优分配方案为,:,让,A1,承建,B3,A2,承建,B2,A3,承建,B1,A4,承建,B4,A5,承建,B5.,这样安排能使总的建造费用最少,为,7+9+6+6+6=34(,万,),5.4.3,其它变异问题,【,例,5-17】,求例,5-14,的最优分配方案,【,解,】,则,求此问题的最小值求解过程如下,最优分配方案是,：甲分配到,B,岗位