El modelo de asignación
El modelo de asignación es un caso especial del modelo de transporte, en el que
los recursos se asignan a las actividades en términos de uno a uno, haciendo
notar que la matriz correspondiente debe ser cuadrada. Así entonces cada recurso
debe asignarse, de modo único a una actividad particular o asignación.
Se tiene un costo Cij asociado con el recurso que es asignado, de modo que el
objetivo es determinar en que forma deben realizarse todas las asignaciones para
minimizar los costos totales.
OBJETIVO
El objetivo del modelo es determinar la asignación óptima (de costo mínimo) de
trabajadores a puestos.
Ejemplo de un modelo de asignación general de tres orígenes y tres
destinos es:
DESTINO
ORIGEN 1 2 3 OFERTA
A C11 C12 C13 1
B C21 C22 C23 1
C C31 C32 C33 1
DEMANDA 1 1 1
Método Húngaro
Caso A: Minimización.
Revisar que todas las casillas tengan su costo ( beneficio) unitario
correspondiente. Si alguna no lo tiene asignarlo en términos del tipo de matriz y
problema considerado.
1. Balancear el modelo, es decir obtener m=n (obtener una matriz cuadrada)
En donde m= número de renglones.
En donde n= número de columnas.
Todo renglón o columna tendrá un costo (beneficio ) unitario de cero.
2. Para cada renglón escoger el MENOR VALOR y restarlo de todos los demás en
el MISMO RENGLÓN.
3. Para cada columna escoger el MENOR VALOR y restarlo de todos los demás
en la MISMA COLUMNA.
4. Trazar el MÍNIMO número de líneas verticales y horizontales de forma tal que
todos los ceros queden tachados.
5. Criterio de optimidad:
¿El número de líneas es igual al orden de la matriz?
SI, el modelo es óptimo y por tanto hacer la asignación y traducir la solución.
La asignación se debe hacer en las casillas donde haya ceros cuidando que cada
renglón y cada columna tenga una sola asignación.
NO pasar al siguiente punto.
6. Seleccionar el menor valor no tachado de toda la matriz. El valor restarlo de
todo elemento no tachado sumarlo a los elementos en la interacción de dos líneas.
7. Regresar al paso 4.
Caso B: Maximización.
Metodología:
Seleccionar el MAYOR ELEMENTO de toda la matriz de beneficio. Este valor
restarlo de todos los demás, los valores negativos que se obtengan representan
los costos de oportunidad, lo que se deja de ganar o producir.
Para el caso de la solución del modelo considerar solo valores absolutos. Con esta
transformación se ha obtenido un modelo de minimización y por tanto resolverlo
como tal.
Ejemplos:
Se necesita procesar 4 diferentes tareas para lo cual se cuenta con 4 máquinas.
Por diferencias tecnológicas el desperdicio que se produce depende del tipo de
tarea y la máquina en la cual se ejecuta, dada la matriz de Desperdicios
expresada en pesos definir la asignación óptima.
MAQUINAS
TAREAS 1 2 3 4
A 49 86 54 70
B 45 79 66 81
C 46 58 78 88
D 44 38 66 69
Como se trata de Desperdicios, buscaremos MINIMIZARLOS.
Checamos que todas las casillas tengan su costo unitario, en este caso se cumple
sin ningún problema.
Balanceamos la tabla M= renglones = 4 N= columnas= 4
Por lo que M=N, quedando balanceada.
MAQUINAS
TAREAS 1 2 3 4
A 49 86 54 70
B 45 79 66 81
C 46 58 78 88
D 44 38 66 69
Por renglón
Elegir el menor valor de renglón y restarlo a los demás. En este caso es son :
49,45,46,38.
Restamos ese valor a cada uno de los demás del renglón.
MAQUINAS
TAREAS 1 2 3 4
A 49-49=0 86-49=37 54-49=5 70-49=21
B 45-45=0 79-45=34 66-45=21 81-45=36
C 46-46=0 58-46=12 78-46=32 88-46=42
D 44-38=6 38-38=0 66-38=28 69-38=31
Formamos la nueva tabla
MAQUINAS
TAREAS 1 2 3 4
A 0 37 5 21
B 0 34 21 36
C 0 12 32 42
D 6 0 28 31
Por columna
Elegimos los menores valores de cada columna en este caso son : 0,0,5,21
Restamos esos valores a los demás números de las columnas
MAQUINAS
TAREAS 1 2 3 4
A 0-0=0 37-0=37 5-5=0 21-21=0
B 0-0=0 34-0=34 21-5=16 36-21=15
C 0-0=0 12-0=12 32-5=27 42-21=21
D 6-0=6 0-0=0 28-5=23 31-21=10
Obtenemos la nueva tabla:
MAQUINAS
TAREAS 1 2 3 4
A 0 37 0 0
B 0 34 16 15
C 0 12 27 21
D 6 0 23 10
Trazamos las líneas.
MAQUINAS
TAREAS 1 2 3 4
A 0 37 0 0
B 0 34 16 15
C 0 12 27 21
D 6 0 23 10
Contamos el número de líneas y observamos que son 3 líneas y el número de la
matriz es de 4 por lo que NO ES ÓPTIMO.
Buscamos dentro de la tabla el menor valor no tachado en este caso es 12
Lo restamos a todos los demás, respetando los valores de los ya tachados y
adicionándolos a los que están intersectados.
MAQUINAS
TAREAS 1 2 3 4
A 0+12=12 37 0 0
B 0 34-12=22 16-12=4 15-12=3
C 0 12-12=0 27-12=15 21-12=9
D 6+12=18 0 23 10
Nos queda:
MAQUINAS
TAREAS 1 2 3 4
A 12 37 0 0
B 0 22 4 3
C 0 0 15 9
D 18 0 23 10
Trazamos las líneas.
3 ≠ 4 NO ES ÓPTIMO
Volvemos a buscar el menor número de los no tachados.
MAQUINAS
TAREAS 1 2 3 4
A 12+3=15 37+3=40 0 0
B 0 22 4-3=1 3-3=0
C 0 0 15-3=12 9-3=6
D 18 0 23-3=20 10-3=7
En este caso es 3 y se lo restamos a los demás no tachados y respetamos a los
tachados y se los sumamos a los intersectados. Y volvemos a trazar líneas.
MAQUINAS
TAREAS 1 2 3 4
A 15 40 0 0
B 0 22 1 0
C 0 0 12 6
D 18 0 20 7
4=4 ES ÓPTIMO
Ahora checamos las asignaciones, sean 1 a 1.
MAQUINAS
TAREAS 1 2 3 4
A 15 40 0 0
B 0 22 1 0
C 0 0 12 6
D 18 0 20 7
0 = se escogen
0= se deshabilitan
Se traduce la solución:
Realizar la tarea A en la máquina 3 con un costo de $54
Realizar la tarea B con la máquina 4 con un costo $81.
Realizar la tarea C en la máquina 1 con un costo $46.
Realizar la tarea D en la máquina 2 con un costo $38.
Costo total mínimo= $219
