线性规划和匈牙利法_第1页
线性规划和匈牙利法_第2页
线性规划和匈牙利法_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、 二、 生产任务分配的匈牙利法在实际的生产管理工作中，常会遇到这样的问题，就是如何根据生产作业汁划将不同任务在不同的工人(或班组)之间分配，使完成任务总的消耗时间或费用最小。解决这类问题的简便而有效的方法是匈牙利法，它是由匈牙利数学家D. Konig所提出。例 有4项任务A、B、C、D，分别由甲、乙、丙、丁4个人去完成，规定每人承担其中一项任务，不同的人完成同一任务所花时间(h)不同，见表3-3，求如何分配，使完成这4项任务的总时间最小。匈牙利法求解此问题的步骤是：1） 按表3-3列出矩阵 2) 将矩阵作行、列约简：首先进行行约简。在矩阵的每一行中选取最小元素，然后将该行的各元素都减去此数，得

2、到如下新矩阵 行约简是比较一名工人担任不同任务时所花的时间，各行中减去最小值后的时间表示该工人担任其它任务时，所多花费的时间，每行中的“0”表示该工人承担这项任务最有利。 然后将经过行约筒后的矩阵中没有“0”的列再进行约简，即从该列中选出最小元素，并将其它元素减去此数，得到新矩阵 列约简是比较一项任务有不同工人承担所托时间，各列中减去最小值后的时间表示任务由其他工人担任时，所多花费的时间，每列中的“0”表示这项任务由该工人承担最有利。 3) 检验是否已得最优分配方案；作零的覆盖线，即对有“0”的行和列，划上一条覆盖线，能覆盖所有零元素的最少覆盖线数称为维数，当覆盖线的维数等于矩阵阶数时，可知已

3、得最优分配方案，若维数小于阶数，再作调整。本例可用三条覆盖线覆盖住所有零元素，维数是3，矩阵的阶数是4，维数不等于阶数，因此矩阵还必须调整。 4) 矩阵的调整。在上述矩阵中有三种元素，一种是无线覆盖元素，另一种是单线覆盖元素，还有一种是双线覆盖元素。在无线覆荒元素中找出最小值，本例为“1”，将无线覆盖得元素都减去“1”，而双线覆盖的元素加上“1”，单线覆盖的元素不变。这样得到新矩阵 5) 再检验作覆盖线，方法与步骤3相同。现在的最少覆盖线数为4，与矩阵阶数相等，可知已能进行最优分配。 6) 确定最优分配方案。进行具体分配时，可以对只有一个零元素的列(行)先分配(记号)，分配后，划去与该零元素同行(列)的其他零元素(记×号)这样依改做完各列(行)，得到分配结果。如果矩阵能通过直接观察找到位于不同行不同列的零元素，那么就可以直接确定分配方

人人文库> 全部分类> 应用文书 > 工作计划

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论