《运筹学匈牙利法精选课件.ppt》由会员分享，可在线阅读，更多相关《运筹学匈牙利法精选课件.ppt（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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第二页，本课件共有26页首先，找到一个可行解，并计算其目标函数值；然后，以其目标值作为一个过滤条件，优于其值的再判断约束条件，直到找到最优解。二、01 整数规划隐枚举法 8 6 1 3 3 -2 5 0 x1.x2.x3满足约束条件（是满足约束条件（是 否否）过滤过滤条件条件 (1)(2)(3)(4)(0.0.0 )(
2、0.0.1)(0.1.0)(1.0.0)(0.1.1)(1.0.1)(1.1.0)(1.1.1)8思考：如果将目标函数变为下式会改进吗？第三页，本课件共有26页三、指派问题的匈牙利法指派问题指派问题（The Assignment ProblemThe Assignment Problem）第四页，本课件共有26页1 1、指派问题的形式表述、指派问题的形式表述给定了一系列所要完成的任务（给定了一系列所要完成的任务（taskstasks）以及一系列完成任）以及一系列完成任务的被指派者（务的被指派者（assigneesassignees），所需要解决的问题就是要确定），所需要解决的问题就是要确定出哪
3、一个人被指派进行哪一项任务出哪一个人被指派进行哪一项任务 2 2、指派问题的假设、指派问题的假设被指派者的数量和任务的数量是被指派者的数量和任务的数量是相同的相同的每一个被指派者只完成每一个被指派者只完成一项任务一项任务 每一项任务只能由每一项任务只能由一一个被指派者个被指派者来完成来完成 每个被指派者和每项任务的组合有一个相关成本每个被指派者和每项任务的组合有一个相关成本 目标是要确定怎样进行指派才能使得总成本最小目标是要确定怎样进行指派才能使得总成本最小 第五页，本课件共有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）第六页，本课件共有26页典型问题典型问题 例例1 1：有一份说明书，要分别译成英、日、德、：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，俄四种文字，交
5、与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一与其中的一个人完成，每个人只能完成其中的一项工作。项工作。第七页，本课件共有26页问：如何分配，能使所需的总时间最少？问：如何分配，能使所需的总时间最少？甲 乙 丙 丁工作人译英文译日文译德文译俄文2 10 9 715 4 14 813 14 16 114 15 13 9 第八页，本课件共有26页建立模型设设 xij=10若第若第i项工作交与第项工作交与第j
6、个人完成个人完成若第若第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 14 813 14 16 11
7、4 15 13 9 第九页，本课件共有26页4、指派问题的匈牙利解法、指派问题的匈牙利解法第十页，本课件共有26页2497第第1 1步：变换指派问题的系数矩阵（步：变换指派问题的系数矩阵（c cijij），使各行各），使各行各列中都出现列中都出现0 0元素元素(1)(1)从（从（c cijij）的每行元素都减去该行的最小元素；）的每行元素都减去该行的最小元素；(2)(2)再从所得新系数矩阵无零元素的列中减去该列的最小元素。再从所得新系数矩阵无零元素的列中减去该列的最小元素。42第十一页，本课件共有26页在变化后的效率矩阵中找尽可能多的独立在变化后的效率矩阵中找尽可能多的独立0 0元素，若能元素
8、，若能找出找出n n个独立个独立0 0元素，就以这元素，就以这n n个独立个独立0 0元素对应解矩阵元素对应解矩阵(x xijij)中的元素为中的元素为1 1，其余为，其余为0 0，这就得到最优解。，这就得到最优解。第第2 2步：进行试指派，即确定独立零元素步：进行试指派，即确定独立零元素（1 1）从有唯一的零元素的行或列开）从有唯一的零元素的行或列开始确定独立零元素，并用始确定独立零元素，并用 表示，表示，并划掉其所在行或列的其他零。直并划掉其所在行或列的其他零。直到尽可能多的零元素都被圈出和划到尽可能多的零元素都被圈出和划掉为止。掉为止。0 0（2 2）若）若独立零元素独立零元素的数目的数
9、目m m等于矩阵等于矩阵的阶数的阶数n n，那么这指派问题的最优解，那么这指派问题的最优解已得到。若已得到。若m m n n,则转入下一步。则转入下一步。第十二页，本课件共有26页第十三页，本课件共有26页例例2 2 有有甲、乙、丙、丁甲、乙、丙、丁四个工人，要分别派他们完成四个工人，要分别派他们完成四乡不同的任务，分别记作四乡不同的任务，分别记作A A、B B、C C、D D。他们完成各项任务。他们完成各项任务所需时间如下表所示，问如何分派任务，可使总时间最少所需时间如下表所示，问如何分派任务，可使总时间最少？任务任务人员人员ABCD甲甲67112乙乙4598丙丙31104丁丁5982第十四
10、页，本课件共有26页第第1 1步，变换系数矩阵：步，变换系数矩阵：-5第第2 2步，确定独立零元素步，确定独立零元素 找到找到 3 个独立零元素，个独立零元素，但但 m=3 工作数时：假想工作数，使得与人工作数时：假想工作数，使得与人数能够匹配数能够匹配,对应的效率设定为对应的效率设定为0 0值。值。当工作数当工作数 人数时：假想人数，使得与工人数时：假想人数，使得与工作数能够匹配作数能够匹配,对应的效率设定为对应的效率设定为0 0值。值。第十九页，本课件共有26页人数和工作数不等的指派问题人数和工作数不等的指派问题第二十页，本课件共有26页（2 2）一个人可做几项工作的指派问题）一个人可做几
11、项工作的指派问题A1可同时做三可同时做三项工作项工作第二十一页，本课件共有26页（3）某项工作一定不能由某人做的指派问题）某项工作一定不能由某人做的指派问题A1不能做不能做B4;A3不能做不能做B3第二十二页，本课件共有26页（4）若目标函数为求）若目标函数为求max z的处理的处理(如效益）如效益）max z=-min(-z)=-min(z)等价于求解 min z =(-aij)xiji=1j=1 n n第二十三页，本课件共有26页最大化指派问题最大化指派问题最大化指派问题最大化指派问题最大值最大值最最小小化化指指派派问问题题第二十四页，本课件共有26页 学生学生A，B，C，D的各门成绩如下表，的各门成绩如下表，将该四名学生派去参加各门课的单项竞将该四名学生派去参加各门课的单项竞赛。由于竞赛同时举行，故每人只能参赛。由于竞赛同时举行，故每人只能参加一项，若以他们的成绩作为选派依据，加一项，若以他们的成绩作为选派依据，应如何分派最为有利？应如何分派最为有利？练习题练习题第二十五页，本课件共有26页感感谢谢大大家家观观看看第二十六页，本课件共有26页