A todo Vapor

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 deFormulaci´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 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, 30y 30
a
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´ 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
HaciaDesde

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 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 deoferta 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 Ciudad 1)
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 seagregan las restricciones xij ≥ 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:
o
a
Puntos de Oferta

Puntos de Demanda
Ciudad 1

x 21

=

01

x3

25

0
x 22 =

s2 = 50

d4 = 30

45

=

x1 =
2
10
x
13

=

d3 = 30

Ciudad 4

Planta 1

d2 = 20

Ciudad 3

s1 = 35

d1 = 45

Ciudad 2

0
x 11 =

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´n General
o

Un problema de transporte queda...