《2022年寻找独立元素的一种新方法分享 .pdf》由会员分享，可在线阅读，更多相关《2022年寻找独立元素的一种新方法分享 .pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、寻找独立 0 元素的一种新方法张联朋( 陕西工业职业技术学院工商管理系陕西咸阳712000 ) 摘要 ：本文根据独立0 元素在矩阵行和列中具有互斥性这一特点，提出了利用0 元素在矩阵中的位置来判断其是否为独立0 元素的对角线方法。关键词 ：指派问题；匈牙利法；独立0 元素；方法中图分类号：文献标识码：文章编号用匈牙利法求解指派问题的过程，实质上就是在矩阵中不断制造并寻找独立0 元素的一个过程， 因为足够数量的一族独立0 元素本身就是指派问题的一个最优解。整个求解过程从本质上看分为两步：第一步：制造独立0 元素。方法是以考尼格（Konig ）第一定理“若从系数矩阵（Cij ）的一行（列）各元素中
2、分别减去该行（列）的最小元素，所得到的新矩阵（Bij ）和原矩阵（Cij ）具有相同的最优解”为理论基础，通过对原矩阵进行化简，使矩阵中出现独立0 元素。第二步：寻找独立0 元素。其本质是从矩阵中已有的0 元素中将其中的独立0 元素标记出来，一般用“? ”来表示独立0 元素，而用“ ”来表示那些非独立0 元素。在用匈牙利法求解过程中，这一步被称之为“试指派”。具体方法是：检查矩阵的行和列，从中找出“0”元素最少的一行（或列），从该行（或列）标记出一个0 元素 若该行（或列）有多个“0”元素，则任标一个 ，用 “? ”表示， 并划去 ? 元素所在行和列上的其他0 元素，用“”表示。若最少0 元素
3、行（或列）同时有几行（或列），则从 0 元素所在列（或行）中最少的开始。在剩下的矩阵中重复上述过程，直至所有0 元素都已标记出或划掉为止。倘若矩阵中独立0 元素数量小于矩阵的阶数，则需继续化简。这种通过“试指派”的方法虽能很快找到独立0 元素，但在寻找之前人们对其位置还是缺乏预见性，因为对于一个n 阶方阵，这些独立0 元素在矩阵中可能的排列方式多达n!种， （注： 4！ 24，5！ 120，6！720 ） ；另外，这样标记出来的“? ”在矩阵中也显得很乱。为此，笔者根据独立0 元素之间在矩阵的行和列中具有互斥性的特点，提出利用0元素在矩阵中的位置来判断其是否独立0 元素的一种新方法对角线法。一
4、、对角线法的原理名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 因为在平衡的指派问题（任务数作业者数）中，一项任务只能由一个作业者来完成，每个作业者也只能承担其中的一项任务，这表现在矩阵中就是 “一行只能有一个独立0 元素，一列也只能有一个独立0 元素”，所以所有的独立0 元素必然分布在方阵的不同行、不同列上，利用这一特点，如果我们对矩阵的行（或列）进行某种调换，或者说重新排列，就一定可使这些独立0 元素集中分布在矩阵的对角线上
5、（如下图5 阶方阵所示） 。这样一来，凡是出现在对角线上的0 元素就一定是独立的0 元素，而那些出现在对角线以外位置上的0 元素也一定是非独立的0 元素。这样我们不仅能很快找到所有独立0 元素，还能很直观地发现矩阵中独立0 元素的数量有多少，还差多少。555453524544434135343231252322211413121154535251454342413534323125242321151413120000000000aaaaaaaaaaaaaaaaaaaaBaaaaaaaaaaaaaaaaaaaaB或二、对角线法的具体方法：经过化简（对系数矩阵的每行元素减去该行的最小元素；再从所得
6、系数矩阵的每列元素减去该列的最小元素）之后，新的系数矩阵(Bij)中各行各列都出现了0 元素。从 0 元素数量最少的列开始，选择该列第一个0 元素，根据该0 元素所在行的位置确定该列元素在新矩阵中列的位置（若该0 元素在原矩阵中所在的行是第i 行，那么就将该0元素所在列放在新矩阵的第i 列） ，并在原矩阵中划去这一列，并划掉同行其它0 元素。再在剩下的矩阵中重新比较各列0 元素的数量，并按前面方法进行，直至完成。这样就可将所有独立0 元素集中安放在新矩阵的对角线上。当新矩阵对角线上全为0元素时，就得到了指派问题的最优解；如果对角线某一处元素不为0，说明该矩阵中独立0元素数量不足，就需要对该矩阵
7、做进一步的化简。示例：有一份中文说明书，需由张、王、李、赵、钱五人翻译成英、日、德、法、俄五种文字 ，他们各自翻译成五种文字所需的时间如下表，问如何指派任务可使所需总时间最短？英日德法俄张12 7 9 7 9 王8 9 6 6 6 李7 17 12 14 9 赵15 14 6 6 10 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 钱4 10 7 10 9 求解：经化简，得元素标记独立经列调换，得经化简，得德法英俄日钱赵李王张
8、德法英俄日钱赵李王张俄法德日英钱赵李王张俄法德日英钱赵李王张3605609485721000232052360560094857021000203205205636040089275100000322020546767min910710410661415914121776669897971230321BBBBB2 B3 说明：在矩阵B2中，第2、5 列 0 元素最少，各有一个，优先排序。第2列 0 元素因在“第一行” ，故该列在新矩阵B3中应排在“第一列” ；第 5 列 0 元素因在“第二行” ， 故该列在新矩阵B3中应排在“第二列” 。 在矩阵 B2中第 1 列有两个0 元素，如选取第一个0
9、 元素，因其在第三行，故该列在新矩阵B3中应排在“第三列” （也可选第二个0元素，按其处在第五行的位置，该列也可排在B3的第五列）。矩阵 B2第 3、4 列 0 元素中上面两行中的0 元素倘若要充当独立0 元素，就得排在新矩阵的前两列，可新矩阵前两列位置已被占据，故不可能排在前两列，这两列剩下的两个0 元素都在矩阵B2的第四行，所以这两列都可排在新矩阵的第四列，可任选一列 （这里选择了第4 列）放在第四列， 另外的一列（这里是第3 列）就只能被放在新矩阵的第五列了。因对角线上仍有一个“非0 元素” ，说明还差一个独立0 元素，故需要再化简，以增加独立0 元素。名师资料总结 - - -精品资料欢
10、迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - 英文钱法文赵俄文李德文王日文张即最优指派方案为：英法俄德日钱赵李王张英法俄德日钱赵李王张德法英俄日钱赵李王张翻译成翻译成翻译成翻译成翻译成元素标记独立经列调换，得43141140805384003702204314110408050384000370220140340011483500800403207205054BBB参考文献：教材编写组运筹学M 北京：清华大学出版社，1990P.130133 梁工谦 .运筹学典
11、型题解析及自测试题M 西安：西北工业大学出版社， 2002P.121 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 寻找独立 0 元素的一种新方法张联朋( 陕西工业职业技术学院工商管理系陕西咸阳712000 ) 摘要 ：本文根据独立0 元素在矩阵行和列中具有互斥性这一特点，提出了利用0 元素在矩阵中的位置来判断其是否为独立0 元素的对角线方法。关键词 ：指派问题，匈牙利法，独立0 元素，方法A new Method of se
12、eking the independent 0 elements Zhang Lian-peng (Department of Industrial and Commercial Management, Shaanxi Polytechnic Institute, Xian yang Shaanxi 712000 )Abstract:According to the Incompatibility of independent 0 elements in the matrix line and the row, the article proposed the diagonal line method of seeking the independent 0 elements in matrix. Key words: Assignment Problem ; The Hungarian Method of Assignment ;Independent 0 elements ; Method 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -