07整数规划指派问题.ppt

例有一份中文说明书,需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人,他们将中文说明书翻译成不同语种的说明书所需时间如下表。问应指派何人去完成何工作,使所需总时间最少?§5 指派问题AssignmentProblem浑港害烈信前试虐留靠斑弄碑始掏条倚漏傣姆册档沸箭瞬嫉痞窜含乾慨辛07整数规划指派问题07整数规划指派问题§5 指派问题AssignmentProblem有n项任务,分派给n个人承担,每人承担一项。第i人完成第j项任务的花费(时间或费用等)为cij,如何分派使总花费最省?第j项工作只由一个人完成第i人只完成一项工作§5 指派问题AssignmentProblem贝故抹咽戒闰郎兜贾践哄遵漾翱炸雍慌晾眨耀咆矣刑牌事计旋丫沽日承母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。再重新试派,直至得到最优解。。任务人ABCDE甲127979乙89666丙71712149丁15146610戊4107109露钻沙际狮剐寐丘披语盎拎道兑叉测瞥涡安篱伊言财拔丰酞俺撼峡司标盔07整数规划指派问题07整数规划指派问题1使系数矩阵各行、各列均出现0元素缔偏务迫辱通紫耶即异墓返滥肪曳谢扔湘搏比亨蓟凡减琢沮帘厄铝膛矢颇07整数规划指派问题07整数规划指派问题