metodo 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
simplificado especial para resolverlo.

1
1.1

Formulaci´
on del Problema de Transporte
Ejemplo deFormulaci´
on

A modo 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 demanda 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 30millones 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
DesdeCiudad 1

Ciudad 2

Ciudad 3

Ciudad 4

Planta 1
Planta 2
Planta 3
Demanda
(Millones kWh)

8
9
14

6
12
9

10
13
16

9
7
5

45

20

30

30

Oferta
(Millones kWh)
35
50
40

En primer lugar debemos definir las variables de decisi´on necesarias para representar las posibles
decisiones que puede tomar la empresa energ´etica . En este caso, corresponde a lacantidad 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
+9x21 + 12x22 + 13x23 + 7x24
+14x31 + 9x32 + 16x33 + 5x34

(Costo deenviar energ´ıa desde la Planta 1)
(Costo de enviar energ´ıa desde la Planta 2)
(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 tresrestricciones:
x11 + x12 + x13 + x14
x21 + x22 + x23 + x24
x31 + x32 + x33 + x34

35
50
40

≤
≤
≤

(Restricci´on de oferta de la Planta 1)
(Restricci´on de oferta de la Planta 2)
(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 demandapara 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´afica del problema:
Puntos de Oferta

Puntos de Demanda
0
x 11 =

s1 = 35

Planta 1

x 21

=

Ciudad 2

d2 = 20

Ciudad 3d3 = 30

Ciudad 4

d4 = 30

0
1

x3

25

0
x 22 =

s2 = 50

d1 = 45

=

x1 =
2
10
x
13

=

Ciudad 1
45

x 32

Planta 2

=

10

x2 =
3
5

x
14

0
x 33 =

s3 = 40

x
24

Planta 3

=
0

=

0

x3 =
4
30

1.2

Formulaci´
on General

Un problema de transporte queda definido por la siguiente informaci´on:
1. Un conjunto de m...