2.3 Problema de la asignación.

Problema de la asignación.

Introducción.

El problema de asignación consiste en encontrar la forma de asignar ciertos recursos disponibles (máquinas o personas) para la realización de determinadas tareas al menor coste, suponiendo que cada recurso se destina a una sola tarea, y que cada tarea es ejecutada por uno solo de los recursos. Es uno de los problemas fundamentales de optimización combinatoria de la rama de optimización o investigación operativa en matemática. El modelo se puede aplicar a la asignación de empleados a tareas, de fábricas a productos, de vendedores a territorios, de postores a contratos, etc. Con una sencilla manipulación, el método también se puede aplicar al caso en el que se pretende maximizar cierta cantidad.

Formalmente, el problema de la asignación consiste en encontrar un emparejamiento de peso óptimo en un grafo bipartito ponderado. El problema de asignación es un caso particular del problema de transporte, en el que la oferta en cada origen y la demanda en cada destino son ambas de valor 1.

Definición del problema de asignación.

En su forma más general, el problema es como sigue:

Hay un número de agentes y un número de tareas. Cualquier agente puede ser asignado para desarrollar cualquier tarea, contrayendo algún coste que puede variar dependiendo del agente y la tarea asignados. Es necesario, para desarrollar todas las tareas, asignar un solo agente a cada tarea de modo que el coste total de la asignación sea mínimo.

Este tipo de problemas son lineales, con una estructura de transporte, solo que la oferta en cada origen es de valor uno y la demanda en cada destino es también de valor uno. Sería muy ineficiente resolver este tipo de problemas por medio del método simplex o por medio del algoritmo de transporte. Debido a la estructura propia de los problemas de asignación, existen métodos de solución llamados "algoritmos de asignación" que son más eficientes que el simplex o que el método de transporte.

Los problemas de asignación presentan una estructura similar a los de transporte, pero con dos diferencias: asocian igual número de orígenes con igual número de demandas y las ofertas en cada origen es de valor uno, como lo es la demanda en cada destino.

La restricción importante para cada agente es que será asignado a una sola tarea.

Características

El problema de asignación presenta las siguientes características:

El Problema de Asignación debe estar equilibrado, es decir, que la relación entre las ofertas y las demandas sean igual a 1. Un elemento importante para el problema de asignación es la matriz de costos. Si el número de renglones o columnas no son iguales el problema está desbalanceado y se puede obtener una solución incorrecta. Para obtener una solución correcta la matriz debe ser cuadrada.

Si el número de agentes y tareas son iguales y el coste total de la asignación para todas las tareas es igual a la suma de los costes de cada agente (o la suma de los costes de cada tarea, que es lo mismo en este caso), entonces el problema es llamado problema de asignación lineal. Normalmente, cuando hablamos de problema de asignación sin ninguna matización adicional, nos referimos al problema de asignación lineal.

Oferta: Cantidad que representa la disponibilidad del artículo en la fuente/fábrica de donde proviene.

Demanda: Cantidad de artículos que necesita recibir el destino para cumplir sus necesidades.

Diferencias con el Modelo de Transporte y Asignación

Los problemas de asignación son casos particulares de los problemas de transporte y constituyen la clase más sencilla de los problemas lineales, en el cual los trabajadores representan las fuentes y los puestos representan los destinos.

·         En el problema de transporte existen m orígenes y n destinos, y el flujo se realiza desde un origen hacia cada uno de los diferentes destinos. Si en este caso permitimos el flujo en ambos sentidos (de origen a destino y destino a origen) se puede hablar de un problema de m + n orígenes y m + n destinos. A este tipo de problemas se les conoce con el nombre de problemas de transbordo (transhipment problems) o transporte con nodos intermedios.

·         En el caso más general, cada punto de origen o destino pude ser un punto de transbordo, es decir, cada origen puede evitar o transportar a otros orígenes o a distintos; y los destinos pueden transportar a su vez a otros destinos o volver a los orígenes. Un punto conserva su identidad, origen o destino, solamente cuando sea respectivamente, un punto que originalmente disponga de un suministro o un punto que tenga una demanda a satisfacer.

·         En los problemas de asignación las ofertas en cada origen es de valor uno, como lo es la demanda en cada destino; una gran diferencia con respecto a los problemas de transporte.

Balanceado

Se dice que un problema de asignación se encuentra balanceado, si los recursos totales son iguales a las demandas totales. En caso contrario se dice que no está balanceado el problema.

Además en el modelo, m = n (obtener una matriz cuadrada), en donde m número de renglones y n es número de columnas.

Para lograr que el modelo este balanceado se pueden agregar trabajadores/tareas ficticias con costos de cero.

Método Húngaro

