欢迎来到天天文库
浏览记录
ID:59928121
大小:413.00 KB
页数:26页
时间:2020-11-28
《运筹学匈牙利法说课材料.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、运筹学匈牙利法首先,找到一个可行解,并计算其目标函数值;然后,以其目标值作为一个过滤条件,优于其值的再判断约束条件,直到找到最优解。二、0-1整数规划——隐枚举法√√√√86133-2√√√√5√√√√0x1.x2.x3满足约束条件(是∨否×)过滤条件(1)(2)(3)(4)(0.0.0)(0.0.1)(0.1.0)(1.0.0)(0.1.1)(1.0.1)(1.1.0)(1.1.1)√√√√8思考:如果将目标函数变为下式会改进吗?三、指派问题的匈牙利法指派问题(TheAssignmentProblem)1、指派问题的形式表述给定了一系列所要完成的任务(tasks)以
2、及一系列完成任务的被指派者(assignees),所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务2、指派问题的假设被指派者的数量和任务的数量是相同的每一个被指派者只完成一项任务每一项任务只能由一个被指派者来完成每个被指派者和每项任务的组合有一个相关成本目标是要确定怎样进行指派才能使得总成本最小设n个人被分配去做n件工作,每人只能完成一项任务,每项任务只能由一人完成。已知第i个人去做第j件工作的的效率为Cij(i=1.2…n;j=1.2…n)并假设Cij≥0。问应如何分配才能使总效率(时间或费用)最高?3、指派问题模型(TheModelforAssignmen
3、tProblem)典型问题例1:有一份说明书,要分别译成英、日、德、俄四种文字,交与甲、乙、丙、丁四个人去完成,因各人专长不同,他们完成翻译不同文字所需要的时间(小时)如表所示。规定每项工作只能交与其中的一个人完成,每个人只能完成其中的一项工作。问:如何分配,能使所需的总时间最少?甲乙丙丁工作人译英文译日文译德文译俄文2109715414813141611415139建立模型设xij=10若第i项工作交与第j个人完成若第i项工作不交与第j个人完成译英文:x11+x12+x13+x14=1译日文:x21+x22+x23+x24=1译德文:x31+x32+x33+x34=
4、1译俄文:x41+x42+x43+x44=1甲:x11+x21+x31+x41=1乙:x12+x22+x32+x42=1丙:x13+x23+x33+x43=1丁:x14+x24+x34+x44=1xij=0或1(i=1,2,3,4;j=1,2,3,4)甲乙丙丁工作人译英文译日文译德文译俄文21097154148131416114151394、指派问题的匈牙利解法2497第1步:变换指派问题的系数矩阵(cij),使各行各列中都出现0元素(1)从(cij)的每行元素都减去该行的最小元素;(2)再从所得新系数矩阵无零元素的列中减去该列的最小元素。42在变化后的效率矩阵中找尽
5、可能多的独立0元素,若能找出n个独立0元素,就以这n个独立0元素对应解矩阵(xij)中的元素为1,其余为0,这就得到最优解。第2步:进行试指派,即确定独立零元素(1)从有唯一的零元素的行或列开始确定独立零元素,并用表示,并划掉其所在行或列的其他零。直到尽可能多的零元素都被圈出和划掉为止。0(2)若独立零元素的数目m等于矩阵的阶数n,那么这指派问题的最优解已得到。若m6、598丙31104丁5982第1步,变换系数矩阵:-5第2步,确定独立零元素找到3个独立零元素,但m=37、系数矩阵中不出现负元素)。新系数矩阵的最优解和原问题仍相同。转回第2步。-5√√√5、指派问题的变形VariantsofAssignmentProblem任务比被指派者多被指派者比要完成的任务多有一些被指派者并不能进行某一些的任务每个被指派者可以同时被指派给多个的任务(1)人数与工作数不等的处理当人数>工作数时:假想工作数,使得与人数能够匹配,对应的效率设定为0值。当工作数>人数时:假想人数,使得与工作数能够匹配,对应的效率设定为0值。人数和工作数不等的指派问题(2)一个人可做几项工作的指派问题A1可同时做三项工作(3)某项工作一定不能由某人做的指派
6、598丙31104丁5982第1步,变换系数矩阵:-5第2步,确定独立零元素找到3个独立零元素,但m=37、系数矩阵中不出现负元素)。新系数矩阵的最优解和原问题仍相同。转回第2步。-5√√√5、指派问题的变形VariantsofAssignmentProblem任务比被指派者多被指派者比要完成的任务多有一些被指派者并不能进行某一些的任务每个被指派者可以同时被指派给多个的任务(1)人数与工作数不等的处理当人数>工作数时:假想工作数,使得与人数能够匹配,对应的效率设定为0值。当工作数>人数时:假想人数,使得与工作数能够匹配,对应的效率设定为0值。人数和工作数不等的指派问题(2)一个人可做几项工作的指派问题A1可同时做三项工作(3)某项工作一定不能由某人做的指派
7、系数矩阵中不出现负元素)。新系数矩阵的最优解和原问题仍相同。转回第2步。-5√√√5、指派问题的变形VariantsofAssignmentProblem任务比被指派者多被指派者比要完成的任务多有一些被指派者并不能进行某一些的任务每个被指派者可以同时被指派给多个的任务(1)人数与工作数不等的处理当人数>工作数时:假想工作数,使得与人数能够匹配,对应的效率设定为0值。当工作数>人数时:假想人数,使得与工作数能够匹配,对应的效率设定为0值。人数和工作数不等的指派问题(2)一个人可做几项工作的指派问题A1可同时做三项工作(3)某项工作一定不能由某人做的指派
此文档下载收益归作者所有