第六章-指派问题.优秀PPT.ppt

《第六章-指派问题.优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第六章-指派问题.优秀PPT.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第六章第六章 指派问题指派问题组合优化理论组合优化理论 Combinatorial Optimization Theory 指派指派 问题问题（Assignment Problem,AP）是一种特）是一种特殊的线性规划问题，也属于殊的线性规划问题，也属于 0-1 整数规划问题整数规划问题.在图在图论中称为最佳匹配问题论中称为最佳匹配问题（Optimal Matching）.问题描述：有问题描述：有 n 项任务须要去完成，恰好有项任务须要去完成，恰好有 n 个人可个人可以去完成这以去完成这 n 项任务，而每个人完成各项任务的效率项任务，而每个人完成各项任务的效率是不同的，假如要求每人完成其中一

2、项，且每项任务是不同的，假如要求每人完成其中一项，且每项任务只交给其中一人去完成，应如何安排，使总的效率最只交给其中一人去完成，应如何安排，使总的效率最高高.第六章第六章 指派问题指派问题1 最大基数匹配问题最大基数匹配问题2 指派问题指派问题3 指派问题的应用指派问题的应用4 瓶颈安排问题瓶颈安排问题第六章第六章 指派问题指派问题1 最大基数匹配问题最大基数匹配问题人员工作安排问题：人员工作安排问题：某公司有工作人员某公司有工作人员 x1,x2,xn,他们去做他们去做 n 项工作项工作 y1,y2,yn，每人会做其中的一，每人会做其中的一项项或几项，要求每人至多做一项，每项工作至多由一人或几

3、项，要求每人至多做一项，每项工作至多由一人来做，问能否每人都安排到一项会做的工作？来做，问能否每人都安排到一项会做的工作？x3x1x2y2y1y3假如不假如不那么最多几人有会做的工作可做？且如何支配？那么最多几人有会做的工作可做？且如何支配？可用图和矩阵给出它的数学模型及求解方法可用图和矩阵给出它的数学模型及求解方法.1 最大基数匹配问题Definition 4.1设图设图 G=(V，E)Graph VertexEdge1、如果如果 ，且对且对 ，与与 无无 公共顶点，则称边子集公共顶点，则称边子集 M 是是 G 的一个的一个匹配匹配；2、M 中的每条边的两个顶点称为关于中的每条边的两个顶点称

4、为关于 M 是是饱和饱和的，的，否则称为否则称为非饱和非饱和的；的；3、G 中中每个顶点都每个顶点都关于关于 M 是是饱和饱和的，则称的，则称 M 是是 G 的的 一个一个完备完备匹配匹配；4、假如、假如 M 是是 一匹配，而不存在其他匹配一匹配，而不存在其他匹配 M1，使得，使得5、如果如果 M 是是 一匹配，而对一匹配，而对 不是不是 G 的匹配，则称的匹配，则称 M 是是G 的一个的一个极大匹配极大匹配.Note:最大匹配与极大匹配最大匹配与极大匹配的边数是不同的的边数是不同的x3x1x2y2y1y3，则称，则称 M 是是 G 的的最大（基数）匹配最大（基数）匹配；第六章第六章 指派问题

5、指派问题6、假如、假如 G 的顶点的顶点 V 可分可分 成两个满足如下条件的成两个满足如下条件的 子集子集 X，Y：对对 ，则与，则与 ej 关联的两个顶点分属关联的两个顶点分属 X Y，称称 G=(X,Y,E)为为二部二部图图或或偶图偶图.x3x1x2y2y1y3x4x5y4y5人员工作安排问题就是在人员工作安排问题就是在二部图中找寻最大匹配二部图中找寻最大匹配.1 最大基数匹配问题x3x1x2y2y1y3x4x5y4y5 该问题也可用矩阵表示该问题也可用矩阵表示假如假如 xi 会做会做 yj否则否则1111111111000000000000000 在矩阵中找寻什在矩阵中找寻什么？么？找寻

