匈牙利算法【优选内容】_第1页
匈牙利算法【优选内容】_第2页
匈牙利算法【优选内容】_第3页
匈牙利算法【优选内容】_第4页
匈牙利算法【优选内容】_第5页
已阅读5页，还剩58页未读， 继续免费阅读

下载本文档

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

文档简介

1、匈牙利方法解决作业问题，第1页，作业问题示例5，有一本中文手册，需要翻译成英语、日语、德语和俄语，分别记为E、J、G和R。有四个人，A，B，C和D，他们将中文手册翻译成英文，日文，德文和俄文，第2页，第3页，类似于：有n个加工任务，如何分配给n个机床分别完成它们；有n条航线，如何指定n艘船分别航行表中的数据称为效益矩阵或系数矩阵，其元素大于零，表示效益(或时间、成本等)。)当第I个人被分配来完成第j个任务时。在第4页，引入了0-1变量xij=1来分配第I个人来完成第j个任务，而xij=0并不分配第I个人来完成第j个任务。分布问题的数学模型是最小z=110-1(j=1，2n)10=1 (I=1，

2、2n)10或1(I=1，2n；J=1，2.第5页，xij=1 (j=1，2.n)意味着jth任务只能由一个人完成。第六个人只能完成一项任务。满足约束条件的解称为可行解，可以写成矩阵形式：x=，0.100001.000.000001，称为解矩阵。每行和每列中元素的总和为1。第6页，匈牙利算法基础：对于相同的作业I，所有机床的效率将增加或减少相同的常数，这不会影响最优分配；同样，对于相同的机床J，做所有工作的效率将以相同的常数增加或减少，并且不会影响最优分配。第7页，匈牙利定律的基本思想：通过变换和修改系数矩阵的行和列的元素，在每一行或列中至少有一个0元素，直到在不同的行和列中至少有一个0元素，从

3、而获得对应于这0个元素的完整分配方案。键：找到n个独立的0元素。第8页有一本中文手册，需要翻译成英文、日文、德文和俄文，分别记为E、J、G和R。目前，有四个人，A、B、C和D，他们需要以下时间将中文手册翻译成英文、日文、德文和俄文。他们问如何分配工作，以尽量减少所需的总时间。第9页，第10页，匈牙利算法步骤：步骤1:转换分配问题的系数矩阵，0元素出现在每行和每列中：从系数矩阵的每行元素中减去每行的最小元素。然后从系数矩阵的元素中减去每列的最小元素。如果一行已经有一个0元素，就没有必要减少它。第11页，(cij)=，2 15 13 44 14 15 9 16 13 7 8 11 9，2 49 7、0 13 11 26 0 10 11 05 7 40 14 2，4 2，0 13 7 06 09 05 3 20 100，第1 2页，第二步：从只有一个0元素的行(或列)开始，圈出该0元素，记住它，然后将它所在的列(或行)中的其他0元素划掉用一个0元素圈出列(或行)的0元素，写下来，然后划掉行(或列)的其他0元素，并记为。重复上述两个步骤，直到所有0个元素都被圈出并划掉。第13页，如果没有带圆圈的0元素，并且同一行(或列)中至少有两个0元素，则从剩余最少0元素的行(或列)开始，比较该行中每个0元素所在的列中0元素的数量，选择少于0元素的列中的0元素进行圈出，然后划掉同一行中的

人人文库> 全部分类> 行业资料 > 机电工程

温馨提示

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

最新文档

评论

0/150

提交评论