运筹学匈牙利法.ppt

《运筹学匈牙利法.ppt》由会员分享，可在线阅读，更多相关《运筹学匈牙利法.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、现在学习的是第1页，共26页 8 3 -2 5 0 x1.x2.x3满足约束条件（是满足约束条件（是 否否）Z 值值 (1)(2)(3)(4)(0.0.0 )(0.0.1)(0.1.0)(1.0.0)(0.1.1)(1.0.1)(1.1.0)(1.1.1)一、01 整数规划枚举法 8现在学习的是第2页，共26页首先，找到一个可行解，并计算其目标函数值；然后，以其目标值作为一个过滤条件，优于其值的再判断约束条件，直到找到最优解。二、01 整数规划隐枚举法 8 6 1 3 3 -2 5 0 x1.x2.x3满足约束条件（是满足约束条件（是 否否）过滤过滤条件条件 (1)(2)(3)(4)(0.0.

2、0 )(0.0.1)(0.1.0)(1.0.0)(0.1.1)(1.0.1)(1.1.0)(1.1.1)8思考：如果将目标函数变为下式会改进吗？现在学习的是第3页，共26页三、指派问题的匈牙利法指派问题指派问题（The Assignment ProblemThe Assignment Problem）现在学习的是第4页，共26页1 1、指派问题的形式表述、指派问题的形式表述给定了一系列所要完成的任务（给定了一系列所要完成的任务（taskstasks）以及一系列完成任务）以及一系列完成任务的被指派者（的被指派者（assigneesassignees），所需要解决的问题就是要确定出），所需要解决的

3、问题就是要确定出哪一个人被指派进行哪一项任务哪一个人被指派进行哪一项任务 2 2、指派问题的假设、指派问题的假设被指派者的数量和任务的数量是被指派者的数量和任务的数量是相同的相同的每一个被指派者只完成每一个被指派者只完成一项任务一项任务 每一项任务只能由每一项任务只能由一一个被指派者个被指派者来完成来完成 每个被指派者和每项任务的组合有一个相关成本每个被指派者和每项任务的组合有一个相关成本 目标是要确定怎样进行指派才能使得总成本最小目标是要确定怎样进行指派才能使得总成本最小 现在学习的是第5页，共26页设设n n 个个人人被被分分配配去去做做n n 件件工工作作，每每人人只只能能完完成成一一项

4、项任任务务，每每项项任任务务只只能能由由一一人人完完成成。已已知知第第i i 个个人人去去做做第第j j 件件工工作作的的的的效效率率为为C Cijij(i i=1.2=1.2n n;j j=1.2=1.2n n)并并假假设设C Cijij 00。问问应应如如何何分分配配才才能能使使总总效效率（率（时间或费用）最高？时间或费用）最高？3、指派问题模型、指派问题模型（The Model for Assignment Problem）现在学习的是第6页，共26页典型问题典型问题 例例1 1：有一份说明书，要分别译成英、日、德、：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个

5、人去完成，俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一与其中的一个人完成，每个人只能完成其中的一项工作。项工作。现在学习的是第7页，共26页问：如何分配，能使所需的总时间最少？问：如何分配，能使所需的总时间最少？甲 乙 丙 丁工作人译英文译日文译德文译俄文2 10 9 715 4 14 813 14 16 114 15 13 9 现在学习的是第8页，共26页建立模型设设 xij=10若第

6、若第i项工作交与第项工作交与第j个人完成个人完成若第若第i项工作不交与第项工作不交与第j个人完成个人完成译英文：译英文：x11+x12+x13+x14=1译日文：译日文：x21+x22+x23+x24=1译德文：译德文：x31+x32+x33+x34=1译俄文：译俄文：x41+x42+x43+x44=1甲：甲：x11+x21+x31+x41=1乙：乙：x12+x22+x32+x42=1丙：丙：x13+x23+x33+x43=1丁：丁：x14+x24+x34+x44=1xij=0或或1 (i=1,2,3,4;j=1,2,3,4)甲 乙 丙 丁工作人译英文译日文译德文译俄文2 10 9 715 4

