Formulacion del Problema de Transporte

A modo de ejemplo, construyamos el modelo de programación lineal para el siguiente problema.
Ejemplo .
 Una empresa energética dispone de tres plantas de generación para satisfacer la de-
manda eléctrica de cuatro ciudades. Las plantas 1, 2 y 3 pueden satisfacer 35, 50 y 40 millones de
[kWh] respectivamente. El valor máximo 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 ³a. La siguiente tabla muestra los costos de envío unitario
desde cada planta a cada ciudad. Formule un modelo de programación lineal que permita minimizar
los costos de satisfacción de la demanda máxima en todas las ciudades.
Hacia
Desde Ciudad 1 Ciudad 2 Ciudad 3 Ciudad 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ón necesarias para representar las posibles
decisiones que puede tomar la empresa energética . 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 = numero de millones de [kWh] producidos en la planta i enviadas a ciudad j
En términos 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.


Como existen tres puntos de oferta o sumistro, existen tres restricciones:
x11 + x12 + x13 + x14 · 35 (Restricción de oferta de la Planta 1)
x21 + x22 + x23 + x24 · 50 (Restricción de oferta de la Planta 2)
x31 + x32 + x33 + x34 · 40 (Restricción 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ón de demanda de la Ciudad 1)
x12 + x22 + x32 ¸ 20 (Restricción de demanda de la Ciudad 2)
x13 + x23 + x33 ¸ 30 (Restricción de demanda de la Ciudad 3)
x14 + x24 + x34 ¸ 30 (Restricción 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ón 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.


 Formulación General
Un problema de transporte queda de¯nido por la siguiente información:
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 punto de demanda j tiene un costo
unitario de transporte cij
Consideremos:
xij = numero de unidades enviadas desde el punto de oferta i al punto de demanda j
2
Luego, la formulación general del problema de transporte queda:
Min Pi=m
i=1 Pj=n
j=1 cijxij
st
Pj=n
j=1 xij · si (i = 1 : : :m) (Restricciones de oferta)
Pi=m
i=1 xij ¸ dj (j = 1 : : : n) (Restricciones de demanda)
xij ¸ 0 (i = 1 : : :m; j = 1 : : : n) (Restricciones de signo)
Si se satisface:
i=m
Xi=1
si =
j=n
Xj=1
dj
se dice que el problema esta balanceado. En el caso del ejemplo anterior, se veri¯ca que tando la
suma de ofertas como las de las demandas es igual a 125. En el caso de un problema de transporte
balanceado todas las restricciones estarán al  permite, por lo tanto la formulación queda:
Min Pi=m
i=1 Pj=n
j=1 cijxij
st
Pj=n
j=1 xij = si (i = 1 : : :m) (Restricciones de oferta)
Pi=m
i=1 xij = dj (j = 1 : : : n) (Restricciones de demanda)
xij ¸ 0 (i = 1 : : :m; j = 1 : : : n) (Restricciones de signo)