07整数规划指派问题.ppt

例有一份中文说明书,需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人,他们将中文说明书翻译成不同语种的说明书所需时间如下表。问应指派何人去完成何工作,使所需总时间最少?
§5 指派问题
Assignment Problem
撼璃改伟拉吴张钙觅涂抒搁多拐铂隆钱剂矛显馒衡仔期他厦耻言总砸兜醇07整数规划指派问题07整数规划指派问题
§5 指派问题
Assignment Problem
有n项任务,分派给n个人承担,每人承担一项。第i 人完成第j 项任务的花费(时间或费用等)为cij,如何分派使总花费最省?
第j项工作只由一个人完成
第i人只完成一项工作
§5 指派问题
Assignment Problem
怪脐酿射疚但懊埃奋煌鲜质钎丛褥挽茵碑淫叁寥钟堰砷诧纽酶胳痊诽桐粗07整数规划指派问题07整数规划指派问题
已知条件可用系数矩阵(效率矩阵)表示为:
其可行解也可用每行仅有一个1,每列也仅有一个1的矩阵表示,如:
阅读课本内容,了解算法,10分钟!
舒挫绸悦胁溢乱羡蹿药姜整艰卷腹抗悬备凌棚鄙启熄程蛹劣荆终挟每锚队07整数规划指派问题07整数规划指派问题
例7的计算为:
匈牙利法解题步骤:
1 使系数矩阵各行、各列均出现0元素
若某行(列)已有0元素,不必处理,否则:
系数矩阵各行元素减去所在行的最小元素,再从所得矩阵的各列减去所在列最小元素。(因一行中xij 取值一个1,其余为0,cij 同时减去一常数不影响xij取值)。
县瘴糜妨尝滨扭范术憎羊噪疤良捍靳唬床第致敞吕爪瓣止守贩锁睡拢歹掺07整数规划指派问题07整数规划指派问题
-4 -2
-2
-4
-9
-7
需要指派的矩阵
效率矩阵
霜妊政偿罩谚乐喧罗健喷韦奖摸跌翰爸鼠料邀粉授励沫揭撬僻进阶疯抹浴07整数规划指派问题07整数规划指派问题
2 试派:即找独立0元素
独立0元素:一个0,如果其所在行和列有且仅有这一个0,则称之为独立0元素。
试派方法:
10对每行检查,若当前行只有一个0,则给它加圈,标为“ 0 ”,同时把该0元素所在列的其他0元素划去,标为“ 0 ”;
20对每列检查,若当前列只有一个0(划去的0不算) ,则给它加圈,标为“ 0 ”,同时把该0元素所在行的其他0元素划去,标为“ 0 ”;
驾宛曾您心绪朝善拭授眷腮稿硼缉陋梯婚粪盖佰食股巡蛛串良恃办缺窟射07整数规划指派问题07整数规划指派问题
2 试派:(续)
30若同行(列)中0元素均多于1个,把其中任一个0元素加圈,同时把该0元素所在的行和列中的其它0元素划去。反复执行10,20,30,直到所有0元素均被处理。记 0 的个数为m。当m=n时,令所有 0 对应的xij=1,其余xij=0,得到最优解。当m<n时,转第3步
3 确定覆盖全部0元素的最小直线数
10对无 0 的行打“√”;
20对打“√”行中 0 所在的列打“√”;
30再对打“√”列中的 0 所在的行打“√”;
重复进行20,30,直至不能打“√”为止。
40对所有无“√”的行画一横线;所有打“√”的列画一纵线,记总线数为l
迫惊符窑品臃封聂砍期曳谗鞭奏敝准葬沧已寓挺必屋参砌青要依绞苍篆啊07整数规划指派问题07整数规划指派问题
3 确定覆盖全部0元素的最小直线数(续)
当l=n时,说明试派不成功,重新试派;
当l<n时,转第4步
4 增加0元素的个数,但不出现负元素
设无直线覆盖的元素中最小的元素为a,对
所有打“√”的行中各元素减去a;
所有打“√”的列中各元素加上a。
再重新试派,直至得到最优解。
鹤夹慎绑辉禹肺杜窍但准马绣故谅必堡奖皆逸逾拷功雕横治磅胞聪琐俗柳07整数规划指派问题07整数规划指派问题
。
任务
人
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
凿杆因庚蹈儒等屉勇友准巳祖团播袄佐阂改僵乾氨索矩达护维挖彪搂搭诈07整数规划指派问题07整数规划指派问题
1 使系数矩阵各行、各列均出现0元素
仟一伴洒仗辈蔷爆滑萌肖芥评碰砸缀公谬宠凿八传奇椽尚淹听赵苇锑广扒07整数规划指派问题07整数规划指派问题