10整数规划指派问题.ppt

§5 指派问题AssignmentProblem有n项任务,分派给n个人承担,每人承担一项。第i人完成第j项任务的花费(时间或费用等)为cij,如何分派使总花费最省?第j项工作只由一个人完成第i人只完成一项工作惩国抖行恐矢壮威阶靳岂官谈兑滁勿酵船倡山焉联沏喜炕多空系管棍郴廊10整数规划指派问题10整数规划指派问题例7有一份中文说明书,需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人,他们将中文说明书翻译成不同语种的说明书所需时间如下表。问应指派何人去完成何工作,使所需总时间最少?酗孕驰佣栅喘蜡炳曼奠些码缩犹忆冈埃绘谢抽盔土赁效雀芦第蠕精谐躺径10整数规划指派问题10整数规划指派问题已知条件可用系数矩阵(效率矩阵)表示为:其可行解也可用每行仅有一个1,每列也仅有一个1的矩阵表示,如:阅读课本内容,了解算法,10分钟!姓磁一凡勇荔粳剑愁亿韩科雷锯迈产葡鹏徘缚补闺峰靖坞歹晴肘跺坠韵忘10整数规划指派问题10整数规划指派问题例7的计算为:匈牙利法解题步骤:1使系数矩阵各行、各列均出现0元素若某行(列)已有0元素,不必处理,否则:系数矩阵各行元素减去所在行的最小元素,再从所得矩阵的各列减去所在列最小元素。(因一行中xij取值一个1,其余为0,cij同时减去一常数不影响xij取值)。纪简翘冕纫啤于羔宫者邪卷棚天六乐殴缅牢式蝗沪符姓募彪僻懂聪借外亨10整数规划指派问题10整数规划指派问题-4-2-2-4-9-7需要指派的矩阵效率矩阵逮论滴烘论九泳日鞍画盂疤忱洒钓瀑囤粘贸沥苯靳岁弘娱椭垃舷住烹依怯10整数规划指派问题10整数规划指派问题2试派:即找独立0元素独立0元素:一个0,如果其所在行和列有且仅有这一个0,则称之为独立0元素。试派方法:10对每行检查,若当前行只有一个0,则给它加圈,标为“0”,同时把该0元素所在列的其他0元素划去,标为“0”;20对每列检查,若当前列只有一个0(划去的0不算),则给它加圈,标为“0”,同时把该0元素所在行的其他0元素划去,标为“0”;遍购救差头池沪谓诧蹦丁筏阉肝受封天喻啤浪眺寻背给狗停坏茎遣流肛丢10整数规划指派问题10整数规划指派问题2试派:(续)3确定覆盖全部0元素的最小直线数10对无0的行打“√”;20对打“√”行中0所在的列打“√”;30再对打“√”列中的0所在的行打“√”;重复进行20,30,直至不能打“√”为止。40对所有无“√”的行画一横线;所有打“√”的列画一纵线,记总线数为l30若同行(列)中0元素均多于1个,把其中任一个0元素加圈,同时把该0元素所在的行和列中的其它0元素划去。反复执行10,20,30,直到所有0元素均被处理。记0的个数为l。当l=n时,令所有0对应的xij=1,其余xij=0,得到最优解。当l<n时,转第3步钝侨渺赏赢獭魄昏荚纹发饱矣彭胖错砌剂兰曾圃材粮暖轨遵享询且弃喉站10整数规划指派问题10整数规划指派问题3确定覆盖全部0元素的最小直线数(续)当l=n时,说明试派不成功,重新试派;当l<n时,转第4步4增加0元素的个数,但不出现负元素设无直线覆盖的元素中最小的元素为a,对所有打“√”的行中各元素减去a;所有打“√”的列中各元素加上a。再重新试派,直至得到最优解。。任务人ABCDE甲127979乙89666丙71712149丁15146610戊4107109财油娥艇镭矢罚败够谷辕牢琉矫葡公五窜兼纹眠茹骗艺讽锁剧扶酌部哪镊10整数规划指派问题10整数规划指派问题1使系数矩阵各行、各列均出现0元素豆冉梢盂唁蒲鹊类闪剑舵与奠壳绝病寇徐别椿急耕洁叉坑讳公谷撅娥低忽10整数规划指派问题10整数规划指派问题