《运筹学04-整数规划-匈牙利解法》由会员分享，可在线阅读，更多相关《运筹学04-整数规划-匈牙利解法（25页珍藏版）》请在金锄头文库上搜索。
1、,第四章 整数规划,例：有甲、乙、丙、丁四个熟练工人，他们都是多面手，有4个任务要他们完成，若规定每人只分配一次任务，而每项任务只能由一个人完成，每人未完成每项任务的工时耗费如表所示，问如何分配使完成任务的总工时耗费最少？,表 任务分配工时耗费表,第四章 整数规划,B、任务分配问题的数学模型,设：xij为第i个工人分配去做第j项任务 aij为第i个工人为完成第 j 项任务时的工时消耗。则,当分配第j项任务给第i个工人时,当不分配第j项任务给第i个工人时,i,j=1,2,n,由于每人只允许分配一项任务， 且每项任务只能由一人来完成， 故其数学模型、目标函数及约束条件如下：,第四章 整数规划,C、
2、任务分配问题的解法-匈牙利解法,匈牙利数学家考尼格（Konig）提出的，得名匈牙利解法 （the Hungarian Method of Assignment）,1、匈牙利解法的基本思想-适用条件 基于任务分配问题的标准型，标准型要满足下述三个条件： （1）目标要求为min （2）效率矩阵aij为n阶方阵 （3）阵中所有元素aij0,且为常数,定理1 设一个任务分配问题的效率矩阵为aij，若aij中每一行元素分别减去一个常数ui，每一列元素分别减去一个常数vj，得到一个新的效率矩阵bij，其中一个元素bij=aij-ui-vj，则bij的最优解等价于aij的最优解。,第四章 整数规划,2、匈牙
3、利解法的基本思路： （1）按照定理1中所述方法不断变化效率，设法在原有效率矩阵基础上经 变换后找出一组有m个不同行、不同列零元素的新效率矩阵。 （2）新效率矩阵中，令对应于不同行、不同列的的那组零元素所对应的 xij=1，其余xij=0，由此计算出目标函数为： 这样得到新效率矩阵的最优解，根据定理 1，他也是原问题的最优解。 （3）验证最优解的方法：设法用最少的直线数覆盖方阵中位于不同行、 不同列的零元素。 如果覆盖所有零元素的最少直线数等于m，则得到最优解，否则不是,定理2 若一个方阵中的一部分元素为零，一部分元素非零，则覆盖方阵中所 有元素的最少直线等于位于不同行、不同列的零元素最多个数。
4、,第四章 整数规划,3、匈牙利解法的计算步骤：,第一步：效率矩阵的初始变换-零元素的获得 （1）行变换：找出每行的最小元素，该行各元素减去这个最小元素。 （2）列变换：找出每列的最小元素，该列各元素减去这个最小元素。 经变换后的效率矩阵，其每行、每列至少有一个零元素。,第二步：最优性检验 检查能否找到m个位于不同行、不同列的零元素，即检查覆盖所有零元 素的直线是否为m条,表 效率 矩阵 的 初始 变换,/,/,第四章 整数规划,3、匈牙利解法的计算步骤：,（1）逐行检查：从第一行开始，如果该行只有一个零元素，就在这个 零元素上打上括号，并划去打括号零元素同列的其他零元素。 如果该行没有零元素，
5、或有两个或多个零元素（已划去的不记在 内），则转下行 （2）逐列检查：依照行检查的方法从第一列开始逐列检查。,表 最优性检验,第四章 整数规划, 每行都有一个零元素标有括号，显然这些括号零在不同行 和不同列，因此得到最优解。 每行、每列都有两个或更多的零，这是从剩有零元素最少的 行开始，比较这行各零元素所在列中零元素的个数，选择零 元素少的那列的这个零元素打括号，划掉同行同列的其他零 元素，然后重复以上步骤，直到所有零都做了标记。 矩阵中所有零都做了标记，但标有（）的零元素个数少于 m，此时就可以找出能覆盖矩阵中所有零元素的最少直线的 集合。 步骤如下：,最优性检验后可能可能出现的情况,/,/
6、,第四章 整数规划,步骤如下： 对无（）的行打 对打行上所有零元素的列打 在打的列上有（）的行打 重复步骤，直到过程结束 对没有打的行划横线，对所有打的列划垂线，这时得 到覆盖矩阵中所有零的最少直线数,第四章 整数规划,3、匈牙利解法的计算步骤：,第三步：非最优阵的变换零元素的移动 当表中的覆盖所有零的直线数小于m时，得到的不是最优解，因此需要 对表中矩阵进一步进行变换，过程如下： 在未被直线覆盖的所有元素中找出最小元素 所有未被直线覆盖的元素都减去这个最小元素 覆盖线十字交叉处的元素都加上这个最小元素 只有一条直线覆盖的元素的值保持不变。 由此，得到新的效率矩阵，以此更易标出m个不同的行和列
7、的零元素。,表 非最优阵的变换,/,/,/,/,/,/,/,/,第四章 整数规划,3、匈牙利解法的计算步骤：,第四步：重新标号 抹掉原来的标号，回到最优性检验，并进行重新标号，直到得到最优解,表 试分配过程,第四章 整数规划,D、目标函数为最大的任务分配问题,如果目标函数为MAX型，则不属于标准的任务分配模型，不能直接运用匈牙利解法求解，这就需要先对max模型进行变换，然后再求解。,例：有甲、乙、丙、丁4人分别操作4台机器，每个工人操作不 同机器时的产值如表，求对4个工人分配不同机器时总产 值最大的方案。,由于maxf(x)与求 -min-f(x)相同，所以将max型的效率矩阵aij变为 ai
8、j求min问题，如下页表,第四章 整数规划,表 任务分配的权益表,表 变换为求最大问题,第四章 整数规划,求解过程,表所示，最终表为最优解，此时甲D，乙B，丙A，丁C 目标函数为 maxf(x)=15+7+13+15=50,分配问题与匈牙利法,非标准型的指派问题：,匈牙利法的条件是：模型求最小值、效率cij0。 当遇到各种非标准形式的指派问题时，处理方法是先将其转化为标准形式，然后用匈牙利法来求解。,分配问题与匈牙利法,1. 最大化指派问题,处理方法：设m为最大化指派问题系数矩阵C中最大元素。令矩阵B（m-cij）nn则以B为系数矩阵的最小化指派问题和原问题有相同的最优解。,例 某人事部门拟招
9、聘4人任职4项工作，对他们综合考评的 得分如下表（满分100分），如何安排工作使总分最多。,分配问题与匈牙利法,解: M95，令,用匈牙利法求解C，最优解为：,即甲安排做第二项工作、乙做第一项、丙做第四项、丁做第三项, 最高总分Z92959080357,分配问题与匈牙利法,2. 不平衡的指派问题,当人数m大于工作数n时，加上mn项虚拟工作，例如：,当人数m小于工作数n时，加上nm个人，例如,分配问题与匈牙利法,3. 一个人可做几件事的指派问题,若某人可做几件事，则将该人化作相同的几个“人”来接受指派，且费用系数取值相同。,例如：丙可以同时任职A和C工作，求最优指派方案。,分配问题与匈牙利法,4
10、. 某事一定不能由某人做的指派问题,将该人做此事的效率系数取做足够大的数，可用M表示。,例 分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务。每个人完成各项任务的时间如表所示。由于任务数多于人数，考虑任务E必须完成，其他4项中可任选3项完成。试确定最优分配方案，使完成任务的总时间最少。,分配问题与匈牙利法,解: 1) 这是不平衡的指派问题，首先转换为标准型，再用匈牙利法求解。 2) 由于任务数多于人数，所以假定一名虚拟人，设为戊。因为工作E必须完成，故设戊完成E的时间为M（M为非常大的数），其余效率系数为0，则标准型的效率矩阵表示为：,分配问题与匈牙利法,用匈牙利法求出最优指派方案为：,即甲B，乙D，丙E，丁A, 任务C放弃。 最少时间为105。,补充例题- 匈牙利法,匈牙利法主要解决指派问题， 指派问题是一种特殊的“0 1”规划。 例： 指派授课问题，现有A、B、C、D四门课程，需由甲、乙、丙、丁四人讲授，并且规定： 每人只讲且必须讲门课。 每门课必须且只需人讲。 四人分别讲每门课的费用示于下表中：,匈牙利法 （2）,授 课 费 用 表,求何人讲何门课才能使总费用最低？,分配问题与匈牙利法,课堂练习：用匈牙利法求解下列指派问题。,练习1：,练习2：,分配问题与匈牙利法,48,21,答案：,
