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

,运筹学 Operations Research,Chapter 5 运输与指派问题 Transportation and 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 数学模型,产地,销地,A1 10,A2 8,B4 3,3,5,4,2,3,1,6,8,2,3,2,9,图5.1,【例5-1】现有A1，A2，A3三个产粮区，可供应 粮食分别为10，8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元/吨）如表5-1所示，问如何安排一个运输计划，使总的运输费用最少。,运价表（元/吨）,表5-1,5.1 运输模型 Model of Transportation Problems,设xij(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种零件的需要量为bj (j=1,2,3)，第i台机床加工第j种零件需要的时间为cij ，如表52所示。问如何安排生产任务使总的加工时间最少？,表52,5.1 运输模型 Model of Transportation Problems,【解】 设 xi j (i=1,2,3；j=1,2,3,)为第i台机床加工第j种零件的数量，则此问题的数学模型为,5.1 运输模型 Model of Transportation Problems,5.1.2 模型特征 运输问题的一般数学模型,设有m个产地（记作A1，A2，A3,Am），生产某种物资，其产量分别为a1,a2，am；有n个销地（记作B1，B2，Bn），其需要量分别为b1,b2，bn；且产销平衡，即 。从第i个产地到j 个销地的单位运价为cij ，在满足各地需要的前提下，求总运输费用最小的调运方案。,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+n1个基变量,因为产销平衡,所以模型最多只有m+n-1个独立约束方程,即系数矩阵的秩最多为m+n-1.,5.2 运输单纯形法 Transportation Simplex Method,设平衡运输问题的数学模型为：,5.2 运输单纯形法 Transportation Simplex Method,运输单纯形法也称为表上作业法，是直接在运价表上求最优解的一种方法，它的步骤是：,第一步：求初始基本可行解（初始调运方案）。 常用的方法有最小元素法、元素差额法（Vogel近似法）、左上角法。,第二步：求检验数并判断是否得到最优解。常用求检验的方法有闭回路法和位势法，当非基变量的检验数ij全都非负时得到最优解，若存在检验数lk0，说明还没有达到最优，转第三步。,第三步：调整运量，即换基。选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步。,5.2 运输单纯形法 Transportation Simplex Method,5.2.1初始基可行解,1. 最小元素法 最小元素法的思想是就近优先运送，即最小运价Cij对应的变量xij优先赋值 然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后得到一个初始基可行解。,5.2 运输单纯形法 Transportation Simplex Method,【例5-3】求表56所示的运输问题的初始基可行解。,表56,5.2 运输单纯形法 Transportation Simplex Method,表5759,【解】,30,10,10,60,5.2 运输单纯形法 Transportation Simplex Method,20,10,到一组基可行解可用矩阵,表示，矩阵X 中空白处对应的变量是非基变量，运量等于零，这组解就是初始调运方案总运费 Z=360+810+520+130+210+910=500,【例5-4】求表5-10给出的运输问题的初始基本可行解,表5-10,5.2 运输单纯形法 Transportation Simplex Method,表5-11,【解】,5,10,0,15,10,10,5.2 运输单纯形法 Transportation Simplex Method,初始基本可行解可用下列矩阵表示,5.2 运输单纯形法 Transportation Simplex Method,2元素差额法（Vogel近似法）最小元素法只考虑了局部运输费用最小。有时为了节省某一处的运费，而在其它处可能运费很大。元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案,前一种按最小元素法求得，总运费是 Z1=108+52+151=105 后一种方案考虑到C11与C21之间的差额是82=6，先调运x21，再是x22，其次是x12这时总运费 Z2=105+152+51=85Z1。,5.2 运输单纯形法 Transportation Simplex Method,基于以上思路，元素差额法求初始基本可行解的步骤是：,第一步：求出每行次小运价与最小运价之差，记为ui，i=1,2,m ；同时求出每列次小运价与最小运价之差，记为vj，j=1，2，n ；,第二步：找出所有行、列差额的最大值，即L=maxui，vi，差额L对应行或列的最小运价处优先调运；,第三步：这时必有一列或一行调运完毕，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，就得到一个初始调运方案。,用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。,5.2 运输单纯形法 Transportation Simplex Method,表5-6,【例5-5】用元素差额法求表56运输问题的初始基本可行解。,【解】 求行差额 ui, i=1,2,3及列差额vj,j=1,2,3,4.计算公式为 ui= i行次小运价i行最小运价 vj= j列次小运价j例最小运价,5.2 运输单纯形法 Transportation Simplex Method,表512,【 】,10,5.2 运输单纯形法 Transportation Simplex Method,表5-13,10,5.2 运输单纯形法 Transportation Simplex Method,【 】,5.2 运输单纯形法 Transportation Simplex Method,表5-14,【 】,20,表5-15,【 】,60,30,10,5.2 运输单纯形法 Transportation Simplex Method,基本可行解为,总运费Z=360+810530+120+210+210=470 比最小元素法的总运费（500）要小30,5.2 运输单纯形法 Transportation Simplex Method,3. 左上角法。左上角法(亦称西北角法)是优先从运价表的左上角的变量赋值，当行或列分配完毕后，再在表中余下部分的左上角赋值，依次类推，直到右下角元素分配完毕当出现同时分配完一行和一列时，仍然应在打“”的位置上选一个变量作基变量，以保证最后的基变量数等于m+n1,【例5-6】用左上角法求例5-3中表5-6的初始基本可行解,表5-16,10,60,0,10,20,5.2 运输单纯形法 Transportation Simplex Method,40,基本可行解为,用左上角法求得的基本可行解对应的目标函数值（总运费）是 Z91036080540110+220=520,求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记xij的检验数为ij由第一章知，求最小值的运输问题的最优判别准则是：,所有非基变量的检验数都非负，则运输方案最优（即为最优解）。,求检验数的方法有两种，闭回路法和位势法。,1闭回路法求检验数 求某一非基变量的检验数的方法是：在单位运价表中，以该非基变量为起点，以基变量为其它顶点，找一条闭回路，由起点开始，分别在顶点上交替标上代数符号+、-、+、-、，以这些符号分别乘以相应的运价，其代数和就是这个非基变量的检验数。,5.2 运输单纯形法 Transportation Simplex Method,5.2.2求检验数,【解】用最小元素法 求得的初始基可行解,【例5-7】用闭回路法求例53表59的检验数。,5.2 运输单纯形法 Transportation Simplex Method,30,10,10,60,20,10,矩阵中打“”的位置是非基变量，其余是基变量，这里只求非基变量的检验数。,求11，先找出x11的闭回路 ，对应的运价为 再用正负号分别交替乘以运价有 直接求代数和得,5.2 运输单纯形法 Transportation Simplex Method,5.2 运输单纯形法 Transportation Simplex Method,同理可求出其它非基变量的检验数：,这里340，说明这组基本可行解不是最优解。,只要求得的基变量是正确的且数目为m+n1，则某个非基变量的闭回路存在且唯一，因而检验数唯一。,5.2 运输单纯形法 Transportation Simplex Method,2位势法求检验 位势法求检验数是根据对偶理论推导出来的一种方法。,设平衡运输问题为,设前m个约束对应的对偶变量为ui,i=1,2,m，后n个约束对应的对偶变量为vj,j=1,2,n则运输问题的对偶问题是,5.2 运输单纯形法 Transportation Simplex Method,加入松驰变量ij将约束化为等式,ui+vj+ij=cij,记原问题基变量XB的下标集合为I，由第二章对偶性质知，原问题xij的检验数是对偶问题的松弛变量ij，当（i，j）I 时ij=0，因而有,解上面第一个方程，将ui、vj代入第二个方程求出ij,5.2 运输单纯形法 Transportation Simplex Method,【例5-8】用位势法求例5-3表59给出的初始基本可行解的检验数。,【解】第一步求位势u1、u2、u3及v1、v2、v3、v4。,10 60 40 30,令u1=0得到位势的解为,5.2 运输单纯形法 Transportation Simplex Method,再由公式 求出检验数，其中Cij是非基变量对应的运价。,计算结果与例5-7结果相同。,5.2 运输单纯形法 Transportation Simplex Method,5.2.3调整运量,前面讲过，当某个检验数小于零时，基可行解不是最优解，总运费还可以下降，这时需调整运输量，改进原运输方案，使总运费减少，改进运输方案的步骤是：,第一步：确定进基变量,第二步：确定出基变量 在进基变量xik的闭回路中，标有负号的最小运量作为调整量，对应的基变量为出基变量，并打上“”以示作为非基变量。,第三步：调整运量 在进基变量的闭回路中标有正号的变量加上调整量，标有负号的变量减去调整量，其余变量不变，得到一组新的基可行解，然后求所有非基变量的检验数重新检验。,5.2 运输单纯形法 Transportation Simplex Method,因为有一个检验数小于零，所以这组基本可行解不是最优解。对应的非基变量x34进基.,x34的闭回路是,x33最小，x33是出基量，调整量=10,5.2 运输单纯形法 Transportation Simplex Method,在x34的闭回路上x34、x23分别加上10，x33、x24分别减去10，其余变量不变，调整后得到一组新的基可行解：,非基变量的检验数：,11=5，14=0，21=6，22=6，32=9，33=3,所有检验数ij 0因而得到最优解,最小运费,5.2 运输单纯形法 Transportation Simplex Method,【例5-9】求下列运输问题的最优解,表5-19,5.2 运输单纯形法 Transportation Simplex Method,【解】 用最小元素法求得初始基本可行解如表5-19,因为有4个检验数小于零，所以这组基本可行解不是最优解。对应的非基变量x11进基.,对应的非基变量x11进基.,x11的闭回路是,x33最小，x33是出基量，调整量=15,5.2 运输单纯形法 Transportation Simplex Method,在x11的闭回路上x11、x32、x23分别加上15，x12、x33、x21分别减去15，并且在x33处打上记号“”作为基变量，其余变量不变，调整后得到一组新的基可行解：,非基变量的检验数：,13=3，14=1，22=0，24=8，31=1，33=4,所有检验数ij 0因而得到最优解,最小运费,5.2 运输单纯形法 Transportation Simplex Method,【例5-10】有四项工作指派给甲、乙两人完成，每人完成两项工作两人完成各项工作的时间（小时）见表5-18，怎样安排工作使总时间最少,表5-18,【解】 设xij(i=1,2；j=1,2,3,4)为第i人完成第j项工作的状态,数学模型为,5.2 运输单纯形法 Transportation Simplex Method,写出表5-18的平衡运输表5-19, 用运输单纯形法求解得到最优表5-20,表5-19,表5-20,最优的工作分配是：甲完成工作C和D，乙完成工作A和B，总时间Z47（小时）,5.2 运输单纯形法 Transportation Simplex Method,设数学模型为,5.2.4 最大值问题,5.2 运输单纯形法 Transportation Simplex Method,第一种方法：将极大化问题转化为极小化问题。设极大化问题的运价表为C=（Cij）mn，用一个较大的数M（MmaxCij）去减每一个Cij得到矩阵C=（Cij）mn ，其中C/ij=MCij0,将C/作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为,例如，下列矩阵C是Ai（I=1，2，3）到Bj的单位货物利润,运输部门如何安排运输方案使总利润最大.,8 14 9,5.2 运输单纯形法 Transportation Simplex Method,用最小元素法求初始方案得,11=8,12=4,21=2,23=2全部非负,得到最优运输方案X,最大利润Z=89+1010+68+54=240,第二种方法:所有非基变量的检验数ij0时最优.求初始运输方案可采用最大元素法.如上例,用最大元素得到 的初始运输方案:,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,由于总产量大于总销量，必有部分产地的产量不能全部 运送完，必须就地库存，即每个产地设一个仓库，库存量 为xi，n+1（i=1，2，m），总的库存量为,5.2 运输单纯形法 Transportation Simplex Method,bn+1作为一个虚设的销地Bn+1的销量。各产地Ai到Bn+1的运价为零，即Ci，n+1=0,（i=1，m）。则平衡问题的数学模型为：,具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可,5.2 运输单纯形法 Transportation Simplex Method,2.当销大于产时,即,数学模型为,5.2 运输单纯形法 Transportation Simplex Method,由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为,xm+1,j 是Am+1运到Bj的运量，也是Bj不能满足需要的数量。Am+1到Bj的运价为零,即Cm+1,j=0(j=1,2, ,n),5.2 运输单纯形法 Transportation Simplex Method,销大于产平衡问题的数学模型为 ：,具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。,5.2 运输单纯形法 Transportation Simplex Method,因为有：,【例5-11】求下列表中极小化运输问题的最优解。,所以是一个产大于销的运输问题。,5.2 运输单纯形法 Transportation Simplex Method,表5-21,表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180160=20的销地B5，Ci5=0，i=1，2，3，4。表的右边增添一列,这样可得新的运价表：,5.2 运输单纯形法 Transportation Simplex Method,下表为计算结果。可看出：产地A4还有20个单位没有运出。,5.2 运输单纯形法 Transportation Simplex Method,【例5-12】在例5-11中，假定B1的需要量是20到60之间，B2的需要量是50到70，试求极小化问题的最优解。,5.2.6 需求量不确定的运输问题,5.2 运输单纯形法 Transportation Simplex Method,先作如下分析： （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.2 运输单纯形法 Transportation Simplex Method,得到这样的平衡表后，计算得到最优方案表5-23。,5.2 运输单纯形法 Transportation Simplex Method,表5-22,表中：x131=0是基变量,说明这组解是退化基本可行解,空格处的变量是非基变量。B1，B2，B3，B4实际收到产品数量分别是50，50，35和45个单位。,5.2 运输单纯形法 Transportation Simplex Method,表5-23,5.2.7 中转问题,产地,销地,3,5,4,2,3,1,6,8,2,3,2,9,图5.2,A4,A5,2,2,7,15,中转地,3,4,1,3,5.2 运输单纯形法 Transportation Simplex Method,设xij为Ai到Aj的运量，i，j=1，2，m+n+r则中转运输问题的数学模型为,产大于销时将式(5-3a)改为“”约束，销大于产时将式(5-3c)改为“”约束,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艘船去航行的问题等.,数学模型为：,甲,乙,丙,丁,A,B,C,D,图5. 3,5.4 指派问题 assignment