Modelo de asignacion

Modelo de asignación pura.
Considere un caso especial del problema de transporte en que se cumple: m = n; es decir, el número de orígenes es igual a los destinos; además [pic]= b j =1.
El modelo así definido es asignación pura, se refiere a la acción de asignar uno a uno; esto es, en forma biunívoca. Se entiende asignar n candidatos a n acciones requeridas, conociendo la medida de desempeño,que puede ser costo, beneficio o rendimiento. El problema consiste en asignar de forma idónea para conseguir el mejor resultado general.
Por ejemplo, la asignación de personas a operar máquinas, para las cuales se tiene la información de la capacidad individual al trabajar con ellas, se acepta como asignación pura de operarios a máquinas. Otro ejemplo, se refiere a la asignación de competidorespara desempeñarse en la competencia de algún evento deportivo, desde luego, con diferente eficiencia individual; aquí también se asigna un competidor para ocupar cada relevo de la carrera o cada posición en un juego colectivo.
[pic]
C i j = costo o valor del desempeño individual de i en la acción j.
Sujeta a las restricciones:
[pic]X i j = 1; desde i = 1 hasta i = n; de j = 1 hasta j= n.
[pic]Matriz de asignación pura

MÉTODO HÚNGARO para la asignación.
La más conocida técnica de solución para el problema de asignación pura es el método húngaro, desarrollado a partir del teorema que demostró el matemático húngaro König en 1916. Este método utiliza la propiedad de reducción de matrices para reducir la matriz original de costo, hasta que los costos Cij asociadoscon 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 unaasignación óptima (no necesariamente única).

Ejemplo 1.
La siguiente matriz contiene los costos para operar n = 4 máquinas, por n = 4 personas así calificadas en su empresa. Optimice la asignación idónea.
[pic]
Matriz de costos en ejemplo
Paso 1. Seleccione en cada renglón i de la matriz, el menor costo Cij, (menor Cij = Ui), luego réstelo en cada elemento del renglón.
[pic]Paso 2. Seleccione en cada columna j de la matriz resultante en el paso 1, el costo menor C ij, (menor Cij=Vj) y réstelo en cada elemento de la misma columna.
[pic]

Paso 3. Sombree los renglones y/o columnas de la matriz, de tal modo que sean los mínimos necesarias para cubrir todos los ceros.
[pic]

Paso 4. Seleccione entre los costos no sombreados, el número menor Cij, (= Uij) o bien,el menor Cij,(= Vij), y réstelo a todos los costos no sombreados; después, sume el mismo a los costos ubicados en la intersección de los renglones y columnas sombreados. Este paso se repite hasta lograr la solución óptima.
[pic]

Se tiene la solución óptima cuando el mínimo necesario de renglones y columnas sombreadas para cubrir los ceros es n. En este problema el mínimo es n = 4.
[pic]Entonces la asignación óptima es la que muestra la tabla siguiente:
[pic]

Solución óptima: X11 = 1, X23 = 1, X32 = 1, X44 = 1
Z = C11 X11 + C23 X23 + C32 X32 + C44 X44 = 1(1) + 10(1) + 5(1) + 5(1) = 21
En la solución óptima, la suma de las costos Ui restados de renglones i en paso 1, más las costos V j restados de columnas j en paso 2, más el costo U i j ó V i j, restado y / o sumado, en paso4, proporciona el correspondiente valor óptimo. Así el costo es:
Z óptimo = [pic]U i + [pic]V j + [pic]U i j + [pic]V i j, para toda i, para toda j.
[pic]U i = U1 + U2 + U3 + U4 + U32 = 1 + 7 + 4 + 5 + 1 = 18
[pic]V j = V1 + V2 + V3 + V4 = 0 + 0 + 3 + 0 = 3
[pic]U i + [pic]V j = 18 + 3 = 21

Ejemplo 2.
La siguiente matriz muestra costos C i j de n = 5 candidatos i (i = 1,2,...,5) así...