7、 14 813 14 16 114 15 13 9 现在学习的是第9页，共26页4、指派问题的匈牙利解法、指派问题的匈牙利解法现在学习的是第10页，共26页2497第第1 1步：变换指派问题的系数矩阵（步：变换指派问题的系数矩阵（c cijij），使各行各），使各行各列中都出现列中都出现0 0元素元素(1)(1)从（从（c cijij）的每行元素都减去该行的最小元素；）的每行元素都减去该行的最小元素；(2)(2)再从所得新系数矩阵无零元素的列中减去该列的最小元素。再从所得新系数矩阵无零元素的列中减去该列的最小元素。42现在学习的是第11页，共26页在变化后的效率矩阵中找尽可能多的独立在变化后的

8、效率矩阵中找尽可能多的独立0 0元素，若能找元素，若能找出出n n个独立个独立0 0元素，就以这元素，就以这n n个独立个独立0 0元素对应解矩阵元素对应解矩阵(x xijij)中的元素为中的元素为1 1，其余为，其余为0 0，这就得到最优解。，这就得到最优解。第第2 2步：进行试指派，即确定独立零元素步：进行试指派，即确定独立零元素（1 1）从有唯一的零元素的行或列开）从有唯一的零元素的行或列开始确定独立零元素，并用始确定独立零元素，并用 表示，表示，并划掉其所在行或列的其他零。直并划掉其所在行或列的其他零。直到尽可能多的零元素都被圈出和划到尽可能多的零元素都被圈出和划掉为止。掉为止。0 0

9、（2 2）若）若独立零元素独立零元素的数目的数目m m等于矩阵的等于矩阵的阶数阶数n n，那么这指派问题的最优解已得，那么这指派问题的最优解已得到。若到。若m m n n,则转入下一步。则转入下一步。现在学习的是第12页，共26页现在学习的是第13页，共26页例例2 2 有有甲、乙、丙、丁甲、乙、丙、丁四个工人，要分别派他们完成四乡四个工人，要分别派他们完成四乡不同的任务，分别记作不同的任务，分别记作A A、B B、C C、D D。他们完成各项任务所需时间。他们完成各项任务所需时间如下表所示，问如何分派任务，可使总时间最少？如下表所示，问如何分派任务，可使总时间最少？任务任务人员人员ABCD甲

10、甲67112乙乙4598丙丙31104丁丁5982现在学习的是第14页，共26页第第1 1步，变换系数矩阵：步，变换系数矩阵：-5第第2 2步，确定独立零元素步，确定独立零元素 找到找到 3 个独立零元素，个独立零元素，但但 m=3 工作数时：假想工作数，使得与人工作数时：假想工作数，使得与人数能够匹配数能够匹配,对应的效率设定为对应的效率设定为0 0值。值。当工作数当工作数 人数时：假想人数，使得与工人数时：假想人数，使得与工作数能够匹配作数能够匹配,对应的效率设定为对应的效率设定为0 0值。值。现在学习的是第19页，共26页人数和工作数不等的指派问题人数和工作数不等的指派问题现在学习的是第

11、20页，共26页（2 2）一个人可做几项工作的指派问题）一个人可做几项工作的指派问题A1可同时做三可同时做三项工作项工作现在学习的是第21页，共26页（3）某项工作一定不能由某人做的指派问题）某项工作一定不能由某人做的指派问题A1不能做不能做B4;A3不能做不能做B3现在学习的是第22页，共26页（4）若目标函数为求）若目标函数为求max z的处理的处理(如效益）如效益）max z=-min(-z)=-min(z)等价于求解 min z =(-aij)xiji=1j=1 n n现在学习的是第23页，共26页最大化指派问题最大化指派问题最大化指派问题最大化指派问题最大值最大值最最小小化化指指派派问问题题现在学习的是第24页，共26页 学生学生A，B，C，D的各门成绩如下表，的各门成绩如下表，将该四名学生派去参加各门课的单项竞赛。将该四名学生派去参加各门课的单项竞赛。由于竞赛同时举行，故每人只能参加一项，由于竞赛同时举行，故每人只能参加一项，若以他们的成绩作为选派依据，应如何分若以他们的成绩作为选派依据，应如何分派最为有利？派最为有利？练习题练习题现在学习的是第25页，共26页感感谢谢大大家家观观看看现在学习的是第26页，共26页