6、最多的不同行不找寻最多的不同行不同列的同列的 1 元素元素.(二部图二部图 G 的的邻接矩阵邻接矩阵)称为独立元称为独立元（素）（素）第六章第六章 指派问题指派问题如何找寻？如何找寻？礼让原则礼让原则 从每行、每列中，从每行、每列中，1 最少的行或列先取，一最少的行或列先取，一样多时随意样多时随意.缺憾的是缺憾的是这是错的这是错的 1 最大基数匹配问题 1965年匈牙利著名数学家年匈牙利著名数学家 Edmonds 为之设计了命为之设计了命名为名为“匈牙利算法匈牙利算法”的有效算法，计算复杂性为的有效算法，计算复杂性为 O(n ).就二部图的邻接矩阵，先给出几个概念：就二部图的邻接矩阵，先给出几

7、个概念：在第在第 i 行第行第 j 列上的列上的 （1 被加圈）表示被加圈）表示 xi(或或yj)已被安排，或该行（或列）已被安排已被安排，或该行（或列）已被安排；此时，由于所在行和列的此时，由于所在行和列的 1 元素不能再取，用元素不能再取，用 1 表示表示;不同行不同列的不同行不同列的，称为，称为 A 的一个安排，用的一个安排，用 M 表示表示;第六章第六章 指派问题指派问题设设 M 为已知安排，为已知安排，xi 未被未被安排，而该行没有安排，而该行没有1，则，则 xi 不能不能被安排；若有被安排；若有1，选择一个，选择一个1(aij),假如第假如第 j 列没有加圈列没有加圈 1，则对该，

8、则对该1 加圈，得到一新的安排加圈，得到一新的安排 M,有有 ，假如有加圈假如有加圈1（ai1j），则对），则对aij,ai1j打打,且划去第且划去第 j 列，列，再看第再看第 i1 行有否没有被划去的行有否没有被划去的1，没有，没有，结束结束；有，再重复上述过程，直至不能接着为止有，再重复上述过程，直至不能接着为止.这时所得序列，称为关于这时所得序列，称为关于 M 的的交互链交互链.假如在交互链假如在交互链中，最终得到的是无圈中，最终得到的是无圈 1，则称该交互链为可增广链，则称该交互链为可增广链.把可增广链中的加圈把可增广链中的加圈1与没圈的与没圈的1，互换标记，互换标记，得到一新的安排得

9、到一新的安排 M,有有 .上述过程称之为增广过程上述过程称之为增广过程.交互链、可增广链交互链、可增广链可在图可在图 G 中描述中描述1 最大基数匹配问题Theorem 4.1(Berge,1957)M 是是 A 的最大安排的充要条件是不存在可增广链的最大安排的充要条件是不存在可增广链.匈牙利算法匈牙利算法：Step 1任给一初始安排任给一初始安排 M，设设 S 为未被为未被 M 安排的行安排的行 集合；集合；Step 2假如假如 ，则此时已得到最大安排，则此时已得到最大安排，End 否则，取否则，取 ；Step 3找寻找寻 xi 动身的可增广链，动身的可增广链，假如存在，则进行增假如存在，则

10、进行增广；广；且令且令Go to Step 2;否则否则xi 不能被安排，不能被安排，令令Go to Step 2;对图对图 G 的最大匹的最大匹配，结论也成立配，结论也成立proofTheorem 4.1 的证明的证明Proof :必要性必要性：若若 M 是是 A 的最大安排，明显的最大安排，明显 A 中中无关于无关于 M 的可增广链，不然的可增广链，不然 M 还可以增广成独立元还可以增广成独立元更多的安排，与更多的安排，与 M 是最大安排相违；是最大安排相违；充分性充分性：反证，若反证，若 M 不是最大安排，不是最大安排，则存在安排则存在安排 M1,作作 由于由于 M2 是由是由 M，M1

11、 中非公共部中非公共部分组成，而分组成，而 M,M1 都是安排，所以都是安排，所以从从 M2 的任一的任一 1 动身，按交互链得到动身，按交互链得到方法，得到的链必是方法，得到的链必是 M,M1 中的中的1 交交替出现替出现.由于由于 ，所以在全部的交互链中，必有，所以在全部的交互链中，必有一条链属于一条链属于 M1 的的 1 多于属于多于属于 M 的的 1，且以，且以 M1 的的 1 动身、结束，这是关于动身、结束，这是关于 M 的可增广链的可增广链.与与 条件条件冲突冲突.证毕证毕第六章第六章 指派问题指派问题Example 1 求求 G 的最大匹配，的最大匹配，G 的邻接矩阵如右所示的邻

