运筹学匈牙利法.ppt

《运筹学匈牙利法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、0－1整数规划是一种特殊形式的整数规划，这时的决策变量xi只取两个值0或1，通常用来表示逻辑性选择的决策。一般的解法为隐枚举法。例求解下列0－1规划问题0－1整数规划的应用√√√√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、优于其值的再判断约束条件，直到找到最优解。二、0－1整数规划——隐枚举法√√√√86133-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思考：如果将目标函数变为下式会改进吗？三、指派问题的匈牙利法指派问题（TheAssignmentProblem）1、指派问题的形式表述给定了一系列所要完成的任务（tasks）以及一系列完成任务的被指派者（assignees），所需要解

3、决的问题就是要确定出哪一个人被指派进行哪一项任务2、指派问题的假设被指派者的数量和任务的数量是相同的每一个被指派者只完成一项任务每一项任务只能由一个被指派者来完成每个被指派者和每项任务的组合有一个相关成本目标是要确定怎样进行指派才能使得总成本最小设n个人被分配去做n件工作，每人只能完成一项任务，每项任务只能由一人完成。已知第i个人去做第j件工作的的效率为Cij(i=1.2…n;j=1.2…n)并假设Cij≥0。问应如何分配才能使总效率（时间或费用）最高？3、指派问题模型（TheModelforAssignmentProblem）典型问题

4、例1：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。问：如何分配，能使所需的总时间最少？甲乙丙丁工作人译英文译日文译德文译俄文2109715414813141611415139建立模型设xij=10若第i项工作交与第j个人完成若第i项工作不交与第j个人完成译英文：x11+x12+x13+x14=1译日文：x21+x22+x23+x24=1译德文：x31+x32+x33+x

5、34=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)甲乙丙丁工作人译英文译日文译德文译俄文21097154148131416114151394、指派问题的匈牙利解法2497第1步：变换指派问题的系数矩阵（cij），使各行各列中都出现0元素(1)从（cij）的每行元素都减去该行的最小元素；(2)再从所得新系数矩阵无零元素的列中减去该列的

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

7、所示，问如何分派任务，可使总时间最少？任务人员ABCD甲67112乙4598丙31104丁5982第1步，变换系数矩阵：-5第2步，确定独立零元素找到3个独立零元素，但m=3

8、素中找出最小元素，然后将所在行（或列）都减去这最小元素；在出现负数的列（或行）都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第2步。-5√√√5、指派问题的变形Va