Algoritmo Húngaro

Análisis de Algoritmos

Algoritmo Húngaro. Solución a los problemas de asignación

Índice:
1. Índice: ....................................................................................................... 2 2. Introducción .............................................................................................. 3 1. El Algoritmo Húngaro................................................................................ 4 2. Ejemplo práctico. ...................................................................................... 6 3. Conclusión............................................................................................... 11 4. Bibliografía .............................................................................................. 12

2

Introducción
Lapresente investigación da a conocer el algoritmo húngaro, que también es conocido como el algoritmo de la asignación de Munkers, este método resuelve problemas de minimización u optimización en cuanto a la asignación de tiempos. Este algoritmo fue propuesto por Harold W. Khun en la década de 1.950 con el principal objetivo de resolver los problemas de acoplamiento máximo en grafos bipartidos. Desdeaquel entonces su método ha sido implantado en muchos proyectos y/o empresas para solucionar problemas de optimización. En este trabajo de investigación, se explicará de una manera práctica cómo se debe aplicar el método húngaro para resolver un caso en particular, que consiste en la asignación de nuevos clientes a directivos de una empresa informática. Tanto los clientes como los directivos serántratados en una matriz de NxM, donde N serán los clientes y M los directivos encargados de prestar atención a los clientes.

3

1. El Algoritmo Húngaro.
Este algoritmo nace por la necesidad de resolver problemas de asignación de tiempos como una matriz de costo de NxM, donde cada elemento representa el costo de asignar al n trabajador al m trabajo. El algoritmo húngaro utiliza unametodología para realizar la minimización sobre aquellos elementos de la matriz, como en el caso de un problema de minimización de precios. Para entender esto de una mejor manera, planteemos un ejemplo sencillo. Imaginemos que se tienen a tres trabajadores en su empresa, los cuales son Pedro, Juan y Diego. Luego necesitamos asignar a cada uno de los trabajadores a una tarea en especial, la cual consistirápor ejemplo en limpiar los pasillos de la oficina, asear los baños y por último ordenar la oficina del Gerente. Es entonces cuando surge la necesidad de realizar la asignación a cada empleado de su organización para una tarea específica, cada una con diferentes costos. Entonces debemos plantear al personal las tareas que se deben cumplir en una matriz de costos que se presenta a continuación.Ordenar oficina del Gerente $30 $30 $20

Limpiar pasillos

Asear baños

Pedro Juan Diego

$10 $30 $30

$20 $30 $30

Se podría determinar la asignación del personal a cada tarea al “ojímetro” como lo llamamos en Chile, donde por ejemplo, Pedro limpiará los pasillos, pues él solo cobra $10, así como podemos asignar a Juan para asear los baños que tiene un costo de $30 y a Diego

4

aordenar la oficina del Gerente por un costo de $20. Pues si realizamos la suma de asignar a cada empleado una tarea le daría un costo de $60. Esto lo hemos resuelto sin utilizar el método húngaro, pues bien, ahora ¿Qué sucedería si ya no fueran solo tres empleados ni tres tareas, sino que tenemos quince tareas y quince empleados con diferentes costos de asignación? . Es en estos casos dondenecesitaremos de un método matemático el cual logre resolver nuestro problema de asignación para que nos permita obtener el menor costo posible, a esto se le llama optimización y/o minimización, y el algoritmo húngaro ofrece esta solución. El algoritmo Húngaro utiliza el método de eliminación de Gauss, que realiza ciertos pasos para lograr que en una matriz aparezcan ceros, esto es, al menos un cero por...