---

MODELOS DE ASIGNACIÓN

---

Los problemas de asignación se ocupan de asignar trabajadores a tareas sobre una base de uno a uno. Se considera el número de trabajadores igual al número de tareas (condición que puede garantizarse creando trabajadores o tareas ficticias) y se conoce el tiempo Cij que necesita el trabajador i para terminar la tarea j. El objetivo es asignar a cada trabajador una tarea de manera que todas las tareas se terminen en un tiempo total mínimo.

El problema de asignación puede transformarse en un problema de transporte al considerar a los trabajadores como orígenes y a las tareas como destinos con todos los suministros y demandas igual a uno. Método húngaro

El algoritmo que se utiliza para resolver el problema de asignación es el método húngaro que consta de cuatro pasos:

1. Localice el menor elemento de cada renglón y réstelo a los demás elementos del mismo renglón. Repítase este procedimiento para cada columna donde el mínimo por columna se determina después de las restas de los renglones.

2. Determine si existe una asignación factible que involucre costos cero en la matriz revisada de costos. Si existe tal asignación es óptima. Si no existe continúe con el paso 3.

3. Cubra todos los ceros en la matriz revisada de costos con el menor número de líneas horizontales y verticales que sea posible. Cada línea horizontal debe pasar por todo el renglón y cada línea vertical por toda la columna. Localice el número menor que no esté cubierto por una línea en la matriz de costos. Reste el valor de este número a cada elemento no cubierto por una línea y súmelo a cada elemento cubierto por dos líneas.

4. Repita el procedimiento del paso 2.

Ejemplo 1.

Una cadena de restaurantes de servicio rápido desea construir cuatro tiendas. Anteriormente, la compañía ha empleado 6 diferentes compañías y, estando satisfecha con todas ellas, las ha invitado a concursar para cada trabajo. Las ofertas finales en miles de dólares son las que se muestran. tienda constructoras

Ya que la cadena desea tener listos los nuevos establecimientos tan pronto como sea posible otorgará cuando más un trabajo a cada compañía constructora, ¿que asignación da como resultado un costo total mínimo para la cadena de restaurantes?

Ejemplo 2.

Una competencia de relevos de 400 metros incluye a cuatro diferentes nadadores quienes nadan sucesivamente 100 metros de dorso, pecho, mariposa y libre. Un entrenador tiene 6 nadadores muy veloces cuyos tiempos esperados en segundos en los eventos individuales se dan en la tabla ¿Cómo deberá el entrenador asignar los nadadores a los relevos a fin de minimizar la suma de sus tiempos?