Fundamentos de investigaci¶on de operaciones el problema de transporte

Fundamentos de Investigaci´n de Operaciones o El Problema de Transporte
Septiembre 2002
El Problema de Transporte corresponde a un tipo particular de un problema de programaci´n o lineal. Si bien este tipo de problema puede ser resuelto por el m´todo Simplex, existe un algoritmo e simplificado especial para resolverlo.

1
1.1

Formulaci´n del Problema de Transporte o
Ejemplo de Formulaci´no

A modo de ejemplo, construyamos el modelo de programaci´n lineal para el siguiente problema. o Ejemplo 1. Una empresa energ´tica dispone de tres plantas de generaci´n para satisfacer la dee o manda el´ctrica de cuatro ciudades. Las plantas 1, 2 y 3 pueden satisfacer 35, 50 y 40 millones de e [kWh] respectivamente. El valor m´ximo de consumo ocurre a las 2 PM y es de 45, 20, 30 y 30 amillones 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´ La siguiente tabla muestra los costos de env´ unitario ıa. ıo desde cada planta a cada ciudad. Formule un modelo de programci´n lineal que permita minimizar o los costos de satisfacci´n de la demanda m´xima en todas las ciudades. o a Hacia Desde Planta 1 Planta 2Planta 3 Demanda (Millones kWh) Ciudad 1 8 9 14 45 Ciudad 2 6 12 9 20 Ciudad 3 10 13 16 30 Ciudad 4 9 7 5 30 Oferta (Millones kWh) 35 50 40

En primer lugar debemos definir las variables de decisi´n necesarias para representar las posibles o decisiones que puede tomar la empresa energ´tica . En este caso, corresponde a la cantidad de e energ´ que se debe enviar desde cada planta a cada ciudad,luego para i = 1 . . . 3 y j = 1 . . . 4 : ıa xij = n´mero de millones de [kWh] producidos en la planta i enviadas a ciudad j u En t´rminos de ´stas variables, el costo total de entregar energ´ a todas las ciudades es: e e ıa 8x11 + 6x12 + 10x13 + 9x14 +9x21 + 12x22 + 13x23 + 7x24 +14x31 + 9x32 + 16x33 + 5x34 (Costo de enviar energ´ desde la Planta 1) ıa (Costo de enviar energ´ desde la Planta 2) ıa(Costo de enviar energ´ desde la Planta 3) ıa

El problema tiene dos tipos de restricciones. En primer lugar, la energ´ total suministrada por cada ıa 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 x21 + x22 + x23 + x24 x31 + x32 + x33 + x34≤ ≤ ≤ 35 50 40 (Restricci´n de oferta de la Planta 1) o (Restricci´n de oferta de la Planta 2) o (Restricci´n de oferta de la Planta 3) o

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 Ciudad1) o x12 + x22 + x32 ≥ 20 (Restricci´n de demanda de la Ciudad 2) o x13 + x23 + x33 ≥ 30 (Restricci´n de demanda de la Ciudad 3) o x14 + x24 + x34 ≥ 30 (Restricci´n de demanda de la Ciudad 4) o Evidentemente, cada xij debe ser no negativo, por lo tanto se agregan las restricciones xij ≥ 0 a o donde i = 1 . . . 3 y j = 1 . . . 4. M´s 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. Por otro lado, es posible construir una representaci´n gr´fica del problema: o a Puntos de Oferta Puntos de Demanda
0 x 11 =
x 21 =
1

Ciudad 1
45
0

d1 = 45

s1 = 35

Planta 1

x1 = 2 10
x 13 = 25

= x3

0 x 22 =
x 32 = 10

Ciudad 2

d2 = 20

s2 = 50

Planta 2

x2 = 35

Ciudad 3
0 x 33 =
x 14 = 0

d3 = 30

s3 = 40

Planta 3

x 24

=

0

x3 = 4 30

Ciudad 4

d4 = 30

1.2

Formulaci´n General o

Un problema de transporte queda definido por la siguiente informaci´n: o 1. Un conjunto de m puntos de oferta. Cada punto de oferta i tiene asociado una oferta s i . 2. Un conjunto de n puntos de demanda. Cada punto de demanda j tiene...