INVESTIGACION DE OPERACIONES

Just another WordPress.com weblog

2.1 Problema de Transporte abril 9, 2010

 Formulación  del  Problema de  Transporte

Una empresa  energética dispone de tres plantas  de generación  para  satisfacer la demanda eléctrica de cuatro  ciudades.  Las  plantas  1, 2 y 3 pueden  satisfacer 35, 50 y 40 millones  de [kWh] respectivamente. El valor máximo de consumo ocurre  a las 2 PM y es de 45, 20, 30 y 30 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ía. La siguiente tabla muestra  los costos de envío unitario desde cada planta a cada ciudad. Formule un modelo de programcion lineal que permita  minimizar  los costos de satisfaccion de la demanda  maxima  en todas las ciudades.

 

 

En primer  lugar debemos definir las variables  de decisión necesarias  para  representar las posibles decisiones que puede tomar  la empresa energética. En este caso, corresponde  a la cantidad de energí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                                                                                                                                                                                                                                                                        (1.1)

En términos de estas variables,  el costo total  de entregar energía a todas  las ciudades  es:

 

(1.2)

 

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. Como existen  tres puntos  de oferta  o sumistro,  existen  tres restricciones:

 

(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  cada  punto  de  demanda quedan:

 

(1.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á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  (figura 1.1).

 

 

Figura 1.1: Representación Gráfica del Problema

 

 

 

Formulación General

Un problema  de transporte queda definido por la siguiente  información:

1.    Un conjunto  de m puntos  de oferta.  Cada  punto  de oferta i tiene asociado una oferta si .

2.    Un conjunto  de n puntos  de demanda. Cada  punto  de demanda  j tiene asociada  una demanda dj .

3.    Cada unidad  enviada desde un punto  de oferta i a un punto  de demanda  j tiene un costo unitario de transporte cij

Consideremos:

xij   =  número de unidades  enviadas  desde el punto  de oferta i al punto  de demanda  j                                                                                                                                                                                                                                                                (1.5)

Luego, la formulación general del problema  de transporte queda:

(1.7)

 

(1.8)

 

Resolución  del  Problema de  Transporte

Solución Inicial

Consideremos  un problema  de transporte balanceado  con m puntos  de oferta  y n puntos  de demanda.  De acuerdo  a la formulación vista  anteriormente, el problema  tendrá m + n restricciones  de igualdad.

Para  proceder  a describir  algunos m´etodos para  encontrar una primera  solución inicial, es importante observar  que si un  conjunto  de valores  para  las variables  xij  satisface  todas  las restricciones salvo una,  automáticamente satisface  la otra  restricción. Por ejemplo consideremos que en el ejemplo anterior  se sabe que los valores de las varibles  satisfacen  todas  las restricciones,  salvo la primera  restricción de oferta.  Por  lo tanto, los valores de las xij satisfacen  d1 + d2 + d3 + d4  = 125 millones de [kWh] y proveen s2 + s3  = 125 − s1  = 90 millones de [kWh] de las plantas  2 y 3. Por lo tanto, la planta 1 debe proveer 125 − (125 − s1 ) = 35 millones de [kWh], luego los valores de xij también satisfacen  la primera  restricción de oferta.

 En lo sucesivo, para resolver el problema  de transporte, consideraremos  que se satisfacen m + n − 1 restricciones,  omitiendo  alguna.  En forma arbitraria, omitiremos  la primera  restricción de oferta. Evidentemente, cualquier colección de m + n − 1 variables no necesariamente es una solución factible para el problema.

Consideremos  el siguiente  problema  de transporte (omitiremos  los costos unitarios):

En  forma  matricial, las restricciones  del problema  de transporte balanceado  anterior  puede  ser escrito de la siguiente  forma:

 

Eliminando  la primera  restricción de oferta el sistema  se reduce a:

 

Como el sistema anterior  tiene 4 restricciones y 6 variables  posee infinitas soluciones, sin embargo, siempre tendrá como solución al menos 4 variables  no nulas.

Para  obtener  una solución básica factible en forma simple introduciremos el concepto  de loop.

  

Definicion 1  Un orden  secuencial  de al menos cuatro  celdas distintas  se denomina  loop si:

1.    Dos celdas consecutivas  estan  en la misma  columna  o en la misma  fila.

2.    No tiene  tres  celdas consecutivas  en una misma  columna  o en una misma  fila

3.    La última  celda  de  la  secuencia  tiene  una  fila o columna  común  con  la  primera celda  de  la secuencia.

 Las figuras siguientes  muestran algunos tipos de loop en dos tableaux de transporte:

    

                               

 

Las siguientes  figuras  muestran algunos  ejemplos  de secuencias  de celdas que no conforman  un loop, pues no satisfacen  todas  las condiciones.

 

                     

Teorema 1  En un problema de transporte balanceado con m puntos de oferta y n puntos de demanda, las celdas correspondientes a un conjunto  de m + n − 1 variables no contienen  un loop si y solo si las n + m − 1 variables constituyen  una solucion inicial. 

El teorema  anterior  se desprende  del hecho de que en un conjunto  de m + n − 1 celdas no contienen un loop si y solo si las m + n − 1 columnas correspondientes a las celdas son linealmente  independientes.

Los métodos más empleados  para  obtener  soluciones iniciales son:

  • El método de la Esquina  Noroeste. 
  • El método del Costo Mínimo.
  • El método de Vogel.

A continuación revisaremos  sólo el método de la Esquina  Noroeste.

 

 

 

VIDEO SOBRE EL PROBLEMA DE TRANSPORTE

 

 

  

Subtema 2.1.1: Método Esquina Noroeste

 

 

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

 
Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.