运筹学匈牙利法PPT

1、第一张，PPT共二十六页，创作于2022年6月 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第二张，PPT共二十六页，创作于2022年6月首先，找到一个可行解，并计算其目标函数值；然后，以其目标值作为一个过滤条件，优于其值的再判断约束条件，直到找到最优解。二、01 整数规划隐枚举法 8 6 1 3 3 -2 5 0 x1 . x2.

2、 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思考：如果将目标函数变为下式会改进吗？第三张，PPT共二十六页，创作于2022年6月三、指派问题的匈牙利法指派问题（The Assignment Problem）第四张，PPT共二十六页，创作于2022年6月1、指派问题的形式表述给定了一系列所要完成的任务（tasks）以及一系列完成任务的被指派者（assignees），所需要解决的问题就是要确定出

3、哪一个人被指派进行哪一项任务 2、指派问题的假设被指派者的数量和任务的数量是相同的每一个被指派者只完成一项任务 每一项任务只能由一个被指派者来完成 每个被指派者和每项任务的组合有一个相关成本 目标是要确定怎样进行指派才能使得总成本最小 第五张，PPT共二十六页，创作于2022年6月设n 个人被分配去做n 件工作，每人只能完成一项任务，每项任务只能由一人完成。已知第i 个人去做第j 件工作的的效率为Cij(i=1.2n;j=1.2n)并假设Cij 0。问应如何分配才能使总效率（ 时间或费用）最高？3、指派问题模型（The Model for Assignment Problem）第六张，PPT共

4、二十六页，创作于2022年6月典型问题 例1：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。 第七张，PPT共二十六页，创作于2022年6月问：如何分配，能使所需的总时间最少？甲 乙 丙 丁工作人译英文译日文译德文译俄文2 10 9 715 4 14 813 14 16 114 15 13 9 第八张，PPT共二十六页，创作于2022年6月建立模型设 xij=10若第i项工作交与第j个人完成若第i项工作不交与第j个人完成译英文：

5、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 114 15 13 9 第九张，P

6、PT共二十六页，创作于2022年6月4、指派问题的匈牙利解法第十张，PPT共二十六页，创作于2022年6月2497第1步：变换指派问题的系数矩阵（cij），使各行各列中都出现0元素(1) 从（cij）的每行元素都减去该行的最小元素；(2)再从所得新系数矩阵无零元素的列中减去该列的最小元素。42第十一张，PPT共二十六页，创作于2022年6月在变化后的效率矩阵中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。第2步：进行试指派，即确定独立零元素（1）从有唯一的零元素的行或列开始确定独立零元素，并用 表示，并划掉其所在

7、行或列的其他零。直到尽可能多的零元素都被圈出和划掉为止。0（2）若独立零元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若m n, 则转入下一步。第十二张，PPT共二十六页，创作于2022年6月第十三张，PPT共二十六页，创作于2022年6月例2 有甲、乙、丙、丁四个工人，要分别派他们完成四乡不同的任务，分别记作A、B、C、D。他们完成各项任务所需时间如下表所示，问如何分派任务，可使总时间最少？ 任务人员ABCD甲67112乙4598丙31104丁5982第十四张，PPT共二十六页，创作于2022年6月第1步，变换系数矩阵：-5第2步，确定独立零元素 找到 3 个独立零元素， 但

8、m = 3 工作数时：假想工作数，使得与人数能够匹配, 对应的效率设定为0值。 当工作数人数时：假想人数，使得与工作数能够匹配, 对应的效率设定为0值。第十九张，PPT共二十六页，创作于2022年6月人数和工作数不等的指派问题第二十张，PPT共二十六页，创作于2022年6月（2）一个人可做几项工作的指派问题A1可同时做三项工作第二十一张，PPT共二十六页，创作于2022年6月（3）某项工作一定不能由某人做的指派问题A1不能做B4;A3不能做B3第二十二张，PPT共二十六页，创作于2022年6月（4）若目标函数为求max z的处理(如效益） max z= - min (-z ) = - min ( z)等价于求解 min z =(-aij)xiji=1j=1 n n第二十三张，PPT共二十六页，创作于2022年6月最大化指派问题最大化指派问题最大值最小化指派问题第二十四张，PPT共二十六页，创作于2022年6月 学生A，B，C