运筹学04-整数规划-匈牙利解法.ppt

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

1、第四章整数规划例：有甲、乙、丙、丁四个熟练工人，他们都是多面手，有4个任务要他们完成，若规定每人只分配一次任务，而每项任务只能由一个人完成，每人未完成每项任务的工时耗费如表所示，问如何分配使完成任务的总工时耗费最少？零件机床ABCD机床甲41821乙98471丙84631丁65721零件1111表任务分配工时耗费表第四章整数规划B、任务分配问题的数学模型设：xij为第i个工人分配去做第j项任务aij为第i个工人为完成第j项任务时的工时消耗。则当分配第j项任务给第i个工人时当不分配第j项任务给第i个工人时i,j=1,2,…,n由于每人只允许分配一项任务

2、，且每项任务只能由一人来完成，故其数学模型、目标函数及约束条件如下：第四章整数规划C、任务分配问题的解法-----匈牙利解法匈牙利数学家考尼格（Konig）提出的，得名匈牙利解法（theHungarianMethodofAssignment）1、匈牙利解法的基本思想---适用条件基于任务分配问题的标准型，标准型要满足下述三个条件：（1）目标要求为min（2）效率矩阵{aij}为n阶方阵（3）阵中所有元素aij≥0,且为常数定理1设一个任务分配问题的效率矩阵为{aij}，若{aij}中每一行元素分别减去一个常数ui，每一列元素分别减去一个常数vj，得到

3、一个新的效率矩阵{bij}，其中一个元素bij=aij-ui-vj，则{bij}的最优解等价于{aij}的最优解。第四章整数规划2、匈牙利解法的基本思路：（1）按照定理1中所述方法不断变化效率，设法在原有效率矩阵基础上经变换后找出一组有m个不同行、不同列零元素的新效率矩阵。（2）新效率矩阵中，令对应于不同行、不同列的的那组零元素所对应的xij=1，其余xij=0，由此计算出目标函数为：这样得到新效率矩阵的最优解，根据定理1，他也是原问题的最优解。（3）验证最优解的方法：设法用最少的直线数覆盖方阵中位于不同行、不同列的零元素。如果覆盖所有零元素的最少直

4、线数等于m，则得到最优解，否则不是定理2若一个方阵中的一部分元素为零，一部分元素非零，则覆盖方阵中所有元素的最少直线等于位于不同行、不同列的零元素最多个数。第四章整数规划3、匈牙利解法的计算步骤：第一步：效率矩阵的初始变换----零元素的获得（1）行变换：找出每行的最小元素，该行各元素减去这个最小元素。（2）列变换：找出每列的最小元素，该列各元素减去这个最小元素。经变换后的效率矩阵，其每行、每列至少有一个零元素。第二步：最优性检验检查能否找到m个位于不同行、不同列的零元素，即检查覆盖所有零元素的直线是否为m条表效率矩阵的初始变换//第四章整数规划3、

5、匈牙利解法的计算步骤：（1）逐行检查：从第一行开始，如果该行只有一个零元素，就在这个零元素上打上括号，并划去打括号零元素同列的其他零元素。如果该行没有零元素，或有两个或多个零元素（已划去的不记在内），则转下行（2）逐列检查：依照行检查的方法从第一列开始逐列检查。表最优性检验ïïþïïýüïïîïïíìÞïïþïïýüïïîïïíì0531)0(3123)0(4217000531031230421700）（第四章整数规划①每行都有一个零元素标有括号，显然这些括号零在不同行和不同列，因此得到最优解。②每行、每列都有两个或更多的零，这是从剩有零元素最少的行

6、开始，比较这行各零元素所在列中零元素的个数，选择零元素少的那列的这个零元素打括号，划掉同行同列的其他零元素，然后重复以上步骤，直到所有零都做了标记。③矩阵中所有零都做了标记，但标有（）的零元素个数少于m，此时就可以找出能覆盖矩阵中所有零元素的最少直线的集合。步骤如下：最优性检验后可能可能出现的情况////第四章整数规划步骤如下：对无（）的行打√对打√行上所有零元素的列打√在打√的列上有（）的行打√重复步骤，直到过程结束对没有打√的行划横线，对所有打√的列划垂线，这时得到覆盖矩阵中所有零的最少直线数第四章整数规划3、匈牙利解法的计算步骤：第三步：非最优

7、阵的变换——零元素的移动当表中的覆盖所有零的直线数小于m时，得到的不是最优解，因此需要对表中矩阵进一步进行变换，过程如下：①在未被直线覆盖的所有元素中找出最小元素②所有未被直线覆盖的元素都减去这个最小元素③覆盖线十字交叉处的元素都加上这个最小元素④只有一条直线覆盖的元素的值保持不变。由此，得到新的效率矩阵，以此更易标出m个不同的行和列的零元素。表非最优阵的变换////////////////第四章整数规划3、匈牙利解法的计算步骤：第四步：重新标号抹掉原来的标号，回到最优性检验，并进行重新标号，直到得到最优解表试分配过程第四章整数规划D、目标函数为最大

8、的任务分配问题如果目标函数为MAX型，则不属于标准的任务分配模型，不能直接运用匈牙利解法求解，这就需要先对m