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 este mismo paso se procede a ajustar la oferta y demanda de la fila y columna afectada, restándole la cantidad asignada a la celda.

PASO 2:

En este paso se procede a eliminar la fila o destino cuya oferta o demanda sea 0 después del "Paso 1", si dado el caso ambas son cero arbitrariamente se elige cual eliminar y la restante se deja con demanda u oferta cero (0) según sea el caso.

PASO 3:

Una vez en este paso existen dos posibilidades, la primera que quede un solo renglón o columna, si este es el caso se ha llegado al final el método, "detenerse".

La segunda es que quede más de un renglón o columna, si este es el caso iniciar nuevamente el "Paso 1".

Método del Costo Mínimo

PASO 1:

De la matriz se elige la ruta (celda) menos costosa (en caso de un empate, este se rompe arbitrariamente) y se le asigna la mayor cantidad de unidades posible, cantidad que se ve restringida ya sea por las restricciones de oferta o de demanda. En este mismo paso se procede a ajustar la oferta y demanda de la fila y columna afectada, restándole la cantidad asignada a la celda.

PASO 2:

En este paso se procede a eliminar la fila o destino cuya oferta o demanda sea 0 después del "Paso 1", si dado el caso ambas son cero arbitrariamente se elige cual eliminar y la restante se deja con demanda u oferta cero (0) según sea el caso.

PASO 3:

Una vez en este paso existen dos posibilidades, la primera que quede un solo renglón o columna, si este es el caso

...