The Hungrian Algorithm Module

This module is an implementation of the Hungarian Algorithm for the Assignment Problem. The user-interface should be straight forward to students using conventional OR/MS textbooks where the algorithm is discussed.

However, .......

Most conventional OR/MS textbooks do not provide a full description of the algorithm. In particular, they do not spell out how to determine the minimum number of rows/columns required to cover all the zeros in the reduced cost matrix.

In small problems this can be done easily by inspection. But, ....

In contrast, this module will let you experiment with all the details of the algorithm, including the minimum coverage issue.

Note that the module is not a "SOLVE-BUTTON" oriented. The user must do the work and must know what to do. The module simply provides a spreadsheet-like facility for keeping track of the records during the implementation of the Hungarian Algorithm for the Assignment Problem. In short, you have to do the work, the module is just a sort of desk-organizer.

During classroom/lab demonstrations lecturers may wish to increase the font size using their browser's setup facilities.


Concerning the Hungarian connection, here is how the inventor of the algorithm explained the title:

... One interesting aspect of the algorithm is the fact that it is latent in the work of D. Konig and E. Egervary that predates the birth of linear programming by more than 15 years (hence the name, the "Hungarian Method") ...

H.W. Kuhn, The Hungarian Method for the Assignment Problem, Naval Research Logistics Quarterly, 2, 83-97, 1955.

 

© The University of Melbourne 2004.
Disclaimer and Copyright Information.

Created: 27 February 2004
Last modified: 27 February 2004
Authorised by: Moshe Sniedovich, Department of Mathematics and Statistics.
Maintained by: Moshe Sniedovich, Department of Mathematics and Statistics.
Email: m.sniedovich@ms.unimelb.edu.au