




已阅读5页,还剩38页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
指派问题,指派问题是一种特殊的整数规划问题 一、问题的提出 设有m个工人,能做n件事,但效率不同,并规定每个工人做且只能做一件事,每件事有且只能有一个工人做,问应该如何安排他们的工作,使花费的总时间(成本)最少或效率最高?,二、指派问题的数学模型,设第i个工人做第j件事的时间是 ,决策变量是 则数学模型如下,举例说明 1)表上作业法 2)匈牙利法,例 有四个工人和四台不同的机床,每位工人在不同的机床上完成给定的任务的工时如表5.12所示,问安排哪位工人操作哪一台机床可使总工时最少?,获得初始解:圈零/划零操作,将时间矩阵C的每一行都减去相应行的最小元素和每一列都减去相应列的最小元素,使每一行和每一列都含有零; 从最少零数的行或列开始,将“零”圈起来,并划去它所在行和所在列的其它零; 反复做2),直到所有零被圈起或被划掉为止。得到初始解。 判断是否为最优解:圈起的零的个数是否等于n。,确定调整行和列,在没有圈起的零所在行上打“”; 在打“”行中所有零所在的列打“”; 在打“”列中含有圈起零的行上打“”, 反复执行2)和3)两步,直到不能打“”为止; 用直线划去打“”的列和不打“”的行,没有划去的行构成调整的行,划去的列构成调整列。,调整可行解的方法,在调整行中寻找最小的元素,将它作为调整量; 将调整行各元素减去调整量,对调整列中各元素加上调整量。 再次执行“圈零”和“划零”的操作,并循环以上的步骤,直到圈起的零数等于n为止。,匈牙利法解例3.3,时间矩阵 各行各列减去最小元素后得,圈零划零,得最优解,将圈起的零改为1,其它元素改为0,即得最优解如下 最小总时间为22。,再看一例,请求解如下矩阵表达的指派问题,减去最小元素,圈零划零,打勾划线确定调整行和列,调整可行解,再圈零划零,得最优解,另一最优解,最小时间(成本)min z=32,匈牙利算法示例,(二)、解题步骤:,指派问题是0-1 规划的特例,也是运输问题的特例,当然可用整数规划,0-1 规划或运输问题的解法去求解,这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法,这就是匈牙利法,即系数矩阵中独立 0 元素的最多个数等于能覆盖所有 0 元素的最少直线数。,第一步:变换指派问题的系数矩阵(cij)为(bij),使在(bij)的各行各列中都出现0元素,即 (1) 从(cij)的每行元素都减去该行的最小元素; (2) 再从所得新系数矩阵的每列元素中减去该列的最小元素。,第二步:进行试指派,以寻求最优解。 在(bij)中找尽可能多的独立0元素,若能找出n个独立0元素,就以这n个独立0元素对应解矩阵(xij)中的元素为1,其余为0,这就得到最优解。找独立0元素,常用的步骤为: (1)从只有一个0元素的行(列)开始,给这个0元素加圈,记作 。然后划去 所在列(行)的其它0元素,记作 ;这表示这列所代表的任务已指派完,不必再考虑别人了。 (2)给只有一个0元素的列(行)中的0元素加圈,记作;然后划去 所在行的0元素,记作 (3)反复进行(1),(2)两步,直到尽可能多的0元素都被圈出和划掉为止。,(4)若仍有没有划圈的0元素,且同行(列)的0元素至少有两个,则从剩有0元素最少的行(列)开始,比较这行各0元素所在列中0元素的数目,选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行,直到所有0元素都已圈出和划掉为止。 (5)若 元素的数目m 等于矩阵的阶数n,那么这指派问题的最优解已得到。若m n, 则转入下一步。 第三步:作最少的直线覆盖所有0元素。 (1)对没有的行打号; (2)对已打号的行中所有含元素的列打号; (3)再对打有号的列中含 元素的行打号;,(4)重复(2),(3)直到得不出新的打号的行、列为止; (5)对没有打号的行画横线,有打号的列画纵线,这就得到覆盖所有0元素的最少直线数 l 。l 应等于m,若不相等,说明试指派过程有误,回到第二步(4),另行试指派;若 lm n,须再变换当前的系数矩阵,以找到n个独立的0元素,为此转第四步。 第四步:变换矩阵(bij)以增加0元素。 在没有被直线覆盖的所有元素中找出最小元素,然后打各行都减去这最小元素;打各列都加上这最小元素(以保证系数矩阵中不出现负元素)。新系数矩阵的最优解和原问题仍相同。转回第二步。,例一:,2,4,9,7,4,2,有一份中文说明书,需译成英、日、德、俄四种文字,分别记作A、B、C、D。现有甲、乙、丙、丁四人,他们将中文说明书译成不同语种的说明书所需时间如下表所示,问如何分派任务,可使总时间最少?,例二、,求解过程如下: 第一步,变换系数矩阵:,5,第二步,试指派:,找到 3 个独立零元素 但 m = 3 n = 4,第三步,作最少的直线覆盖所有0元素:,独立零元素的个数m等于最少直线数l,即lm=3n=4;,第四步,变换矩阵(bij)以增加0元素:没有被直线覆盖的所有元素中的最小元素为1,然后打各行都减去1;打各列都加上1,得如下矩阵,并转第二步进行试指派:,得到4个独立零元素, 所以最优解矩阵为:,15,练习:,11,5,7,6,4,戊,6,9,6,3,7,丁,8,6,4,5,8,丙
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025北京市平谷区教育委员会所属事业单位面向应届毕业生招聘教师140人模拟试卷及答案详解(名师系列)
- 2025江苏盐城市射阳县商务局等单位招聘政府购买服务工作人员12人考前自测高频考点模拟试题及一套参考答案详解
- 2025年科技园区建设诚信专项整治考核试卷
- 2025广东湛江市坡头区社会保险基金管理局招聘编外人员1人考前自测高频考点模拟试题及答案详解(全优)
- 2025湖南省农村信用社联合社校园招聘15人模拟试卷及答案详解(名校卷)
- 2025广东深圳九州光电子技术有限公司招聘生产主管等2人模拟试卷及答案详解(名师系列)
- 2025广西梧州市公安局第二批公开招聘警务辅助人员160人考前自测高频考点模拟试题附答案详解(典型题)
- 2025广州医科大学校本部招聘工作人员9人(第二次)模拟试卷含答案详解
- 2025年风电行业市场前瞻:技术创新在风电场建设中的应用报告
- 2025河南开封市杞县消防救援大队政府专职消防员招聘10人考前自测高频考点模拟试题及答案详解(夺冠)
- 桥梁工程技术总结报告合集
- 第6课 书衣之美说课稿初中美术沪书画版五四学制2024六年级上册-沪书画版五四学制2024
- 心血管疾病预防规定
- 2026版一本英语阅读真题80篇-3年级
- 婚礼婚纱款式指南
- 国开2025年《特殊教育概论》形考作业1-8大作业答案
- 2026届高考备考数学总复习的一些想法和做法
- 四川数据集团有限公司招聘笔试题库2025
- 2025年乡镇工会集体协商指导员岗位知识面试模拟题及答案
- 基于单片机技术的智能家居远程监控系统设计与实践
- 大学生心理健康教育(兰州大学)
评论
0/150
提交评论