运筹学匈牙利法

√√

√

√8√×

√

√

×

×

√

√√×

√

√

√√

√

√3√√

√

√-2√√

√

√5√√

√

√0x1.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)一、0－1整数规划——枚举法

√√

√

√8第2页,共26页，星期六，2024年，5月首先，找到一个可行解，并计算其目标函数值；然后，以其目标值作为一个过滤条件，优于其值的再判断约束条件，直到找到最优解。二、0－1整数规划——隐枚举法

√√

√

√86

13

3

-2√√

√

√5√√

√

√0x1.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思考：如果将目标函数变为下式会改进吗？第3页,共26页，星期六，2024年，5月三、指派问题的匈牙利法指派问题（TheAssignmentProblem）第4页,共26页，星期六，2024年，5月1、指派问题的形式表述给定了一系列所要完成的任务（tasks）以及一系列完成任务的被指派者（assignees），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务

2、指派问题的假设被指派者的数量和任务的数量是相同的每一个被指派者只完成一项任务

每一项任务只能由一个被指派者来完成每个被指派者和每项任务的组合有一个相关成本目标是要确定怎样进行指派才能使得总成本最小第5页,共26页，星期六，2024年，5月设n个人被分配去做n件工作，每人只能完成一项任务，每项任务只能由一人完成。已知第i个人去做第j件工作的的效率为Cij(i=1.2…n;j=1.2…n)并假设Cij≥0。问应如何分配才能使总效率（时间或费用）最高？3、指派问题模型（TheModelforAssignmentProblem）第6页,共26页，星期六，2024年，5月典型问题例1：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。

第7页,共26页，星期六，2024年，5月问：如何分配，能使所需的总时间最少？甲乙丙丁工作人译英文译日文译德文译俄文2109715414813141611415139第8页,共26页，星期六，2024年，5月建立模型设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,3,4;j=1,2,3,4)甲乙丙丁工作人译英文译日文译德文译俄文2109715414813141611415139第9页,共26页，星期六，2024年，5月4、指派问题的匈牙利解法第10页,共26页，星期六，2024年，5月2497第1步：变换指派问题的系数矩阵（cij），使各行各列中都出现0元素(1)从（cij）的每行元素都减去该行的最小元素；(2)再从所得新系数矩阵无零元素的列中减去该列的最小元素。42第11页,共26页，星期六，2024年，5月

在变化后的效率矩阵中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。第2步：进行试指派，即确定独立零元素（1）从有唯一的零元素的行或列开始确定独立零元素，并用表示，并划掉其所在行或列的其他零。直到尽可能多的零元素都被圈出和划掉为止。0（2）若独立零元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若m<n,则转入下一步。第12页,共26页，星期六，2024年，5月第13页,共26页，星期六，2024年，5月例2有甲、乙、丙、丁四个工人，要分别派他们完成四乡不同的任务，分别记作A、B、C、D。他们完成各项任务所需时间如下表所示，问如何分派任务，可使总时间最少？

任务人员ABCD甲67112乙4598丙31104丁5982第14页,共26页，星期六，2024年，5月第1步，变换系数矩阵：-5第2步，确定独立零元素找到3个独立零元素，但m=3<n=4求解过程如下第3步，作最少的直线覆盖所有零元素：(5)对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有零元素的最少直线数(1)对没有独立零元素的行打√号；√(2)对已打√号的行中所有含划掉零元素的列打√号；√(3)再对打有√号的列中含独立零元素的行打√号；(4)重复(2)，(3)直到得不出新的打√号的行、列为止；√第15页,共26页，星期六，2024年，5月第4步：在没有被直线覆盖的所有元素中找出最小元素，然后将所在行（或列）都减去这最小元素；在出现负数的列（或行）都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第2步。

第16页,共26页，星期六，2024年，5月-5√√√第17页,共26页，星期六，2024年，5月5、指派问题的变形

VariantsofAssignmentProblem任务比被指派者多被指派者比要完成的任务多有一些被指派者并不能进行某一些的任务每个被指派者可以同时被指派给多个的任务第18页,共26页，星期六，2024年，5月（1）人数与工作数不等的处理当人数>工作数时：假想工作数，使得与人数能够匹配,对应的效率设定为0值。当工作数>人数时：假想人数，使得与工作数能够匹配,对应的效率设定为0值。第19页,共26页，星期六，2024年，5月人数和工作数不等的指派问题第20页,共26页，星期六，2024年，5月（2）一个人可做几项工作的指派问题A1可同时做三项工作第21页,共26页，星期六，2024年，5月（3）某项工作一定不能由某人做的指派问题A1不能做B4;A3不能做B3第22页,共26页，星期六，2024年，5月（4）若目标函数为求maxz的处理(如效益）∵maxz=-min(-z)=-min(z

)∴等价于求解minz

=∑∑(-aij)xiji=1j=1nn第23页,共26页，星期六，2024