第4章整数规划-第5节.ppt
《第4章整数规划-第5节.ppt》由会员分享,可在线阅读,更多相关《第4章整数规划-第5节.ppt(27页珍藏版)》请在三一文库上搜索。
1、第5节 指 派 问 题,n项任务由n个人完成,各人完成各任务的效率不同。于是产生应指派哪个人去完成哪项任务,使完成n项任务的总效率最高(或所需总时间最小)。这类问题称为指派问题或分派问题(assignment problem)。 例7 有一份中文说明书,需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人。他们将中文说明书翻译成不同语种的说明书所需时间如表5-7所示。问应指派何人去完成何工作,使所需总时间最少?,对于每个指派问题,都有相应的效率矩阵或系数矩阵,其元素cij0(i , j=1,2,n)表示指派第i人去完成第j项任务时的效率(或时间、成本等)。 引入变量xi
2、j:,当问题要求极小化时数学模型是:, ,可行解矩阵的特点: 与效率矩阵同阶数; 每行只有一个非零元素,值为1,并且位于不同行不同列,其余元素均为0,这表示人与任务是一对一的关系,约束条件说明第 j 项任务只能由1人去完成 约束条件说明第 i 人只能完成1项任务。 满足约束条件的可行解 xij 也可写成表格或矩阵形式,称为解矩阵。 如例7的一个可行解矩阵,指派问题的求解方法匈牙利法,匈牙利法基本原理,定理 若将指派问题的效率矩阵的某行(列)都减去同一常数 t,则新效率矩阵对应的指派问题和原指派问题最优解相同。,推论 将指派问题的效率矩阵的各行各列分别减去相应的行或列的最小元素,则新指派问题与原
3、指派问题有相同的最优解。 新效率矩阵中必然出现一些零元素,分两类: (1) 圈0元素,表示采取指派行为 (2) 被划去的0元素,表示不采取指派行为,定义 效率矩阵中,有一组处在不同行不同列的零元素,称为独立零元素。即圈0元素,指派问题的匈牙利解法,步骤1 变换系数矩阵。先对各行元素分别减去本行中最小元素,再对各列元素分别减去本列中最小元素。,步骤2 在变换后的系数矩阵中确定独立零元素,若独立零元素为n个,得到最优解,否则,作能覆盖所有零元素的最小直线数目的直线集合,转步骤3,步骤3 继续变换系数矩阵,在未被覆盖的元素中找出一个最小元素,未被覆盖的元素所在行或列中各元素都减去这一最小元素,从而出
4、现零元素。,经第一步变换后,系数矩阵中每行每列都已有了0元素;但需找出n个独立的0元素。若能找出,就以这些独立0元素对应解矩阵(xij)中的元素为1,其余为0,这就得到最优解。当n较小时,可用观察法、试探法去找出n个独立0元素。若n较大时,就必须按一定的步骤去找,常用的步骤为:,(1) 从只有一个0元素的行(列)开始,给这个0元素加圈,记作。这表示对这行所代表的人,只有一种任务可指派。然后划去所在列(行)的其他0元素,记作。这表示这列所代表的任务已指派完,不必再考虑别人了。,(2) 给只有一个0元素列(行)的0元素加圈,记作;然后划去所在行的0元素,记作。 (3) 反复进行(1),(2)两步,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 整数 规划
链接地址:https://www.31doc.com/p-2120853.html