指派问题市公开课一等奖省赛课获奖课件

指派问题（AssignmentProblem,AP）是一个特殊线性规划问题，也属于0-1整数规划问题.5.5指派问题问题描述：在实际中经常会碰到这么问题，有n项不一样任务，需要n个人分别完成其中一项，但因为任务性质和各人专长不一样，所以各人去完成不一样任务效率（或花费时间或费用）也就不一样。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成n项任务总效率最高（或所需时间最少），这类问题称为指派问题或分配问题。指派问题第1页x3x1x2y2y1y3x4x5y4y5

该问题也可用矩阵表示假如xi

会做yj不然1111111111000000000000000

在矩阵中寻找什么？寻找最多不一样行不同列1元素.指派问题第2页指派问题数学模型设n个人被分配去做n件工作，要求每个人只做一件工作，每件工作只有一个人去做。已知第i个人去做第j件工作效率（时间或费用）为Cij(i=1.2…n;j=1.2…n)并假设Cij≥0。问应怎样分配才能使总效率（时间或费用）最高？指派问题第3页任务人员EJGRA215134B1041415C9141613D78119

Example

有一份汉字说明书需要译成英、日、德、俄四种语言，分别记为E、J、G、R.现有A、B、C、D

四人，他们将汉字翻译成不一样语言所需时间如表,问应分配何人去完成何任务（一人完成一项任务），使所需总时间最少？指派问题第4页设决议变量1分配第i个人去做第j件工作

xij=0相反(i,j=1.2.…n)其数学模型为：指派问题第5页

显然，这是一个0-1规划问题，

也是一个特殊运输问题

任务人员EJGRaiA2151341B10414151C91416131D781191bj1111

所以,分配问题可用解IP问题方法（如：分支定界法),或解运输问题表上作业法.

因为算法引用了匈牙利数学家König结论,所以，该算法也称为匈牙利算法.指派问题第6页Theorem假如从效益矩阵(cij)第i行中每个元素减去a和第j

列中每个元素加上b，得到一个新效益矩阵(cij)*.则以(cij)*为新目标函数与原目标函数指派问题最优解相同.指派问题第7页匈牙利算法：Step1使效益矩阵各行各列出现零元素；详细：从效益矩阵每行各元素减去该行最小元素；再从所得矩阵每列各元素减去该列最小元素

.指派问题第8页第二步：画最少0元素覆盖线，求维数r,检验是否能找到最优解；当维数r=矩阵阶数时，则已能找到最优解，转第四步；当维数r<矩阵阶数时，则还不能找到最优解，转第三步；指派问题第9页=28每行每列有零元素，能确保有n个独立零元素吗？

R=4=n,则已得到最优解；Zmin=指派问题第10页第三步：调整0元素分布后，重复第二步。调整0元素分布步骤：（1）在未被直线覆盖元素中找出最小数，记a;（2）将未被直线覆盖元素减去a;（3）仅被一条直线覆盖元素不变；（4）同时被两条直线覆盖元素加上a.第四步：找出n个独立0元素，确定最优解。指派问题第11页要强调是匈牙利法要求人数与任务数相等，且目标函数必须极小化。当人数与任务数不等，目标函数为极大化时，必须进行适当处理后才能用匈牙利法求解。指派问题第12页

任务人员ABCD甲15182124乙19232218丙26171619丁19212317例6.11

有4个工人，要指派他们分别完成4项工作，每人做各项工作所消耗时间如表所表示。问指派哪个工人去完成哪项工作，可使总消耗时间最小？

指派问题第13页求解过程以下：第一步，变换系数矩阵：指派问题第14页

第三步，作最少直线覆盖全部0元素：

独立零元素个数m等于最少直线数l，即l＝m=3<n=4；

第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖全部元素中最小元素为1,指派问题第15页得到3个独立零元素，再调整指派问题第16页线条数4=阶数4，所以能找到最优解：总时间=15+22+16+17=70指派问题第17页例6.12最大收益最优分配问题：有5名工人完成5项不一样任务收益如表所表示：求使总收益到达最高任务分配方案。指派问题第18页工人\任务12345110591811213196121433244541891217155116141910指派问题第19页这是一个寻求总收益为最大值得极大化问题，我们必须把极大化问题转化成极小化问题后才能用匈牙利法求解。解：设最大总收益问题收益矩阵为B=(bij),假如b=max(bij),则令cij=b-bij组成矩阵C,以C为矩阵最优方案就是原最大总收益问题最优方案。指派问题第20页练习：115764戊69637丁86458丙9117129乙118957甲EDCBA费工作用人员指派问题第21页-1-2指派问题第22页◎Ø◎◎◎ØØ指派问题第23页◎Ø◎◎◎ØØ√√√l=m=4<n=5指派问题第24页◎Ø◎◎◎ØØ指派问题第25页◎Ø◎Ø◎Ø◎Ø√√√√√√√指派问题第26页◎Ø◎Ø◎Ø◎Ø√√√√√√√l=m=4<n=5指派问题第27页◎Ø◎Ø◎Ø◎Ø√√√√√√√