Problemas de transporte

Fundamentos de Investigaci¶on de Operaciones
El Problema de Transporte
Septiembre 2002
El Problema de Transporte corresponde a un tipo particular de un problema de programaci¶on
lineal. Si bien este tipo de problema puede ser resuelto por el m¶etodo Simplex, existe un algoritmo
simpli¯cado especial para resolverlo.
1 Formulaci¶on del Problema de Transporte
1.1 Ejemplo de Formulaci¶on
Amodo de ejemplo, construyamos el modelo de programaci¶on lineal para el siguiente problema.
Ejemplo 1. Una empresa energ¶etica dispone de tres plantas de generaci¶on para satisfacer la de-
manda el¶ectrica de cuatro ciudades. Las plantas 1, 2 y 3 pueden satisfacer 35, 50 y 40 millones de
[kWh] respectivamente. El valor m¶aximo de consumo ocurre a las 2 PM y es de 45, 20, 30 y 30
millones de[kWh] en las ciudades 1, 2, 3 y 4 respectivamente. El costo de enviar 1 [kWh] depende
de la distancia que deba recorrer la energ¶³a. La siguiente tabla muestra los costos de env¶³o unitario
desde cada planta a cada ciudad. Formule un modelo de programci¶on lineal que permita minimizar
los costos de satisfacci¶on de la demanda m¶axima en todas las ciudades.
Hacia
Desde Ciudad 1 Ciudad 2 Ciudad 3Ciudad 4
Oferta
(Millones kWh)
Planta 1 8 6 10 9 35
Planta 2 9 12 13 7 50
Planta 3 14 9 16 5 40
Demanda
(Millones kWh)
45 20 30 30
En primer lugar debemos de¯nir las variables de decisi¶on necesarias para representar las posibles
decisiones que puede tomar la empresa energ¶etica . En este caso, corresponde a la cantidad de
energ¶³a que se debe enviar desde cada planta a cada ciudad,luego para i = 1 : : : 3 y j = 1 : : : 4 :
xij = n¶umero de millones de [kWh] producidos en la planta i enviadas a ciudad j
En t¶erminos de ¶estas variables, el costo total de entregar energ¶³a a todas las ciudades es:
8x11 + 6x12 + 10x13 + 9x14 (Costo de enviar energ¶³a desde la Planta 1)
+9x21 + 12x22 + 13x23 + 7x24 (Costo de enviar energ¶³a desde la Planta 2)
+14x31 + 9x32 + 16x33 + 5x34(Costo de enviar energ¶³a desde la Planta 3)
El problema tiene dos tipos de restricciones. En primer lugar, la energ¶³a total suministrada por cada
planta no puede exceder su capacidad. En este caso se habla de restricciones de oferta o suministro.
1
Como existen tres puntos de oferta o sumistro, existen tres restricciones:
x11 + x12 + x13 + x14 · 35 (Restricci¶on de oferta de la Planta 1)
x21 +x22 + x23 + x24 · 50 (Restricci¶on de oferta de la Planta 2)
x31 + x32 + x33 + x34 · 40 (Restricci¶on de oferta de la Planta 3)
En segundo lugar, se deben plantear las restricciones que permitan asegurar que se satisfaga la
demanda en las cuatro ciudades. As¶³, las restricciones de demanda para cada punto de demanda
quedan:
x11 + x21 + x31 ¸ 45 (Restricci¶on de demanda de la Ciudad 1)
x12 +x22 + x32 ¸ 20 (Restricci¶on de demanda de la Ciudad 2)
x13 + x23 + x33 ¸ 30 (Restricci¶on de demanda de la Ciudad 3)
x14 + x24 + x34 ¸ 30 (Restricci¶on de demanda de la Ciudad 4)
Evidentemente, cada xij debe ser no negativo, por lo tanto se agregan las restricciones xij ¸ 0
donde i = 1 : : : 3 y j = 1 : : : 4. M¶as adelante demostraremos que la soluci¶on de este problema es
z = 1020, x12 =10, x13 = 25, x21 = 45, x23 = 5, x32 = 10 y x34 = 30. El resto de las variables vale
cero.
Por otro lado, es posible construir una representaci¶on gr¶a¯ca del problema:
Planta 1
Planta 2
Planta 3
Ciudad 1
Ciudad 2
Ciudad 3
Ciudad 4
x11 = 0
x12 = 10
x13 = 25
x14 = 0
x21 = 45
x22 = 0
x23 = 5
x24 = 0
x31 = 0
x32 = 10
x33 = 0
x34 = 30
Puntos de Oferta Puntos de Demanda
s1 = 35s2 = 50
s3 = 40
d1 = 45
d2 = 20
d3 = 30
d4 = 30
1.2 Formulaci¶on General
Un problema de transporte queda de¯nido por la siguiente informaci¶on:
1. Un conjunto de m puntos de oferta. Cada punto de oferta i tiene asociado una oferta si.
2. Un conjunto de n puntos de demanda. Cada punto de demanda j tiene asociada una demanda
dj .
3. Cada unidad enviada desde un punto de oferta i a un...