Investigación Operaciones problema de transbordo

Fundamentos de Investigaci´n de Operaciones
o
El Problema de Transporte
15 de mayo de 2004

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

1.

Formulaci´n del Problema de Transporte
o

1.1.Ejemplo de Formulaci´n
o

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 demanda
e
o
el´ctrica de cuatro ciudades. Las plantas 1, 2 y 3 pueden satisfacer 35, 50 y 40 millones de [kWh]
e
respectivamente. El valor m´ximo de consumo ocurre a las 2 PM y esde 45, 20, 30 y 30 millones de
a
[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 desde cada planta a
ıa.
ıo
cada ciudad. Formule un modelo de programci´n lineal que permita minimizar los costos de satisfacci´n
o
o
de la demanda m´xima en todas lasciudades.
a
Hacia
Desde

Ciudad 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

Oferta
(Millones kWh)
35
50
40

30

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 estecaso, corresponde a la cantidad de energ´
e
ıa
que se debe enviar desde cada planta a cada ciudad, luego para i = 1 . . . 3 y j = 1 . . . 4 :
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
1

(1.1)

Segundo Semestre 2003

El Problema de Transporte8x11 + 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

(1.2)

El problema tiene dos tipos de restricciones. En primer lugar, la energ´ total suministrada por cada
ıa
planta no puede exceder su capacidad. En estecaso se habla de restricciones de oferta o suministro.
Como existen tres puntos de oferta o sumistro, existen tres restricciones:
x11 + x12 + x13 + x14 ≤ 35
x21 + x22 + x23 + x24 ≤ 50
x31 + x32 + x33 + x34 ≤ 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

(1.3)

En segundo lugar, se deben plantear lasrestricciones 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
x12 + x22 + x32
x13 + x23 + x33
x14 + x24 + x34

≥
≥
≥
≥

45
20
30
30

(Restricci´n
o
(Restricci´n
o
(Restricci´n
o
(Restricci´n
o

de
de
de
de

demanda
demanda
demanda
demanda

de
de
dede

la
la
la
la

Ciudad
Ciudad
Ciudad
Ciudad

1)
2)
3)
4)

(1.4)

Evidentemente, cada xij debe ser no negativo, por lo tanto se agregan las restricciones x ij ≥ 0
donde i = 1 . . . 3 y j = 1 . . . 4. M´s adelante demostraremos que la soluci´n de este problema es
a
o
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 (figura 1.1).
o
a
Puntos de Oferta

Puntos de Demanda
Ciudad 1
0
=
1
x3

x1

25
0
x 22 =
=

s2 = 50

d4 = 30

45

x 21
x12 =
10
3 =

d3 = 30

Ciudad 4

Planta 1

d2 = 20

Ciudad 3

=

s1 = 35

d1 = 45

Ciudad 2

0
x 11 =

10

x 32

Planta 2

x23 =
5

x

0
x 33 =...