Sistemas

PROBLEMAS ESPECIALES DE PROGRAMACION LINEAL

1.- Problema del Transporte:

Un problema de transporte trata la distribución de cualquier bien, desde determinados centros de abastecimiento, llamados "orígenes" o “fuentes”, a cualquier grupo de centros de recepción, llamados “destinos”, de tal manera que se minimicen los costos totales de distribución.

En general, en un modelo de transportese cuenta con los siguientes datos:

Nivel de oferta en cada origen y la cantidad de demanda en cada destino.
El costo de transporte unitario desde cada origen a cada destino.

Como sólo se considera una mercancía a distribuir, un destino puede recibir su demanda desde diferentes orígenes, por lo tanto, el objetivo del modelo es el de determinar la cantidad de mercancía que se enviará decada origen a cada destino, tal que se minimice el costo de transporte total, bajo el supuesto que el costo de transporte en una ruta es directamente proporcional al número de unidades transportadas.

Considerando que el origen i (i=1,2,...,m) dispone de si unidades para distribuir a los distintos destinos j y cada destino j (j=1,2,...n) tiene una demanda de dj unidades que recibe desde losorígenes, podemos representar el modelo de transporte como una red de m orígenes y n destinos, siendo cij el costo unitario de transporte entre el origen i y el destino j.

Origen Destino










Si xij es el número de unidades que se distribuyen del origen i al destino j y z el costo total de transporte, entonces la formulación del modelo de un problema detransporte es:

Las restricciones del problema implican que la oferta total de los orígenes, debe ser por lo menos igual a la demanda total . Cuando la oferta total es igual a la demanda total se trata de un problema de transporte equilibrado o balanceado y en este caso las restricciones son igualdades. En general, en la mayoría de los problemas del mundo real esto no se cumple, pero sin embargo,un modelo de transporte siempre puede equilibrarse agregando orígenes o destinos ficticios.

En general, para cualquier problema de transporte, la tabla que resulta de las restricciones tiene la siguiente estructura:









Cualquier problema de programación lineal que se ajuste a esta formulación especial, sin importar su contexto físico, es de tipo de transporte. Si bien aestos problemas se los puede resolver mediante los métodos de resolución de problemas lineales enteros, se han desarrollado algoritmos especiales que son mucho más eficientes que el algoritmo símplex.

Ejemplo: (W. L. Winston, cap. 7) Una empresa tiene tres plantas de generación de energía eléctrica que suministran la energía requerida por cuatro ciudades. La cantidad de energía que puedesuministrar cada planta, la demanda requerida por cada ciudad y los costos para enviar 1 millón de kwh de energía desde una planta a una ciudad, los cuales dependen de la distancia que la energía tiene que viajar, se muestran en la siguiente tabla. Minimizar el costo para satisfacer la demanda máxima de energía de cada ciudad.


DESDE
HACIA

OFERTA
(millones de kwh)

Ciudad 1 ($)
Ciudad 2 ($)Ciudad 3 ($)
Ciudad 4 ($)

Planta 1
8
6
10
9
35
Planta 2
9
12
13
7
50
Planta 3
14
9
16
5
40
DEMANDA
(millones de kwh)
45
20
30
30


Solución:
Como se debe determinar cuánta energía hay que mandar de cada planta hacia cada ciudad, se define como variable de decisión:

xij = cantidad de kwh (en millones) producidos en la planta i y enviados a la ciudad j

Comola oferta total y la demanda total son iguales, se trata de un problema de transporte balanceado.


s. a:
Restricciones de oferta


Restricciones de demanda


Restricciones lógicas


La solución óptima calculada utilizando STORM (transpo1) es:

z = 1020 , x12 = 10, x13 = 25, x21 = 45, x23 = 5, x32 = 10, x34 = 30



La columna etiquetada cell cost...