transporte_y_transbordo_(2008)

Vista previa del material en texto

PROBLEMAS ESPECIALES 
DE PROGRAMACIÓN 
LINEAL
PROBLEMAS ESPECIALES 
DE PROGRAMACIÓN 
LINEAL
a. PROBLEMA DE TRANSPORTE
1
N
2
M
2
1a1
O
R
I a2
G
E
N
am
b1 
D
b2 E
S
T
I
N
O
bn 
Xij
b. PROBLEMA DE ASIGNACIÓN
1
N
2
M
2
1a1=1
O
R
I a2=1
G
E
N
am=1
b1=1 
D
b2=1 E
S
T
I
N
O
bn=1 
Xij binaria
c. PROBLEMA DE TRANSBORDO
1
N
2
M
2
1a1
O
R
I a2
G
E
N
am
b1 
D
b2 E
S
T
I
N
O
bn 
Xij
T1
T2
a. PROBLEMA TRANSPORTE
EJEMPLO:
Una empresa posee 3 plantas ( 1, 2 y 3 ) en las cuales fabrica un determinado 
producto, el que es vendido en los mercados ( A y B ) con demandas de 25 y 10 
unidades por mes. La capacidad de producción es de 10, 15 y 10 u/mes para las 
plantas 1, 2 y 3 respectivamente. El costo de transportar una unidad de producto a 
un mercado cualquiera es variable dependiente de la fabrica de donde se envía, 
tales costos se muestran en la tabla siguiente :
PLANTA MERCADO A MERCADO B
-------------------------------------------------
1 2 2
2 5 9
3 6 4
El modelo de PL asociado es el siguiente :
Min Z = 2x11 + 2x12 + 5x21 + 9x22 + 6x31 + 4x32
s.a.
x11 + x12 = 10 capacidad de plantas
x21 + x22 = 15
x31 + x32 = 10
x11 + x21 + x31 = 25 demanda de mercados
x12 + x22 + x32 = 10
xij >= 0, para todo i= 1..3 ; j= 1,2.
FORMA GENERAL:
m n
Min Z = ∑ ∑ Cij*Xij
i=1 j=1
s.a.
n
∑ Xij = ai , para todo i=1....m
j=1
m
∑ Xij = bj , para todo j=1....n
i=1
Xij >= 0 para todo i,j.
En donde :
Cij : costo de transportar una unidad de item
desde el origen i al destino j.
Xij : cantidad de unidades transportadas desde el
origen i al destino j.
ai : disponibilidad del origen i.
bj : requerimiento del destino j.
n : número de destinos
m : número de orígenes
El problema tiene solución si:
m n
∑ ai = ∑ bj
i=1 j=1
Si lo anterior no se cumple se debe crear un origen o un destino ficticio 
para balancear el sistema, luego :
m n
i. Si ∑ ai > ∑ bj , entonces se debe crear un destino ficticio, con 
i=1 j=1 j = n + 1, que tendrá una demanda de :
m n
bn+1 = ∑ ai - ∑ bj
i=1 j=1
m n
ii. Si ∑ ai < ∑ bj , entonces se debe crear un origen ficticio, con
i=1 j=1 i = m + 1, que tendrán una capacidad de :
n m
am+1 = ∑ bj - ∑ ai
j=1 i=1
cij = 0 para todos los nodos ficticios
Tabla simplex de transporte
C11
x11
C12
x12
………. C1n
x1n
C21
x21
C22
x22
………. C2n
x2n
.
.
.
.
………. .
.
Cm1
xm1
Cm2
xm2
………. Cmn
xmn
D E S T I N O
O
R
I
G
E
N
b1 b2 … … … … . …………….. bn 
a1
a2
.
.
.
.
.
.
.
am
Nosotros utilizamos 
una modificación de 
esta
Cada celda esta 
conformada por
Xij
δij Cij
±Θ
Costo 
unitario 
asociado a 
la ruta i-j
Valor asociado a la 
variable entrante
Variable de decisión a 
definir
Precio sombra
Tabla simplex de transporte
C11
x11
C12
x12
………. C1n
x1n
C21
x21
C22
x22
………. C2n
x2n
.
.
.
.
………. .
.
Cm1
xm1
Cm2
xm2
………. Cmn
xmn
D E S T I N O
O
R
I
G
E
N
b1 b2 … … … … . …………….. bn 
a1
a2
.
.
.
.
.
.
.
am
X11
δ11 C11
±Θ X12
δ12 C12
±Θ
X21
δ21 C21
±Θ X22
δ22 C22
±Θ
Xm1
δm1 Cm
1
±Θ Xm2
δm2 Cm
2
±Θ
X1n
δ1n C1n
±Θ
X2n
δ2n C2n
±Θ
Xmn
δmn Cmn
±Θ
Métodos para encontrar solución básica 
inicial
A. METODO DE LA ESQUINA NOROESTE
Consiste en asignar la mayor cantidad de unidades a la esquina noroeste ( 
X11 ), luego se desplaza al renglón o columna siguiente en donde pueda 
hacer una asignación, y así sucesivamente.
B. METODO DEL MENOR COSTO
Se selecciona la celda con el menor costo y a ella se le asigna la mayor 
cantidad de unidades posibles, luego se elimina la fila o columna cuya 
capacidad o demanda ha sido completada. De las celdas no eliminadas se 
elige nuevamente la de menor costo ( empates se resuelven 
arbitrariamente ) y se asigna la mayor cantidad de unidades posibles 
y así sucesivamente.
C. METODO DE APROXIMACION DE VOGEL ( VAM )
– Se determina para cada renglón o columna la diferencia entre los 2 menores 
costos.
– Seleccionar la fila o columna con la mayor diferencia de costos.
– De la fila o columna seleccionada se escoge la celda con menor costo y se 
asigna la mayor cantidad de unidades posibles.
– Eliminar la fila o columna cuya capacidad o demanda fue copada. Repetir el 
procedimiento anterior.
Método simplex de transporte
• Este Método se fundamenta en el teorema de las Holguras Complementarias y 
trabaja con el Problema Dual. Entonces sean:
• ui : variable dual correspondiente a las restricciones de capacidad del problema 
primal.
• vj : variable dual correspondiente a las restricciones de demanda del problema primal.
Para cada variable Xij se debe evaluar cij - ui - vj ; así :
- si Xij es básica entonces cij - ui - vj = 0
- si Xij es no básica entonces cij - ui - vj >= 0
Por lo tanto si hay m+n-1 var. básicas, habrá m+n-1 ecuaciones del tipo cij - ui -
vj = 0. Este sistema se resuelve asignando un valor cualquiera a una de la 
variables ui, vj (por convención se asigna un valor cero) y luego se determina 
el resto de las variables. Luego se debe determinar para cada Xij no básico 
la expresión cij - ui - vj ; si esta expresión es >= 0 para todo Xij no básico, 
entonces la solución es óptima. Sino se debe iterar según el siguiente 
procedimiento:
Procedimiento:
1. Paso inicial :
Construir una solución básica inicial factible mediante alguno de los procedimientos descritos 
anteriormente. Luego hacer prueba de optimalidad.
2. Paso iterativo :
• Determinar la variable básica entrante eligiendo la variable no básica con el valor 
cij - ui - vj más negativo. 
• Determinar la variable básica saliente identificando la reacción en cadena que se 
necesita para mantener la factibilidad, y seleccionando aquella variable básica 
que se hace primero igual a cero cuando la variable básica entrante aumenta su valor.
• Obtener la nueva solución factible sumando el valor de la variable básica que sale a 
las celdas receptoras y restándolo a las celdas donadoras.
3. Prueba de optimalidad :
Determinar ui y vj para cada fila y columna haciendo algún ui = 0 y resolviendo el sistema de 
ecuaciones cij - ui -vj = 0 para cada i,j tal que Xij es básico. Si cij - ui -vj >= 0 para 
todo i,j, tal que Xij es no básico, entonces la solución actual es óptima. De lo contrario 
hacer otra iteración.
EJEMPLO:
Es necesario planear el sistema de energía de un nuevo edificio. Las tres fuentes posibles de 
energía son Electricidad, Gas Natural y Unidades de Celdas Solares.
Los requerimientos diarios de energía son:
- Electricidad 20 unidades
- Calefactores de Agua 10 "
- Calefactores de Ambiente 30 “
El tamaño del techo limita la unidad de celdas solares a 30 unidades, pero no hay límite en la 
disponibilidad de electricidad y gas natural. Las necesidades de electricidad sólo pueden 
satisfacerse con energía eléctrica (a un costo de 50 $/u). Las otras dos necesidades 
energéticas se pueden satisfacer con cualquier fuente o combinación de fuentes. Los 
costos unitarios ($/u) son:
FUENTE CALEFACTOR DE 
AGUA AMBIENTE
ELECTRICIDAD 90 80
GAS NATURAL 60 50
CELDAS SOLARES 30 40
Si el objetivo es minimizar el costo total para cumplir con las necesidades de energía:
a. Formule el problema como un cuadro de transporte
b. Obtenga una solución básica inicial mediante: 
- Costo Menor
- Esq. Noroeste
- Vogel
c. Obtenga la solución óptima
b. PROBLEMA DE ASIGNACIÓN:
Modelo general de PL es :
m n
Min Z = ∑ ∑ Cij*Xij
i=1 j=1
s.a.
n
∑ Xij = 1 , para todo i=1....m
j=1
m
∑ Xij = 1 , para todo j=1....ni=1
Xij variable de decisión que indica :
1 , recurso i es asignado a actividad j.
Xij = 
0 , sino.
Cij costo de asignar recurso i a actividad j.
Ejemplo prototipo:
Una empresa ha adquirido 3 máquinas nuevas, para lo cual 
dispone de 4 lugares posibles de localización. Sin embargo 
se debe determinar la localización óptima de manera de 
minimizar el costo de flujo de materiales.
Para ello se ha determinado el costo por unidad de tiempo del 
manejo de materiales para cada máquina según la 
localización. Estos costos se muestran en la tabla siguiente:
Localización maq 1 maq 2 maq 3
1 13 15 5
2 10 - 7
3 12 13 10
4 11 20 6
Por razones de espacio la máquina 2 no puede localizarse en 2.
Modelo de Prog. Lineal:
Xij : máquina i es asignada en j.
Min Z = 13x11 + 15x12 + 5x13 + 10x21 + 5x23 + 12x31 + 13x32
+ 10x33 + 11x41 + 20x42 + 6x43 + Mx22
s.a. 
x11 + x12 + x13 + x14 = 1 cada máquina es localizada
x21 + x22 + x23 + x24 = 1 solo en un lugar.
x31 + x32 + x33 + x34 = 1
x41 + x42 + x43 + x44 = 1 
x11 + x21 + x31 + x41 = 1 en cada localización
x12 + x22 + x32 + x42 = 1 se asigna solo a una
x13 + x23 + x33 + x43 = 1 máquina.
x14 + x24 + x34 + x44 = 1 
Xij = 0 ó 1
PROCEDIMIENTO DEL METODO HUNGARO:
i. Balancear el problema de tal forma que el número de 
orígenes sea igual al de destinos ( n = m ). 
ii. Hacer reducción de filas ( dejar al menos un cero en cada 
fila de la matriz de asignación ).
iii. Hacer reducción de columnas ( dejar al menos un cero en 
cada columna de la matriz de asignación ).
iv. Cubrir los ceros de la matriz con el número mínimo de líneas 
horizontales o verticales.
v. Si el número mínimo de líneas del punto anterior es inferior 
a n, ir al paso siguiente; de lo contrario, si el número de 
líneas es igual a n, entonces la asignación es óptima y 
quedar indicada en los pares i,j con valor igual a cero.
vi. De los números no cubiertos con líneas, elegir al menor de 
ellos. Este número se debe restar a todos los números no 
cubiertos y sumar a aquellos valores que pertenecen a la 
intersección de líneas. Volver al paso iv.
Nota : Cuando se trata de problemas de maximización 
los Cij se multiplican por -1, o bien se calcula la 
matriz de costo de oportunidad.
c. PROBLEMA DE TRANSBORDO
- Problema de transporte con nodos 
intermedios o trasbordo
- Un origen puede ser un destino y un 
destino un origen
- Las capacidades y demandas no son 
evidentes
- Solución: sumar a cada nodo una cantidad 
de amortiguamiento
m n
A = ∑ ai = ∑ bj
i=1 j=1
Método de solución:
- Transporte completo
- Transporte reducido
- Transporte sin trasbordo
Ejemplo:
100 3 2 80
4 2 5 4
3 4 160
230 5 3 6 3
- 6 4 90
1
2
4
3
7
6
5
Problemas especiales de 
PL:
Problema de 
Transbordo
Problemas especiales de 
PL:
Problema de 
Transbordo
Introducción
• El problema de transbordo se refiere a la 
minimización de los costos de transporte 
de algún producto entre nodos.
• En donde cada nodo puede ser un punto de 
abastecimiento (origen), un punto de 
demanda (destino), o ambos.
• En un problema de transbordo existen 3 
tipo de nodos.
– Origen puro: un nodo solo de oferta
– Destino puro: un nodo solo de demanda
– Nodo de Transbordo: un nodo que puede embarcar y 
recibir.
Ejemplo 1:
• Una empresa decide reasignar cierta cantidad de 
artículos entre sus diferente locales de ventas.
• Considere que en los locales [1], [5] y [6] hay 10, 6 
y 4 unidades sobrantes y que en los locales [2], [3] 
y [7] faltan 8,5 y 7 unidades respectivamente. 
• Se desea determinar la redistribución de estos 
artículos de modo que el costo total de transporte 
sea mínimo, basado en la siguiente red que señala 
la ubicación de los nodos y los costos de 
transporte por unidad de producto.
Ejemplo 1:
cont.
5
4
3
2
1 7
6
35
5
20
1
8
45
15 5
10
5 10
20
[1], [5] y [6] hay 10, 6 y 4 unidades sobrantes
4
6
10
[2], [3] y [7] faltan 8,5 y 7 unidades
-8
-5 -7
Xij : unidades a transportar desde el nodo i al nodo j.
Ejemplo 1: modelo
12 13 14 25 32 36
43 53 56 57 64 67
12 13 14
12 32 25
13 43 53 32 36
14 64 43
25 53 56 57
35 15 45 5 20 5
1 10 5 20 8 10
. .
(nodo 1) : 10
(nodo 2) : 8
(nodo 3) : 5
(nodo 4) :
(nodo 5) : 6
(nod
min Z x x x x x x
x x x x x x
s a
x x x
x x x
x x x x x
x x x
x x x x
= + + + + +
+ + + + + +
= + +
+ = +
+ + = + +
+ =
+ = + +
36 56 64 67
57 67
o 6) : 4
(nodo 7) : 7
0 ; ,ij
x x x x
x x
x i j
+ + = +
+ =
≥ ∀
Método de solución
• Par resolver un problema de transbordo se 
puede modelar mediante una tabla de 
transporte y resolver aplicando el 
algoritmo Simplex-Transporte.
• Para esto hay dos métodos:
– Uno de ellos se basa en determinar la distancia 
mínima entre cada nodo de oferta y cada nodo 
de demanda. Esto implica utilizar un algoritmo 
adicional llamado “Algoritmo de ruta más 
corta”.
– El segundo es un método más directo. No es 
necesario usar otro algoritmo. Pero las tablas 
son de dimensiones mayores.
Método de solución
• Método 1:
– Construir una tabla de transporte considerando como 
nodos orígenes aquellos que tengan una oferta y como 
nodos de destino los que tengan demanda.
– Seleccionar el menor costo para ir desde un origen a un 
destino.
2 3 7 Of.
35 15 ?
? 10 20
? ? 10
Dda. 8 5 7
10
6
4
1
5
6
La dificultad de este método radica en que para encontrar el 
menor costo de
un origen a un destino se tiene que aplicar un algoritmo 
adicional
Los costos que se deben incluir en la tabla no son obvios
Método de solución
Método 2:
La tabla de transporte se construye como sigue:
• Los orígenes son los orígenes puros y los nodos de 
transbordo. 
– La oferta o disponibilidad en cada nodo de transbordo i se 
reemplaza por (ai + B), donde ai es el máximo entre la cero y 
la oferta del nodo i.
• Los destinos son los destinos puros y los nodos de 
transbordo.
– La demanda en un nodo de transbordo j será (bj + B), donde 
bj es el máximo entre cero y la demanda del nodo j.
• Los nodos de oferta y demanda no se alteran.
Método de solución
Método 2: (cont.)
• Si no existe un “arco” entre el nodo i y el 
nodo j, entonces cij=M, donde M→∝.
• Para los nodos de transbordo, la distancia 
desde el nodo a sí mismo es cero.
• SI el problema no está balanceado, agregar 
un nodo de oferta o demanda puro con costos 
cero, de tal forma que se cumpla:
•
i iB a b= =∑ ∑
Ejemplo 1:
cont.
5
4
3
2
1 7
6
35
5
20
1
8
45
15 5
10
5 10
20
4
6
10
-8
-5 -7
Nodos de oferta: 1
Nodos de demanda: 7
Nodos de transbordo: 2, 3, 4, 5, 6
Observemos que el problema está balanceado
¿Qué pasa si no está balanceado?
Resolver !!!
Ejemplo 1: Solución
(salida WinQSB)
Ejemplo 2:
• Nodos 1 y 5 son ubicaciones de las plantas. Esas 
plantas producen 200 y 150 unidades 
respectivamente.
• Los nodos 3, 6 y 9 son las ubicaciones de las 
tiendas, y demandan 50, 250 y 100 unidades 
respectivamente. 
• El número en el arco (i , j) señala el costo de 
transportar una unidad de producto desde el nodo 
i al nodo j. 
• Supongamos que el costo desde i a j es el mismo 
que desde j a i.
Ejemplo 2:
2 5
1 4 7 9
3 6 8
6
1 7 8
5 4
8 4
4
3
2
4
53
4
6
6
-50
+200
+150
-250
-100
¿Plantear la tabla de transporte?
¿Plantar el modelo de PL asociado al problema?
El nodo ficticio se conecta directamente, con costo
cero a todos los nodos demandantes, sean estos
de transbordo o puros.
2 5
1 4 7 9
3 6 8
200
50
50
50150
100
-50
+200
+150
-250
-100
50
Solución directa por WinQSB
2 5
1 4 7 9
3 6 8
200
50
50
50150
100
-50
+200
+150
-250
-100
50
Solución por Transporte