《运筹》教学课件整数规划第四章(五）指派问题及应用.ppt

《《运筹》教学课件整数规划第四章(五）指派问题及应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章指派问题与匈牙利法经典指派问题n个员工分配作n项工作，一致的i个员工作的j项工作的成本为cij，i=1,…,n;j=1,…,n。求最佳分配方案。指派问题的数学模型s.t.指派问题的解应对应于成本矩阵的不同行与不同列，且总成本最小例cij指派问题的性质定理：对于指派问题，成本矩阵的任一行(或列)减去(或加上)一个相同的数得到的新指派问题与原问题同解匈牙利法的基本思路：对费用矩阵C的行和列减去某个常数，将C化成有n个位于不同行不同列的零元素，令这些零元素对应的变量取1，其余变量取零，既得指派问题的最优

2、解算法和例题说明：1.书上的算法比较繁琐,且计算量大,一般教材中采用本课件提供的算法.课堂上讲的算法本质上是这种算法的变形,不再列出.例：求费用矩阵为右表的指派问题的最优解工作人费用ABCDE甲乙丙丁戊12797989666717121412151466104107106-7-6-7-6-4得4个○，且不存在没打×的0√√√第一步：每行减去最小元素，每列减掉最小元素;第二步：对零元素画圈打×;第三步:划线覆盖零元素;第四步：在没有被直线复盖的元素中找出最小元素，让打√号的列加上这个元素，打√号的行减去这

3、个元素。√√√匈牙利法的具体步骤：第一步：变换指派问题的费用矩阵，使其在各行各列都出现0元素：方法：首先每行元素减去该行的最小元素，然后每列减去该列的最小元素第二步：进行试指派（画○）方法：从含0元素最少的行或列开始，圈出一个0元素，用○表示，然后划去该○所在的行和列中的其余0元素，用×表示，依次类推。若矩阵中的○的个数等于n，则得最优解若矩阵中的○的个数

4、打√号4）重复以上步骤直到得不出新的打√号为止5）对没有打√号的行画横线，所有打√号的列画纵线，所得到的直线既是复盖所有0元素的最小直线集合第四步：在没有被直线复盖的元素中找出最小元素，让打√号的列加上这个元素，打√号的行减去这个元素。一般指派问题最大化指派问题人数和工作数不等的指派问题一个人可做几项工作的指派问题某项工作一定不能由某人做的指派问题最大化指派问题最大化指派问题最大值最小化指派问题人数和工作数不等的指派问题一个人可做几项工作的指派问题A1可同时做三项工作一个算法不适用的例子√√√√√√√√

5、线性规划有关的英文词汇Operational/operationsresearch运筹学Linearprogramming线性规划Feasibledomain可行域Convexset凸集Basicfeasiblesolutions基础可行解Simplexalgorithm单纯型法Pivot主元Pivoting主元变换Revised,dualsimplexalgorithm修正、对偶单纯型法Relativecost相对成本(机会成本)Shadowprice影子价格Slack,Surplus,Artific

6、ialvariable松弛，剩余，人工变量Unbounded,Infeasible,Degeneratesolution无界解,无可行解,退化解Duality对偶性Primal,dualproblem原问题，对偶问题Complementaryslackness互补松弛Sensitivityanalysis灵敏度分析Ttransportationproblem运输问题Assignmentproblem任务分配(指派)问题Bipartitematching两部图匹配Hungarianmethod匈牙利算法小

7、结会用分枝定界法会用割平面法会用0-1规划建模会解指派问题