Download - Problemas de Transbordo
-
OPERACIONES 2
TransbordoProfesor: Pablo Diez Bennewitz
Ingeniera Comercial - U.C.V.Operaciones 2, Ingeniera Comercial, Universidad Catlica de Valparaso
Pablo Diez Bennewitz
-
MODELO DE TRANSBORDO
Se reconoce mediante el uso de nodos intermedios o transitorios para el envo de recursos entre las distintas fuentes (oferta) y destinos (demanda)
Se construye una malla con orientacin desde las fuentes (nodos de inicio) hacia los destinos (nodos de llegada), utilizando amortiguadores (nodos transitorios) que permiten recibir y transferir recursos. Las flechas que unen los nodos de la malla representan los eventuales flujos de recursos en la secuencia de distribucin
-
MODELO DE TRANSBORDO
Luego, la malla permite convertir un modelo de transbordo en un modelo de transporte regular y resolverse como tal, utilizando los amortiguadores
As, la malla reconoce tres tipos de nodos:
Nodos puros de Oferta: solo transfieren recursos Nodos de Transbordo: entregan y reciben recursos Nodos puros de Demanda: solo reciben recursosEl amortiguador debe ser suficientemente grande para permitir que los recursos se transfieran desde las fuentes hacia los destinos
-
ESQUEMA DE TRANSBORDO
Un esquema simple del modelo de transbordo se expresa como una red de modelo de asignacin:
D1
D2
Nodos puros de Oferta
Nodos puros de Demanda
A1
A2
Nodos de Transbordo
F1
F2
F3
-
EJEMPLO DE TRANSBORDO
Dos fbricas de automviles, P1 y P2, estn conectadas a tres distribuidores, D1, D2 y D3, por medio de dos centros de trnsito, T1 y T2, de acuerdo con la red que se muestra en la siguiente diapositiva
Las cantidades de la oferta en las fbricas P1 y P2, son de 1000 y 1200 automviles, y las cantidades de la demanda en las distribuidoras D1, D2 y D3, son de 800, 900 y 500 automviles. El costo de envo por automvil (en cientos de pesos) entre los pares de nodos, se muestra en los eslabones (arcos) de conexin de la red
-
800
900
500
1200
1000
D3
D2
D1
T1
T2
P1
P2
3
4
4
2
5
8
6
5
3
9
RED - MODELO DE ASIGNACION
-
PROBLEMA PROGRAMACION LINEAL
Cada vez que se plantea un problema de programacin lineal, se procede cumpliendo las siguientes etapas:
1.- Comprensin del problema (lectura en detalle)
2.- Definicin de las variables de decisin
3.- Descripcin de la funcin objetivo
4.- Identificacin de las restricciones del problema
-
PROBLEMA PROGRAMACION LINEAL
Se plantea identificando como variables de decisin a todas las posibilidades de flujos de asignacin, a transferir entre los nodos de la red de transbordo
Se define como funcin objetivo la minimizacin de los costos de transporte asociados al transbordo
Las restricciones corresponden a un balance de transferencia de unidades para cada nodo de la red de asignacin, sin olvidar la condicin de no negatividad
-
800
900
500
1200
1000
T1
T2
P1
P2
XP1T1
XP1T2
XT2D2
XP2T1
XP2T2
XT1D1
XT1D2
XD1D2
XD2D3
XT2D3
D2
D1
D3
PROBLEMA PROGRAMACION LINEAL
Red para plantear el PPL:
-
F.O. Mn Z =
3XP1T1 + 4XP1T2 + 2XP2T1 + 5XP2T2 + 8XT1D1 + 6XT1D2 + 4XT2D2 + 9XT2D3 + 5XD1D2 + 3XD2D3
s.a. :
1000 = XP1T1 + XP1T2
1200 = XP2T1 + XP2T2
XP1T1 + XP2T1 = XT1D1 + XT1D2
XP1T2 + XP2T2 = XT2D2 + XT2D3
XT1D1 = XD1D2 + 800
XT1D2 + XT2D2 + XD1D2 = XD2D3 + 900
XT2D3 + XD2D3 = 500
Xij > 0
PROBLEMA PROGRAMACION LINEAL
-
EJEMPLO DE TRANSBORDO
El transbordo ocurre ya que la cantidad de la oferta de 2200 (1000 + 1200) automviles en los nodos P1 y P2, requiere pasar a travs de los nodos de transbordo de la red (T1 y T2) ,antes de llegar a sus puntos de destino en los nodos D1, D2 y D3
Nodos puros de Oferta Nodos de Transbordo Nodos puros de DemandaEl modelo de transbordo se convierte a un modelo de transporte con seis puntos de origen (P1, P2, T1, T2, D1 y D2) y cinco de destino (T1, T2, D1, D2 y D3)
P1, P2
D3
T1, T2, D1, D2
-
NODOS PUROS DE OFERTA
Y NODOS PUROS DE DEMANDA
Las cantidades de la oferta y la demanda en los nodos puros de oferta y puros de demanda, queda:
Oferta en un Nodo puro de Oferta
Demanda en un Nodo puro de Demanda
Oferta Original
Demanda Original
Un nodo puro de oferta no posee amortiguador
Un nodo puro de demanda no posee amortiguador
-
NODOS DE TRANSBORDO
Las cantidades de la oferta y la demanda en los nodos de transbordo, se establece de acuerdo a:
Oferta en un Nodo de Transbordo
Demanda en un Nodo de Transbordo
Oferta Original
Amorti-
guador
Demanda Original
Amorti-
guador
+
+
La oferta necesariamente posee un amortiguador, mientras que a veces se encuentra oferta original
La demanda necesariamente posee amortiguador, mientras que en ocasiones hay demanda original
-
NODOS DE TRANSBORDO
La oferta del nodo de transbordo T1 s posee oferta original, mientras que la oferta del nodo de transbordo T2 no posee oferta original
400
400
200
300
500
200
P1
P2
T1
T2
D1
D2
D2
-
NODOS DE TRANSBORDO
La demanda del nodo de transbordo T1 no posee demanda original, mientras que la demanda del nodo de transbordo T2 s posee demanda original
300
200
300
600
400
200
P1
P2
T1
T2
D1
D2
D2
-
EJEMPLO DE TRANSBORDO
P1
T1
Ofta
Dda
1000
1200
B1
900+B4
800+B3
B1
B2
500
3
T2
D1
D3
D2
P2
T1
B2
B3
B4
T2
D1
D2
3
5
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
4
5
M
2
8
6
4
9
M
Se obtiene la 1 solucin mediante mtodo de Vogel
M
-
800
900
500
1200
1000
T1
T2
P1
P2
XP1T1
XP1T2
XT2D2
XP2T1
XP2T2
XT1D1
XT1D2
XD1D2
XD2D3
XT2D3
D2
D1
D3
MODELO DE ASIGNACION
PROBLEMA DE TRANSBORDO
-
MODELO DE ASIGNACION
PROBLEMA DE TRANSPORTE
800
900
500
1200
1000
T1
P1
XP1T1
XP1T2
XP2T1
XT1D2
XD1D2
XD2D3
D1
P2
T1
T2
T2
D2
D1
D2
D3
XT2D3
XP2T2
XT1D1
XT2D2
-
EJEMPLO DE TRANSBORDO
Obtener la primera solucin factible mediante Vogel, implica asignar el mximo nmero de unidades posible en las celdas de menor costo marginal, segn los sucesivos gradientes
No obstante, en ocasiones, la celda de menor costo marginal puede asociarse con un mximo nmero de unidades determinado por los amortiguadores. Luego, se requiere definir los rangos posibles para cada amortiguador
800 < B1 < 2200 0 < B3 < 1400
0 < B2 < 1400 0 < B4 < 500
-
EJEMPLO DE TRANSBORDO
P1
T1
Ofta
Dda
1000
1200
500
3
T2
D1
D3
D2
P2
T1
T2
D1
D2
3
5
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
4
5
M
2
8
6
4
9
M
1
3
M
5
M
1
1
M
1
6
800
*
800
1000
1400
400
500
B1
B2
B3
B4
B1
B2
800+B3
900+B4
2
*
M
M
*
M
3
*
*
*
M
M
Operaciones 2, Ingeniera Comercial, Universidad Catlica de Valparaso
Pablo Diez Bennewitz
-
EJEMPLO DE TRANSBORDO
Al calcular los gradientes del mtodo de Vogel, se van obteniendo los valores de los amortiguadores
Valores de los amortiguadores:
B1 = 800
B2 = 1400
B3 = 0
B4 = 500
Si es que hay 2 o ms gradientes de igual valor (como sucede con los gradientes + M ), entonces se asigna el mximo nmero de unidades posibles en aquella celda de menor costo unitario de transporte
-
1 asignacin: XD2D3 = 500, gradiente fila D2 = M
2 asignacin: XT1D2 = 1400, gradiente fila T2 = M
3 asignacin: XT1D1 = 800, gradiente fila T1 = M
4 asignacin: XP2T1 = 800, gradiente fila P2 = 3
5 asignacin: XP1T2 = 1000
6 asignacin: XP2T2 = 400
Asignacin manual
As, Vogel determina la 1 solucin bsica factible, sin embargo falta verificar la condicin de optima-lidad e iterar va simplex si es que se requiere
EJEMPLO DE TRANSBORDO
-
EJEMPLO DE TRANSBORDO
m + n - 1 = 10
Sin embargo, la asignacin inicial mediante mtodo de Vogel tiene solamente 6 variables bsicas
Deben ingresarse cuatro valores 0 a la base
XT1T2 = 0, XT2T2 = 0, XD1T2 = 0, XD2T2 = 0
Luego, se deben calcular los precios sombra para verificar si la solucin bsica factible es o no es ptima
-
EJEMPLO DE TRANSBORDO
Ofta
Dda
1000
1200
500
3
3
5
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
4
5
M
2
8
6
4
9
M
800
800
1000
1400
400
500
0
0
0
0
P1
T1
T2
D1
D3
D2
P2
T1
T2
D1
D2
B1
B2
B3
B4
B1
B2
800+B3
900+B4
Se deben calcular todos los precios sombra
-
EJEMPLO DE TRANSBORDO
Ofta
Dda
1000
1200
500
3
3
5
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
4
5
M
2
8
6
4
9
M
800
800
1000
1400
400
500
0
0
0
0
E
E
E
+M
+M
+M
+M
+M
+M
+2
Ya que
ij
>
XJ
0
i,j
A
Solucin ptima
E
E
E
E
E
E
E
E
E
E
P1
T1
T2
D1
D3
D2
P2
T1
T2
D1
D2
B1
B2
B3
B4
B1
B2
800+B3
900+B4
-
EJEMPLO DE TRANSBORDO
Solucin ptima del ejemplo de transbordo:
XJ = ( XP1T2, XP2T1, XP2T2, XT1T2, XT1D1,
XP1T2
XP2T1
XP2T2
XT1T2
XT2T2
XT2D2
XD1T2
= 1400
= 1000
= 800
= 0
= 400
La solucin no es nica, pues es una solucin degenerada
XT2T2, XT2D2, XD1T2, XD2T2, XD2D3 )
XT1D1
XD2T2
XD2D3
= 800
= 500
= 0
= 0
= 0
Z = (1000*4) + (800*2) + (400*5) + (800*8) + (1400*4) + (500*3) = 21.100 ($100)