12、接矩阵如右所示：Solution:不妨设初始匹配不妨设初始匹配取取 x3，从，从x3y2 动身，动身，得一增广链：得一增广链：增广得增广得：取取 x4，得一增广链：得一增广链：增广得增广得：取取 x5，从，从x5y3 动身，动身，得一交互链，但不是增广链得一交互链，但不是增广链.从从 x5y4 动身，动身，因因 y4 未被安排，所以对未被安排，所以对 x5y4 加圈，得：加圈，得：所以，所以，M 是最大匹配，且是完备匹配是最大匹配，且是完备匹配.2 指派问题 在第一节的人员工作支配问题中，安排工作时，在第一节的人员工作支配问题中，安排工作时，只考虑人员有工作做只考虑人员有工作做.但事实上，由于

13、工作的性质和但事实上，由于工作的性质和个人的特长不同，在完成不同的任务时，其效益是不个人的特长不同，在完成不同的任务时，其效益是不同的（成本、时间、利润、费用同的（成本、时间、利润、费用 etc.）.2 指派问题指派问题 设有设有 n 个人员去完成个人员去完成 n 项任务，第项任务，第 i 人完成第人完成第 j 项项任务的效益为任务的效益为 ，要求每人完成且仅完成一项，要求每人完成且仅完成一项，问如何安排，使完成问如何安排，使完成 n 项任务的总效益最佳项任务的总效益最佳.可以是可以是 max、min先考察先考察 min称称 C=(cij)nn 为为效益矩阵效益矩阵.第六章第六章 指派问题指派

14、问题Example 2 任务任务人员人员EJGRA215134B1041415C9141613D78119 有一份中文说有一份中文说明书须要译成英、日、德、明书须要译成英、日、德、俄四种语言，分别记为俄四种语言，分别记为 E、J、G、R.现有现有 A、B、C、D 四人，他们将中文翻译四人，他们将中文翻译成不同语言所需时间如表成不同语言所需时间如表,问应安排何人去完成何任问应安排何人去完成何任务（一人完成一项任务），使所需总时间最少？务（一人完成一项任务），使所需总时间最少？Solution:当分配第当分配第 i 人完成第人完成第 j 项任务项任务否则否则设设s.t.2 指派问题 明显，这是一个

15、明显，这是一个 0-1 规划问题，规划问题，任务任务人员人员EJGRA215134B1041415C9141613D78119 任务任务人员人员EJGRaiA2151341B10414151C91416131D781191bj1111 也是一个也是一个特殊的运输问题特殊的运输问题.所以所以,安排问题可用安排问题可用解解IP IP 问题方法（如：分问题方法（如：分支定界法支定界法),),或解运输问或解运输问题的表上作业法题的表上作业法.但是，但是，1、IP 是是 NP-C 问题；问题；2、有基变量、有基变量 2n-1 个，而有个，而有 n-1 个为零，高度退化个为零，高度退化.1955年，年，K

16、uhn-Munkras 提出了解提出了解AP 的算法，将求的算法，将求AP 转化为求完备匹配问题，其计算困难性为转化为求完备匹配问题，其计算困难性为 O(n3).由于算法引用了匈牙利数学家由于算法引用了匈牙利数学家 Knig 的结论的结论,所以，该算法也称为匈牙利算法所以，该算法也称为匈牙利算法.第六章第六章 指派问题指派问题Theorem 4.2(Knig,1931)Definition 4.2 图图 G=(V，E)，一个顶点在一个顶点在 C 中，称中，称 C 为为 G 的一的一个个点点（对边的）（对边的）覆盖覆盖.点集点集 若若 G 中每条边至少有中每条边至少有点数最少的点覆盖点数最少的点

17、覆盖 C 称为称为 G 的的最小点覆盖最小点覆盖.二部图二部图 G=(X，Y，E)，M 为最大匹配，为最大匹配，C 为最为最小点覆盖，则有小点覆盖，则有 监测点的设置等是最小点覆盖的应用监测点的设置等是最小点覆盖的应用.点覆盖点覆盖在二部图在二部图 G 的的邻接矩阵邻接矩阵上如何表示？上如何表示？Proof x3x1x2y2y1y3x4y4Theorem 4.2 的证明的证明Proof:明显，若明显，若 ，则则若若 ，设设 X1为在为在 M 中没有独立元的行的集合中没有独立元的行的集合.如右如右 令令 Z 是是 X1 中行动身的关于中行动身的关于 M 的交互链上的全部点，的交互链上的全部点，如

