Clase pracica N15 Distribucion (Asignacion)

Vista previa del material en texto

CLASE PRACTICA: Investigación Operativa
Trabajo Practico Nº 7 – Distribución 
Profesores: JTP. Ing. Néstor O. Cruz
AY1. Ing. Mariela E. Rodríguez
Facultad de Ingeniería
Universidad Nacional de Jujuy
Método de Asignación – Método “Húngaro” 
A B C D
1 23 22 27 21
2 22 24 25 24
3 34 30 30 28
4 42 47 45 48
1
2
3
4
A
B
C
D
23
22
27
21
22
24
25
24
34
30
30
28
42 47
45
48
Red de Asignación 
Tabla de Costos
Método de Asignación – Método Húngaro 
A B C D
1 23 22 27 21
2 22 24 25 24
3 34 30 30 28
4 42 47 45 48
Z(min) = 23 X1A + 22 X1B + 27 X1C + 21 X1D + 22 X2A + 24 X2B + 25 X2C + 24 X2D +
34 X3A + 30 X3B + 30 X3C + 28 X3D + 42 X4A + 47 X4B + 45 X3C + 48 X4D
SA: 
X1A + X1B + X1C + X1D = 1
X2A + X2B + X2C + X2D = 1
X3A + X3B + X3C + X3D = 1
X4A + X4B + X4C + X4D = 1
X1A + X2A + X3A + X4A = 1
X1B + X2B + X3B + X4B = 1
X1C + X2C + X3C + X4C = 1
X1D + X2D + X3D + X4D = 1
Xij ≥ 0 i = {1, 2, 3, 4} j = {A, B, C, D}
Formulación Matemática 
Tabla de Costos
Método de Asignación – Método Húngaro 
A B C D
1 23 22 27 21
2 22 24 25 24
3 34 30 30 28
4 42 47 45 48
Aplicación del Método 
A B C D
1 2 1 6 0
2
3
4
Pasos:
1. Identificar el mínimo de cada fila.
2. Restar el valor mínimo identificado a los demás elementos de la fila.
3. Repetir los pasos hasta completar todas las filas
A B C D
1 23 22 27 21
2 22 24 25 24
3 34 30 30 28
4 42 47 45 48
Aplicación del Método 
A B C D
1 2 1 6 0
2 0 2 3 2
3
4
Pasos:
1. Identificar el mínimo de cada fila.
2. Restar el valor mínimo identificado a los demás elementos de la fila.
3. Repetir los pasos hasta completar todas las filas
Método de Asignación – Método Húngaro 
A B C D
1 23 22 27 21
2 22 24 25 24
3 34 30 30 28
4 42 47 45 48
Aplicación del Método 
A B C D
1 2 1 6 0
2 0 2 3 2
3 6 2 2 0
4
Pasos:
1. Identificar el mínimo de cada fila.
2. Restar el valor mínimo identificado a los demás elementos de la fila.
3. Repetir los pasos hasta completar todas las filas
Método de Asignación – Método Húngaro 
A B C D
1 23 22 27 21
2 22 24 25 24
3 34 30 30 28
4 42 47 45 48
Aplicación del Método 
A B C D
1 2 1 6 0
2 0 2 3 2
3 6 2 2 0
4 0 5 3 6
Pasos:
1. Identificar el mínimo de cada fila.
2. Restar el valor mínimo identificado a los demás elementos de la fila.
3. Repetir los pasos hasta completar todas las filas
Método de Asignación – Método Húngaro 
A B C D
1 2 1 6 0
2 0 2 3 2
3 6 2 2 0
4 0 5 3 6
Aplicación del Método 
A B C D
1 2
2 0
3 6
4 0
Pasos:
1. Identificar el mínimo de cada fila.
2. Restar el valor mínimo identificado a los demás elementos de la fila.
3. Repetir los pasos hasta completar todas las filas
4. Ahora trabajaremos con la matriz obtenida hasta el paso 3
5. Identificar el mínimo de cada columna.
6. Restar el valor mínimo identificado a los demás elementos de la columna
Método de Asignación – Método Húngaro 
A B C D
1 2 1 6 0
2 0 2 3 2
3 6 2 2 0
4 0 5 3 6
Aplicación del Método 
A B C D
1 2 0
2 0 1
3 6 1
4 0 4
Pasos:
1. Identificar el mínimo de cada fila.
2. Restar el valor mínimo identificado a los demás elementos de la fila.
3. Repetir los pasos hasta completar todas las filas
4. Ahora trabajaremos con la matriz obtenida hasta el paso 3
5. Identificar el mínimo de cada columna.
6. Restar el valor mínimo identificado a los demás elementos de la columna
7. Repetir los pasos hasta completar todas las filas
Método de Asignación – Método Húngaro 
A B C D
1 2 1 6 0
2 0 2 3 2
3 6 2 2 0
4 0 5 3 6
Aplicación del Método 
A B C D
1 2 0 4
2 0 1 1
3 6 1 0
4 0 4 1
Pasos:
1. Identificar el mínimo de cada fila.
2. Restar el valor mínimo identificado a los demás elementos de la fila.
3. Repetir los pasos hasta completar todas las filas.
4. Ahora trabajaremos con la matriz obtenida hasta el paso 3
5. Identificar el mínimo de cada columna.
6. Restar el valor mínimo identificado a los demás elementos de la columna
7. Repetir los pasos hasta completar todas las columnas.
Método de Asignación – Método Húngaro 
A B C D
1 2 1 6 0
2 0 2 3 2
3 6 2 2 0
4 0 5 3 6
Aplicación del Método 
A B C D
1 2 0 4 0
2 0 1 1 2
3 6 1 0 0
4 0 4 1 6
Pasos:
1. Identificar el mínimo de cada fila.
2. Restar el valor mínimo identificado a los demás elementos de la fila.
3. Repetir los pasos hasta completar todas las filas
4. Ahora trabajaremos con la matriz obtenida hasta el paso 3
5. Identificar el mínimo de cada columna.
6. Restar el valor mínimo identificado a los demás elementos de la columna
7. Repetir los pasos hasta completar todas las filas
8. Trazar con la mínima cantidad de líneas horizontales o verticales todos los 
ceros posibles.
Método de Asignación – Método Húngaro 
Método de Asignación – Método Húngaro 
Aplicación del Método 
A B C D
1 2 0 4 0
2 0 1 1 2
3 6 1 0 0
4 0 4 1 6
Pasos:
8. Si la cantidad de líneas utilizadas es igual a la dimensión n=4 de la tabla, 
ya llegamos a la solución. 
9. Si la cantidad de líneas es menor a la dimensión n de la tabla, se debe 
encontrar el valor mínimo de los valores no tachados.
10. Restar el valor mínimo encontrado a todos los valores NO trazados.
A B C D
1
2 0 0 1
3
4 3 0 5
Método de Asignación – Método Húngaro 
Aplicación del Método 
A B C D
1 2 0 4 0
2 0 1 1 2
3 6 1 0 0
4 0 4 1 6
Pasos:
8. Trazar con la mínima cantidad de líneas horizontales o verticales todos los 
ceros.
9. Si la cantidad de líneas utilizadas es igual a la dimensión n=4 de la tabla, 
ya llegamos a la solución. 
10. Si la cantidad de líneas es menor a la dimensión n de la tabla, se debe 
encontrar el valor mínimo de los valores no tachados.
11. Restar el valor mínimo encontrado a todos los valores NO trazados.
12. Sumar el valor mínimo encontrado a todos los valores trazados 
doblemente.
A B C D
1 3
2 0 0 1
3 7
4 3 0 5
Método de Asignación – Método Húngaro 
Aplicación del Método 
A B C D
1 3 0 4 0
2 0 0 0 1
3 7 1 0 0
4 0 3 0 5
Pasos:
8. Trazar con la mínima cantidad de líneas horizontales o verticales todos los 
ceros.
9. Si la cantidad de líneas utilizadas es igual a la dimensión n = 4 de la tabla, 
ya llegamos a la solución. 
10. Si la cantidad de líneas es menor a la dimensión n de la tabla, se debe 
encontrar el valor mínimo de los valores no tachados.
11. Restar el valor mínimo encontrado a todos los valores NO trazados.
12. Sumar el valor mínimo encontrado a todos los valores trazados 
doblemente.
13. Los demás valores de la tabla quedan igual.
14. (volvemos al paso 8) Trazamos con líneas horizontales o verticales todos 
los ceros.
15. La cantidad de líneas utilizadas es igual a la dimensión n = 4, se llego a la 
solución, donde los ceros en la tabla son los casilleros donde se puede 
asignar.
A B C D
1 3 0 4 0
2 0 0 0 1
3 7 1 0 0
4 0 3 0 5
Método de Asignación – Método Húngaro 
Aplicación del Método 
A B C D
1 3 0 4 0
2 0 0 0 1
3 7 1 0 0
4 0 3 0 5
Pasos:
16. Asignar un cero de la tabla para cada fila y columna como asignación en 
la tabla solución, como se realiza en la tabla. 
17. Hacemos este paso hasta completar la tabla.
A B C D
1 1
2
3
4
Tabla para Asignar
Solución 1
Aplicación del Método 
A B C D
1 3 0 4 0
2 0 0 0 1
3 7 1 0 0
4 0 3 0 5
A B C D
1 1
2 1
3
4
Tabla para Asignar
Solución 1
Pasos:
16. Asignar un cero de la tabla para cada fila y columna como asignación en 
la tabla solución, como se realiza en la tabla. 
17. Hacemos este paso hasta completar la tabla.
Método de Asignación – Método Húngaro 
Aplicación del Método 
A B C D
1 3 0 4 0
2 0 0 0 1
3 7 1 0 0
4 0 3 0 5
A B C D
1 1
2 1
3 1
4
Tabla para Asignar
Solución 1
Pasos:
16. Asignar un cero de la tabla para cada fila y columna como asignación en 
la tabla solución, como se realiza en la tabla. 
17. Hacemos este paso hasta completar la tabla.
Método de Asignación – Método Húngaro 
Aplicación del Método 
A B C D
1 3 0 4 0
2 0 0 0 1
3 7 1 0 0
4 0 3 0 5
A B C D
1 1
2 1
3 1
4 1
Tabla para Asignar
Solución 1
Pasos:
16. Asignarun cero de la tabla para cada fila y columna como asignación en 
la tabla solución, como se realiza en la tabla. 
17. Hacemos este paso hasta completar la tabla.
Encontramos todas las soluciones posibles de asignación
Método de Asignación – Método Húngaro 
Aplicación del Método 
A B C D
1 3 0 4 0
2 0 0 0 1
3 7 1 0 0
4 0 3 0 5
A B C D
1 1
2 1
3 1
4 1
A B C D
1 1
2
3
4
Tabla para Asignar
Solución 1 Solución 2
Pasos:
16. Asignar un cero de la tabla para cada fila y columna como asignación en 
la tabla solución, como se realiza en la tabla. 
17. Hacemos este paso hasta completar la tabla.
Encontramos todas las soluciones posibles de asignación
Método de Asignación – Método Húngaro 
Aplicación del Método 
A B C D
1 3 0 4 0
2 0 0 0 1
3 7 1 0 0
4 0 3 0 5
A B C D
1 1
2 1
3 1
4 1
A B C D
1 1
2 1
3
4
Tabla para Asignar
Solución 1 Solución 2
Pasos:
16. Asignar un cero de la tabla para cada fila y columna como asignación en 
la tabla solución, como se realiza en la tabla. 
17. Hacemos este paso hasta completar la tabla.
Encontramos todas las soluciones posibles de asignación
Método de Asignación – Método Húngaro 
Aplicación del Método 
A B C D
1 3 0 4 0
2 0 0 0 1
3 7 1 0 0
4 0 3 0 5
A B C D
1 1
2 1
3 1
4 1
A B C D
1 1
2 1
3 1
4
Tabla para Asignar
Solución 1 Solución 2
Pasos:
16. Asignar un cero de la tabla para cada fila y columna como asignación en 
la tabla solución, como se realiza en la tabla. 
17. Hacemos este paso hasta completar la tabla.
Encontramos todas las soluciones posibles de asignación
Método de Asignación – Método Húngaro 
Aplicación del Método 
A B C D
1 3 0 4 0
2 0 0 0 1
3 7 1 0 0
4 0 3 0 5
A B C D
1 1
2 1
3 1
4 1
A B C D
1 1
2 1
3 1
4 1
Tabla para Asignar
Solución 1 Solución 2
Pasos:
16. Asignar un cero de la tabla para cada fila y columna como asignación en 
la tabla solución, como se realiza en la tabla. 
17. Hacemos este paso hasta completar la tabla.
Encontramos todas las soluciones posibles de asignación
Método de Asignación – Método Húngaro 
Aplicación del Método 
A B C D
1 3 0 4 0
2 0 0 0 1
3 7 1 0 0
4 0 3 0 5
A B C D
1 1
2 1
3 1
4 1
A B C D
1 1
2 1
3 1
4 1
Tabla para Asignar
Solución 1 Solución 2
Pasos:
16. Asignar un cero de la tabla para cada fila y columna como asignación en 
la tabla solución, como se realiza en la tabla. 
17. Hacemos este paso hasta completar la tabla.
Encontramos todas las soluciones posibles de asignación
Método de Asignación – Método Húngaro 
Aplicación del Método 
A B C D
1 3 0 4 0
2 0 0 0 1
3 7 1 0 0
4 0 3 0 5
A B C D
1 1
2 1
3 1
4 1
A B C D
1 1
2 1
3 1
4 1
A B C D
1 1
2
3
4
Tabla para Asignar
Solución 1 Solución 2 Solución 3
Pasos:
16. Asignar un cero de la tabla para cada fila y columna como asignación en 
la tabla solución, como se realiza en la tabla. 
17. Hacemos este paso hasta completar la tabla.
Encontramos todas las soluciones posibles de asignación
Método de Asignación – Método Húngaro 
Aplicación del Método 
A B C D
1 3 0 4 0
2 0 0 0 1
3 7 1 0 0
4 0 3 0 5
A B C D
1 1
2 1
3 1
4 1
A B C D
1 1
2 1
3 1
4 1
A B C D
1 1
2 1
3
4
Tabla para Asignar
Solución 1 Solución 2 Solución 3
Pasos:
16. Asignar un cero de la tabla para cada fila y columna como asignación en 
la tabla solución, como se realiza en la tabla. 
17. Hacemos este paso hasta completar la tabla.
Encontramos todas las soluciones posibles de asignación
Método de Asignación – Método Húngaro 
Aplicación del Método 
A B C D
1 3 0 4 0
2 0 0 0 1
3 7 1 0 0
4 0 3 0 5
A B C D
1 1
2 1
3 1
4 1
A B C D
1 1
2 1
3 1
4 1
A B C D
1 1
2 1
3 1
4
Tabla para Asignar
Solución 1 Solución 2 Solución 3
Pasos:
16. Asignar un cero de la tabla para cada fila y columna como asignación en 
la tabla solución, como se realiza en la tabla. 
17. Hacemos este paso hasta completar la tabla.
Encontramos todas las soluciones posibles de asignación
Método de Asignación – Método Húngaro 
Aplicación del Método 
A B C D
1 3 0 4 0
2 0 0 0 1
3 7 1 0 0
4 0 3 0 5
A B C D
1 1
2 1
3 1
4 1
A B C D
1 1
2 1
3 1
4 1
A B C D
1 1
2 1
3 1
4 1
Tabla para Asignar
Solución 1 Solución 2 Solución 3
Pasos:
16. Asignar un cero de la tabla para cada fila y columna como asignación en 
la tabla solución, como se realiza en la tabla. 
17. Hacemos este paso hasta completar la tabla.
Encontramos todas las soluciones posibles de asignación
Método de Asignación – Método Húngaro 
Calculo de Z
A B C D
1 23 22 27 21
2 22 24 25 24
3 34 30 30 28
4 42 47 45 48
A B C D
1 1
2 1
3 1
4 1
A B C D
1 1
2 1
3 1
4 1
A B C D
1 1
2 1
3 1
4 1
Tabla de Costos
Solución 1 Solución 2 Solución 3
El calculo de Z se realiza de la siguiente manera:
Solución 1:
Z = 22 + 22 + 28 + 45 = 117
Solución 2:
Z = 21 + 24 + 30 + 42 = 117
Solución 3: 
Z = 22 + 25 + 28 + 42 = 117
Método de Asignación – Método Húngaro 
Problema de Asignación – Caso de Maximización
Seleccionar el mayor valor de toda la tabla
Luego restar a todos los costos .
EQUIPO
E1 E2 E3 E4
T
R
A
B
A
J
O T1 86 38 40 34
T2 46 84 50 58
T3 38 50 80 75
T4 32 34 44 36
EQUIPO
E1 E2 E3 E4
T
R
A
B
A
J
O T1 0 48 46 52
T2 40 2 36 28
T3 48 36 6 11
T4 54 52 42 50
EQUIPO
E1 E2 E3 E4
T
R
A
B
A
J
O T1 0 46 40 41
T2 40 0 30 17
T3 48 34 0 0
T4 54 50 36 39
EQUIPO
E1 E2 E3 E4
T
R
A
B
A
J
O T1 0 46 23 24
T2 40 0 13 0
T3 65 51 0 0
T4 54 50 19 22
86
84
80
44
0 2 6 11
Convertimos en Minimización. 
Problema de Asignación, Maximización
EQUIPO
E1 E2 E3 E4
T
R
A
B
A
J
O T1 86 38 40 34
T2 46 84 50 58
T3 38 50 80 75
T4 32 34 44 36
EQUIPO
E1 E2 E3 E4
T
R
A
B
A
J
O T1 0 46 23 24
T2 40 0 13 0
T3 65 51 0 0
T4 54 50 19 22
86
84
80
44
EQUIPO
E1 E2 E3 E4
T
R
A
B
A
J
O T1 0 46 23 24
T2 40 0 13 0
T3 65 51 0 0
T4 35 31 0 3
FO : 86+84+44+75 = 289Solución :
EQUIPO
E1 E2 E3 E4
T
R
A
B
A
J
O T1 1
T2 1
T3 1
T4 1
EQUIPO
E1 E2 E3 E4
T
R
A
B
A
J
O T1 86 38 40 34
T2 46 84 50 58
T3 38 50 80 75
T4 32 34 44 36
86
84
80
44
Resolver por software, utilizando Solver.
Preguntas