Problema de asignación Método Hungaro

Problema de Asignación

Para poder explicar el concepto de asignación analizaremos los siguientes ejemplos:
1.- Suponga que somos entrenadores de natación y que próximamente participaremos en unas competencias, especialmente en una prueba de relevos combinando cuatro estilos: pecho, mariposa, dorso y libre, además contamos con cuatro experimentados nadadores que obviamente no son expertos ono harían el mismo tiempo en todas y cada una de los estilos. El problema consiste en qué competidor participará en qué estilo de tal manera de que el tiempo total de la competencia sea el mínimo. Los datos del problema pueden presentarse en la siguiente tabla que representa una matriz de tiempos.
E s t i l o s
Nadadores: Pecho Mariposa Dorso Libre
José Alberto 40 60 40 40Isaais 20 40 50 10
Noé 30 50 30 20
Carlos 40 30 20 30

Nótese que estamos hablando de cuatro estilos y cuatro nadadores o sea de una matriz cuadrada.
2.- Suponga que administramos un taller que funciona por medio de órdenes de trabajo y que para ello se cuenta con máquinas que pueden realizar cualquiera de los trabajos solicitados, ahoraparticularizando suponga que tenemos que realizar cinco trabajos y que tenemos cinco máquinas que pueden hacer dicho trabajo, ahora si cada una de las máquinas por diferentes circunstancias hace un trabajo en particular con costos diferentes, ya sea por el estado de la máquina, el grado de automatización que tenga, su antigüedad o simplemente el manejo del operador. Tenemos el problema de qué máquina deberáprocesar qué trabajo de tal manera que se minimice el costo total de realización de los cinco trabajos. Los datos del problema pueden presentarse en la siguiente tabla que representa una matriz de costos.
M á q u i n a s
Trabajos: A B C D
1 45 63 45 41
2 20 42 50 19
3 37 50 32 22
4 40 38 23 39

Eneste caso son cuatro máquinas y cuatro trabajos, si nada más tuviéramos tres trabajos a realizar debemos incluir un trabajo ficticio con costo de operación iguales a cero, pues una condición para que pueda funcionar el algoritmo que resuelve el problema es que la tabla de datos debe ser una matriz cuadrada. Podemos considerar esto último en la siguiente tabla:


M á q u i n a s
Trabajos:A B C D
1 45 63 45 41
2 20 42 50 19
3 37 50 32 22
4(ficticio) 0 0 0 0

3.- Suponga que tenemos la posibilidad de invertir en tres instituciones bancarias y cada una ofrece rendimientos según sus planes de inversión X,Y, Z, en particular digamos que la cantidad a invertir es de $ 1,000,000 , los tresbancos ofrecen las mismas alternativas pero con diferentes rendimientos según la eficiencia y políticas de cada institución. Tenemos el problema en qué plan debo invertir en qué banco de tal manera que se maximice el rendimiento total sobre mi inversión. Los datos del problema pueden presentarse en la siguiente tabla que representa una matriz de rendimientos porcentaje.
P l an
Banco: X Y Z
Bmx 45 63 35
BBV 50 42 50
SFN 37 50 42

Todo problema de asignación se puede plantear como un problema de Programación Lineal. También podemos mencionar que el problema de transporte puede ser considerado como un problema de asignación pero con restricciones de capacidad y de demanda.Conclusión: en concreto se tienen “m” recursos y “n” actividades y se quiere asignar un recurso a una actividad y una actividad a un recurso de tal manera que se minimice o maximice según sea el criterio de decisión (costos, tiempos, utilidades, rendimientos, etc.).


Método Húngaro

El método que se utiliza para resolver un problema de asignación es el llamado “método Húngaro”, que consiste de los...