18、右如右 记记则则 表示表示 S 中的行的全部中的行的全部 1 对应对应的列的列取取则则 B 是是 A 的一个覆盖，的一个覆盖，假如不是，则有假如不是，则有 1 元素行在元素行在S 列在列在 Y-T 中，这与中，这与 冲突冲突.而而 ，明显明显所以所以 B 是最小覆盖是最小覆盖.证毕证毕2 指派问题 明显，明显，Ex.2 的可行解可的可行解可用一个用一个 0-1 矩阵表示矩阵表示.表示表示：因此，求解指派问题可在效益矩阵上进行因此，求解指派问题可在效益矩阵上进行.Theorem 4.3 假如从效益矩阵假如从效益矩阵(cij)的第的第 i 行中每个行中每个元元素减去素减去 a 和第和第 j 列中每

19、个元素加上列中每个元素加上 b，得到一个新的效，得到一个新的效益矩阵益矩阵 .则以则以 为新的目标函数与原目标函数的为新的目标函数与原目标函数的指派问题最优解相同指派问题最优解相同.第六章第六章 指派问题指派问题匈牙利算法匈牙利算法：Step 1使效益矩阵各行各列出现零元素使效益矩阵各行各列出现零元素；具体：从效益矩阵的每行各元素减去该行最小元素；具体：从效益矩阵的每行各元素减去该行最小元素；再从所得矩阵的每列各元素减去该列最小元素再从所得矩阵的每列各元素减去该列最小元素.称各行各列所减的数值之总和为称各行各列所减的数值之总和为缩减量缩减量，记为，记为 S.S=2+4+9+7+4+2=282

20、指派问题Step 2试寻求最优解；试寻求最优解；用上节的求最大匹配的算法用上节的求最大匹配的算法.这时得到最大匹配这时得到最大匹配 M.假如假如 ，则已得到最优解；，则已得到最优解；即即28=S每行每列有零元素，能保证有每行每列有零元素，能保证有 n 个独立零元素吗？个独立零元素吗？假如假如 ，则则 go to step 3；第六章第六章 指派问题指派问题Step 3作缩减后的效益矩阵的作缩减后的效益矩阵的最小覆盖最小覆盖；具体：具体：a、对没有、对没有 0 的行打的行打 ；b、对已打、对已打 的行中全部含的行中全部含 0 元素的列打元素的列打；c、对打对打 的列上有的列上有 0 的行打的行打

21、；d、重复、重复 b、c，直到得不出新的打，直到得不出新的打 的行列的行列 为止；为止；e、对打、对打 的列画纵线，没打的列画纵线，没打 行画横线行画横线.这就得到这就得到最小覆盖最小覆盖.2 指派问题Example 3求求效益矩阵为效益矩阵为 C 的最小指派的最小指派.Solution:缩减量缩减量 S1=26此时，此时，.第六章第六章 指派问题指派问题Step 4增加零元素增加零元素具体：具体：a、求出未被直线覆盖的元素中的最小值、求出未被直线覆盖的元素中的最小值 k ；明显，在直线下明显，在直线下增加零元素是不增加增加零元素是不增加独立零的独立零的本例本例 k=2b、对打、对打 的行减去

22、的行减去 k，打，打 的列加上的列加上 k，go to step 2.-2-2+2缩减量为缩减量为S2=2+2-2=2此时，此时，所以最优解为所以最优解为zmin=S1+S2=26+2=28 28 零元素是增加吗？零元素是增加吗？2 指派问题考虑极大化问题考虑极大化问题令令 可以吗？可以吗？匈牙利算法要求矩匈牙利算法要求矩阵元素非负阵元素非负作一新矩阵作一新矩阵 取取则则Example 4（婚姻问题）（婚姻问题）取取 M=28对人多任务少，人少任务多，如何？对人多任务少，人少任务多，如何？虚设虚设.第六章第六章 指派问题指派问题3 指派问题的应用指派问题的应用Example 5 现有现有 6

