1

El Problema del Transporte

Maestro Ing. Julio Rito Vargas Avilés Octubre 2014

ASIGNATURA

PROGRAMACIÓN LINEAL

2

Problema de Transporte

Es un caso especial de problema de programación lineal (PPL), para el cual se ha desarrollado una versión distinta del método Simplex.

3

Principales características Suponga que se dispone de n fábricas y de m centros de consumo, ambos localizados en distintos puntos. Cada fábrica i posee una capacidad de producción Oi, y cada centro de consumo j posee una demanda Dj. El costo de producir una unidad en la fábrica i es de CPi, y el costo de transportar cada unidad desde la fábrica i al centro de consumo j es de CTij. El problema es determinar la cantidad a producir en cada fábrica y las cantidades a transportar, al mínimo costo. Luego xij es la cantidad a producir en la fábrica i para ser llevado al centro de consumo j.

Red de distribución

4

Fábrica

Centro de consumo

RAAN

RAAS

5

RED DE TRANSPORTE

6

D1 D2 D3 D4 D5 D6 D7 D8 OF

F1 10 12 600

F2 12 13 15 350

F3 25 15 17 900

F4 20 15 18 650

DEM 500 300 200 200 150 400 150 600

7

8

Modelo

de Programación Lineal

MIN costo = s.a.

xij 0 con i:1.. n y j:1..m

Se utilizará el siguiente modelo de programación lineal (PPL)

n

1i

m

1j

