运筹学匈牙利算法示例

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

1、匈牙利算法示例信管网(www.cnitpm.com)：最专业信息系统项目管理师网站（二）、解题步骤：指派问题是0-1规划的特例，也是运输问题的特例，当然可用整数规划，0-1规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是匈牙利法，即系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。第一步：变换指派问题的系数矩阵（cij）为(bij)，使在(bij)的各行各列中都出现0元素，即(1)从（cij）的每行元素都减去该行的最小元素；(2)再从所得新系数矩阵的每列元素中减去该列的最小

2、元素。第二步：进行试指派，以寻求最优解。在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为：(1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎。然后划去◎所在列(行)的其它0元素，记作Ø；这表示这列所代表的任务已指派完，不必再考虑别人了。(2)给只有一个0元素的列(行)中的0元素加圈，记作◎；然后划去◎所在行的0元素，记作Ø．(3)反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止。(4)若仍有没有划圈的0元素

3、，且同行(列)的0元素至少有两个，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。（5）若◎元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若m

4、(5)对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最少直线数l。l应等于m，若不相等，说明试指派过程有误，回到第二步(4)，另行试指派；若l＝m

5、最小元素（选择次小元素）时的费用增加，可给出最优或近似最优的方案，因此它是一种十分有效的方法。伏格尔法把费用增量定义为给定行或列次小元素与最小元素的差（如果存在两个或两个以上的最小元素费用增量定义为零）。最大差对应的行或列中的最小元素确定了产品的供应关系，即优先避免最大的费用增量发生。当产地或销地中的一方在数量上供应完毕或得到满足时，划去运价表中对应的行或列，再重复上述步骤，即可得到一个初始的基可行解。仍以例4-1来说明伏格尔法。第一步：在表4-1中找出每行、每列两个最小元素的差额，并填入该表的最右列和最下行，见表4-12伏格尔法例一：甲乙丙丁两最小元

6、素之差A3113100B19281C741051两最小元素之差2513例一：第二步：从行和列的差额中选出最大者，选择它所在的行或列中的最小元素的位置确定供应关系。在表4-12中乙列是最大差额“5”所在的列，乙列中的最小元素是“4”，从而确定了C与乙间的供应关系，表4-13即反应了这一供应关系。同最小元素法一样，由于乙的需求已得到了满足，将运价表中的乙列划去。第三步：对运价表中未划去的元素再分别计算出各行、各列两个最小运费的差，并填入该表的最右列和最下行，见表4-14。重复第一、第二两步，直到给出一个初始基可行解，例一：任务人员ABCD甲215134乙10

7、41415丙9141613丁78119249742◎Ø◎ØØ◎◎有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？任务人员ABCD甲67112乙4598丙31104丁5982例二、求解过程如下：第一步，变换系数矩阵：－5第二步，试指派：◎◎◎ØØ找到3个独立零元素但m=3

8、素：没有被直线覆盖的所有元素中的最小元素为1，然后打√各行都减去1；打√各列都加