El método húngaro es un método de optimización de problemas de asignación, conocido como tal gracias a que los primeros aportes al método clásico definitivo fueron de Dénes König y Jenő Egerváry dos matemáticos húngaros.

Este método utiliza la propiedad de reducción de matrices para reducir la matriz original de costo, hasta que los costos C i j asociados con la asignación óptima, sean cero y todos los otros costos sean no negativos.

En cada iteración del método húngaro, se reduce la matriz de tal manera que haya al menos un cero en cada renglón y columna, comprobando con el teorema de König si se ha alcanzado la solución óptima. Si el número mínimo de renglones y/o columnas necesarios para cubrir todos los ceros es n, entonces existe una asignación óptima (no necesariamente única).

El algoritmo tal como se detallará a continuación está diseñado para la resolución de problemas de minimización únicamente, ya que es más eficaz para resolver el problema del transporte por el alto grado de degeneración que pueden presentar los problemas de asignación.

Los problemas de asignación incluyen aplicaciones tales como asignar personas a tareas. Aunque sus aplicaciones parecen diferir de las del problema del transporte, constituye un caso particular. Los problemas de transporte y asignación son casos particulares de un grupo más grande de problemas, llamados problemas de flujo en redes.

Suposiciones de un problema de asignación:

1.    El número de asignados es igual al número de tareas (se denota por n). (esto puede variar).

2.    Cada asignado se asigna exactamente a una tarea.

3.    Cada tarea debe realizarla exactamente un asignado.

4.    Existe un costo cij asociado con el asignado i (i=1,2,…,n).

5.    El objetivo es determinar cómo deben hacerse las asignaciones para minimizar los costos totales

Procedimiento:
El Método Húngaro consta de los siguientes pasos:
Paso 1: En la matriz original de costo, identificar el mínimo de cada fila y restarlo de todos los elementos de la fila.
Paso 2: En la matriz que resulte del Paso 1, identificar el mínimo de cada columna, y restarlo de todos los elementos de la columna.
Paso 3: Identificar la solución óptima como la asignación factible asociada con los elementos cero de la matriz obtenida en el Paso 2.

A continuación presentaremos un ejemplo que muestra la aplicación del Método Húngaro que nos permite decidir la asignación de trabajadores a puestos de trabajo.
Ejemplo:
Un equipo de 3 ingenieros debe ser asignado para la realización de 3 tareas, donde cada ingeniero debe hacer una tarea. Se requiere encontrar la asignación de costo mínimo para lo cual se dispone de los costos asociados a que el ingeniero i realice la tarea j. Por ejemplo, representa el costo correspondiente a que el ingeniero 1 asuma la tarea 1.

Aplicar el Método Húngaro para encontrar una asignación óptima de los ingenieros a las tareas.
El Paso 1 del Método Húngaro requiere identificar el valor mínimo de cada fila. En el caso de la fila 1 dicho valor es $9 siendo el costo de que el ingeniero realice la tarea 3.
En particular si se dispone de un problema de mayor tamaño, hacer uso de Excel facilita los cálculos tal como se muestra en la siguiente imagen:

A continuación se resta el mínimo de cada fila a cada uno de los valores de la fila respectiva, para obtener la matriz reducida:

La aplicación del Paso 2 produce los mínimos de cada columna según se observa en la tabla anterior. Al restar esos valores de las columnas respectivas se obtiene la siguiente matriz reducida:

Las celdas con valor cero y color azul son la solución óptima. En consecuencia el ingeniero 1 realiza la tarea 2, el ingeniero 2 asuma la tarea 1 y el ingeniero 3 la tarea 3. Cada ingeniero realiza exactamente una tarea y el costo total de dicha asignación (valor óptimo) es de: 

$9 + $10 + $8 = $27

Los pasos presentados del Método Húngaro para el ejemplo anterior funcionaron bien debido a que los elementos cero de la matriz anterior permiten una asignación factible de ingenieros a las tareas (en el sentido que las tareas se asignan de forma única a los ingenieros). Aunque no siempre es posible lograr una solución factible en la aplicación, caso en el cual se requiere de pasos adicionales para la aplicación del método.

Conclusión

El método de asignación es computacionalmente más eficiente que el método simplex para una clase especial de problemas. Su objetivo es asignar personas para realizar ciertas tareas, minimizando costos. Sin embargo, no necesariamente deben de ser personas, también pueden ser máquinas, vehículos, fábricas, etc.

Los problemas de asignación de hicieron con el objetivo de reducir el tiempo de fabricación al mínimo para así aumentar la producción lo máximo posible organizar las máquinas y los trabajadores, Para así optimizar los recursos que posee la organización en cuestión

Para satisfacer la demanda que exige el día a día en las operaciones de la empresa sin estos métodos de asignación los precios de los productos se dispararían por las nubes, y las fábricas serian todo un caos, los recursos se desperdiciarían.