运筹学匈牙利法ppt课件.ppt

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

1、 0 01 1 整整数数规规划划是是一一种种特特殊殊形形式式的的整整数数规规划划，这这时时的的决决策策变变量量xi 只只取取两两个个值值0 0或或1 1，通通常常用用来来表表示示逻逻辑辑性性选选择择的决策。一般的解法为隐枚举法。的决策。一般的解法为隐枚举法。例例 求解下列求解下列01 规划问题规划问题01 整数规划的应用 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、并计算其目标函数值；然后，以其目标值作为一个过滤条件，优于其值的再判断约束条件，直到找到最优解。二、01 整数规划隐枚举法 8 6 1 3 3 -2 5 0 x1.x2.x3满足约束条件（是满足约束条件（是 否否）过滤过滤条件条件 (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)8思考：如果将目标函数变为下式会改进吗？三、指派问题的匈牙利法指派问题指派问题（The Assignment ProblemThe Assignment Problem）1 1、指派问题的形式表述、指派问题的形式表述给定了一系列所

3、要完成的任务（给定了一系列所要完成的任务（taskstasks）以及一系列完成）以及一系列完成任务的被指派者（任务的被指派者（assigneesassignees），所需要解决的问题就是），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务要确定出哪一个人被指派进行哪一项任务 2 2、指派问题的假设、指派问题的假设被指派者的数量和任务的数量是被指派者的数量和任务的数量是相同的相同的每一个被指派者只完成每一个被指派者只完成一项任务一项任务 每一项任务只能由每一项任务只能由一一个被指派者个被指派者来完成来完成 每个被指派者和每项任务的组合有一个相关成本每个被指派者和每项任务的组合有一个相关成

4、本 目标是要确定怎样进行指派才能使得总成本最小目标是要确定怎样进行指派才能使得总成本最小 设设n n 个个人人被被分分配配去去做做n n 件件工工作作，每每人人只只能能完完成成一一项项任任务务，每每项项任任务务只只能能由由一一人人完完成成。已已知知第第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

5、Problem）典型问题典型问题 例例1 1：有一份说明书，要分别译成英、日、：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。每个人只能完成其中的一项工作。问：如何分配，能使所需的总时间最少？问：如何分配，能使所需的总时间最少？甲 乙 丙 丁工作人译英文译日文译德文译俄文2 10

6、 9 715 4 14 813 14 16 114 15 13 9 建立模型设设 xij=10若第若第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

7、,3,4;j=1,2,3,4)甲 乙 丙 丁工作人译英文译日文译德文译俄文2 10 9 715 4 14 813 14 16 114 15 13 9 4、指派问题的匈牙利解法、指派问题的匈牙利解法2497第第1 1步：变换指派问题的系数矩阵（步：变换指派问题的系数矩阵（c cijij），使各行），使各行各列中都出现各列中都出现0 0元素元素(1)(1)从（从（c cijij）的每行元素都减去该行的最小元素；）的每行元素都减去该行的最小元素；(2)(2)再从所得新系数矩阵无零元素的列中减去该列的最小元素。再从所得新系数矩阵无零元素的列中减去该列的最小元素。42在变化后的效率矩阵中找尽可能多的独立

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

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

10、第第1 1步，变换系数矩阵：步，变换系数矩阵：-5第第2 2步，确定独立零元素步，确定独立零元素 找到找到 3 个独立零元素，个独立零元素，但但 m=3 工作数时：假想工作数，使得工作数时：假想工作数，使得与人数能够匹配与人数能够匹配,对应的效率设定为对应的效率设定为0 0值。值。当工作数当工作数 人数时：假想人数，使得与人数时：假想人数，使得与工作数能够匹配工作数能够匹配,对应的效率设定为对应的效率设定为0 0值。值。人数和工作数不等的指派问题人数和工作数不等的指派问题（2 2）一个人可做几项工作的指派问题）一个人可做几项工作的指派问题A1可同时做可同时做三项工作三项工作（3）某项工作一定不

11、能由某人做的指派问题）某项工作一定不能由某人做的指派问题A1不能做不能做B4;A3不能做不能做B3（4）若目标函数为求）若目标函数为求max z的处理的处理(如效益）如效益）max z=-min(-z)=-min(z)等价于求解 min z =(-aij)xiji=1j=1 n n最大化指派问题最大化指派问题最大化指派问题最大化指派问题最大值最大值最最小小化化指指派派问问题题 学生学生A，B，C，D的各门成绩如下的各门成绩如下表，将该四名学生派去参加各门课的单表，将该四名学生派去参加各门课的单项竞赛。由于竞赛同时举行，故每人只项竞赛。由于竞赛同时举行，故每人只能参加一项，若以他们的成绩作为选派能参加一项，若以他们的成绩作为选派依据，应如何分派最为有利？依据，应如何分派最为有利？练习题练习题数学物理化学英语A89926881B87886578C95708572D75788996