单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,OR,课件,回 顾,到目前为止，针对规划问题所建立的算法有一个共同的特征：,但是：,在决策的实践中，有些问题约束条件存在一定的,特殊性,，按常规办法,有可能,出现严重退化而导致问题,无法顺利求解,。如：运输问题、指派问题等。,从约束条件入手,OR课件 回 顾到目前为止，针对规,OR,课件,运 筹 帷 幄 之 中,决 胜 千 里 之 外,运输问题与指派问题,第五章,Transportation Problem,IP,& Assignment Problem,AP,OR课件运 筹 帷 幄 之 中决 胜 千 里,OR,课件,运输问题与指派问题,运输问题和指派问题是一种,特殊,的,LP,问题，要求,了解,两问题的基本特征；,掌握,两问题的求解算法原理及计算过程；,学会,对它们的特殊形式的处理。,本章的要求,TP & AP,OR课件运输问题与指派问题 运输问题和指派问题是,OR,课件,运输问题与指派问题,重点,本章重点与难点,难点,TP & AP,运输与指派问题模型及其特征,算法原理,特殊问题的处理,两算法的思想及其实现,OR课件运输问题与指派问题重点本章重点与难点难点TP & A,OR,课件,运输问题与指派问题,运输问题,主要内容,指派问题,TP & AP,运输问题及其数学模型,求解方法,表上作业法,特殊运输问题的求解,指派问题及其数学模型,求解方法匈牙利法,特殊指派问题的求解,OR课件运输问题与指派问题运输问题主要内容指派问题TP &,OR,课件,运输问题,运输问题及其数学模型,TP & AP,设某种物资有,m,个产地：,A,1,A,2,A,m,；,产量分别为：,a,1,a,2,a,m,个单位；,n,个销地：,B,1,B,2,B,n,；,销量分别为：,b,1,b,2,b,n,个单位；,假设产销总量是平衡的，即,单位运价：,A,i,B,j,：c,ij,问：,如何调运,这种物资才能使,总的运费最小,？,OR课件运输问题运输问题及其数学模型TP & AP,OR,课件,运输问题,单位运价表与平衡表（合表）,TP & AP,单位运价,产销量（平衡）,OR课件运输问题单位运价表与平衡表（合表）TP & AP单位,OR,课件,运输问题,模型,TP & AP,设：,x,ij,为,A,i,B,j,的运量,OR课件运输问题模型TP & AP设：xij为AiBj的运,OR,课件,运输问题,表上作业法,TP & AP,【简例】已知有关资料如下表,算法的提出,：观测模型的特征,要求建立总运费最小的模型。,OR课件运输问题表上作业法TP & AP【简例】已知有关资料,OR,课件,运输问题,模型,TP & AP,约束条件个数为,m+n，,但只有,m+n-1,个是线性无关,元素只有0和1，每列只有两个1,OR课件运输问题模型TP & AP约束条件个数为 m+n，但,OR,课件,表上作业法,算法思想,TP & AP,与,单纯形法,一样，最优解在基本可行解中产生。但基于,模型的特征,，初始基本可行解是通过分析,单位运价表,，首先满足局部最优，然后通过,调整,（迭代）使,整体达到最优,。,平衡表,OR课件表上作业法算法思想TP & AP 与单,OR,课件,表上作业法,步骤,算法步骤及要点,TP & AP,初始调运方案,检验数,ij,0 ?,Y,最优解,N,调整：找到新的调运方案,特征,：解变量（基变量）个数为,m+n-1；,以解变量为顶点不构成,折现闭回路,。,方法,：,最小元素法,、,差值法,方法：,闭回路法,、,位势法,方法：,闭回路法,OR课件表上作业法 步骤算法步骤及要点TP & AP初始,OR,课件,表上作业法,初始方案,折现闭回路：,TP & AP,顶点:,x,11,x,12,x,32,x,31,顶点：,x,12,x,13,x,33,x,34,x,24,x,22,定理：以,m+n-1,个变量构成的基本可行解的充要条件是它不含折现闭回路。,OR课件表上作业法初始方案折现闭回路：TP & AP顶点:,OR,课件,表上作业法,初始方案,最小元素法,TP & AP,基本思想：“,就近供应,”或称“,就廉供应,”,3,4,2,3,4,5,Z=139543247422100,OR课件表上作业法初始方案最小元素法TP & AP基本思想,OR,课件,表上作业法,初始方案,差值法伏格尔（,Vogel),法,TP & AP,基本思想：在考虑,最大差值,的基础上，,就近供应,差值（行、列）次小元素最小元素,Z=23954324712588,3,2,5,2,8,5,4,1,3,1,5,OR课件表上作业法初始方案差值法伏格尔（Vogel) 法,OR,课件,表上作业法,最优性检验,闭回路法,TP & AP,基本原理,：以任一非基变量为顶点，其它顶点为基变量，所构成的,闭回路是唯一,的。,3,4,2,3,4,5,4,7,1,3,2,3,OR课件表上作业法最优性检验闭回路法TP & AP,OR,课件,表上作业法,最优性检验,TP & AP,位势法,基本原理,：由于找闭回路带来的麻烦，根据对偶理论，设两组变量（对偶变量）,u,i,和,v,j,，,及基变量的检验数等于0，建立一组,参数方程,：,基变量所对应的价格系数,非基变量所对应的价格系数,行位势,列位势,OR课件表上作业法最优性检验TP & AP位势法,OR,课件,表上作业法,最优性检验,TP & AP,3,4,2,3,4,5,v,j,u,i,令,u,1,= 0,0,-5,-5,6,9,7,7,-4,7,-1,3,2,3,OR课件表上作业法最优性检验TP & AP342,OR,课件,表上作业法,方案调整,TP & AP,3,4,2,3,4,5,-4,7,-1,3,1,3,闭回路法,基本思想,：确定,换入,、,换出,变量。在闭回路上采用“,奇加偶减,”调整运量,x,ij,，,闭回路以外,x,ij,不变。,3,1,5,?,?,?,OR课件表上作业法方案调整TP & AP342,OR,课件,表上作业法,方案调整,TP & AP,4,5,3,1,5,3,v,j,u,i,0,2,9,7,-5,-5,7,4,11,-1,3,2,3,5,6,0,4,0,3,6,3,5,v,j,u,i,0,2,7,-5,8,-4,6,4,10,1,4,3,2,S=83,OR课件表上作业法方案调整TP & AP4531,OR,课件,运输问题,TP & AP,特殊运输问题及其求解,目标取极大（,MaxZ）：,用,ij, 0,进行最优性检验。,供过于求（产销）：,加虚销点,，且,C,i,虚,0 ，销量为产销之差 【,例,】,供不应求（销产）：,加虚产点,，且,C,虚,j,= 0 ，,产量为销产之差 【,例,】,OR课件运输问题TP & AP特殊运输问题及其求解目标取极大,OR,课件,特殊运输问题及求解,TP & AP,21,15,OR课件特殊运输问题及求解TP & AP2115,OR,课件,特殊运输问题及求解,TP & AP,21,25,OR课件特殊运输问题及求解TP & AP2125,OR,课件,指派问题,TP & AP,问题的提出,设有,n,个人，需要分派他们去做,n,件工作。,要求一个人做一件事，一件事只能由一个人完成,；由于每人的专长不同，各人做任一种工作的效率可能不同，因而创造的价值也不同。问如何安排，才能使创造的,总价值最大,？,OR课件指派问题TP & AP问题的提出 设有,OR,课件,指派问题,TP & AP,数学模型,【例】现有4辆装载不同货物的待卸车，派班员要分派给4个装卸班组，每个班组卸一辆车。由于各个班组的,技术专长不同,，各个班组卸不同车辆所需时间（小时）如下表。问派班员应如何分配卸车任务，才能使卸车所花的总时间最少？,待卸车,装卸组,c,ij,OR课件指派问题TP & AP数学模型【例】现有4辆装载不同,OR,课件,指派问题,数学模型,TP & AP,解：引入01变量,x,ij,，,并令:,待卸车,装卸组,b,j,a,i,1,1,1,1,1,1,1,1,OR课件指派问题数学模型TP & AP解：引入01变量x,OR,课件,指派问题,TP & AP,匈牙利算法,算法的提出,：观测模型的特征,特殊的运输问题,OR课件指派问题TP & AP匈牙利算法算法的提出：观测模型,OR,课件,匈牙利算法,TP & AP,算法原理,c,ij,nn,不同行（列）减去最小元素,b,ij,nn,有相同的最优指派,？,OR课件匈牙利算法TP & AP算法原理cijnn不同,OR,课件,匈牙利算法,TP & AP,设：,i,，,j,分别是系数矩阵,c,ij,行和列减去的最小元素。则,b,ij,=c,ij,-,i,-,j,因为,b,ij,0，x,ij,0,则上式为,b,ij,所对应的最优目标值0。,c,ij,所对应的最优目标值为行、列减去的,最小元素之和,。,当不同行不同列的,b,ij,=0,时，,x,ij,1；,否则，,x,ij,0,OR课件匈牙利算法TP & AP设：i，j 分别是系数矩,OR,课件,匈牙利算法,TP & AP,算法步骤,使,c,ij,的行（列）出现0元素,c,ij, ,b,ij,？,Y,确定最优指派,调整方案：,使,c,ij,出现更多的0元素,N,行（列）减去该行（列）的,最小元素,【,例1,】,b,ij,中存在不同行、不同列的0元素,b,ij,= (0),时，,x,ij,=1;,否则，,x,ij,=0,变换系数矩阵,【,例2,】,OR课件匈牙利算法TP & AP算法步骤使cij的行（列,OR,课件,匈牙利算法,TP & AP,-1,-2,-3,-2,-2,(0),(0),(0),(0),Z=,1+2+5+2,=,1+2+3+2+2,=10,【例1】,OR课件匈牙利算法TP & AP-1-2-3-2-2(0)(,OR,课件,匈牙利算法,TP & AP,-7,-5,-4,-2,-1,【例2】,(0),(0),(0),-1,-1,1,(0),(0),(0),(0),(0),(0),(0),(0),或：,关键,：能覆盖所有0元素的,最少直线数,？,如何画,？,？,OR课件匈牙利算法TP & AP-7-5-4-2-1【例2】,OR,课件,匈牙利算法,TP & AP,Z=20,【例2】,或：,OR课件匈牙利算法TP & AP Z=20【例2】或：,OR,课件,匈牙利算法,TP & AP,【例2】,定理,：能覆盖所有0元素的,最少直线数,等于在0元素处作出标号,（0）的最多个数,。,画法,：,在没有（0）的,行,打,号,对打,号的行上的所有,有0元素的,列,打号,再对打,号的列上,有（0）的,行,打号,有新的打,号,的,行列,吗？,Y,N,对,没有,打,号的,行,画横线,对,所有,打号的,列,画纵线,OR课件匈牙利算法TP & AP【例2】定理：能覆盖所有0元,OR,课件,指派问题,TP & AP,特殊指派问题的求解,目标为,MaxZ：,令：,C,ij,=M- C,ij,，,转化为,MinS.,“人多于事”（,mn）：,处理,：加（,m-n）,件虚事，,C,i,虚,0,“事多于人”（,mn）：,处理,：加（,n,- m ）,个虚人，,C,虚,j,0,OR课件指派问题TP & AP特殊指派问题的求解目标为Max,OR,课件,本章小结,TP & AP,本章重点介绍了一类特殊线性规划问题（运输问题和指派问题）的模型与求解；,应注意到：,两问题都有最优解；,两算法思想基本相同，均从目标函数系数入手，并且直接求得整数最优解；,思考：两算法的区别？,OR课件本章小结TP & AP本章重点介绍了一类特殊线性规划,