El método húngaro de asignación: aplicaciones

Abstract

The linear sum assignment problem is one of the most interesting problems in linear programming and in combinatorial optimization. It consists of finding a minimum weight perfect matching in a weighted bipartite graph. It is a problem that has interested many people throughout history, because it has many applications,from the allocation of resources in military operations in the Second World War, to the configuration of satellite communication and other communication technologies. Other applications that will be considered specifically in this study are the following: The traveling salesperson (or, salesman) problem (TSP) is a wellknown and important combinatorial optimization problem. The goal is to find the shortest tour that visits each city in a given list exactly once and then returns to the starting city. As it will be shown, the solution of the assignment problem determines a lower bound of the optimal objective of the TSP and it can be used as the starting solution of a cutting algorithm for the TSP. Matrix visualization: Permutation of the rows and columns of matrices to analyze multivariate data with medium to low sample size. The idea is to make a data matrix more understandable by simultaneously rearranging rows (variables) and columns (cases) + grouping. This process is related to the TSP and hence, the solution of the assignment problem could be considered as an initial rearrangement that, possibly, should be improved in order to have an optimal representation of the matrix. The Hungarian algorithm is the most relevant procedure that have been devised in order to solve the linear assignment problem. The genesis of this method was reported by the author H. W. Kuhn. In 1953, while reading the classical graph theory book by Konig, he encountered an efficient algorithm for determining the maximum cardinality of a bipartite graph. In this essay we will describe this method, study its complexity and show the main properties that make it one of the most useful algorithm in Operations Research.