运筹学匈牙利法.ppt

0 1整数规划是一种特殊形式的整数规划 这时的决策变量xi只取两个值0或1 通常用来表示逻辑性选择的决策 一般的解法为隐枚举法 例求解下列0 1规划问题 0 1整数规划的应用 8 3 2 5 0 一 0 1整数规划 枚举法 8 首先 找到一个可行解 并计算其目标函数值 然后 以其目标值作为一个过滤条件 优于其值的再判断约束条件 直到找到最优解 二 0 1整数规划 隐枚举法 8 6 1 3 3 2 5 0 8 思考 如果将目标函数变为下式会改进吗 三 指派问题的匈牙利法 指派问题 TheAssignmentProblem 1 指派问题的形式表述给定了一系列所要完成的任务 tasks 以及一系列完成任务的被指派者 assignees 所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务 2 指派问题的假设被指派者的数量和任务的数量是相同的每一个被指派者只完成一项任务每一项任务只能由一个被指派者来完成每个被指派者和每项任务的组合有一个相关成本目标是要确定怎样进行指派才能使得总成本最小 设n个人被分配去做n件工作 每人只能完成一项任务 每项任务只能由一人完成 已知第i个人去做第j件工作的的效率为Cij i 1 2 n j 1 2 n 并假设Cij 0 问应如何分配才能使总效率 时间或费用 最高 3 指派问题模型 TheModelforAssignmentProblem 典型问题 例1 有一份说明书 要分别译成英 日 德 俄四种文字 交与甲 乙 丙 丁四个人去完成 因各人专长不同 他们完成翻译不同文字所需要的时间 小时 如表所示 规定每项工作只能交与其中的一个人完成 每个人只能完成其中的一项工作 问 如何分配 能使所需的总时间最少 建立模型 设xij 1 0 若第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 1 xij 0或1 i 1 2 3 4 j 1 2 3 4 4 指派问题的匈牙利解法 2 4 9 7 第1步 变换指派问题的系数矩阵 cij 使各行各列中都出现0元素 1 从 cij 的每行元素都减去该行的最小元素 2 再从所得新系数矩阵无零元素的列中减去该列的最小元素 4 2 在变化后的效率矩阵中找尽可能多的独立0元素 若能找出n个独立0元素 就以这n个独立0元素对应解矩阵 xij 中的元素为1 其余为0 这就得到最优解 第2步 进行试指派 即确定独立零元素 2 若独立零元素的数目m等于矩阵的阶数n 那么这指派问题的最优解已得到 若m n 则转入下一步 例2有甲 乙 丙 丁四个工人 要分别派他们完成四乡不同的任务 分别记作A B C D 他们完成各项任务所需时间如下表所示 问如何分派任务 可使总时间最少 第1步 变换系数矩阵 5 第2步 确定独立零元素 找到3个独立零元素 但m 3 n 4 求解过程如下 第3步 作最少的直线覆盖所有零元素 5 对没有打 号的行画横线 有打 号的列画纵线 这就得到覆盖所有零元素的最少直线数 1 对没有独立零元素的行打 号 2 对已打 号的行中所有含划掉零元素的列打 号 3 再对打有 号的列中含独立零元素的行打 号 4 重复 2 3 直到得不出新的打 号的行 列为止 第4步 在没有被直线覆盖的所有元素中找出最小元素 然后将所在行 或列 都减去这最小元素 在出现负数的列 或行 都加上这最小元素 以保证系数矩阵中不出现负元素 新系数矩阵的最优解和原问题仍相同 转回第2步 5 5 指派问题的变形VariantsofAssignmentProblem 任务比被指派者多被指派者比要完成的任务多有一些被指派者并不能进行某一些的任务每个被指派者可以同时被指派给多个的任务 1 人数与工作数不等的处理 当人数 工作数时 假想工作数 使得与人数能够匹配 对应的效率设定为0值 当工作数 人数时 假想人数 使得与工作数能够匹配 对应的效率设定为0值 人数和工作数不等的指派问题 2 一个人可做几项工作的指派问题 A1可同时做三项工作 3 某项工作一定不能由某人做的指派问题 A1不能做B4 A3不能做B3 4 若目标函数为求maxz的处理 如效益 maxz min z min z 等价于求解minz aij xij i 1j 1 n