transbordo npj 2013.pdf
TRANSCRIPT
Transbordo
Noé Panozo Jiménez
MODELO DE TRANSBORDO
Se reconoce mediante el uso de nodos intermedios
o transitorios para el envío de recursos entre las
distintas fuentes (oferta) y destinos (demanda)
Se construye una malla con orientación 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 distribución
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 recursos
El 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 asignación:
D1
D2
Nodos puros
de Oferta
Nodos puros
de Demanda
A1
A2
Nodos de
Transbordo
F1
F2
F3
EJEMPLO DE TRANSBORDO
Dos fábricas de automóviles, P1 y P2, están
conectadas a tres distribuidores, D1, D2 y D3, por
medio de dos centros de tránsito, T1 y T2, de
acuerdo con la red que se muestra en la siguiente
diapositiva
Las cantidades de la oferta en las fábricas P1 y P2,
son de 1000 y 1200 automóviles, y las cantidades
de la demanda en las distribuidoras D1, D2 y D3,
son de 800, 900 y 500 automóviles. El costo de
envío por automóvil (en cientos de pesos) entre
los pares de nodos, se muestra en los eslabones
(arcos) de conexión 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 programación lineal, se procede
cumpliendo las siguientes etapas:
1.- Comprensión del problema (lectura en detalle)
2.- Definición de las variables de decisión
3.- Descripción de la función objetivo
4.- Identificación de las restricciones del problema
PROBLEMA PROGRAMACION LINEAL
Se plantea identificando como variables de decisión
a todas las posibilidades de flujos de asignación, a
transferir entre los nodos de la red de transbordo
Se define como función objetivo la
minimización 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 asignación,
sin olvidar la condición de no negatividad
800
900
500
1200
1000 T1
T2
P1
P2
XP1T1
XP2T2
XD
1D
2
XD
2D
3
D2
D1
D3
PROBLEMA PROGRAMACION LINEAL
Red para plantear el PPL:
F.O. Mín 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) automóviles en los nodos P1
y P2, requiere pasar a través 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 Demanda
El 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ª solución mediante método de Vogel
M
800
900
500
1200
1000 T1
T2
P1
P2
XP1T1
XP2T2
XD
1D
2
XD
2D
3
D2
D1
D3
MODELO DE ASIGNACION
PROBLEMA DE TRANSBORDO
MODELO DE ASIGNACION
PROBLEMA DE TRANSPORTE
800
900
500
1200
1000 T1
P1
D1
P2
T1
T2
T2
D2
D1
D2
D3
EJEMPLO DE TRANSBORDO
Obtener la primera solución factible mediante
Vogel, implica asignar el máximo número de
unidades posible en las celdas de menor costo
marginal, según los sucesivos gradientes
No obstante, en ocasiones, la celda de menor
costo marginal puede asociarse con un máximo
número 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
EJEMPLO DE TRANSBORDO
Al calcular los gradientes del método 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 más gradientes de igual valor
(como sucede con los gradientes + M ), entonces se
asigna el máximo número de unidades posibles en
aquella celda de menor costo unitario de transporte
1ª asignación: XD2D3 = 500, gradiente fila D2 = M
2ª asignación: XT1D2 = 1400, gradiente fila T2 = M
3ª asignación: XT1D1 = 800, gradiente fila T1 = M
4ª asignación: XP2T1 = 800, gradiente fila P2 = 3
5ª asignación: XP1T2 = 1000
6ª asignación: XP2T2 = 400
Asignación
manual
Así, Vogel determina la 1ª solución básica factible,
sin embargo falta verificar la condición de optima-
lidad e iterar vía simplex si es que se requiere
EJEMPLO DE TRANSBORDO
EJEMPLO DE TRANSBORDO
m + n - 1 = 10 Sin embargo, la asignación inicial
mediante método de Vogel tiene
solamente 6 variables básicas
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 solución básica 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 Solución ó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
Solución óptima del ejemplo de transbordo:
XJ = ( XP1T2, XP2T1, XP2T2, XT1T2, XT1D1,
XP1T2
XP2T1
XP2T2
XT1T2
XT2T2
XT2D2
XD1T2
= 1400
= 1000
= 800
= 0
= 400
La solución no
es única, pues
es una solución
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)
El modelo de transbordo con capacidades, es esencialmente
idéntico al modelo de transporte que se vio en IO 1, salvo por
lo siguiente:
i) Cualquier planta o almacén puede enviar embarques a
cualquier planta o almacén y
ii) Puede haber cotas (capacidades) superiores e inferiores
en cada embarque (rama)
Puesto que esas capacidades se pueden agregar al modelo, y
los embarques puede pasar de un modelo a otro (o de una
planta a otra planta), se dice que este es un modelo de
transbordo con capacidades.
Su Modelo de PL, hay una ecuación de balance de flujo: lados
derechos positivos corresponden a nodos que son
proveedores, nodos negativos son destinos.
Tiene un estructura especial de este modelo de red, se genera
la matriz de incidencia nodo-arco
Flujo restringido de Costo Mínimo: es la generalización del
modelo del flujo máximo:
i) Todos los arcos son direccionales (un sentido)
ii) Un costo de flujo por unidad (no negativo) esta asociado
con cada arco.
iii) Los arcos pueden tener limites positivos de capacidad
inferior.
iv) Cualquier nodo en la red puede actuar como punto de
origen o un pozo.
El nuevo modelo determina los flujos en los diferentes arcos
que minimizan el costo total, al mismo tiempo que satisface
las restricciones del flujo de arcos y las cantidades de la
oferta y demanda en los nodos.