MÉTODO HÚNGARO DE ASIGNACIÓN

TEMA 04 MÉTODO HÚNGARO DE ASIGNACIÓN

Introducción

Los matemáticos Dénes Köning y Jenö Egervary presentaron sus trabajos en la primera mitad del siglo XX, estos trabajos fueron la base con lo que el matemático  William  Harold Kuhn (1925-2014) presento en 1955 su trabajo sobre el problema de asignación, y desde entonces se le conoce como el método húngaro.

Un caso particular del modelo de transporte es el modelo de asignación, que tiene como propósito asignar personas u objetos a tareas de tal forma que se optimice algún objetivo, por ejemplo: minimizar tiempos de producción, costos o defectos de producción. Históricamente el problema de asignación se resolvió utilizando las  mismas técnicas que se utilizaban para el modelo de transporte, sin embargo, resultaba tedioso hacerlo de esta manera debido a las características particulares del mismo. A partir del trabajo realizado por dos matemáticos húngaros, se obtiene un algoritmo eficiente para este modelo;  Iniciamos la unidad planteando el problema general de asignación, hacemos hincapié en su estructura, como en el caso especial del modelo de transporte y planteamos algunos problemas tipo. Continuamos resolviendo el modelo de asignación por el método húngaro. Terminamos la unidad estudiando algunos problemas de asignación desbalanceados.

Mapa conceptual

[pic 1]

4.1 El problema de asignación

Gould, Eppen & Schmidt (1992)  nos explican el problema de asignación de la siguiente manera:

Los problemas de asignación ocurren en muchos contextos de administración. En general consisten en el problema para determinar la asignación óptima de agentes u objetos  “individuales” a “n” tareas. Por ejemplo, el administrador puede tener que asignar agentes  de venta  a territorios designados, o telefonistas para atender llamadas de servicios, o editores a los manuscritos, o modelos a las agencias de publicidad. Los agentes u objetos  que van a designarse son indivisibles en el sentido de que ningún agente se puede dividir entre varias  tareas. La restricción importante, para cada agente, es que será designado a una y solo una tarea. (p, 299)

William Harold Kuhn, presento la primera versión conocida del método Húngaro en 1955. Esta fue revisada por James Munkres en 1957, y ha sido conocido desde entonces como el   algoritmo del método húngaro, método de asignación Munkres, o el algoritmo de Kuhn-Munkres.

El algoritmo modela un problema de asignación como una matriz de costo m x n, donde cada elemento representa el costo de asignar la n trabajadora al m trabajo. El algoritmo utiliza el método de eliminación Gaussiana para hacer aparecer por lo menos un ceros en cada fila y columna. Sin embargo, en el caso de un problema de maximización de  beneficio, el costo de la matriz necesita ser modificada de modo que la minimización de sus elementos resulte maximizar los valores de costo originales.

4.2 El algoritmo del método Húngaro

Respecto al algoritmo del método húngaro Kamlesh & Solow (1996) nos presenta el algoritmo del método húngaro

Características claves para satisfacer la asignación óptima, cada nueva matriz calculada deberá satisfacer los siguientes criterios:

• Propiedad 1: Todos los números son no negativos.
• Propiedad 2: Cada fila y cada columna tiene  al menos una celda con un valor de cero

Siempre que en cualquiera de estas matrices, encuentre una asignación en la que cada celda seleccionada  tenga un valor  de cero, ha encontrado, de hecho la asignación  óptima.

Pasos conceptuales del algoritmo de asignación

• Paso 0.   Inicialización: al sustraer números apropiados de las filas y/o columnas de la matriz de asignación original, cree una nueva matriz de asignación que tenga las propiedades 1 y 2
• Paso 1. Prueba de optimalidad: Sí es posible encontrar una asignación factible en la matriz actual en la que cada celda seleccionada tenga un valor de cero, deténgase con una asignación óptima; de otra forma, vaya al paso 2.
• Paso 2.  Movimiento: Al sumar y/o sustraer  números apropiados  de las filas y/o columnas de la actual matriz de asignación, cree una nueva matriz de asignación con las propiedades 1 y 2 y vaya al paso 1.   (p, 449)

4.2.1 Ejercicio resuelto

Un Vicepresidente de una compañía Francesa desea envía cuatro gerentes (G1, G2, G3 y G4)  para un proceso de auditoría a las plantas situadas en Argentina, Brasil, Perú  y  Venezuela. Los costos de envío y las plantas se reflejan en la Tabla 4.2.1  (Los costos pueden representar las habilidades de cada gerente para solucionar ciertos problemas ubicados en cada planta, asimismo puede ser costos de dinero o una relación relativa de capacidades)

Paso uno: Se identifica en cada fila el valor mínimo, que luego es restada de todos los valores de cada fila

[pic 2]

Paso  dos: Se restan a cada fila el valor mínimo

[pic 3]

Paso tres : Se hace lo mismo con cada columna

[pic 4]

Paso cuatro: Se tachan los ceros con líneas (con las mínimas posibles) de tal manera que si el número de líneas es igual al tamaño de la matriz (en este caso es 4x4), se detiene el proceso, y se asignan los valores; para nuestra caso tenemos solo tres líneas por lo que se necesita hacer otro paso adicional.

Se ubica el valor mínimo de la matriz que no se encuentre cubierta por las líneas, para nuestro caso es el número 2, el cual se restara a todos los otro números no cubiertos por las líneas; pero para los números ubicados en las intersecciones de las líneas se sumaran

[pic 5]

Pasó cinco: Se tachan todos los ceros (cuidando que sean con  las líneas  mínimas posibles), para nuestro caso son cuatro, como la matriz es 4x4, el método ha terminado y procedemos a la asignación de recursos.

[pic 6]

Paso seis: La asignación de recursos empieza siempre por las columnas o filas que solo tienen un cero, de otra manera no sería posible asignarles otro valor; posteriormente se trabaja para asignarle a cada recurso a su actividad.

...