Modelo transporte
Páginas: 33 (8080 palabras)
Publicado: 10 de junio de 2010
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.
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 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 es de 45, 20, 30 y 30millones 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 las ciudades. a Hacia Desde Planta 1Planta 2 Planta 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 energ´ e ıa que se debe enviar desde cada planta a cadaciudad, 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 Transporte
8x11 + 6x12 + 10x13 + 9x14 +9x21 + 12x22 + 13x23 + 7x24 +14x31 + 9x32 + 16x33 + 5x34
(Costo de enviarenerg´ 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 este caso se habla de restricciones de oferta o suministro. Como existen tres puntos de oferta o sumistro, existen tresrestricciones: 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 las restricciones que permitan asegurar que se satisfaga la demanda en las cuatro ciudades. As´ las restricciones de demanda para cadapunto 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 de de 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
0 x 11 =
Ciudad 1
45
0
d1 = 45
=
s1 = 35
Planta 1
x 21x12 = 10
=
1 x3
x1
3 =
25
0 x 22 =
= 10
Ciudad 2
d2 = 20
s2 = 50
Planta 2
x 32
x23 = 5
Ciudad 3
0 x 33 =
x
14
d3 = 30
= 0
s3 = 40
Planta 3
x2
4 =
0
x34 = 30
Ciudad 4
d4 = 30
Figura 1.1: Representaci´n gr´fica del problema o a
Departamento de Inform´tica a
2
Universidad Santa Mar´ ıa
Segundo Semestre 2003
El...
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.
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 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 es de 45, 20, 30 y 30millones 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 las ciudades. a Hacia Desde Planta 1Planta 2 Planta 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 energ´ e ıa que se debe enviar desde cada planta a cadaciudad, 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 Transporte
8x11 + 6x12 + 10x13 + 9x14 +9x21 + 12x22 + 13x23 + 7x24 +14x31 + 9x32 + 16x33 + 5x34
(Costo de enviarenerg´ 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 este caso se habla de restricciones de oferta o suministro. Como existen tres puntos de oferta o sumistro, existen tresrestricciones: 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 las restricciones que permitan asegurar que se satisfaga la demanda en las cuatro ciudades. As´ las restricciones de demanda para cadapunto 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 de de 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
0 x 11 =
Ciudad 1
45
0
d1 = 45
=
s1 = 35
Planta 1
x 21x12 = 10
=
1 x3
x1
3 =
25
0 x 22 =
= 10
Ciudad 2
d2 = 20
s2 = 50
Planta 2
x 32
x23 = 5
Ciudad 3
0 x 33 =
x
14
d3 = 30
= 0
s3 = 40
Planta 3
x2
4 =
0
x34 = 30
Ciudad 4
d4 = 30
Figura 1.1: Representaci´n gr´fica del problema o a
Departamento de Inform´tica a
2
Universidad Santa Mar´ ıa
Segundo Semestre 2003
El...
Leer documento completo
Regístrate para leer el documento completo.