寻找独立0元素的一种新方法.docVIP

寻找独立0元素的一种新方法 张联朋 ( 陕西工业职业技术学院 工商管理系 陕西咸阳 712000 ) 摘要：本文根据独立0元素在矩阵行和列中具有互斥性这一特点，提出了利用0元素在矩阵中的位置来判断其是否为独立0元素的对角线方法。 关键词：指派问题；匈牙利法；独立0元素；方法 中图分类号文献标识码文章编号 二、对角线法的具体方法： 经过化简（对系数矩阵的每行元素减去该行的最小元素；再从所得系数矩阵的每列元素减去该列的最小元素）之后，新的系数矩阵(Bij)中各行各列都出现了0元素。 从0元素数量最少的列开始，选择该列第一个0元素，根据该0元素所在行的位置确定该列元素在新矩阵中列的位置（若该0元素在原矩阵中所在的行是第i行，那么就将该0元素所在列放在新矩阵的第i列） 英 日 德 法 俄 张 12 7 9 7 9 王 8 9 6 6 6 李 7 17 12 14 9 赵 15 14 6 6 10 钱 4 10 7 10 9 求解： B2 → B3 说明：在矩阵B2中，第2、5列0元素最少，各有一个，优先排序。第2列0元素因在“第一行”，故该列在新矩阵B3中应排在“第一列”；第5列0元素因在“第二行”， 故该列在新矩阵B3中应排在“第二列”。 在矩阵B2中第1列有两个0元素，如选取第一个0元素，因其在第三行，故该列在新矩阵B3中应排在“第三列”（也可选第二个0元素，按其处在第五行的位置，该列也可排在B3的第五列）。矩阵B2第3、4列0元素中上面两行中的0元素倘若要充当独立0元素，就得排在新矩阵的前两列，可新矩阵前两列位置已被占据，故不可能排在前两列，这两列剩下的两个0元素都在矩阵B2的第四行，所以这两列都可排在新矩阵的第四列，可任选一列（这里选择了第4列）放在第四列，另外的一列（这里是第3列）就只能被放在新矩阵的第五列了。 因对角线上仍有一个“非0元素”，说明还差一个独立0元素，故需要再化简，以增加独立0元素。 参考文献： ①教材编写组．运筹学[M]．北京：清华大学出版社，1990．P.130~133 ②梁工谦.运筹学典型题解析及自测试题[M]．西安：西北工业大学出版社 ，2002．P.121 寻找独立0元素的一种新方法 张联朋 ( 陕西工业职业技术学院 工商管理系 陕西咸阳 712000 ) 摘要：本文根据独立0元素在矩阵行和列中具有互斥性这一特点，提出了利用0元素在矩阵中的位置来判断其是否为独立0元素的对角线方法。 关键词：指派问题，匈牙利法，独立0元素，方法 A new Method of seeking 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