《管理运筹学》分配问题与匈牙利算法市公开课一等奖百校联赛获奖课件.pptx

运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题分配问题与匈牙利法分配问题与匈牙利法10/10/1第1页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题在实际中经常会碰到这么问题，有在实际中经常会碰到这么问题，有n 项不一样任务，需要项不一样任务，需要n 个人分别完成其中一项，但因为任个人分别完成其中一项，但因为任务性质和各人专长不一样，所以各人去完成不一样任务效率（或花费时间或费用）也就不一务性质和各人专长不一样，所以各人去完成不一样任务效率（或花费时间或费用）也就不一样。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成样。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成 n 项任务总效率最高（或项任务总效率最高（或所需时间最少），这类问题称为分配问题或指派问题。所需时间最少），这类问题称为分配问题或指派问题。1.分配问题分配问题10/10/2第2页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题例例 1 任务任务人员人员ABCD甲甲215134乙乙1041415丙丙9141613丁丁7811910/10/3第3页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题2.匈牙利法匈牙利法第一步：变换指派问题系数矩阵（第一步：变换指派问题系数矩阵（cij）为）为(bij)，使在，使在(bij)各行各列中都出现各行各列中都出现0元素元素第二步：进行试分配，以寻求最优解。假如得到最优解，运算结束，不然转到第三步。第二步：进行试分配，以寻求最优解。假如得到最优解，运算结束，不然转到第三步。第三步：作最少直线覆盖全部第三步：作最少直线覆盖全部0元素。元素。第四步：变换矩阵第四步：变换矩阵(bij)以增加以增加0元素，转到第二步。元素，转到第二步。10/10/4第4页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题例例 1 任务任务人员人员ABCD甲甲215134乙乙1041415丙丙9141613丁丁7811910/10/5第5页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题-2-4-9-7求解过程以下：求解过程以下：第一步，变换系数矩阵：第一步，变换系数矩阵：10/10/6第6页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题-4-2-0-010/10/7第7页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题 第二步，试分配：第二步，试分配：10/10/8第8页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题 任务任务人员人员ABCD甲甲215134乙乙1041415丙丙9141613丁丁78119此分配问题最优时间：此分配问题最优时间：4+4+9+11=2810/10/9第9页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题例例 2 有一份汉字说明书，需译成英、日、德、俄四种文字。现有甲、乙、丙、丁四人，他们有一份汉字说明书，需译成英、日、德、俄四种文字。现有甲、乙、丙、丁四人，他们将汉字说明书译成不一样语种说明书所需时间以下表所表示，问怎样分配任务，使总时间最少将汉字说明书译成不一样语种说明书所需时间以下表所表示，问怎样分配任务，使总时间最少？任务任务人员人员英语英语日语日语德语德语俄语俄语甲甲67112乙乙4598丙丙31104丁丁598210/10/10第10页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题求解过程以下：求解过程以下：第一步，变换系数矩阵：第一步，变换系数矩阵：5第二步，试指派：第二步，试指派：找到找到 3 个独立零元素个独立零元素 但但 m=3 n=410/10/11第11页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题第三步，作最少直线覆盖全部第三步，作最少直线覆盖全部0元素：元素：独立零元素个数独立零元素个数m等于最少直线数等于最少直线数l，即，即lm=3n=4；第四步，变换矩阵第四步，变换矩阵(bij)以增加以增加0元素：没有被直线覆盖全部元素中最小元素为元素：没有被直线覆盖全部元素中最小元素为1，然后打，然后打各各行都减去行都减去1；打；打各列都加上各列都加上1，得以下矩阵，并转第二步进行试指派：，得以下矩阵，并转第二步进行试指派：10/10/12第12页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题000 0 00得到得到4个独立零元素，个独立零元素，所以所以最优解矩阵为：最优解矩阵为：10/10/13第13页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题 任务任务人员人员英语英语日语日语德语德语俄语俄语甲甲67112乙乙4598丙丙31104丁丁5982此分配问题最优时间：此分配问题最优时间：2+4+1+8=152+4+1+8=1510/10/14第14页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题例例3115764戊戊69637丁丁96458丙丙9117129乙乙118957甲甲EDCBA费费 工作工作 用用人员人员10/10/15第15页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题-1-210/10/16第16页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题 10/10/17第17页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题 l=m=4 n=510/10/18第18页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题 10/10/19第19页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题 10/10/20第20页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题 l=m=4 n=510/10/21第21页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题 10/10/22第22页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题此问题有多个最优解此问题有多个最优解总时间为总时间为2810/10/23第23页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题 总时间为总时间为2810/10/24第24页运筹学运筹学第第4 4章章 整数规划与分配问题整数规划与分配问题 总时间为总时间为2810/10/25第25页