[运筹学匈牙利法.ppt

0－1 整数规划的应用 一、0－1 整数规划——枚举法 二、0－1 整数规划——隐枚举法 三、指派问题的匈牙利法 1、指派问题的形式表述 给定了一系列所要完成的任务（tasks）以及一系列完成任务的被指派者（assignees），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务 典型问题 4、指派问题的匈牙利解法 在变化后的效率矩阵中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。 求解过程如下 人数和工作数不等的指派问题 （2）一个人可做几项工作的指派问题 （3）某项工作一定不能由某人做的指派问题 最大化指派问题 0－1 整数规划是一种特殊形式的整数规划，这时的决策变量xi 只取两个值0或1， 通常用来表示逻辑性选择的决策。一般的解法为隐枚举法。 例 求解下列0－1 规划问题 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. √ √ √ √ 8 √ × √ √ × × √ √ √ × √ √ √ √ √ √ 3 √ √ √ √ -2 √ √ √ √ 5 √ √ √ √ 0 x1 . x2. x3 ( 0. 0. 0 ) ( 0. 0. 1 ) ( 0. 1. 0 ) ( 1. 0. 0 ) ( 0. 1. 1 ) ( 1. 0. 1 ) ( 1. 1. 0 ) ( 1. 1. 1 ) 满足约束条件（是∨ 否×） (1) (2) (3) (4) Z 值 √ √ √ √ 8 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 首先，找到一个可行解，并计算其目标函数值；然后，以其目标值作为一个过滤条件，优于其值的再判断约束条件，直到找到最优解。 √ √ √ √ 8 6 1 3 3 -2 √ √ √ √ 5 √ √ √ √ 0 x1 . x2. x3 ( 0. 0. 0 ) ( 0. 0. 1 ) ( 0. 1. 0 ) ( 1. 0. 0 ) ( 0. 1. 1 ) ( 1. 0. 1 ) ( 1. 1. 0 ) ( 1. 1. 1 ) 满足约束条件（是∨ 否×） (1) (2) (3) (4) 过滤条件 √ √ √ √ 8 思考：如果将目标函数变为下式会改进吗？ Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 指派问题（The Assignment Problem） Evaluation only. Created with Aspose.Slides for .NET 3.5 Cl