Programación Lineal de Transporte.

Programación Lineal de Transporte.

Como formular un problema de Transporte

Para comenzar el análisis de los problemas de transporte, se formula un modelo de programación lineal de la situación.

Ejemplo 1:

Powerco tiene 3 centrales eléctricas que cubren 4 ciudades. Cada planta suministra las siguientes cantidades de kilowatts-hora(kwh).

Planta 1  35 millones de kwh

Planta 2  50 millones de kwh

Planta 3  40 millones de kwh

Las demandas de potencia pico de las 4 ciudades suceden a la misma hora, son estas:

Ciudad 1  45 millones de kwh

Ciudad 2  20 millones de kwh

Ciudad 3  30 millones de kwh

Ciudad 4  30 millones de kwh

Los costos por enviar un millón de kwh de electricidad de cada planta a la ciudad dependen de la distancia que debe recorrer la electricidad.

De Ciudad 1 Ciudad 2 Ciudad 3 Ciudad 4 Suministros

(mills kwh)

Planta 1 $8 $6 $10 $9 35

Planta 2 $9 $12 $13 $7 50

Planta 3 $14 $9 $16 $5 40

Demanda

(mills kwh) 45 20 30 30

Para formular el problema definimos una variable para cada decisión que debe tomar Powerco.

• Se define i = 1, 2, 3 y j = 1, 2, 3, 4

• La variable i son las plantas y j las ciudades

• Xij=Número de millones de kwh producidos en la planta i y enviados a la ciudad j.

Lo anterior se traduce así:

8x₁₁ + 6x₁₂ + 10x₁₃ + 9x₁₄ = Costo de enviar potencia desde planta 1

9x₂₁ + 12x₂₂ + 13x₂₃ + 7x₂₄ = Costo de enviar potencia desde planta 2

14x₃₁ + 9x₃₂ + 16x₃₃ + 5x₃₄ = Costo de enviar potencia desde planta 3

Powerco tiene 2 tipos de restricciones

-La potencia total suministrada por cada planta no puede exceder la capacidad de la planta.

• Por ejemplo, la potencia total enviada de la planta 1 no puede exceder los 35 millones.

-Asegurarse que cada ciudad recibirá la suficiente potencia para satisfacer su demanda pico.

• Por ejemplo, la ciudad 1 debe recibir AL MENOS 45 millones de kwh

La solución óptima para este problema es: z= 1020.

8x₁₁ + 6x₁₂ + 10x₁₃ + 9x₁₄ = 8*0+6*10+10*25+9*0 = 310

9x₂₁ + 12x₂₂ + 13x₂₃ + 7x₂₄ = 9*45+12*0+13*5+7*0 = 470

14x₃₁ + 9x₃₂ + 16x₃₃ + 5x₃₄ = 14*0+9*10+16*0+5*30 = + 240

1020

Manejo de la Escasez

Se cuenta con 2 depósitos para suministrar agua a 3 ciudades. Cada depósito puede suministrar hasta 50 millones de galones por día. A cada ciudad le gustaría recibir 40 millones de galones por día. Por cada millón de galones por día sin satisfacer, hay una multa.

• Ciudad 1  $20 de multa

• Cuidad 2  $22 de multa

• Ciudad 3  $23 de multa

En resumen:

• Suministro: 50 + 50 = 100 mill de galones diarios

• Demanda: 40 + 40 + 40 = 120 mill de galones

Costos de envío

De Ciudad 1 Ciudad 2 Ciudad 3

Depósito 1 $7 $8 $10

Depósito 2 $9 $7 $8

Para equilibrar el problema se suma un punto de suministro ficticio que tiene un suministro de 120 – 100 = 20 millones de galones por día. La demanda de la ciudad 1 tendrá un déficit de 20 millones de galones diarios.

Problema de Transporte equilibrado

Método de la Esquina Noroeste

El método de la esquina Noroeste es un algoritmo heurístico capaz de solucionar problemas de transporte o distribución mediante la consecución de una solución básica inicial que satisfaga todas las restricciones existentes sin que esto implique que se alcance el costo óptimo total.

Este método tiene como ventaja frente a sus similares la rapidez de su ejecución, y es utilizado con mayor frecuencia en ejercicios donde el número de fuentes y destinos sea muy elevado. Su nombre se debe al génesis del algoritmo, el cual inicia en la ruta, celda o esquina Noroeste. Es común encontrar gran variedad de métodos que se basen en la misma metodología de la esquina Noroeste, dado que podemos encontrar de igual manera el método e la esquina Noreste, Sureste o Suroeste.

Algoritmo de resolución de la Esquina Noroeste

Se parte por esbozar en forma matricial el problema, es decir, filas que representen fuentes y columnas que representen destinos, luego el algoritmo debe de iniciar en la celda, ruta o esquina Noroeste de la tabla (esquina superior izquierda).

PASO 1:

En la celda seleccionada como esquina Noroeste se debe asignar la máxima cantidad de unidades posibles, cantidad que se ve restringida ya sea por las restricciones de oferta o de demanda. En

...