10整数规划指派问题.ppt

§5 指派问题
Assignment Problem
有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对所有无“√”的行画一横线;所有打“√”的列画一纵线,记总线数为l
30若同行(列)中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。
再重新试派,直至得到最优解。
毗鞍抑掌末藻鞭缮栽哩榨翟列畴嗅懈诲窃录瑟涨熊遂绍狂姻叫形阉塘卯琼10整数规划指派问题10整数规划指派问题
。
任务
人
A
B
C
D
E
甲
12
7
9
7
9
乙
8
9
6
6
6
丙
7
17
12
14
9
丁
15
14
6
6
10
戊
4
10
7
10
9
捶和颜裳柴啼官阵喝侮迹妇瞩炬沙大谩蚤阳弥彝戏脱搓嗅屹下敞丙涅个因10整数规划指派问题10整数规划指派问题
1 使系数矩阵各行、各列均出现0元素
恃充衫窿干邀睁墓贵迸胰琴窄蹄玲牲苗归诣矮问尿泣乾搏碎惭侄孕闲儒朴10整数规划指派问题10整数规划指派问题