第六章_指派问题

第六章指派问题组合优化理论CombinatorialOptimizationTheory指派问题（AssignmentProblem,AP）是一种特殊的线性规划问题，也属于0-1整数规划问题.在图论中称为最佳匹配问题（OptimalMatching）.问题描述：有n项任务需要去完成，恰好有n个人可以去完成这n项任务，而每个人完成各项任务的效率是不同的，如果要求每人完成其中一项，且每项任务只交给其中一人去完成，应如何分配，使总的效率最高.第六章指派问题§1最大基数匹配问题§2指派问题§3指派问题的应用§4瓶颈分配问题第六章指派问题§1最大基数匹配问题人员工作分配问题：某公司有工作人员x1,x2,…,xn,他们去做n项工作y1,y2,…,yn，每人会做其中的一项或几项，要求每人至多做一项，每项工作至多由一人来做，问能否每人都分配到一项会做的工作？如果不那么最多几人有会做的工作可做？且如何安排？可用图和矩阵给出它的数学模型及求解方法.§1最大基数匹配问题Definition4.1设图G=(V，E)GraphVertexEdge2、M中的每条边的两个顶点称为关于M是饱和的，否则称为非饱和的；3、G中每个顶点都关于M是饱和的，则称M是G的一个完备匹配；4、如果M是一匹配，而不存在其他匹配M1，使得第六章指派问题6、如果G的顶点V可分成两个满足如下条件的子集X，Y：②对，则与ej关联的两个顶点分属XY，称G=(X,Y,E)为二部图或偶图.x3x1x2y2y1y3x4x5y4y5①人员工作分配问题就是在二部图中寻找最大匹配.§1最大基数匹配问题x3x1x2y2y1y3x4x5y4y5该问题也可用矩阵表示如果xi会做yj否则1111111111000000000000000在矩阵中寻找什么？寻找最多的不同行不同列的1元素.(二部图G的邻接矩阵)称为独立元（素）第六章指派问题如何寻找？礼让原则从每行、每列中，1最少的行或列先取，一样多时随意.×××××遗憾的是这是错的××××××××ק1最大基数匹配问题就二部图的邻接矩阵，先给出几个概念：在第i行第j列上的①（1被加圈）表示xi(或yj)已被分配，或该行（或列）已被分配；不同行不同列的①，称为A的一个分配，用M表示;第六章指派问题×××设M为已知分配，xi未被分配，而该行没有1，则xi不能被分配；若有1，选择一个1(aij),如果第j列没有加圈1，则对该1加圈，得到一新的分配M′,有，如果有加圈1（ai1j），则对aij,ai1j打√,√√√且划去第j列，再看第i1行有否没有被划去的1，有，再重复上述过程，直至不能继续为止.这时所得序列，称为关于M的交互链.如果在交互链中，最后得到的是无圈1，则称该交互链为可增广链.把可增广链中的加圈1与没圈的1，互换标记，得到一新的分配M′,有.上述过程称之为增广过程.交互链、可增广链可在图G中描述§1最大基数匹配问题Theorem4.1(Berge,1957)M是A的最大分配的充要条件是不存在可增广链.匈牙利算法：Step1任给一初始分配M，设S为未被M分配的行集合；Step2如果，则此时已得到最大分配，End否则，取；Step3寻找xi出发的可增广链，如果存在，则进行增广；且令GotoStep2;否则xi不能被分配，令GotoStep2;对图G的最大匹配，结论也成立proofTheorem4.1的 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 Proof:必要性：若M是A的最大分配，显然A中无关于M的可增广链，不然M还可以增广成独立元更多的分配，与M是最大分配相违；充分性：反证，若M不是最大分配，则存在分配M1,作由于M2是由M，M1中非公共部分组成，而M,M1都是分配，所以从M2的任一1出发，按交互链得到方法，得到的链必是M,M1中的1交替出现.√√√√√√√由于，所以在所有的交互链中，必有一条链属于M1的1多于属于M的1，且以M1的1出发、结束，这是关于M的可增广链.与条件矛盾.证毕√√√√第六章指派问题Example1求G的最大匹配，G的邻接矩阵如右所示：√Solution:不妨设初始匹配取x3，从x3y2出发，√√√得一增广链：增广得：√√√√√取x4，得一增广链：增广得：取x5，从x5y3出发，√得一交互链，但不是增广链.从x5y4出发，因y4未被分配，所以对x5y4加圈，得：所以，M是最大匹配，且是完备匹配.§2指派问题在第一节的人员工作安排问题中，分配工作时，只考虑人员有工作做.但事实上，由于工作的性质和个人的特长不同，在完成不同的任务时，其效益是不同的（成本、时间、利润、费用etc.）.§2指派问题设有n个人员去完成n项任务，第i人完成第j项任务的效益为，要求每人完成且仅完成一项，问如何分配，使完成n项任务的总效益最佳.可以是max、min先考察min称C=(cij)n×n为效益矩阵.第六章指派问题Example2任务人员EJGRA215134B1041415C9141613D78119有一份中文说明书需要译成英、日、德、俄四种语言，分别记为E、J、G、R.现有A、B、C、D四人，他们将中文翻译成不同语言所需时间如表,问应分配何人去完成何任务（一人完成一项任务），使所需总时间最少？Solution:设s.t.§2指派问题显然，这是一个0-1规划问题，任务人员EJGRA215134B1041415C9141613D78119任务人员EJGRaiA2151341B10414151C91416131D781191bj1111也是一个特殊的运输问题.所以,分配问题可用解IP问题方法（如：分支定界法),或解运输问题的表上作业法.但是，1、IP是NP-C问题；2、有基变量2n-1个，而有n-1个为零，高度退化.1955年，Kuhn-Munkras提出了解AP的算法，将求AP转化为求完备匹配问题，其计算复杂性为O(n3).由于算法引用了匈牙利数学家König的结论,所以，该算法也称为匈牙利算法.第六章指派问题Theorem4.2(König,1931)Definition4.2图G=(V，E)，一个顶点在C中，称C为G的一个点（对边的）覆盖.点集若G中每条边至少有点数最少的点覆盖C称为G的最小点覆盖.二部图G=(X，Y，E)，M为最大匹配，C为最小点覆盖，则有监测点的设置等是最小点覆盖的应用.点覆盖在二部图G的邻接矩阵上如何表示？Proofx3x1x2y2y1y3x4y4Theorem4.2的证明Proof:显然，若，则若，设X1为在M中没有独立元的行的集合.如右令Z是X1中行出发的关于M的交互链上的所有点，如右记则表示S中的行的所有1对应的列取则B是A的一个覆盖，如果不是，则有1元素行在S列在Y-T中，这与矛盾.而，显然所以B是最小覆盖.证毕§2指派问题显然，Ex.2的可行解可用一个0-1矩阵表示.表示：因此，求解指派问题可在效益矩阵上进行.Theorem4.3如果从效益矩阵(cij)的第i行中每个元素减去a和第j列中每个元素加上b，得到一个新的效益矩阵.则以为新的目标函数与原目标函数的指派问题最优解相同.第六章指派问题匈牙利算法：Step1使效益矩阵各行各列出现零元素；具体：从效益矩阵的每行各元素减去该行最小元素；再从所得矩阵的每列各元素减去该列最小元素.称各行各列所减的数值之总和为缩减量，记为S.S=2+4+9+7+4+2=28§2指派问题Step2试寻求最优解；用上节的求最大匹配的算法.这时得到最大匹配M.如果，则已得到最优解；即28=S每行每列有零元素，能保证有n个独立零元素吗？如果，则gotostep3；第六章指派问题Step3作缩减后的效益矩阵的最小覆盖；具体：a、对没有0的行打√；b、对已打√的行中所有含0元素的列打√；c、对打√的列上有0的行打√；d、重复b、c，直到得不出新的打√的行列为止；e、对打√的列画纵线，没打√行画横线.这就得到最小覆盖.§2指派问题Example3求效益矩阵为C的最小指派.Solution:√√√缩减量S1=26此时，.第六章指派问题Step4增加零元素√√√具体：a、求出未被直线覆盖的元素中的最小值k；显然，在直线下增加零元素是不增加独立零的本例k=2b、对打√的行减去k，打√的列加上k，gotostep2.-2-2+2缩减量为S2=2+2-2=2此时，所以最优解为zmin=S1+S2=26+2=2828零元素是增加吗？§2指派问题考虑极大化问题令可以吗？匈牙利算法要求矩阵元素非负作一新矩阵取则Example4（婚姻问题）取M=28对人多任务少，人少任务多，如何？虚设.第六章指派问题§3指派问题的应用Example5现有6项任务，由4个工厂来完成，已知各个工厂完成各项任务的费用矩阵为C，应如何分配任务，使总费用最小？具体分别1、无要求；2、一厂至多完成两项；3、一厂至多完成两项，至少完成一项.Solution:1、无要求碰巧，符合2、3的要求Zmin=13§3指派问题的应用2、一厂至多完成两项设想每个工厂由两个分厂组成，问题变为8个工厂完成6项任务,虚设2个任务，费用为零.说明什么？3、一厂至多完成两项，至少完成一项.一个厂不能同时完成最后两个任务.如何做到？MMMMMMMMZmin=13第六章指派问题Example6（铁路列车运行分派问题）A站与B站之间拟开7对客车，客车的运行时间如图，现在要给列车固定乘务组.现在假定，哪站的乘务组换班地点就在那站，乘务组在对方折返停留的最短时间为2小时，问如何分派任务使7个乘务组在折返点的总耗时最小？问题：列车如何配对，乘务组由哪个车站提供？AB0246810121416182022241214108642131197531§3指派问题的应用AB0246810121416182022241214108642131197531Solution:24681012142024最大数与最小数？2172468101214221825……24…14构造一个新矩阵C,2468101214zmin=20小时如何考虑A、B两站的均衡？第六章指派问题指派问题的分支与定界算法因为，所以是没必要使用B.B.M，在此只是对方法的训练.参见Ex.3Solution:该问题的可行解仅有24个，然而若n=20,则可行解超过1018个.指派问题的约束为：考虑去掉约束（*）得一松弛问题.§3指派问题的应用分配人工作时间AE2BJ4AG9AR7总时间=22解松弛问题，得：下界为22.显然，不是可行解.考虑最优解中，任务E必为A、B、C、D四人中一人完成.所以分成四支，每支先确定一人完成E，余下三项按前述松弛问题处理.第一支AE，不可行，得下界为27.分配人工作时间AE2BJ4DG13BR8总时间=27类似得到：第二支BE，etc.分配人工作时间BE15AJ10AG9AR7总时间=41第六章指派问题1222273414336367248341237112813399281031AEEEEDCBDE,524EJJJCBACAGG可行可行*JJJDCB*可行***经计算13次(几乎是可行解的一半)找到最优解，BJAG,CRzmin=28§4瓶颈分配问题§4瓶颈分配问题经典分配问题（AP）任务人员EJGRA215134B1041415C9141613D78119每人完成一个任务每个任务一人完成条件：目标：总完成时间最少总效益最佳数学模型：求解方法：匈牙利算法s.t.第六章指派问题瓶颈分配问题(BAP)每人完成一个任务每个任务一人完成条件：目标：最大完成时间最小经典分配问题：z=5瓶颈分配问题：z=2数学模型：设§4瓶颈分配问题任务人员EJGRA215134B1041415C9141613D78119第一个任务的完成时间：s.t.这是非线性的第六章指派问题求解方法：首先会想到什么方法一、化为经典分配问题1144413404013求效益矩阵(dij)的经典分配：所以，fmin=2§4瓶颈分配问题对原效益矩阵C的元素cij的不同的值按从小到大的顺序排序.c(k)为第k个值，用s表示不同c(k)值的个数，则定义数列d(t)如下：构建新的效益矩阵D：令则效益矩阵D的经典分配问题的最优解即为原问题的最优解.如前例有什么缺点吗？计算量如：s=20，n=10这给计算机的存储和运算带来巨大困难.第六章指派问题二、阀门算法几个记号：1、yk表示第k个可行方案的最大完成时间算法步骤：Step1任给初始可行方案，令k=1;Step2Step3否则，令k=k+1，gotostep2.§4瓶颈分配问题见前例：取x11=1,x22=1,x33=1其余为零,得y1=4取x11=1,x23=1,x32=1其余为零,得y2=3取x12=1,x21=1,x33=1其余为零,得y3=2所以最优解为x12==x21=x33,其余为零fmin=y3=2有什么改进吗？第六章指派问题三、改进的阀门算法Theorem问题(BAP)的目标函数值的下界为算法思想：首先取出(cij)中每一行每一列的最小元素，构建矩阵C0.寻找C0的最大匹配，如果M(C0)=n，则该最大匹配即为最优解；否则，像经典分配问题的匈牙利算法中增加零元素一样增加最小元素，直到最大匹配数为n.§4瓶颈分配问题见前例：212121212此时为最优解，fmin=2.第六章指派问题完