Metodo Hungaro

Método Húngaro

Autor: Manuel Dzul May

Para dar un inicio a este ensayo pienso que es muy importante abarcar como primer punto los orígenes del método, así mismo como su desarrollo histórico. En esta sección se describe el desarrollo del método utilizado para resolver el PA (Problemas de Asignación).

A pesar de la simplicidad de la formulación del PA, en los últimos 50 años este problema atrajo a cientos de investigadores, acompañando y a veces anticipando el desarrollo de la optimización combinatoria. Los orígenes del problema de asignación datan del siglo XVIII, cuando Monge en 1781 formuló el problema de transporte de la masa continua como un enorme problema de asignación que minimiza el coste de transportar todas las moléculas. La estructura combinatoria del problema fue investigada al principio del siglo XX (Miller, Kónig, Frobenius) mientras que el primer algoritmo de enumeración implícita (en tiempo exponencial) fue propuesto en los años 40 por Easterfield (1946). El problema fue formulado en un contexto moderno en los años 50, curiosamente no por un matemático, si no por un psicólogo. Thorndike (1950), presidente de la división de evaluación y medición de la asociación americana de psicología, definió el problema de asignación de la misma forma que un profesor hoy en día se lo explica a sus alumnos. "Sea un conjunto de “N” tareas y “N” trabajadores, debemos asignar a cada trabajador una tarea de forma que el beneficio sea máximo".

El nombre del problema, sin embargo, no fue inventado por Thorndike, sino por Votaw y Orden (1952) en un documento titulado: 'El problema de asignación de personal'. Thorndike explicó que presentó el problema a un matemático, quien observo que hay un número finito de permutaciones en el problema de asignar trabajadores a vacantes, por lo que desde el punto de vista matemático no había problema. Solo había que probarlos todos y elegir el mejor. El matemático concluyo ahí su estudio del problema, pero Thorndike observó: “Cuándo consideremos solo 10 vacantes y 10 hombres, hay alrededor de 3,5 millones de permutaciones. Probar todas las posibles permutaciones y elegir la mejor puede ser una solución matemática pero no es práctica”. Es sorprendente que un psicólogo de los años 50 comprendiera mejor la complejidad de un problema que un matemático (los matemáticos entenderían esto 15 años después con Edmond (1965)). El primer algoritmo moderno en tiempo polinomial para el problema de asignación, inventado por Harold W. Kuhn hace 50 años, fue bautizado como 'El método húngaro' para destacar que deriva de resultados anteriores de Kónig y Egerváry obtenidos en los primeros años del siglo XX.  Al analizar los resultados de estos matemáticos húngaros entendemos más este método diseñado para la optimización de un problema plantado que son los Problemas de Asignación en el método húngaro. Pese a los avances de los matemáticos fue entonces, Kuhn uso un diccionario de húngaro y escribió en ingles la traducción del documento. El principal resultado probado por Egerváry es un teorema en el que demuestra que en el problema de asignación (PA) el problema dual y el problema primal tienen el mismo valor objetivo. Egerváry no proporciono un algoritmo explicito para probar esto. Sin embargo, describió un método iterativo, que más adelante, Kuhn bautizó como el Método Húngaro en honor a Kónig y Egerváry. A lo largo de los orígenes de este método que estoy abarcando es relevante mencionar otra una de las definiciones del modelo matemático que abarca PA. Las preguntas que me hago para darle entendimiento a este término abreviado son: ¿Qué es PA? Y ¿quién diseño este modelo de problema matemático?, en realidad las respuestas se encuentran resuelto con el siguiente texto el matemático Jacobi dio la siguiente definición, en la cual el Problema de Asignación (PA) es fácilmente reconocible: “Sean n2 números en una tabla cuadrada de forma que hay n series horizontales y n series verticales, cada una teniendo n=números. Con estos números queremos seleccionar n transversales, es decir, todos en diferentes series verticales y horizontales, de forma que determinen la máxima suma de los n números seleccionados” Jacobi no solo definió el PA, también dio un algoritmo para resolverlo en tiempo polinomial.

De acuerdo al tema investigado y profundizado en la práctica del Método Húngaro, observe que existen diferentes métodos en el tema general que es de la Programación Lineal. Y determino a mi entendimiento, referente a los métodos relacionados a la programación lineal en general, que este realiza la búsqueda de soluciones óptimas. Pero por decir soluciones óptimas se refiere a la búsqueda de resultados posibles a tareas y/o actividades que no se pueden tener solución según el entendimiento humano, pero estos métodos a usar hacen posible su solución a los problemas que se pretendan dar una posible solución óptima. En las mayorías de las soluciones de estos problemas se usan programas tales como. (TORA Y FUNCIONES DE EXCEL) por mencionar algunas de cada uno de los temas abarcados de en programación lineal, estos programas mencionados pueden ser usados como resultado de sus funciones o fórmulas de cada programa, para problemas de transporte el método Simplex siempre resulta poco eficiente para resolver problemas de asignación, especialmente en problemas que son de gran tamaño. Por ello, para resolver problemas de asignación (minimización) se emplea normalmente el Método Húngaro. La cual ayuda a verificar si una solución es óptima La principal ventaja es que el método húngaro es considerablemente más simple que el método Simplex del problema de transporte por mencionar algunos problemas de asignación de la misma manera que los demás métodos que, en total son siete, hacen más fácil su solución de problemas de programación lineal. Otras de las cosas que observe al revisar información del método húngaro es el trabajo en conjunto que pueden tener el método PERT y CMP ya que estos dos métodos que pueden tener la facultad usar los modelos matemáticos y sus funciones de los métodos mencionados pueden hacer un trabajo en conjunto para llegar a una solución óptima y más clara en el entendimiento. Por lo tanto, cabe mencionar que es importante decir que este método húngaro de acuerdo al resultado matemático obtenido se puede asignar actividades y acondicionar las mismas en el caso de acondicionamiento de actividades no es decir que elimine actividades al ser asignadas como se podría entender en su representación en el modelo matemático, sino que hace que delimite la actividad, asignándole a un determinado terminó N para realizar la función.

...