ijijiji ) xCT x(CP

n

1i

jij D x

m

1j

iij O x

Se satisface toda la Demanda

No se puede producir más allá de la capacidad de la fábrica.

9

Modelo

de Programación Lineal

MIN costo = s.a. xij 0 con i:1.. n y j:1..m

Suponiendo que:

n

1i

m

1j

ijij xC

n

1i

jij D x

m

1j

iij O x

y reemplazando Cij=CPi+CTij queda el siguiente modelo:

n

1i

i

m

1j

j O D Cap. de Producción igual a la Demanda.

10

Modelo

de Programación Lineal

Si

n

1i

m

1j

jiF DOD

entonces se genera un nuevo centro de consumo ficticio. Lo que consuma ese centro no es real, por tanto queda como capacidad de producción ociosa.

n

1i

i

m

1j

j O DCap. de Prod. mayor a la

demanda.

11

Modelo

de Programación Lineal

Si

n

1i

i

m

1j

jF ODO

entonces se genera una nueva fábrica ficticia. Lo que produzca esa fábrica no es real. Por tanto queda como demanda insatisfecha.

n

1i

i

m

1j

j O DCap. de Producción

menor a la Demanda.

12

Modelo

de Programación Lineal Ejemplo: Suponga que se dispone de 3 bodegas con capacidades de 15,000,

25,000 y 5,000 unidades. Por otra parte, se tienen 4 centros de consumo con demandas de 5000, 15,000, 15,000, y 10,000 unidades respectivamente. Encuentre las cantidades óptimas a producir y transportar, tal de minimizar los costos que se muestran a continuación:

C1 C2 C3 C4 Bodega

B1 10 0 20 11 15000

B2 12 7 9 20 25000

B3 0 4 16 18 5000

Dem 5000 15000 15000 10000

13

C1 C2 C3 C4 Bodega

B1 10 X11 0 X12 20 X13 11 X14 15000

B2 12 X21 7 X22 9 X23 20 X24 25000

B3 0 X31 4 X32 16 X33 18 X34 5000

Demanda 5000 15000 15000 10000

14

𝑀𝑖𝑛 𝑧 = 10𝑋11 + 0𝑋12 + 20𝑋13 + 11𝑋14+12𝑋21 + 7𝑋22 + 9𝑋23 + 20𝑋24 +

0𝑋31 + 4𝑋32 + 16𝑋33 + 18𝑋34

Sujeto a:

Ecuaciones de Oferta: 𝑋11 + 𝑋12 + 𝑋13 + 𝑋14=15,000

𝑋21 + 𝑋22 + 𝑋23 + 𝑋24 = 25,000

Bodega 1

Bodega 2

𝑋31 + 𝑋32 + 𝑋33 + 𝑋34= 5,000 Bodega 3

Ecuaciones de Demanda: 𝑋11 + 𝑋21 + 𝑋31=5,000

𝑋12 + 𝑋22 + 𝑋32=15,000

𝑋13 + 𝑋23 + 𝑋33=15,000

𝑋14 + 𝑋24 + 𝑋34=10,000

𝑋𝑖𝑗≥0 i=1..3; j=1..4

Solución usando Módulo de PL de POM-QM

15

Variable

X11

X12

X13

X14

X21

X22

X23

X24

X31

X32

X33

X34

Optimal Value (Z)

Value

0

5000

0

10000

0

10000

15000

0

5000

0

0

0

315,000

Usando Módulo de Transporte POM-QM

16

17

Solución factible inicial

Al igual que en el método Simplex tradicional, el problema de transporte requiere partir de una solución inicial factible. Para ello se necesita asignar las cantidades xij de manera de cumplir con las restricciones. Para ello existen al menos 4 posibilidades:

• Método de la esquina Noroeste.

• Método de Vogel.

• MODELO DE COSTO MÍNIMO

• Método Simplex –Programación Lineal

18

Método de la esquina Noroeste

Este método no considera los costos, por eso puede que su solución quede alejada del óptimo. Consiste en asignar la máxima cantidad factible al casillero superior izquierdo que no posea ninguna asignación o marca. La cantidad a asignar es el mínimo entre la oferta disponible y la demanda en dicho momento. Hecha la asignación, se descuenta la cantidad tanto a la oferta como a la demanda. Con esto, una de las dos quedará en cero (fila o columna). Por tanto se marcan todos los casilleros vacíos de ella.

19

Método de la esquina Noroeste

Ejemplo: C1 C2 C3 C4 O

B1 10 0 20 11

15000 5000 10000 - -

B2 12 7 9 20

25000 - 5000 15000 5000

B3 0 4 16 18

5000 - - - 5000

D 5000 15000 15000 10000 C=410

20

Método de la esquina Noroeste

En caso de que al realizar una asignación simultáneamente ambas se hagan cero (fila y columna), entonces se asigna una nueva variable con valor cero en el casillero de la fila o columna que tenga un menor costo. Se producen entonces 2 asignaciones: Una con el valor mínimo y la otra con cero. Esto se debe a que el sistema debe tener n+m-1 variables básicas definidas. Esto se muestra en el siguiente ejemplo:

21

Método de la esquina Noroeste

Ejemplo 2:

1 2 3 4 5 O

1 7 20 13 5 2

15 15 - - - 0

2 10 15 12 7 10

20 - 20 - 0 -

3 8 11 8 3 9

20 - - 20 - -

4 12 10 12 8 10 10

- - 10 0 -

5 15 15 12 11 10 25

- - - 15 10

D 15 20 30 15 10 C=950

22

Método de Aproximación a Vogel Este método si considera los costos, por tanto entrega una mejor solución factible inicial que la esquina noroeste. El método consiste en la

realización de un algoritmo que consta de 3 pasos fundamentales y 1

más que asegura el ciclo hasta la culminación del método.

PASO 1

Determinar para cada fila y columna una medida de penalización

restando los dos costos menores en filas y columnas.

PASO 2

Escoger la fila o columna con la mayor penalización, es decir que de la

resta realizada en el "Paso 1" se debe escoger el número mayor. En caso

de haber empate, se debe escoger arbitrariamente (a juicio personal).

Método Aproximación a Vogel

23

PASO 3

De la fila o columna de mayor penalización determinada en el paso anterior

debemos de escoger la celda con el menor costo, y en esta asignar la mayor

cantidad posible de unidades. Una vez se realiza este paso una oferta o demanda

quedará satisfecha por ende se tachará la fila o columna, en caso de empate solo

se tachará 1, la restante quedará con oferta o demanda igual a cero (0).

PASO 4: DE CICLO Y EXCEPCIONES

- Si queda sin tachar exactamente una fila o columna con cero oferta o demanda,

detenerse.

- Si queda sin tachar una fila o columna con oferta o demanda positiva, determine

las variables básicas en la fila o columna con el método de costos mínimos,

detenerse.

- Si todas las filas y columnas que no se tacharon tienen cero oferta y demanda,

determine las variables básicas cero por el método del costo mínimo, detenerse.

- Si no se presenta ninguno de los casos anteriores vuelva al paso 1 hasta que las

ofertas y las demandas se hayan agotado.

Ejemplo: Método de Aproximación a Vogel

24

EL PROBLEMA

Una empresa energética colombiana dispone de cuatro

plantas de generación para satisfacer la demanda diaria

eléctrica en cuatro ciudades, Cali, Bogotá, Medellín y

Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80, 30,

60 y 45 millones de KW al día respectivamente. Las

necesidades de las ciudades de Cali, Bogotá, Medellín y

Barranquilla son de 70, 40, 70 y 35 millones de Kw al día

respectivamente.

Los costos asociados al envío de suministro energético

por cada millón de KW entre cada planta y cada ciudad

son los registrados en la siguiente tabla.

25

Formule un modelo de programación lineal que permita satisfacer las

necesidades de todas las ciudades al tiempo que minimice los costos

asociados al transporte.

SOLUCIÓN PASO A PASO

26

Paso 1: determinar las medidas de penalización y consignarlas en la tabla

de costos, tal como se muestra a continuación.

27

Paso 2: escoger la fila o columna con la mayor

penalización:

Paso 3: escoger de esta columna el menor valor, y se le asigna la mayor cantidad

posible de unidades, podemos observar como el menor costo es "2" y que a esa

celda se le pueden asignar como máximo 60 unidades "que es la capacidad de la

planta 3".

28

Dado que la fila de la "Planta 3" ya ha asignado toda su capacidad (60

unidades) esta debe desaparecer.

Se ha llegado al final del ciclo, por ende se repite el proceso

29

Iniciamos una nueva iteración:

30

31

Iniciamos una nueva iteración

32

Iniciamos una nueva iteración

33

Iniciamos una nueva iteración

6

34

Al finalizar esta iteración podemos observar como la tabla queda una fila sin

tachar y con valores positivos, por ende asignamos las variables básicas y

hemos concluido el método.

35

36

Los costos asociados a la distribución son:

Costo = 5*25 + 2*40

+ 7*10 + 3*5 + 1*30

+ 2*60 + 4*45 =125

+ 80 + 70 + 15 + 30

+ 120 + 180 = $620