PROBLEMAS DE ASIGNACION




I.-PROBLEMA DE ASIGNACIÓN


DEFINICIÒN.-

Es una variación del problema original de transporte, variación en la cual las variables de decisión X solo pueden tomar valores binarios, es decir ser cero (0) o uno (1) en la solución óptima, lo que supone que la oferta y la demanda están perfectamente alineadas, de hecho ambas son iguales a uno (1).

SOLUCIÒN ÒPTIMA POR EL METODO HÙNGARO

Estealgoritmo se usa para resolver problemas de minimización, ya que es más eficaz que el empleado para resolver el problema del transporte por el alto grado de degeneración que pueden presentar los problemas de asignación.

Las fases para la aplicación del método Húngaro son:

Paso 1:

Encontrar primero el elemento más pequeño en cada fila de la matriz de costos m*m; se debe construir una nueva matriz alrestar de cada costo el costo mínimo de cada fila; encontrar para esta nueva matriz, el costo mínimo en cada columna. A continuación se debe construir una nueva matriz (denominada matriz de costos reducidos) al restar de cada costo el costo mínimo de su columna.



Paso 2:

(En algunos pocos textos este paso se atribuye a Flood). Consiste en trazar el número mínimo de líneas (horizontales overticales o ambas únicamente de esas maneras) que se requieren para cubrir todos los ceros en la matriz de costos reducidos; si se necesitan m líneas para cubrir todos los ceros, se tiene una solución óptima entre los ceros cubiertos de la matriz. Si se requieren menos de m líneas para cubrir todos los ceros, se debe continuar con el paso 3. El número de líneas para cubrir los ceros es igual a lacantidad de asignaciones que hasta ese momento se pueden realizar.

Paso 3:

Encontrar el menor elemento diferente de cero (llamado k) en la matriz de costos reducidos, que no está cubierto por las líneas dibujadas en el paso 2; a continuación se debe restar k de cada elemento no cubierto de la matriz de costos reducidos y sumar k a cada elemento de la matriz de costos reducidos cubierto por doslíneas (intersecciones). Por último se debe regresar al paso 2.

Notas:

1. Para resolver un problema de asignación en el cual la meta es maximizar la función objetivo, se debe multiplicar la matriz de ganancias por menos uno (-1) y resolver el problema como uno de minimización.

2. Si el número de filas y de columnas en la matriz de costos son diferentes, el problema de asignación está desbalanceado.El método Húngaro puede proporcionar una solución incorrecta si el problema no está balanceado; debido a lo anterior, se debe balancear primero cualquier problema de asignación (añadiendo filas o columnas ficticias) antes de resolverlo mediante el método Húngaro.

3. En un problema grande, puede resultar difícil obtener el mínimo número de filas necesarias para cubrir todos los ceros en la matrizde costos actual.
Se puede demostrar que si se necesitan líneas para cubrir todos los ceros, entonces se pueden asignar solamente j trabajos a un costo cero en la matriz actual; esto explica por qué termina cuando se necesitan líneas.

Mediante el siguiente ejemplo vamos a ilustrar la manera de aplicar el método Húngaro a la solución de un problema de asignación de minimización: Una factoría tienecuatro operarios, los cuales deben ser asignados al manejo de cuatro máquinas; las horas requeridas para cada trabajador en cada máquina se dan en la tabla adjunta; el tiempo a laborar por cada operario en cada una de las máquinas se pretende que sea mínimo, para lo cual se busca la asignación óptima posible.







Planteamiento del Modelo Primal:MINW=10X11+14X12+16X13+13X14+12X21+13X22+15X23+12X24++9X31+12X32+12X33+11X34+14X41+16X42+18X43+16X44

Sujeto a las siguientes restricciones:



Aplicando el método húngaro tenemos:





Restamos 10, 12, 9 y 14 (costos mínimos de cada fila) de cada elemento en cada una de las filas correspondientes

En la matriz anterior trazamos el menor número de líneas (3), de manera tal que cubran todos los ceros (Método de Flood)


En la matriz anterior...