23、项任务，项任务，由由 4 个工厂来完成，个工厂来完成，已知各个工厂完成各项任务的已知各个工厂完成各项任务的费用矩阵为费用矩阵为 C，应如何安排任务，使总费用最小？应如何安排任务，使总费用最小？具体分别具体分别 1、无要求；、无要求；2、一厂至多完成两项、一厂至多完成两项；3、一厂至多完成两项，一厂至多完成两项，至少完成一项至少完成一项.Solution:1、无要求、无要求碰巧，符合碰巧，符合 2、3的要求的要求Z min=133 指派问题的应用2、一厂至多完成两项、一厂至多完成两项 设想每个工厂由两设想每个工厂由两个分厂组成，问题变为个分厂组成，问题变为 8 个工厂完成个工厂完成 6 项任务项

24、任务,虚设虚设 2 个任务，费用为个任务，费用为零零.说明什么？说明什么？3、一厂至多完成两项，一厂至多完成两项，至少完成一项至少完成一项.一个厂不能同时完成最终两个任务一个厂不能同时完成最终两个任务.如何做到？如何做到？M M M M M M M M Z min=13第六章第六章 指派问题指派问题Example 6（铁路列车运行分派问题）（铁路列车运行分派问题）A 站与站与 B 站之间拟开站之间拟开 7 对客车对客车，客车的运行时间客车的运行时间如图，现在要给列车固定乘务组如图，现在要给列车固定乘务组.现在假定，哪站的现在假定，哪站的乘务组换班地点就在那站，乘务组在对方折返停留的乘务组换班地

25、点就在那站，乘务组在对方折返停留的最短时间为最短时间为 2 小时，问如何小时，问如何分派任务分派任务使使 7 个乘务组在个乘务组在折返点的总耗时最小？折返点的总耗时最小？问题：列车如何配对，乘务组由哪个问题：列车如何配对，乘务组由哪个车站供应？车站供应？AB 0 2 4 6 8 10 12 14 16 18 20 22 24 12141086421311975313 指派问题的应用AB 0 2 4 6 8 10 12 14 16 18 20 22 24 1214108642131197531Solution:2 4 6 8 10 12 1420 24最大数与最大数与最小数？最小数？217 2

26、4 6 8 10 12 142218252 4 14构造一个新矩阵构造一个新矩阵 C,2 4 6 8 10 12 14 zmin=20 小时小时如何考虑如何考虑 A、B 两站的均衡？两站的均衡？第六章第六章 指派问题指派问题指派问题的分支与定界算法指派问题的分支与定界算法 因为因为 ，所以是没必要运用，所以是没必要运用 B.B.M，在此，在此只是对方法的训练只是对方法的训练.参见参见 Ex.3Solution:该问题的可行解仅该问题的可行解仅有有 24 个，然而若个，然而若 n=20,则可则可行解超过行解超过 1018 个个.指派问题的约束为：指派问题的约束为：考虑去掉约束考虑去掉约束 （*）

27、得一松弛问题）得一松弛问题.3 指派问题的应用 分分 配配 人人 工作工作 时间时间 A E 2 B J 4 A G 9 A R 7 总时间总时间=22解松弛问题，得：下界为解松弛问题，得：下界为 22.明显，不是可行解明显，不是可行解.考虑最优解中，任务考虑最优解中，任务 E 必为必为 A、B、C、D 四人中一人完四人中一人完成成.所以分成四支，每支先所以分成四支，每支先确定一人完成确定一人完成 E，余下三项，余下三项按前述松弛问题处理按前述松弛问题处理.第一支第一支 A E，不行行，得不行行，得 下界为下界为 27.分分 配配 人人 工作工作 时间时间 A E 2 B J 4 D G 13

28、 B R 8 总时间总时间=27类似得到类似得到：其次支其次支 B E，etc.分分 配配 人人 工作工作 时间时间 B E 15 A J 10 A G 9 A R 7 总时间总时间=41第六章第六章 指派问题指派问题 122 227 341 433 636 724 834123711281339 9281031AEEEEDCBD E,524EJJJCBACAGG可行可行可行可行*JJJDCB*可行可行*经计算经计算 13 次次(几乎是可行解的几乎是可行解的一一半半)找到最优解，找到最优解，B JA G,C Rzmin=284 瓶颈安排问题瓶颈安排问题4 瓶颈安排问题经典安排问题（经典安排问题

