a
2.
METÓDOS
CUANTITATIVOS AVANZADOS 2.12 ©
Prof. Raúl Espejo Rodarte
LECTURAS
UABC FCAS (414) 2.12.2.
2.12.2-1
Modelos de Transporte y Asignación
Nombre recibido por que la mayor parte de los problemas que pretende determinar la manera óptima de asignación de rutas, aunque también se usa para otras aplicaciones (como el control de la producción) que no tienen nada que ver con el transporte. También se describen las técnicas para optimizar los problemas de asignación, en los que los valores posibles de las variables de decisión son booleanos (1 o 0). Es el caso de tener que asignar operarios a máquinas, donde solo se asigna un operario a una máquina. En cualquier caso, aunque hay un gran número de variables y de restricciones, la matriz resultante es altamente redundante, por lo que puede usarse el método SIMPLEX. Si además encontramos alguna solución inicial factible, nos evitamos las variables artificiales, lo que permite una técnica de resolución más sencilla. 2.12.2.1.
Modelos de Transporte
Para la solución de problemas en los que se ha de optimizar la asignación de productos o servicios que se generan en ciertas ubicaciones de una zona geográfica, mientras los centros de distribución y consumo están en otros lugares, dentro de dicha región. La asignación de productos de una fuente a cada destino tiene un costo, distancia, riesgos, u otros inconvenientes, posiblemente diferentes entre si, por lo que existe al menos una solución óptima. Si estos costos son cuantificables, el problema se puede resolver por programación lineal para minimizar costos o maximizar utilidades. Por razones propias de cada zona hay ubicaciones en que se puede poner una planta de producción: {Uso de suelo, Materia prima, Mano de obra, Costo de terreno, Agua y drenaje, Facilidades de comunicaciones, Posibilidades de transporte, reglamentación, etc.}. En cambio, los centros de distribución se ubican en áreas densamente pobladas con una gran facilidad de transporte y facilidades financieras. No es conveniente, ni factible económicamente poner la fábrica en el centro de distribución. En un modelo más realista, se puede considerar el reenvío, y la posibilidad de contar con varios modelos o productos, así como ahorros por volumen. La producción, la demanda y el costo de traslado son los parámetros del problema, que obligan a buscar la forma más económica de asignar los productos a sus centros de demanda. Estos se pueden resumir en la siguiente tabla:
Distribuidores Productores
i
1 2 … m
j 1 C1,1 C2,1 … Cm,1
Cantidad Demandada
2 … C1,2 … C2,2 … … Ci,j Cm,2 ….
n C1,n C2,n … Cm,n
Cantidad Producida
P1 P2 Pi Pm n
D1
2.12.2.1.1.
D2
Dj
Dn
m
D P j 1
j
i 1
i
Sistema equilibrado
Si se cumple la siguiente condición (la suma de demandas es igual a la suma de productores):
©
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
2.12.2-2
UABC FCAS (414) n
m
D P j 1
j
i 1
i
Se dice que el problema está equilibrado. 2.12.2.1.1.1.
Equilibrando
Si no está equilibrado, agregar una columna o un renglón que lo equilibre, con costos 0. Para el caso de que la suma de demandas (producciones) sea mayor que la suma de producciones (demandas), entonces agregar un renglón de producción (demanda) tal que equilibre ambas sumas, con costos cero. 2.12.2.1.1.1.
00 5 10 3 10 2 4
8
7
3
6
7
17
11
17
Ejemplo 00 5 00 3 10 2
20
4
10
Agregar un renglón con producción de 10 y costos 0
5
3
17
00 5 10 3 10 2 4
8
7
3
6
7
17
11
7
15
0 11
00 5 00 3 10 2
Agregar una columna con demanda de 10 y costos 0
→35≠45↓
5 0
10 5 10 →45≠45↓
17
0
4
8
7
0
3
6
5
0
17 2.12.2.1.2.
7
Ejemplo
20 10
6
0
→45≠35↓
2.12.2.1.1.2.
8
20
11
7
10
20 10 5 →45≠45↓
Destinos prohibidos
En el caso de que un destino sea inaccesible o prohibido, se asigna como costo la variable M, que significa un número mayor que el mayor costo incluido en el problema, para impedir que se haga una asignación a dicho destino.
©
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414)
Ejemplo
2.12.2.1.2.1.
00 M 10 3 10 2 4
8
7
3
6
7
17
2.12.2.1.3.
11
2.12.2-3
20 10 5 →35≠35↓
7
Variables de decisión
Son las diferentes asignaciones de unidades a mover de cada fuente a cada destino. Estas suelen ser muchas pues son m*n donde m es el número de fuentes y n es el número de destinos.
Distribuidores Productores
i
1 2 … m
J 1 X1,1 X2,1 … Xn,1
Cantidad Demandada
… … … XI,J ….
2 X1,2 X2,2 … Xn,2
Cantidad Producida
N X1,m X2,m … Xn,m
P1 P2 Pi Pm n
D1
D2
2.12.2.1.4.
Dj
m
D P
Dn
j 1
j
i 1
i
Restricciones
Resultan ser muchas, de tal manera que se requiere de una computadora para su resolución. Se tiene una restricción por cada columna y una restricción por cada renglón, lo que hace m+n restricciones: m
n
D j X i, j
Pi X i, j
i 1
j 1
Como el número de variables es mayor que el número de ecuaciones, puede haber un gran número de soluciones. De estas soluciones, hay al menos una con costo total mínimo 2.12.2.1.5.
Función objetivo
Es el Costo Total, que debe minimizarse, se calcula sumando todos los productos de cada asignación por su costo asociado, con la fórmula: m
n
CTotal Ci, j X i, j i 1 j 1
En la que
Ci , j
significa el costo de enviar una unidad de la fuente
i
al destino
j (Costos
Unitarios de Transporte)y
©
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414)
X i , j es la cantidad de (Variables de decisión)
unidades que se envían desde la fuente
i
2.12.2-4 el destino j
Si acaso hubiera destinos prohibidos asignarles un costo mucho mayor (1000 veces) que el mayor de los asignados Para ejemplificar tenemos el siguiente ejemplo: 2.12.2.1.6.
Caso Ejemplar
En un ejemplo, sencillo, para ilustrar los planteamientos anteriores, se tienen tres plantas productoras: D, M, S, con capacidades de producción 20, 10 y 5 unidades, respectivamente, siendo las producciones individuales PD=20, PM=10 y PS=5. Estos productos se consumen en centros de distribución cuyas demandas en R, T, U son 15, 12 y 8, respectivamente. Siendo las demandas particulares DR=15, DT=12, DU=8. El costo de traslado de D a R es CD,R=1, los otros costos de transporte al destino R es CM,R=4,
CS,T=3,
al destino T: CD,T=3, CM,T=1, CS,T=6, y a Podemos resumir estos datos en la siguiente tabla:
U: CD,U=6, CM,U=6 y CS,U=1.
Costos, Producción y Demandas Productores
P Cantidad Producida
R
T
U
D M S
1 4 3
3 1 6
2 7 1
Di Cantidad Demandada
DR
DT
DU
15
12
8
Distribuidores
PD PM PS
20 10 5
D i 15 12 8 35 i
P j 20 10 5 35 j
EQUILIBRADO La función objetivo es: Z= CD,R*XD,R+CD,T*XD,T+CD,U*XD,U+CM,R*XM,R+CM,T*XM,T+CM,U*XM,U+CS,R*XS,R+CS,T*XS,T+CS,U*XS,U
Z= 1*XD,R+3*XD,T+2*XD,U+4*XM,R+1*XM,T+7*XM,U+3*XS,R+6*XS,T+1XS,U En notación matricial es:
C
D,R
Z C M ,R
C
S ,R
C C C
D ,T
M ,T S ,T
C C C
D ,U
M ,U S .U
X X X
D,R M ,R S ,R
X X X
D ,T M ,T S ,T
X X X
D ,U M ,U S ,U
Donde significa producto interno (la suma de los productos correspondientes al mismo renglón, columna) ©
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414) 2.12.2.1.6.1.
2.12.2-5
Restricciones
Las restricciones de la solución óptima se dan por las exigencias de producción y de demanda. Haciendo que la suma de todas las asignaciones de productos que se envían a cada destino sean las requeridas:
Por demanda:
XD,R + XM,R + XS,R = DR XD,T + XM,T + XS,T
= DT
XD,U + XM,U + XS,U = DU Los productos de cada centro de producción deben ser igual a la suma de las cantidades asignadas a cada destino
Por producción:
XD,R + XD,T + XD,U = PD XM,R + XM,T + XM,U =PM XS,R + XS,T + XS,U =PS
Que en forma matricial es:
1 0 0 1 0 0
0 1 0 1 0 0
0 0 1 1 0 0
1 0 0 0 1 0
0 1 0 0 1 0
2.12.2.1.6.2.
0 0 1 0 1 0
1 0 0 0 0 1
0 1 0 0 0 1
0 0 1 0 0 1
X D ,R X D ,T D R 15 X D ,U 12 X M ,R DT 8 DU X M ,T P D 20 X M ,U P M 10 X S ,R 5 PS X S ,T X S ,U
Función Objetivo
El costo total es la suma de productos de costos por asignaciones, y la optimización consiste en reducirla al mínimo sin violar las restricciones
Minimizar Z =XD,R*CD,R + XD,T*CD,T+ XD,U*CD,U+ XM,R*CM,R + XM,T*CM,T+ XM,U*CM,U+ XS,R*CS,R + XS,T*CS,T+ XS,U*CD,U
©
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414) 2.12.2.1.6.3.
2.12.2-6
Uso de Excel® para la Solución R
T
U Disponibilidad CostoTotal
Costos
D M S Demandas
1
3
2
20
4
1
7
10
3 15
6 12
R
T
1 5 8 Equilibrado
U Utilizados
Asignaciones
D M S Satisfechos
15
2
3
20
0
10
0
10
0
0 12
5 8
5
15
R
42
T
U
Se deben preparar las celdas: Los datos del problema se concentran en los bloques Costos, Disponibilidad y Demandas
Asignaciones, es el conjunto de celdas vacías en que se entregara el resultado 2.12.2.1.6.3.1. CostoTotal, es la celda en que aparecerá el Costo Mínimo, debe contener la fórmula: =Suma (Costos * Asignaciones) que para que funcione adecuadamente se debe finalizar con la secuencia
Preparación de las celdas
Los datos del problema se concentran en los bloques Costos, Disponibilidad y , las tres teclas simultáneamente oprimidas, que pondrá la formula entre corchetes {}. Asignaciones, es eldeben conjunto de celdas vacías en que se el resultado Las celdas de Utilizados ser la suma del renglón correspondiente de entregará Asignaciones .
Demandas.
Las celdas de Satisfechos deben de la columna correspondiente Asignaciones CostoTotal, es la celda en ser quela suma aparecerá el Costo Mínimo,dedebe contener la. fórmula: ® La mediante el Solver requiere = optimización Suma (Costos*Asignaciones) quede:para que funcione adecuadamente se debe finalizar
con la secuencia , las tres teclas simultáneamente oprimidas, que pondrá la ® directa o indirectamente ( EXCEL exige que sea una formula) (CostoTotal) formula entre corchetes = {Suma (Costos*Asignaciones) }. Indicar si se busca un máximo, un mínimo o que la celda objetivo alcance un valor dado (seleccionamos la opción Min) Las celdas Utilizados deben ser laensuma del renglón correspondiente de Asignaciones. Variables dede decisión que es un espacio que se han de arrojar los valores de la asignación que cumplan con todas Las celdas deySatisfechos ser lalasuma la columna correspondiente de )Asignaciones. las restricciones que minimicendeben (maximicen) celda de objetivo (seleccionamos Asignaciones Una función objetivo, que obviamente debe ser una función del valor de todas las asignaciones (variables de decisión),
Restricciones, que son expresiones de (des)igualdad: del lado izquierdo debe haber una formula en función de las
Parámetros del Solver®
variables de decisión, en el centro un 2.12.2.1.6.3.2. símbolo de igualdad o desigualdad, y del lado derecho debe haber un valor que acote las restricciones. La optimización elSe Solver® requiere de: Pueden ser definidos mediante por bloques. puede pedir como restricción valores enteros, positivos o de valor booleano (1 o 0) . Seleccionamos: 2.12.2.1.6.3.2.1. Satisfechos = Demandas Utilizados = Disponibilidad Obviamente debe ser una función del valor de todas las asignaciones (variables de decisión), directa o
Una función objetivo
Asignaciones = Entero indirectamente (EXCEL® exige que sea una formula) (CostoTotal)
Asignaciones >= 0 Para ejecutar la optimización seleccionar Resolver y verificar que se reporte: 2.12.2.1.6.3.2.2. Solver encontró una solución, Se cumplen todas las restricciones y condiciones óptimas. si se busca un máximo, unasignados mínimoy oenque la celda elobjetivo alcance un valor dado el yIndicar en Asignaciones aparecerán los valores CostoTotal costo mínimo. Es posible que haya(en más soluciones, pero ninguna con un costo mejor. renglón para seleccionamos la opción Min).
Una tendencia de optimización
2.12.2.1.6.3.2.3.
Las Variables de Decisión
Que es un bloque en que se han de arrojar los valores de la asignación que cumplan con todas las restricciones y que minimicen (maximicen) la celda objetivo (En el renglón: Cambiando las celdas de variables: seleccionamos Asignaciones)
©
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414) 2.12.2.1.6.3.2.4.
2.12.2-7
Restricciones
Que son expresiones de (des)igualdad: del lado izquierdo debe haber una formula en función de las variables de decisión, en el centro un símbolo de igualdad o desigualdad, y del lado derecho debe haber un valor que acote las restricciones. Pueden ser definidos por bloques. Se puede pedir como restricción valores enteros, positivos o de valor booleano (1 o 0). Seleccionamos: Satisfechos = Demandas Utilizados = Disponibilidad Asignaciones = Entero Asignaciones >= 0 2.12.2.1.6.3.2.5.
Método de Solución
Se pueden ejecutar tres métodos de solución: GRG no lineal para problemas no lineales suavizados, solo encuentra soluciones locales1. Simplex LP Para problemas lineales, encuentra soluciones globales2 Evolutionary Problemas no suavizados. Encuentra soluciones locales. 2.12.2.1.6.3.3.
Ejecución
Para ejecutar la optimización seleccionar Resolver y verificar que se reporte: “Solver encontró una solución, Se cumplen todas las restricciones y condiciones óptimas”. y en Asignaciones aparecerán los valores asignados y en CostoTotal el costo mínimo. Es posible que haya más soluciones, pero ninguna con un costo mejor.
1 2
Las soluciones metaestables más próximas a los datos iniciales La mejor solución para todo el rango de validez de las variables del modelo ©
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414) 2.12.2.1.7.
2.12.2-8
Método SIMPLEX
La filosofía general del método es la de plantear una solución factible, determinar si esta es la óptima, y en caso de no serlo, determinar una mejor solución, para repetir el procedimiento hasta que se haya logrado la mejor solución (verifica y mejora). En nuestro caso se obtiene un resultado final, gracias a que se avanza de vértice a vértice, lo que garantiza un resultado final exacto. En otros métodos la terminación es cuando se ha llegado a una aproximación deseada. Se detallan, a continuación, técnicas de solución, que puesto que todos los coeficientes del problema son ceros o unos, de gran simetría, y altamente redundantes, se genera un algoritmo simplificado que se describe aquí. Como siempre, si se parte de una solución factible, se simplifica aún más el procedimiento, por lo que la primera tarea es encontrar una solución factible inicial, que se aproxime lo más posible a la solución final. 2.12.2.1.7.1.
Solución Inicial
3
Se inicia con un tablau que se encuentre equilibrado. Para disminuir los problemas de solución, encontramos una solución inicial, que nos ubique en el espacio de factibilidad, desde el cual iniciaremos las iteraciones de optimización, si son necesarias. Para ubicar dicha solución inicial se describen a continuación cuatro métodos, desde el más sencillo, que no garantiza estar cerca del óptimo, hasta el más complejo, que garantiza un estado inicial muy cercano (a unas cuantas iteraciones) del óptimo. 2.12.2.1.7.1.1.
Costo Total
Se calcula el costo total sumando todos los productos de cada asignación por su costo. n m
CTotal C i , j X i , j i 1 j 1
2.12.2.1.7.1.2.
Método de la esquina Noroeste
En un tablau equilibrado, en la celda que se encuentra arriba a la derecha (siempre y cuando no esté prohibida) se asigna la mayor cantidad posible: mínimo de la demanda, en la celda correspondiente del último renglón del tablau y la producción, celda correspondiente en la última columna del tablau. Esto satisface o la producción de una fuente o los requerimientos de un destino, lo que elimina o un renglón o una columna. La nueva tabla reducida se vuelve a tratar con el mismo método, hasta terminar con todos los valores. Como pago por la sencillez de cálculo, no ofrece ninguna garantía de acercarse al óptimo (como efecto de su aleatoriedad, puede darse la casualidad de que se logre el óptimo por este medio). Este procedimiento se realiza en una sola tabla. Por razones didácticas elaboro una tabla para cada paso para que el alumno pueda visualizar el procedimiento.
3
Tablau que así le nombramos por no tratarse de una tabla pues es un recurso para la ejecución de un algoritmo. ©
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414) 2.12.2.1.7.1.2.1.
2.12.2-9
Ejemplo
00 1 00 3 00 2 A 00 1 00 3 00 2 a 00 1 00 3 00 2 a 00 1 00 3 00 2 20 20 20 20 15 15 5 15 5 15 5 00 4 00 1 00 7 A 00 4 00 1 00 7 a 00 4 00 1 00 7 a 00 4 00 1 00 7 10 10 10 10 7 7 3 00 3 00 6 00 1 A 00 3 00 6 00 1 a 00 3 00 6 00 1 a 00 3 00 6 00 1 5 5 5 5 8 15 12 8 15 12 8 15 12 8 15 12 8 Costo Total: 15*1+5*3+7*1+3*7+8*1=15+15+7+21+8=66 2.12.2.1.7.1.2.2.
Costos E
E 414
M T
F TKT M Q R T Producción 0 MM 251 MM 132 MM 281 MM 193 MM 76 MM 103 449
281
198
146
0
474
210
178
103
355
29
178
296
33
0
-
Demandas 414 Costos
Ejemplo
E
16
91
856
5
121
931 1534
1411
TKT M Q R T Producción 132 281 193 76 103 E 449 414 16 MM MM MM MM MM 281 198 146 0 474 210 178 M 931 103 355 29 178 296 33 0 T 1534 Demandas 414 16 91 856 5 121 1411 0
Costos
F 251
F TKT M Q R T Producción 0 MM 251 MM 132 MM 281 MM 193 MM 76 MM 103 E 449 414 16 19 281 198 146 0 474 210 178 M 931 103 355 29 178 296 33 0 T 1534 Demandas 414 16 91 856 5 121 1411
©
E
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414)
Costos
E
Costos
E
Costos
E
Costos
E
Costos
E
2.12.2-10
F TKT M Q R T Producción 0 MM 251 MM 132 MM 281 MM 193 MM 76 MM 103 E 449 414 16 19 281 198 146 0 474 210 178 M 931 72 103 355 29 178 296 33 0 T 1534 Demandas 414 16 91 856 5 121 1411 F TKT M Q R T Producción 0 MM 251 MM 132 281 MM 193 MM 76 MM 103 E 449 414 16 19 281 198 146 0 474 210 178 M 931 72 856 103 355 29 178 296 33 0 T 1534 Demandas 414 16 91 856 5 121 1411 F TKT M Q R T Producción 0 MM 251 MM 132 281 MM 193 MM 76 MM 103 E 449 414 16 19 281 198 146 0 474 210 178 M 931 72 856 3 103 355 29 178 296 33 0 T 1534 Demandas 414 16 91 856 5 121 1411 F TKT M Q R T Producción 0 MM 251 MM 132 281 MM 193 MM 76 MM 103 E 449 414 16 19 281 198 146 0 474 210 178 M 931 72 856 3 103 355 29 178 296 33 0 T 1534 2 Demandas 414 16 91 856 5 121 1411 F TKT M Q R T Producción 0 MM 251 MM 132 281 MM 193 76 MM 103 E 449 414 16 19 281 198 146 0 474 210 178 M 931 72 856 3 103 355 29 178 296 33 0 T 1534 2 121 Demandas 414 16 91 856 5 121 1411
©
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
2.12.2-11
UABC FCAS (414)
Costos
E
F TKT M Q R T Producción 0 MM 251 MM 132 281 MM 193 76 103 E 449 414 16 19 281 198 146 0 474 210 178 M 931 72 856 3 103 355 29 178 296 33 0 T 1534 2 121 1411 Demandas 414 16 91 856 5 121 1411
414*00+16*251+19*132+00*281+00*193+00*76+00*103+00*281 +00*198+72*146+856*00+03*474+00*210+00*178+00*103+00*355 +00*29+00*178+02*296+121*33+1411*0 = 16*251+19*132+72*146+3*474+2*296+121*33 = 4016
+ 2508 + 10512+ 1422+ 592 + 3993 = 23043
CT=23043 2.12.2.1.7.1.2.3.
10 5 10 3 10 2 4
8
7
3
6
7
17
11
10 1 10 3 10 4
20 10 5
7
3
1
7
7
4
1
39
14
30
Ejercicios
10 10 1 10 3 10 4
20 10
7
3
1
8
4
8
1
16
17
20 10 20
17
9
11
3
5
7
12
4
2
25
25
40 20 40
25 25
425 – 425 – 515 - 425
©
1
7
7
7
8
6
8
8
8
7
30
40
37
30
45
9
11 3
5
7
12 4
2
25
40 20 40
25 25 25 385 – 425
79 - 79 10 1 10 10 a 8 10 6
10 1 10 10 8 10 6
40 50 60
38
2584 – 2478 - 1568 - 1088
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414) 2.12.2.1.7.1.3.
2.12.2-12
Método de Costo Mínimo
Se busca el menor costo de la tabla y se le asigna lo más posible, eliminando con esto algún renglón o columna. En caso de haber varios candidatos, se usa el de arriba y el de la izquierda. Se repite el procedimiento en las celdas restantes hasta terminar con todo el tablau. 2.12.2.1.7.1.3.1.
Ejemplo
00 1 00 3 00 2 A 00 1 00 3 00 2 a 00 1 00 3 00 2 a 00 1 00 3 00 2 20 20 20 20 15 15 15 15 2 3 00 4 00 1 00 7 A 00 4 00 1 00 7 a 00 4 00 7 a 00 4 00 1 00 7 10 10 10 10 10 10 10 00 3 00 6 00 1 A 00 3 00 6 00 1 a 00 3 00 6 00 1 a 00 3 00 6 00 1 5 5 5 5 5 5 15 12 8 15 12 8 15 12 8 15 12 8 Costo Total: 15*1+2*3+3*2+10*1+5*1=15+6+6+10+5=42 2.12.2.1.7.1.3.2.
Costos E
E 414
F TKT M Q R T Producción 0 251 132 281 193 76 103 449
281 198 146
M
Costos
E
F TKT 0 251 132 -
-
1534
M Q R T Producción 281 193 76 103 449 0
103 355 29
Costos
0
474 210 178
931
856
Demandas 414 E
16
178 296 33 856
91
F TKT 0 251 132
414
5
M Q R 281 193 76
281 198 146 16 91
Prof. Raúl Espejo Rodarte (11950)
1534
T
Producción 103
0 474 210
856 103 355 29
0
121 1411
-
Demandas 414 ©
931
91 856 5 121 1411
281 198 146
T
T
16
414
M
M
474 210 178
103 355 29 178 296 33
Demandas 414
E
0
-
T
E
Ejemplo
178 -
178 296 33 856
0
1411 5 121 1411
[email protected] 6461766600x173
449 931 1534
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414)
Costos
E
F TKT M 0 251 132 281 E 414 281 198 146 0 M 856 103 355 29 178 T 91 Demandas 414 16 91 856 Costos
E
Costos
E
Q R 193 76
T
Producción 103
474 210
178 -
296 33 5
2.12.2-13
0
1411 121 1411
449 931 1534
F TKT M Q R T Producción 0 251 132 281 193 76 103 E 449 414 281 198 146 0 474 210 178 M 931 856 103 355 29 178 296 33 0 T 1534 91 32 1411 Demandas 414 16 91 856 5 121 1411 F TKT M Q R T Producción 0 251 132 281 193 76 103 E 449 414 35 281 198 146 0 474 210 178 M 931 856 103 355 29 178 296 33 0 T 1534 91 32 1411 Demandas 414 16 91 856 5 121 1411 El resto solo se puede escoger de una manera
Costos
E
F TKT M Q R T Producción 0 251 MM 132 281 MM 193 MM 76 103 E 449 414 35 281 198 146 0 474 210 178 M 931 16 856 5 54 103 355 29 178 296 33 0 T 1534 91 32 1411 Demandas 414 16 91 856 5 121 1411 414*0+0*251+0*132+0*281+0*193+35*76+0*103+ 0*281+16*198+0*146+856*0+5*474+54*210+0*178 +0*103+0*355+91*29+0*178+0*296+32*33+1411*0= 35*76+16*198+5*474+54*210+91*29+32*33= 2660+3168+2370+11340+2639+1056= 23233 ©
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414) 2.12.2.1.7.1.4.
2.12.2-14
Método de Vogel
Se determinan indicadores de costo como la diferencia de los dos costos más pequeños, por cada columna y por cada renglón. Se elige el mayor de dichos indicadores, y en ese renglón o columna se elige el costo mínimo y en él se asigna todo lo que se pueda, se elimina la columna o el renglón que satisfagan su suma marginal, y se repite el procedimiento hasta que solo quede un renglón (columna), al que se asigna lo pertinente para cuadrar las sumas marginales. 2.12.2.1.7.1.4.1.
00 1 00 3 00 2 00 4 00 1 00 7 00 3 00 6 00 1 15 2
12 2
20 10 5
1 3 2
8 1
00 1 00 3 00 2
Ejemplo
1 1 a 00 1 00 3 00 2 20 1 1 2 00 4 00 1 00 7 3 a 00 4 00 1 00 7 10 3 10 10 10 00 3 00 6 00 1 2 2 a 00 3 00 6 00 1 5 2 2 5 15 12 8 15 12 8 2 2 1 2 2 1 2 3 1 2 3 1 20
00 1 00 3 00 2 1 1 1 00 1 00 3 00 2 00 1 00 3 00 2 20 20 20 2 2 15 2 3 00 4 00 1 00 7 3 00 4 00 1 00 7 00 4 00 1 00 7 10 10 10 10 10 10 00 3 00 6 00 1 2 2 2 00 3 00 6 00 1 00 3 00 6 00 1 5 5 5 5 5 15 12 8 15 12 8 15 12 8 2 2 1 2 3 1 2 1 Costo Total: 15*1+2*3+3*2+10*1+5*1=15+6+6+10+5=42 2.12.2.1.7.1.4.2.
Costos E M
E 0
F TKT M Q R T Producción 251 132 281 193 76 103 76 449
281 198 146
0
474 210 178
103 355 29 178 296 33
T
Ejemplo
0
931
146
1534
29
Demandas 414 16 91 856 5 121 1411 103 53 103 178 103 43 178
©
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414)
Costos E M
E 0 281 103
T
Demandas 414 103 103 Costos
E 0 E 414 281 M 103 T Demandas 414 103 103 103 Costos
E 0 E 414 281 M 103 T Demandas 414 103 103 103
©
F TKT M 251 132 281 198 146 0 856 355 29 178 16 91 856 53 103 178 53 103 F TKT M 251 132 281 198 146 0 856 355 29 178 16 91 856 53 103 178 53 103 53 103 F TKT 251 132 198 146 355 29 91 16 91 53 103 53 103 53 103 53 103
M 281 0 856 178 856 178
Prof. Raúl Espejo Rodarte (11950)
2.12.2-15
Q R T Producción 193 76 103 76 76 449 474 210 178 296 33
0
931
146 32
1534
29 29
5 121 1411 103 43 178 103 43 178 Q R 193 76
T Producción 103 76 76 76 449
474 210 178 296 33
0 1411 5 121 1411 103 43 178 103 43 178 103 43 Q R 193 76
1534
146 32 52 29 29 4
T Producción 103 76 76 76 56 449
474 210 178 296 33
931
0 1411 5 121 1411 103 43 178 103 43 178 103 43 103 43
931 1534
[email protected] 6461766600x173
146 32 52 52 29 29 4 4
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414)
Costos
E 0 E 414 281 M 103 T Demandas 414 103 103 103
Costos
E 0 E 414 281 M 103 T Demandas 414 103 103 103
Costos
E 0 E 414 281 M 103 T Demandas 414 103 103 103
©
F TKT 251 132 198 146 355 29 91 16 91 53 103 53 103 53 103 53 103 53
M 281 0 856 178 856 178
F TKT 251 132 198 146 355 29 - 91 16 91 53 103 53 103 53 103 53 103 53 53
M 281 0 856 178 856 178
F TKT 251 132 198 146 355 29 - 91 16 91 53 103 53 103 53 103 53 103 53 53
M 281 0 856 178 856 178
Prof. Raúl Espejo Rodarte (11950)
Q R 193 76
T Producción 103 76 76 76 56 117 449
474 210 178 296 33
0 1411 5 121 1411 103 43 178 103 43 178 103 43 103 43 103 43 Q R 193 76
33 32 121 43 43 43 43 43 134
Q R 193 76
0 1411 1411 178 178
33 32 121 43 43 43 43 43 134
1534
146 32 52 52 12 29 29 4 4 263
931 1534
146 32 52 52 12 12 29 29 4 4 263
T Producción 103 76 76 76 56 117 117 449
474 210 178 296 5 103 103 103 103 103 281
931
T Producción 103 76 76 76 56 117 117 449
474 210 178 296 5 103 103 103 103 103 281
2.12.2-16
0 1411 1411 178 178
931 1534
[email protected] 6461766600x173
146 32 52 52 12 12 29 29 4 4 263
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414)
Costos
E 0 E 414 281 M 103 T Demandas 414 103 103 103
Costos
E 0 E 414 281 M 103 T Demandas 414 103 103 103
©
F TKT 251 132 198 146 355 29 - 91 16 91 53 103 53 103 53 103 53 103 53 53 53
M 281 0 856 178 856 178
Q 193 5 474 296 5 103 103 103 103 103 281
F TKT 251 132 198 146 355 29 - 91 16 91 53 103 53 103 53 103 53 103 53 53 53
M 281 0 856 178 856 178
Q 193 5 474 296 5 103 103 103 103 103 281
Prof. Raúl Espejo Rodarte (11950)
R 76
T Producción 103 76 76 76 56 117 117 175 449
210 178 33 32 121 43 43 43 43 43 134 134
2.12.2-17
0 1411 1411 178 178
931 1534
146 32 52 52 12 12 12 29 29 4 4 263
R T Producción 76 103 76 76 76 56 117 117 175 449 30 210 178 146 32 52 52 12 12 12 931 33 32 121 43 43 43 43 43 134 134
0 1411 1411 178 178
1534
[email protected] 6461766600x173
29 29 4 4 263
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414)
Costos
E
F TKT M Q R 00 0 00 251 00 132 00 281 00 193 76 E 414 5 30 281 198 146 0 474 210 M 16 856 59 103 355 29 178 296 33 T 91 32 Demandas 414 16 91 856 5 121 414 * 0 = 00 5 * 193 = 965 30 * 76 = 2280 16 * 198 = 3168 856 * 0 = 0 59 * 210 = 12390 91 * 29 = 2639 32 * 33 = 1056 1411 * 0 = 0 Costo Total = 22498 2.12.2.1.7.1.5.
T 103 178 0 1411 1411
2.12.2-18
Producción 449 931 1534
Método de Russel.
Para cada renglón se determina el máximo costo (Vi). Para cada columna se asigna el máximo costo a una variable Uj. En cada celda, se calcula 𝛥𝑖,𝑗 = 𝑈𝑗 + 𝑉𝑖 − 𝐶𝑖,𝑗 . A la celda con el mayor de los valores 𝛥𝑖,𝑗 se le asigna todo lo que se puede, con lo que se satisface algún renglón o columna. Con las celdas restantes se repite el procedimiento. 2.12.2.1.7.1.5.1.
4 3 7 6
6
7
06 1 06 3 08 2 7 4 12 1 10 7 3 6 6 15
©
12
3
2
a 00 1 00 3 00 2 20 15 2 3 7 7 A 4 1 7 a 4 1 7 10 10 10 10 10 12 1 A 6 3 6 6 7 1 a 3 6 1 5 6 5 5 5 5 8 15 12 8 15 12 8 Costo Total: 15*1+2*3+3*2+10*1+5*1=15+6+6+10+5=42 20
A
6
Ejemplo
3
05 1 06 3 03 2
Prof. Raúl Espejo Rodarte (11950)
20
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414) 2.12.2.1.7.1.5.2.
000 Vj
Ui Costos
281
E
474
M
355
T Demandas
000 Vj
Ui Costos
251
E
474
M
355
T Demandas
000 Vj 193 474 296
355 146 281 474 210 178 F TKT M Q R T 381 251 295 132 281 281 562 193 415 76 356 103 474 281 631 198 474 146 755 0 474 474 474 210 474 178 856 433 103 355 355 472 29 458 178 533 296 532 33 533 0 414 16 91 856 5 121 1411 355 146 F TKT 355 251 265 132 474 281 631 198 474 146 16 433 103 355 355 472 29 414 16 91
Ui Costos
281 E 474 0 E 414 474 281 M 474 103 T Demandas 414
000 Vj
Ui Costos
193
E
474
M
296
T Demandas
©
Ejemplo
281 E 562 0
281 E 532 0
E 0 414 281 103 414
474 210 178 M Q R T 281 532 193 385 76 326 103 0 474 474 474 210 474 178 856 178 533 296 532 33 533 0 856 5 121 1411
146 F TKT 251 207 132 198 474 146 16 355 413 29 16 91
474 210 178 M Q R T 281 474 193 327 76 268 103 0 474 474 474 210 474 178 856 178 474 296 473 33 474 0 856 5 121 1411
146 F TKT 251 207 132 198 474 146 16 59 355 413 29 16 91
474 210 178 M Q R T 281 474 193 327 76 268 103 0 474 474 474 210 474 178 856 178 474 296 473 33 474 0 856 5 121 1411
Prof. Raúl Espejo Rodarte (11950)
2.12.2-19
[email protected] 6461766600x173
Producción 449 931 1534
Producción 449 931 1534
Producción 449 931 1534
Producción 449 931 1534
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414) 000 Vj
Ui Costos
193
E M
296
T Demandas
000 Vj
Ui Costos
193
E M
296
T Demandas
000 Vj
Ui Costos
193
E M
296
T Demandas
000 Vj
E 0 414 281 103 414
E 0 414 281 103 414
E 0 414 281 103 414
Ui Costos E M T Demandas
E 0 414 281 103 414
132 F TKT 251 193 132 198 146 16 59 355 399 29 32 16 91
F 251 198 16 355 16
F 251 198 16 355 16
F 251 198 16 355 16
296 76 103 M Q R T 281 296 193 193 76 193 103 0 474 210 178 856 178 296 296 339 33 399 0 856 5 121 1411
TKT 132 146 59 29 32 91
296 76 103 M Q R T 281 296 193 193 76 193 103 0 474 210 178 856 178 296 296 339 33 399 0 1411 856 5 121 1411
TKT 132 146 59 29 32 91
296 76 M Q R 281 296 193 193 76 0 474 210 856 178 296 296 339 33 91 856 5 121
TKT 132 146 59 29 32 91
M 281 0 856 178 856
Q 193 5 474 296 5
R 76 30 210 33 91 121
T
2.12.2-20 Producción 449 931 1534
Producción 449 931 1534
Producción 103
178 0 1411 1411
T
449 931 1534
Producción 103
178 0 1411 1411
449 931 1534
414*0 = 5*193 = 30*76 = 16*198 = 59*146 = 856*0 = 32*29 = 91*33 = 1411*0 =
0 965 2 280 3 168 8 614 0 928 3 003 0 CostoTotal = 18 958.
©
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414) 2.12.2.1.7.1.
2.12.2-21
Optimización
Una vez encontrada una solución factible inicial, hay que determinar si esta es la óptima, o si hay que buscar una solución más barata. En caso de que no se tenga la solución más barata, hay que determinar un método para ubicar una mejor asignación 2.12.2.1.7.1.1.
Prueba de optimalidad
Para determinar si la asignación propuesta es la mejor se procede de la siguiente manera: Hay que encontrar cantidades, para cada uno U1=0, U2=5, U3=2, V1=4, V2=3, V3=1, que en la tabla se ubican como de los n renglones (Vi) y para cada una de las m encabezadores columnas (Uj), que sumen el costo Cij, de las celdas a las que se les ha asignado un valor. 4 3 1 aaaa Para esto es necesario que haya al menos n+mAA 4 . -1 a 2 . AA 1 . 1 celdas con valores asignados. En caso de no 0. 30 30 ser así, se dice que la solución es 9 8 6 degenerada, que después analizaremos 5. 30 5 10 15 (Soluciones degeneradas.). 7 5 3 Con esto determinamos un sistema de n+m-1 2. 10 10 ecuaciones (linealmente independientes), con 35 20 15 n+m variables. Este sistema tiene un número infinito de soluciones. Para fijar los valores A continuación, calculamos en las celdas sin introducimos una ecuación en la que asignamos asignación el costo correspondiente menos los valor arbitrario a cualquier variable. El valor dos valores que encabezan ese renglón y mas cómodo es el 0, que por orden asignamos a columna, así: Cij-Ui-Vj, que para la primera U1.
celda sin asignación es: 2-3-0=-1. Esto es el costo de asignar una unidad a dicha celda, que significa un ahorro, pues para asignar una unidad a dicha celda, hay que añadir en las
V1 V2 V3 aaaa AA 4 . AA 2 . AA 1 . U1 . 30 30 9 8 6 U2 . 30 5 10 15 7 5 3 U3 . 10 10 35 20 15 𝐔𝟏 + 𝐕𝟏 = 𝟒 = 𝐂𝟏𝟏
azules uno gastando para ello 2+9=11, y las quitaremos de las celdas rosas, ahorrando, 4+8=12, así el nuevo costo agrega 11 y disminuye 12, ahorrando en total 1 por cada unidad asignada a esta celda.
𝐔𝟐 + 𝐕𝟏 = 𝟗 = 𝐂𝟏𝟐 𝐔𝟐 + 𝐕𝟐 = 𝟖 = 𝐂𝟐𝟐 𝐔𝟐 + 𝐕𝟑 = 𝟔 = 𝐂𝟐𝟑 𝐔𝟑 + 𝐕𝟐 = 𝟓 = 𝐂𝟐𝟑 Asignamos el primer valor: 𝐔𝟏 = 𝟎 Así la primera ecuación 𝐔𝟏 + 𝐕𝟏 = 𝟒 , 0 + V1 = 4 → V1=4 De la segunda 𝑼𝟐 + 𝑽𝟏 = 𝟗 = 𝑼𝟐 + 𝟒 = 𝟗 →𝑼 𝟐 = 𝟗 − 𝟒 = 𝟓
En las celdas ya asignadas este cálculo resulta siempre cero, por lo que no tiene caso hacerlo en dichas ubicaciones El cálculo de los valores restantes es: en la celda (1,3)el costo es de: 1-1-0=0. Esto significa que asignarle una unidad a esta celda no se gasta nada, por lo que podemos inferir que hay muchas soluciones con el mismo costo.
Así conseguimos todos los valores ©
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
22 aaaa
UABC FCAS (414)
(3,1) el costo de asignación es: 7-4-2=7-6=1, y en la celda (3,3) sería de 3-1-2=0.
4
En la celda
Estos resultados se reportan en rojo en la siguiente tabla:
4
3
1
A 4 -1 2 0 1 A . a . A . . 30 9 8 6 5 5 10 15 . 5 0 3 2 1 7 10 . 0
35
20
15
aaaa 30 30 10 Ct=385 .
El costo total es de
30*4 + 5*9 + 10*8 + 15*6 + 10*5= 120+45+80+90+50=385 El resultado de transferir 10 unidades es debido a que de las celdas rosas solo tienen esa capacidad, pues aunque a celda (1,1) se le
30, en la celda (2,2)solo es factible quitarle 10. Al transferir 10unidades con un ahorro de 1 por unidad, se reduce el costo total de 385en 10, quedando ahora en 375
3
1
A 4 -1 2 0 1 A . a . A . . 29 1 9 8 6 5 6 9 15 . 5 0 3 2 1 7 10 . 0
30 30 10
Ct=384 . Ct=29*4+1*2+6*9+9*8+15*6+10*5 = 116+2+54+72+90+50=384. 35
20
15
4 3 1 AA 4 . -1 a 2 . 0 A 1 . 0. 20 10 9 8 6 5. 15 0 15 1 7 5 0 3 2. 10 -
35
20
aaaa 30 30 10
15 Ct=375.
puede quitar hasta
Si hacemos el movimiento de una unidad, ahorramos 1
4 AA 4 . 0. 20 9 5. 15 0 7 3. 35
2 1 aaaa a 2 . 0A 1 . 30 10 1 8 6 30 15 5 -1 3 10 10 20 15 Ct=375.
Ahora la asignación se tiene que hacer en varias celdas. En este caso en anillo está compuesto de tres celdas de reducción y tres de incremento: El costo se incrementa por:
3+9+2=14
©
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414)
23
AA 4 . a 2 . 0A 1 . 30 10 20 9 1 8 6 30 25 5 0 7 5 -1 3 10 . 0 10 35 20 15 Ct=365. Y se reduce por5+4+6=15, el costo se incrementa por: 14-15=-1se ahorra uno por unidad. La máxima cantidad a asignar es el
menor de (10, 20, 15)=10 Con un ahorro de 1 y una cantidad de 10 se ahorran 10y el nuevo
Costo totales
de
375-10=365
©
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414) 2.12.2.1.7.1.1.1.
24
Ejemplo
Solución inicial obtenida con método Russel 000 Ui 0 124 72 -74 193 76 43 Vj Costos E F TKT M Q R T Producción 0 127 251 60 132 355 281 193 76 60 103 0 E 449 414 5 30 207 281 198 0 146 0 207 474 60 210 61 178 74 M 931 16 59 856 146 103 274 355 0 29 285 178 146 296 33 0 -43 T 1534 32 91 1411 Demandas 414 16 91 856 5 121 1411
¡¡ Óptimo !! CT=18958 2.12.2.1.7.1.1.2.
Ejemplo
Solución inicial obtenida con el método Vogel. 000 Ui 0 64 72 -134 193 76 43 Vj Costos E F TKT M Q R T Producción 0 187 251 60 132 415 281 193 76 146 103 0 E 449 414 5 30 147 281 198 -60 146 0 147 474 210 87 178 134 M 931 16 - + 856 59 146 103 334 355 29 355 178 146 296 33 0 -43 T 1534 91 32 + 1411 Demandas 414 16 91 856 5 121 1411
Se puede Optimizar CT=22498 Se pueden mover 59 con una ganancia unitaria de 60 nuevo CT=22498 – (59*60) = 22498 – 3540 = 18958 000 Vj
Ui Costos
124 72 -74 193 76 43 F TKT M Q R T Producción 0 127 251 60 132 355 281 193 76 60 103 0 E 449 414 5 30 207 281 198 146 0 207 474 60 210 61 178 74 M 931 16 59 856 0 146 103 274 355 29 285 178 146 296 33 0 -43 T 1534 32 91 1411 Demandas 414 16 91 856 5 121 1411 Óptimo.
©
0 E
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414) 2.12.2.1.7.1.1.3.
1 0 1 15 1 3 1 0 6 5 5 20 2 3 0
7
0 1 10 0 3 2 0 6 5 10 20 0
13 5 7 1 8 13 -1 4 0 7 0 12 3 1 6 2 - 10 10 11 14 6 2 10 1 17 4 1 4 7 10 0 6 0 12 4 8 3 9 -1 11 2 3 3 10 1 10 10 10 10 2 1 2 2 Ct= 326 2 1 2 1 2
0 7 3 0
-5 3 1 6 1 3 1 2 30 2 -2 8 0 8 30 5 3 2 8 4 30 30 30 30 1 5 2 5 2 2 4
©
2
2
0 2 3 5 15 5 0 4 6 9 15 15 0 8 2 7 15 0 5 20 5 Ct= 175
6 12 4 7 2 8 1 13 -1 4 0 7 0 12 0 2 10 3 11 0 14 0 6 1 10 2 17 9 8 0 6 0 12 4 8 2 9 0 11 10 1 10 10 10 10
1 0 1 40 0 1 1 10 8 40 6 0 0 0 10 4 40 1 0 0 0 10 30 Ct=400 3 3 3 4
Prof. Raúl Espejo Rodarte (11950)
Ejercicios
1
3 2 -1 2 3 5 15 1 0 4 6 9 15 1 1 15 0 8 0 7 15 1 1 5 5 20 5 2 2 Ct= 180 4 2
25
Ct= 324
-3 4 1 0 2 5 30 3 3 3 30
3
1
3 20 8 10 2 8 30
1 2 2 8 4 30 30
[email protected] 6461766600x173
1 1 40 20 2 8 40 4 40 10 30 Ct=380
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414)
11 4 15 1 -5 6 1 5 0 15 0 30 4 - - 30 12 10 8 9 10 12 -3 20 2 2 2 2 19 1 6 -8 8 9 20 5 30 2 2 1 11 2 22 6 19 15 4 10 11 10 10 -5 20 0 0 0 0 20 32 19 22 27 Ct=724 5 2 4 3 4 0 1 2 0 1 2 1 2
26
1
8 8 0 2 10 2 2 . 2 -4 18 22 4 2 2
©
5 5 19 -2 5 8 1 19 0 0 -
1
4
7
1 3 6 1 5 8 15 30 4 10 8 1 10 12 5 13 7 6 8 9 8 20 5 2 6 22 11 15 4 10 3 10 10 3 20 32 19 22 27 0
5 8 38 8 21 3 3 - 0 4 7 2 10 22 2 2 3 0 20 0 43 4 18 1 - - -4 18 20 Ct=343 22 2 1 1
Prof. Raúl Espejo Rodarte (11950)
3
5 5 17 5 2 89 19
30 20 30 20 Ct=676
7 18 21 7 17 20 25 11 20 Ct=339
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414)
1 1 10 9 8 6 -2 2 3 16 0
1 8
1 1 2 9 8 -3 1 8
0 5 5 8 3 3 11 14
1 7
2 3
1 1 10 9 1 1 8 6 -2 2 1 - 3 16
10
1 1 0
17 11
-2 4 2 3 9 0 1 8 8
0 5 5 8 11 3 3 14
Ct=193
1 10 9 8 3 . 2 1 3 16
10
0
17 11
0 2 2 1 9 1 8 8
0 5 5 8 14 2 3 0 14
Ct=169
10 1 10 10 8 10 6 a 40 5 4 25 - 15 9 11 3 5 28 20 2 2 2 7 12 4 2 40 2 2 2 25 25
1
25 25
27
10 17
.
11 Ct=163
1
10
8
6
9
11
3
5
7
12
4
2
25 25
40 20 40
25 25
6 1 1 3 1 1 3 1 1 2 425 – 425 – 515 - 425 2584 – 2478 - 1568 – 1088 10 1 10 7 a 7 10 7 8
6
- 8 28
8
8
7
30
40
37 30
45
40
1
7
7
7
8
6
8
8
50 60
38
40 50
8
7
37 30
30 45
40
60
38
425 – 425 – 515 - 425 2584 – 2478 - 1568 – 1088
©
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414) 2.12.2.1.7.1.2.
28
Soluciones degeneradas.
Cuando en laguna solución hay menos de m+n-1 celdas asignadas, el sistema no tiene suficientes ecuaciones para encontrar la solución. En este caso se dice que la solución es degenerada. Las operaciones con degeneradas son interesantes, pero no sirven para trabajar, pues ofrecen muchos problemas. El problema se resuelve haciendo alguna asignación de un infinitésimo a la celda más adecuada (la que interese a más celdas asignadas), y ahora se procede como si dicha celda tuviera un valor asignado. 2.12.2.1.7.1.2.1.
Ejemplo
La segunda celda del primer renglón interesa a 3 celdas.
1
2
1 2 15 0 0 3 4 2 15 -1 6 0 8 6 5 15 20 0
1 4 5 15 6 9 15 7 15 10 10 Ct= 185
.
1
2
1 2 15 0 0 3 4 2 15 -1 6 0 8 6 5 15 20 0
1 4 5 15 6 9 15 7 15 10 10 Ct= 185
. .
1
2
1 2 10 5 0 3 4 2 15 6 1 8 5 5 15 20 0
2 3 5 15 5 9 15 7 15 10 10 Ct= 180
La primera celda del tercer renglón interesa tres celdas.
©
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414)
1 1 15 1 3 1 6 5 0 15 0
1
2 3 5 15 6 9 15 7 15 10 10 Ct= 185
2
1 10 0 3 2 6 5 5 15 0
3 -1 2 4 15 8 5 20
2
2 3 5 15 5 0 4 5 9 15 15 1 8 7 15 10 20 10 Ct= 180
2.12.2.1.7.1.2.2.
0
0 -3 -4
©
Prof. Raúl Espejo Rodarte (11950)
29
Ejemplo
6 6 10 3 3 10
3 3 40 2 4 40
4 20 3 20 40
2 30 10 5 20 10 Ct=340
6 6 10 3 3 10
3 3 40 2 4 40
7 7 0 4 20 3 20 40
5 4 50 2 30 10 5 20 10 Ct=340
7 -
4 -
50
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414)
6
3
6 3 10 40 0 3 2 2 -3 1 3 5 4 -4 10 40 0
6
3
6 3 10 40 0 3 2 2 -3 1 3 5 4 -4 10 40 0
6
3
0 6 3 40 3 2 2 -3 10 1 3 5 4 -4 10 40 0
©
Prof. Raúl Espejo Rodarte (11950)
30
7 5 7 -1 4 50 0 4 2 30 20 10 3 4 5 20 20 40 10 Ct=340 7 5 7 -1 4 50 0 4 2 30 20 10 3 4 5 20 20 40 10 Ct=340
7 4 7 4 50 0 10 4 1 2 30 20 3 5 5 20 20 40 10 Ct=330
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414) 2.12.2.1.7.1.1.
31
Destinos prohibidos.
Solo por el método de esquina NW resultan, en cuyo caso nada más se evitan. 2.12.2.1.7.1.1.1.
Ejemplo
M
2 15 4
5
6 0 8
7
5
1
3
15
20
9
M 2 5 15 3 4 9 15 6 0 8 7 15 20 10
15 15 15
15 15 15 Ct=
10 Ct=30 6
2 M 3
2 15 4
5 9
6 0 8
7
15
20
M 2 5 15 15 3 4 9 15 15 6 0 8 7 15 5 10 15 20 10 Ct=
15 15 15
10 Ct=30
Ct= 30 + 45 + 40 + 70 = 185 3 M 2 15 3 4 15 6 0 8 15
20
5 9
2.12.2.1.7.1.1.2.
15
Ejercicio
1
15
7 15 0 10 Ct=75
M
2
5
M
4
9
6 0 8
7
15
20
15 15 15
10 Ct=
4 M 2 5 15 3 4 9 15 6 0 8 7 15 20 10
2
15 15 15
M
2
5
M
4
9
6 0 8
7
Ct= 15
20
15 15 15
10 Ct=
Ct=
.
©
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173
Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.1 Modelos de Transporte
UABC FCAS (414) 2.12.2.2.
Problemas de asignación
En los problemas de asignación queremos resolver el problema de asignar un operador a cada operación, teniendo tantos operadores como operaciones. Se contabilizan costos (que pudieran no ser monetarios, como ejemplo podemos poner multas en rutas, proyectos rechazados por rubro, etc.) que tiene cada operador en cada operación. El algoritmo se facilita, pues en los problemas de asignación, las tablas son cuadradas (el mismo número de renglones que de columnas) y el resultado es 0 en toda la tabla, y solamente un 1 en cada renglón y en cada columna. 2.12.2.2.1.
Ejemplo
E N W S 7 7 2 1 6 6 3 1 9 7 6 3 6 7 4 8 En la distribución de productos de una empresa panificadora en esta ciudad, se han asignado rutas de distribución de utilidades semejantes, pero con áreas geográficas muy diversas y nivel socioeconómico muy contrastante. Alberto Beatriz Carlo Darío
Para cada empleado, se han contabilizado las infracciones a los diferentes reglamentos, y se resumen en la tabla anexa: Determine la asignación para lograr el costo en infracciones mínimo (16). 2.12.2.2.1.
Método Húngaro
A cada renglón se le resta el menor de sus valores.
3 3 1 5 6 2 2 1 6
Prof. Raúl Espejo Rodarte (11950)
1 2 0 2 4 0 0 0 5
Se cruzan todos los ceros con la menor cantidad posible de rayas.
1 2 0 3 4 0 0 0 5
Con dos líneas podemos Tachar todos los ceros.
Si la menor cantidad de rayas que tachan todos los ceros no es igual al número de renglones, entonces no hay suficientes ceros para hacer la asignación, en cuyo caso se procede como se indica a continuación: A los no tachados se les resta el menor de ellos,
1 2 0 3 4 0 0 0 5
El menor de los no tachados es 1
0 2 2 3
A los que están tachados una sola vez se dejan con el mismo valor,
1 2 0 3 4 0 0 0 5
0 2 0 2 3 0 0 0
Y a los que están tachados dos veces, se les suma el valor que se restó a los no tachados.
1 2 0 3 4 0 0 0 5
0 2 0 2 3 0 0 0 6
Si la menor cantidad posible de rayas es igual que el número de renglones
0 2 0 2 3 0 0 0 6 Si no fuesen suficientes, se repite el procedimiento antes señalado, hasta que haya suficientes ceros para hacer la asignación.
2 2 0 3 4 0 1 0 5
A cada columna se le resta el menor de sus valores. ©
2 2 0 3 4 0 1 0 5
32
Se hace la asignación en la celda en que se encuentre el cero solitario (o uno de los ceros del renglón (o columna) en que haya menos) en renglón o columna.
[email protected] 6461766600x173 Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.2 Problemas de asignación
UABC FCAS (414)
33
0 2 0 2 3 0 0 0 6 Ese renglón y esa columna se descartan, y a los restantes, se hace la asignación de la celda con el cero solitario:
0 2 0 2 3 0 0 0 6
0 2 0 2 3 0 0 0 6
Esta asignación, en la tabla inicial indica los costos individuales, el costo mínimo es la suma.
3 3 1 5 6 2 2 1 6 El costo mínimo es Cm=3+2+1=6 Es posible que existan varias soluciones, pero ninguna con un costo menor al calculado 2.12.2.2.2.
6 14 17 17 7 8 5 3
13 16 9 15 4 4 4 5
5 8 5 2
15 9 13 13
15 14 12 12 36
3 5 7 4 14
©
Ejercicios
9 10 11 14
15 16 15 11
15 13 14 10
14 13 11 9
11 10 9 7 46
12 11 11 11
14 13 12 10
15 15 14 9 41
Prof. Raúl Espejo Rodarte (11950)
[email protected] 6461766600x173 Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.2 Problemas de asignación
UABC FCAS (414)
©
Prof. Raúl Espejo Rodarte (11950)
34
[email protected] 6461766600x173 Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.2 Problemas de asignación
UABC FCAS (414)
©
Prof. Raúl Espejo Rodarte (11950)
35
[email protected] 6461766600x173 Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.2.2 Problemas de asignación
