On the assignment and transportation problems (abstract)
On the assignment and transportation problems (abstract)
复制标题
关于分配和交通问题（摘要）
DOI：
10.1002/nav.3800040112
复制
发表时间：
1957
期刊：
影响因子：
--
通讯作者：
J. Munkres
中科院分区：
文献类型：
--
作者：
J. Munkres
本文提出了一种求解分配问题的算法，该算法是h.w.库恩所谓的匈牙利方法的一种变体[11]。我们还对运输问题进行了推广。由于详细的论述将在其他地方出现，我们在这里只作一些一般性的评论就够了。成本矩阵。在匈牙利方法及其变体中，一般的过程是通过在矩阵的行和列中加减常数来变换矩阵，直到得到一个在某一关键排列中包含零元素的矩阵。在确定要加减哪些数字的过程中，需要区分某些行和列，这些行和列通常被称为覆盖行或列。人们还需要区分某些零元素，通常通过星号（以及在本算法中使用的素数）来完成。如果手工操作，会很繁琐。密歇根大学（University of Michigan）的运筹学研究小组（Operations Research group）建造了一台特殊用途的计算机来辅助这一过程。作者的算法是为这台计算机开发的。每个都能显示从0到10的任意整数。有一个附加的电话拨号，用于在面板上初始设置矩阵。在每一行和每一列的旁边都有一个按钮，按下一个按钮将使对应行（或列）中的每个数字减少1；按下另一个会使这一行中的每一个数字增加
In this paper we presented an algorithm for the assignment problem which is a variant of H. W. Kuhn's so-called Hungarian method [11. We also gave a generalization of it to the transportation problem. Since a detailed exposition will appear elsewhere [23, we shall content ourselves here with a few general remarks. the cost matrix. In the Hungarian method and its variants, the general procedure is to transform the matrix by adding and subtracting constants from rows and columns of the matrix, until a matrix is obtained which contains zero elements in a certain crucial arrangement. In the process of determining what numbers to add and subtract, one needs to distinguish certain rows and columns, which are usually called covered rows or columns. One also needs to distinguish certain zero elements, usually done by means of asterisks (and primes, as well, in the present algorithm). tedious if carried out by hand. The Operations Research group, ERI, University of Michigan, has constructed a special-purpose computer to aid in this procedure. The author's algorithms were developed for use with this computer. each one capable of displaying any integer from 0 to 10. There is a telephone dial attached which is used to set up the matrix on the panel initially. Next to each row and column are push-buttons-pressing one button will cause each number in the corresponding row (or column) to be diminished by 1; pressing the other will cause each number in the row to be increased