《指派题目精华》ppt课件

《《指派题目精华》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息处理中的组合优化第四章指派问题CombinatorialOptimizationinInformationProcessing黔缕捐糯祈蛛缀牙娥敏俭倡空诲志皇恍缄浚俏仰涝赫壤氧甭惊香绷半马狗第四章_指派问题第四章_指派问题指派问题（AssignmentProblem,AP）是一种特殊的线性规划问题，也属于0-1整数规划问题.在图论中称为最佳匹配问题（OptimalMatching）.问题描述：有n项任务需要去完成，恰好有n个人可以去完成这n项任务，而每个人完成各项任务的效率是不同的，如果要求每人完成其中一项，且每项任务只交给其中一人去完成，应如何分配，

2、使总的效率最高.第四章指派问题若返蹲伞沸辽颂颇兆事咐茨矽流瘤负执钎匿廉颜瘪影宁拈啪史己响碌点腔第四章_指派问题第四章_指派问题§1最大基数匹配问题§2指派问题§3指派问题的应用§4瓶颈分配问题色堑涧蜕急掘凭蜜亲去灼氏豺镀央仆肆饿白开戎筒锗兆屯贫究堑篓锻恿纫第四章_指派问题第四章_指派问题第四章指派问题§1最大基数匹配问题人员工作分配问题：某公司有工作人员x1,x2,…,xn,他们去做n项工作y1,y2,…,yn，每人会做其中的一项或几项，要求每人至多做一项，每项工作至多由一人来做，问能否每人都分配到一项会做的工作？x3x1x2y2y1y3如果不那么最多几人

3、有会做的工作可做？且如何安排？可用图和矩阵给出它的数学模型及求解方法.叛猛芝脂骸鼻略翼怔莹击渤唾亭瓣埃税扮帛娟睁陈裁刮贸已园舟良兔槛次第四章_指派问题第四章_指派问题§1最大基数匹配问题Definition4.1设图G=(V，E)GraphVertexEdge1、如果，且对，与无公共顶点，则称边子集M是G的一个匹配；2、M中的每条边的两个顶点称为关于M是饱和的，否则称为非饱和的；3、G中每个顶点都关于M是饱和的，则称M是G的一个完备匹配；4、如果M是一匹配，而不存在其他匹配M1，使得5、如果M是一匹配，而对不是G的匹配，则称M是G的一个极大匹配.Note:

4、最大匹配与极大匹配的边数是不同的x3x1x2y2y1y3，则称M是G的最大（基数）匹配；集孪友拥兑霓几秘浪擂眶儒泳恒捍爱卒奇踏逮泳动娃忠简嗅击尤奇侵贡助第四章_指派问题第四章_指派问题第四章指派问题6、如果G的顶点V可分成两个满足如下条件的子集X，Y：②对，则与ej关联的两个顶点分属XY，称G=(X,Y,E)为二部图或偶图.x3x1x2y2y1y3x4x5y4y5①人员工作分配问题就是在二部图中寻找最大匹配.拿视随幽角围退锥界颗揽薛噎伏劣五敬陕灼炎灼紧额霜吐赶现挪炮手器枕第四章_指派问题第四章_指派问题§1最大基数匹配问题x3x1x2y2y1y3x4x5y

5、4y5该问题也可用矩阵表示如果xi会做yj否则1111111111000000000000000在矩阵中寻找什么？寻找最多的不同行不同列的1元素.(二部图G的邻接矩阵)称为独立元（素）剩萄熊瑚造例柞婴俩供脊贞仕衙喂抱靡巩幢华辰渠墩缸誊堤笋钠躇衙萧哆第四章_指派问题第四章_指派问题第四章指派问题如何寻找？礼让原则从每行、每列中，1最少的行或列先取，一样多时随意.×××××遗憾的是这是错的×××××××××卫奶嚏展犀住所全构尸嫡扣梆北谨汲调割叉饮腆收蚁摊兼从攻糯拄硫惕阵第四章_指派问题第四章_指派问题§1最大基数匹配问题1965年匈牙利著名数学家Edmonds

6、为之设计了命名为“匈牙利算法”的有效算法，计算复杂性为O(n).就二部图的邻接矩阵，先给出几个概念：在第i行第j列上的①（1被加圈）表示xi(或yj)已被分配，或该行（或列）已被分配；此时，由于所在行和列的1元素不能再取，用1表示;×不同行不同列的①，称为A的一个分配，用M表示;须予完残酷栏宇我歹沿翔吱俊野箕胡针艇鳃烙粟翟苫辑钓晚岳肠央夸贼钙第四章_指派问题第四章_指派问题第四章指派问题×××设M为已知分配，xi未被分配，而该行没有1，则xi不能被分配；若有1，选择一个1(aij),如果第j列没有加圈1，则对该1加圈，得到一新的分配M′,有，如果有加圈1（

7、ai1j），则对aij,ai1j打√,√√√且划去第j列，再看第i1行有否没有被划去的1，没有，结束；有，再重复上述过程，直至不能继续为止.这时所得序列，称为关于M的交互链.如果在交互链中，最后得到的是无圈1，则称该交互链为可增广链.把可增广链中的加圈1与没圈的1，互换标记，得到一新的分配M′,有.上述过程称之为增广过程.交互链、可增广链可在图G中描述撂极翅园戮圆热俩随迸核壁锑诡倾汝犁窗壮笔自劫留燎交北翌迭菱壳俩情第四章_指派问题第四章_指派问题§1最大基数匹配问题Theorem4.1(Berge,1957)M是A的最大分配的充要条件是不存在可增广链.匈牙

8、利算法：Step1任给一初始分配M，设S为未被M分配的行集合；St