Ejercicio 1
Transcript of Ejercicio 1
![Page 1: Ejercicio 1](https://reader036.fdocumento.com/reader036/viewer/2022082606/55827f18d8b42adf088b52db/html5/thumbnails/1.jpg)
EJERCICIO DE UN
PROBLEMA DE ASISGNACIÓN
![Page 2: Ejercicio 1](https://reader036.fdocumento.com/reader036/viewer/2022082606/55827f18d8b42adf088b52db/html5/thumbnails/2.jpg)
Juan Manuel necesita asignar cuatro trabajos que recibió a cuatro empleados de planta. Las diversas habilidades de éstos dan origen a costos variados por el desempeño de los trabajos. La tabla siguiente resume los datos del costo de las asignaciones. Los datos indican que el empleado 1 no puede desempeñarse en el trabajo 3 y que el empleado 3 no puede desempeñarse en el trabajo 4. Determine la asignación óptima.
TRABAJADORTRABAJO
1 2 3 4
José Luís 50 50 20
José Paúl 70 40 20 30
José Miguel 90 30 50
José Antonio 70 20 50 70
![Page 3: Ejercicio 1](https://reader036.fdocumento.com/reader036/viewer/2022082606/55827f18d8b42adf088b52db/html5/thumbnails/3.jpg)
MODELO MATEMÁTICO DEL
PROBLEMA DE ASIGNACIÓN
![Page 4: Ejercicio 1](https://reader036.fdocumento.com/reader036/viewer/2022082606/55827f18d8b42adf088b52db/html5/thumbnails/4.jpg)
1J. Luís
2J. Paúl
4J. Antonio
3J. Miguel
1Trabajo
2Trabajo
3Trabajo
4Trabajo
50
50
50
50
20
20
20
70
70
70
40
30
90 30
1
1
1
1
1
1
1
1
![Page 5: Ejercicio 1](https://reader036.fdocumento.com/reader036/viewer/2022082606/55827f18d8b42adf088b52db/html5/thumbnails/5.jpg)
Expresiones que indican el tiempo necesario para completar los proyectos:
Costo de asignación para José Luís = 50x11 + 50x12 + 20x14
Costo de asignación para José Paúl = 70x21 + 40x22 + 20x23 + 30x24
Costo de asignación para José Miguel = 90x31 + 30x32 + 50x33
Costo de asignación para José Antonio = 70x41 + 20x42 + 50x43 + 70x44
Min 50x11+50x12+0x13+20x14+70x21+40x22+20x23+30x24+90x31
+30x32+50x33+0x34+70x41+20x42+60x43+70x44
RESTRICCIONES:
José Luís ≠ trabajo 3
José Miguel ≠ trabajo 4
xij≥0 para i=1,2,3,4 y para j =1,2,3,4
FUNCIÓN OBJETIVO:
![Page 6: Ejercicio 1](https://reader036.fdocumento.com/reader036/viewer/2022082606/55827f18d8b42adf088b52db/html5/thumbnails/6.jpg)
RESOLUCIÓN DEL PROBLEMA
MEDIANTE EL MÉTODO HÚNGARO
![Page 7: Ejercicio 1](https://reader036.fdocumento.com/reader036/viewer/2022082606/55827f18d8b42adf088b52db/html5/thumbnails/7.jpg)
Solo problemas de minimización Número de personas a asignar , es igual al número de lugares m Todas las asignaciones son posibles Una asignación por persona y una persona por asignación
TRABAJADORTRABAJO
1 2 3 4 Costo menor
José Luís 50 50 - 20 20
José Paúl 70 40 20 30 20
José Miguel 90 30 50 - 30
José Antonio 70 20 50 70 20
RESTRICCIONES DEL MÉTODO
MATRIZ DE COSTOS
![Page 8: Ejercicio 1](https://reader036.fdocumento.com/reader036/viewer/2022082606/55827f18d8b42adf088b52db/html5/thumbnails/8.jpg)
Restar el menor valor de cada fila
TRABAJADORTRABAJO
1 2 3 4 Costo menor
José Luís 50-20=30 50-20=30 - 20-20=0 20
José Paúl 70-20=50 40-20=20 20-20=0 30-20=10 20
José Miguel 90-30=60 30-30=0 50-30=20 - 30
José Antonio 70-20=50 20-20=0 50-20=30 70-20=50 20
![Page 9: Ejercicio 1](https://reader036.fdocumento.com/reader036/viewer/2022082606/55827f18d8b42adf088b52db/html5/thumbnails/9.jpg)
Restar el menor valor de cada columna
TRABAJADORTRABAJO
1 2 3 4 Costo menor
José Luís 30-30=0 30 - 0 20
José Paúl 50-30=20 20 0 10 20
José Miguel 60-30=30 0 20 - 30
José Antonio 50-30=20 0 30 50 20
Costo menor 30 0 0 0
![Page 10: Ejercicio 1](https://reader036.fdocumento.com/reader036/viewer/2022082606/55827f18d8b42adf088b52db/html5/thumbnails/10.jpg)
Trazar el mínimo número de líneas que cubran los ceros de la matriz obtenida en el punto anterior
TRABAJADORTRABAJO
1 2 3 4
José Luís 0 30 - 0
José Paúl 20 20 0 10
José Miguel 30 0 20 -
José Antonio 20 0 30 50
Como se puede ver existen 3 columnas y no es igual al número de filas que son 4 por lo tanto esta no es una solución óptima
![Page 11: Ejercicio 1](https://reader036.fdocumento.com/reader036/viewer/2022082606/55827f18d8b42adf088b52db/html5/thumbnails/11.jpg)
Identificar el menor valor no rayado
TRABAJADORTRABAJO
1 2 3 4
José Luís 0 30 - 0
José Paúl 20 20 0 10
José Miguel 30 0 20 -
José Antonio 20 0 30 50
![Page 12: Ejercicio 1](https://reader036.fdocumento.com/reader036/viewer/2022082606/55827f18d8b42adf088b52db/html5/thumbnails/12.jpg)
Identificar el menor valor no rayado y restarlo a los demás números no rayados
TRABAJADORTRABAJO
1 2 3 4
José Luís 0 30 - 0
José Paúl 20-10=10 20 0 10-10=0
José Miguel 30-10=20 0 20 -
José Antonio 20-10=10 0 30 50-10=40
![Page 13: Ejercicio 1](https://reader036.fdocumento.com/reader036/viewer/2022082606/55827f18d8b42adf088b52db/html5/thumbnails/13.jpg)
TRABAJADOR
TRABAJO
1 2 3 4
José Luís 0 30 - 0
José Paúl 20-10=10 20 0 10-10=0
José Miguel 30-10=20 0 20 -
José Antonio 20-10=10 0 30 50-10=40
Las asignaciones corresponde a los valores donde existe 0
TRABAJADORTRABAJO
1 2 3 4
José Luís 0 0
José Paúl 0 0
José Miguel 0
José Antonio 0
![Page 14: Ejercicio 1](https://reader036.fdocumento.com/reader036/viewer/2022082606/55827f18d8b42adf088b52db/html5/thumbnails/14.jpg)
Como se puede observar a José Paul se le puede asignar el trabajo 3 y con la resta del menor valor mas bien complico la asignación por que le abrió la posibilidad de asignación al cuarto trabajo y no soluciono el problema
TRABAJADORTRABAJO
1 2 3 4
José Luís 0 0
José Paúl 0 0
José Miguel 0
José Antonio 0
![Page 15: Ejercicio 1](https://reader036.fdocumento.com/reader036/viewer/2022082606/55827f18d8b42adf088b52db/html5/thumbnails/15.jpg)
Por lo tanto debemos encontrar el valor mínimo de la los nuevos valores que obtuvimos en todas las filas no seleccionadas
TRABAJADORTRABAJO
1 2 3 4
José Luís 0 30 - 0
José Paúl 10-10=0 20 0 0
José Miguel 20-10=10 0 20 -
José Antonio 10-10=0 0 30 40-10=20
TRABAJADORTRABAJO
1 2 3 4
José Luís 0 30 - 0
José Paúl 10 20 0 0
José Miguel 20 0 20 -
José Antonio 10 0 30 40
El menor valor es 10 y procedemos a restar
![Page 16: Ejercicio 1](https://reader036.fdocumento.com/reader036/viewer/2022082606/55827f18d8b42adf088b52db/html5/thumbnails/16.jpg)
TRABAJADORTRABAJO
1 2 3 4
José Luís 0 30 - 0
José Paúl 0 20 0 0
José Miguel 10 0 20 -
José Antonio 0 0 30 40-10=20
Después de realizar la resta vemos que la fila uno nos dio 2 nuevos ceros
Ahora vemos que a José Paul ya la seleccionamos el trabajo 3 por lo tanto proseguimos con José Antonio le asignaremos el trabajo 1 y a José Luis le seleccionamos al trabajo 4
![Page 17: Ejercicio 1](https://reader036.fdocumento.com/reader036/viewer/2022082606/55827f18d8b42adf088b52db/html5/thumbnails/17.jpg)
La asignación resultante es:
TRABAJADOR TRABAJO
José Luís 4
José Paúl 3
José Miguel 2
José Antonio 1
Costo Asignación:
TRABAJADORTRABAJO
1 2 3 4
José Luís 50 50 20
José Paúl 70 40 20 30
José Miguel 90 30 50
José Antonio 70 20 50 70
70+30+20+20= 140