29、（APAP）任务任务人员人员EJGRA215134B1041415C9141613D78119每人完成一个任务每人完成一个任务每个任务一人完成每个任务一人完成条件：条件：目标：目标：总完成时间最少总完成时间最少总效益最佳总效益最佳数学模型：数学模型：求解方法：求解方法：匈牙利算法匈牙利算法s.t.第六章第六章 指派问题指派问题瓶颈安排问题瓶颈安排问题(BAP)每人完成一个任务每人完成一个任务每个任务一人完成每个任务一人完成条件：条件：目标：目标：最大完成时间最小最大完成时间最小经典安排问题：经典安排问题：z=5瓶颈安排问题：瓶颈安排问题：z=2数学模型：数学模型：当分配第当分配第 i 人完成第

30、人完成第 j 项任务项任务否则否则设设4 瓶颈安排问题 任务任务人员人员EJGRA215134B1041415C9141613D78119第一个任务的完成时间：第一个任务的完成时间：s.t.这是非线性的这是非线性的第六章第六章 指派问题指派问题求解方法：求解方法：首先会想到首先会想到什么方法什么方法一、化为经典安排问题一、化为经典安排问题1144413404013求效益矩阵求效益矩阵(dij)的经典安排：的经典安排：所以，所以，fmin=24 瓶颈安排问题 对原效益矩阵对原效益矩阵 C 的元素的元素 cij 的不同的值按从小到的不同的值按从小到大大的依次排序的依次排序.c(k)为第为第 k 个

31、值，用个值，用 s 表示不同表示不同 c(k)值的个数，则值的个数，则定义数列定义数列 d(t)如下：如下：构建新的效益矩阵构建新的效益矩阵 D：对对当当令令 则则 效益矩阵效益矩阵 D 的经典安排问题的经典安排问题的最优解即为原问题的最优解的最优解即为原问题的最优解.如前例如前例有什么缺点吗？有什么缺点吗？计算量计算量如：如：s=20，n=10这给计算机的存储和运算带来巨大困难这给计算机的存储和运算带来巨大困难.第六章第六章 指派问题指派问题二、阀门算法二、阀门算法几个记号：几个记号：1、yk 表示第表示第 k 个可行方案的最大完成时间个可行方案的最大完成时间2、表示矩阵表示矩阵 中擦去中擦

32、去的矩的矩阵阵,3、表示矩阵表示矩阵 的最大匹配数的最大匹配数 算法步骤：算法步骤：Step 1 任给初始可行方案任给初始可行方案，令，令 k=1;Step 2计算计算 yk ,在在 中擦去中擦去 得得 求求 的最大匹配的最大匹配 Mk+1；Step 3若若 则则 Mk 为最优解，为最优解，fmin=yk否则，令否则，令 k=k+1，go to step 2.4 瓶颈安排问题见前例：见前例：取取 x11=1,x22=1,x33=1 其余为零其余为零,得得 y1=4取取 x11=1,x23=1,x32=1 其余为零其余为零,得得 y2=3取取 x12=1,x21=1,x33=1 其余为零其余为零

33、,得得 y3=2所以所以 最优解为最优解为x12=x21=x33,其余为零其余为零 fmin=y3=2有什么改进吗？有什么改进吗？第六章第六章 指派问题指派问题三、改进的阀门算法三、改进的阀门算法Theorem 问题问题 (BAP)的目标函数值的下界为的目标函数值的下界为算法思想：算法思想：首先取出首先取出(cij)中每一行每一列的最小元素，构中每一行每一列的最小元素，构建建矩阵矩阵 C0.找寻找寻 C0 的最大匹配，假如的最大匹配，假如 M(C0)=n，则，则该该最大匹配即为最优解；否则，像经典安排问题的匈牙最大匹配即为最优解；否则，像经典安排问题的匈牙利算法中增加零元素一样增加最小元素，直到最大匹利算法中增加零元素一样增加最小元素，直到最大匹配数为配数为 n.4 瓶颈安排问题见前例：见前例：212121212此时为最优解，此时为最优解，fmin=2.第六章第六章 指派问题指派问题 完完