07整数规划指派问题.ppt
《07整数规划指派问题.ppt》由会员分享,可在线阅读,更多相关《07整数规划指派问题.ppt(20页珍藏版)》请在三一文库上搜索。
1、例 有一份中文说明书,需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人,他们将中文说明书翻译成不同语种的说明书所需时间如下表。问应指派何人去完成何工作,使所需总时间最少?,5 指派问题,Assignment Problem,5 指派问题,Assignment Problem,有n项任务,分派给n个人承担,每人承担一项。第i 人完成第j 项任务的花费(时间或费用等)为cij,如何分派使总花费最省?,第j项工作只由一个人完成,第i人只完成一项工作,5 指派问题,Assignment Problem,已知条件可用系数矩阵(效率矩阵)表示为:,其可行解也可用每行仅有一个1,
2、每列也仅有一个1的矩阵表示,如:,阅读课本内容,了解算法,10分钟!,例7的计算为:,匈牙利法解题步骤:,1 使系数矩阵各行、各列均出现0元素 若某行(列)已有0元素,不必处理,否则: 系数矩阵各行元素减去所在行的最小元素,再从所得矩阵的各列减去所在列最小元素。(因一行中xij 取值一个1,其余为0,cij 同时减去一常数不影响xij取值)。,-4 -2,-2 -4 -9 -7,需要指派的矩阵,效率矩阵,2 试派:(续),30若同行(列)中0元素均多于1个,把其中任一个0元素加圈,同时把该0元素所在的行和列中的其它0元素划去。 反复执行10,20,30,直到所有0元素均被处理。 记 0 的个数
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 07 整数 规划 指派 问题
链接地址:https://www.31doc.com/p-3401196.html