AÑO DE LA CONSOLIDACIÓN DEL MAR DE GRAU ”
UNIVERSIDAD NACIONAL JOSE FAUSTINO SANCHEZ CARRIÓN
“FACULTAD DE INGENIERIA INDUSTRIAL, SISTEMAS E
INFORMATICA”
TEMA: MODELO ASIGNACIÓN
CURSO: INVESTIGACIÓN DE OPERACIONES
DOCENTE: Ing. PEREZ RAMIREZ JOSE LUIS
INTEGRANTE:
-ALEJANDRO MORA SAMANTA
-LOARTE SANA KIMBERLY
-SANCHEZ MARIN MARICELY YAZMIN
Huacho-PERÚ
MODELO DE ASIGNACIÓN
El modelo considera la asignación de n labores a n trabajadores, optimizando una
determinada medida de efectividad en la asignación óptima (la menos costosa) de
trabajadores a las labores, que logre un beneficio máximo para la empresa. El
modelo de asignación es una aplicación del modelo de transporte, donde el
modelo matemático es:
c
ij el costo de asignar una labor i a un trabajador j. Las asignaciones se efectúan
es
de uno a uno, por lo tanto: n = m, o sea:
Cada trabajador ð efectua una sola labor
Cada labor ð requiere un solo trabajador
Si Nº labores > Nº trabajadores ð quedan labores sin efectuarse;
Nº trabajadores > Nº labores ð quedan trabajadores sin
labor.
Números de variables
Números de restricciones
N° de soluciones factibles
Ejemplo: Si se asignan 5 operarios a 5 tareas, entonces tendremos en la solución
del modelo de asignación: 25 variables; 10 restricciones, y 120 soluciones factibles.
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.
Entre las aplicaciones del modelo de asignación, podemos mencionar:
Asignar tareas a máquinas, trabajadores a labores, personal de ventas a puntos
de ventas, contratistas a contratos (proyectos), etc.
Método Húngaro
Es un método de solución del modelo de asignación, los autores fueron los matemáticos
Konning y Egervary (de origen húngaro) quienes desarrollaron el algoritmo húngaro.
METODOLOGÍA
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.
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.- Razar el MÍNIMO número de líneas verticales y horizontales de forma tal que
todos los ceros queden tachados.
5.- Determinar el 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 tachadao sumarlo a los elementos en la interacción de dos
líneas.
7.- Regresar al paso 4.
Caso B: Maximización.
• 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.
EJEMPLO:
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.
M A Q U I N A
S
T 1 2 3 4
A A 49 86 54 70
B 45 79 66 81
R
C 46 58 78 88
E D 44 38 66 69
A
S
Como se trata de desperdicios, buscaremos MINIMIZARLOS.
Verificamos 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.
M A Q U I N A
S
T 1 2 3 4
A A 49 86 54 70
B 45 79 66 81
R
C 46 58 78 88
E D 44 38 66 69
A
S
POR FILA O RENGLÓN
Elegir el menor valor de cada fila o renglón y restarlo a los demás; en este caso son : 49,
45, 46, 38; luego restamos ese valor a cada uno de los demás números de la fila.
M A Q U I N A S
T 1 2 3 4
A A 49-49=0 86-49=37 54-49=5 70-49=21
R
B 45-45=0 79-45=34 66-45=21 81-45=36
E
A C 46-46=0 58-46=12 78-46=32 88-46=42
S D 44-38=6 38-38=0 66-38=28 69-38=31
FORMAMOS LA NUEVA TABLA
M A Q U I N A S
T 1 2 3 4
A
A 0 37 5 21
R
B 0 34 21 36
E
A C 0 12 32 42
S D 6 0 28 31
POR COLUMNA.
Elegimos el menor valor de cada columna, en este caso son : 0, 0, 5, 21;
luego restamos esos valores a los demás números de las columnas
M A Q U I N A S
T 1 2 3 4
A 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
R
C 0-0=0 12-0=12 32-5=27 42-21=21
E D 6-0=6 0-0=0 28-5=23 31-21=10
A
S
Obtenemos una tabla nueva
M A Q U I N A
T 1 2 3 4
A A 0 37 0 0
B 0 34 16 15
R
C 0 12 27 21
E D 6 0 23 10
A
S
Trazamos las líneas: Considerando en donde hay mas ceros seguidos en las filas y/o columnas
Contamos el número de líneas y observamos que son 3 líneas y el número de la matriz es de 4x4, por lo tanto NO
ES ÓPTIMO. Continuamos la metodología:
Buscamos dentro de la tabla el menor valor no tachado en este caso es 12
Lo restamos 12 a todos los demás, respetando los valores de los ya tachados y adicionándolo 12 a los que están
intersectados.
M A Q U I N A S
T 1 2 3 4
A A 0+12=12 37 0 0
R
B 0 34-12=22 16-12=4 15-12=3
E
A
C 0 1 27-12=15 21-12=9
S
2
-
1
2
=
0
D 6+12=18 0 23 10
3 ≠ 4 NO ES ÓPTIMO
Volvemos a buscar el menor número de los no tachados, en este caso es
Luego lo restamos 3 a los demás valores no tachados y respetamos a los tachados y sumamos 3 a los intersectados.
M A Q U I N A S
T 1 2 3 4
A 12+3=15 37+3=40 0 0
A
B 0 22 4-3=1 3 -
R
3
E
=
A
0
S C 0 0 15-3=12 9-3=6
D 18 0 23-3=20 10-3=7
Y volvemos a trazar líneas. 3
Ahora verificamos que las asignaciones, sean 1 a 1.
M A Q U I N A S
T 1 2 3 4
A 15 40 0 0
A
B 0 22 1 0
R C 0 0 12 6
D 18 0 20 7
E
A
S
0 = se escogen; 0 = se deshabilitan
La solución de asignar tareas a máquinas será:
Realizar la tarea A en la máquina 3 con un costo de $54
Realizar la tarea B en la máquina 4 con un costo de $81.
Realizar la tarea C en la máquina 1 con un costo de $46.
Realizar la tarea D en la máquina 2 con un costo de $38.
Costo total mínimo: Z = $ 219
Elaboramos la red de asignación:
A 1
B 2
C 3
D 4
T a reas M áquin as
GRACIAS
