1

El Problema de

Transporte

INVESTIGACIÓN DE OPERACIONES I

Maestro

Ing. Julio Rito Vargas Avilés Julio 2012

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

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.

7

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 Prod. igual a la Dda.

8

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 D Cap. de Prod. mayor a la Dda.

9

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 D Cap. de Prod. menor a la Dda.

10

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:

1 2 3 4

1 10 0 20 11

2 12 7 9 20

3 0 4 16 18

11

Procedimiento

Para trabajar se utiliza la siguiente tabla:

1 2 ... m Oi ui

1 h11 c11 h12 c12

... h1m c1m

O1 u1 x11 x12 x1m

2 h21 c21 h22 c22

... h2m c2m

O2 u2 x21 x22 x2m

... ... ... ... ... ...

n hn1 cn1 hn2 cn2

... hnm cnm

On un xn1 xn2 xnm

Dj D1 D2 ... Dm

vj v1 v2 ... vm

12

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 3 posibilidades:

• Solución por “tanteo”.

• Método de la esquina Noroeste.

• Método de Vogel.

•

13

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.

14

Método

de la esquina Noroeste

Ejemplo:

1 2 3 4 O

1 10 0 20 11

15000 5000 10000 - -

2 12 7 9 20

25000 - 5000 15000 5000

3 0 4 16 18

5000 - - - 5000

D 5000 15000 15000 10000 C=410

15

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:

16

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

17

Método

de Vogel

Este método si considera los costos, por tanto entrega una mejor solución factible inicial que la esquina noroeste. Consiste en: para cada fila y columna se calcula la diferencia entre el mayor y el menor costo de los casilleros sin marcar. Calculada la diferencia, se selecciona la fila o columna de mayor valor, en donde se le asigna la máxima cantidad factible a su casillero de menor costo que no posea ninguna asignación o marca. Luego, se actualizan las cantidades disponibles. Hecha la asignación, se descuenta la cantidad de forma similar al método de la esquina noroeste. En caso que la fila y columna se hagan cero, se hace lo mismo que en el método anterior.

Método Vogel

18

Este método es heurístico y suele producir una mejor solución inicial que los

métodos anteriores. De hecho, suele producir una solución inicial óptima, o

próxima al nivel óptimo.

Los pasos del procedimiento son los siguientes

1.- Evalúese una penalización para cada renglón (columna) restando el

menor elemento de costo del renglón (columna) del elemento de costo

menor siguiente en el mismo renglón (columna).

2.- Identifíquese el renglón o columna con mayor penalización, rompiendo

empates en forma arbitraria. Asigne el mayor valor posible a las variables

con el costo más bajo del renglón o columna seleccionado. Ajústese la

oferta y la demanda y táchese el renglón o columna satisfecho. Si un

renglón y una columna se satisfacen al mismo tiempo, sólo uno de ellos se

tacha y al renglón (columna) restante se le asigna una oferta (demanda)

cero. Cualquier renglón o columna con oferta o demanda cero no debe

utilizarse para calcular penalizaciones futuras (en el paso 3).

Método de Vogel.

19

3:

a) Si sólo hay un renglón o columna sin tachar, deténgase.

b) si sólo hay un renglón (columna) con oferta (demanda) positiva sin tachar

,determínese las variables básicas del renglón ( columna) a través

del método de costo mínimo.

c) si todos los renglones o columnas sin tachar tiene oferta y demanda

cero asignadas, determínese las variables básicas cero a través del

método de costo mínimo. Deténgase.

d) de lo contrario, calcúlese las penalizaciones de los renglones y columnas

no tachados y después diríjase al paso 2. (Obsérvese que los renglones y

columnas con oferta y demanda cero asignadas no deben utilizarse para

determinar estas penalizaciones).

20

Simplex de Transporte

Paso 1

1 2 3 4 O

1 10 0 20 11

15 5 10 - -

2 12 7 9 20

25 - 5 15 5

3 0 4 16 18

5 - - - 5

D 5 15 15 10

C=410

Se encuentra una solución factible inicial.

21

Simplex de Transporte

Paso 2

1 2 3 4 O ui

1 10 0 20 11

15 u1 5 10 - -

2 12 7 9 20

25 u2 - 5 15 5

3 0 4 16 18

5 u3 - - - 5

D 5 15 15 10

vj v1 v2 v3 v4 C=410

Se determinan los valores de los ui y de los vj . Se plantean n+m-1

ecuaciones con n+m incógnitas, por lo que a una de ellas se le hace valer cero arbitrariamente, y se resuelve el sistema.

u1+v1=10

u1+v2=0

u2+v2=7

u2+v3=9

u2+v4=20

u3+v4=18

22

Simplex de Transporte

Paso 3

1 2 3 4 O ui

1 0 10 0 0 + 20 -2 11

15 -7 5 10 - -

2 -5 12 0 7 0 9 0 20

25 0 - 5 15 5

3 -15 0 -1 4 + 16 0 18

5 -2 - - - 5

D 5 15 15 10

vj 17 7 9 20 C=410

Se determinan los hij para ver la variable que entra. Para todos los

xij se tiene que hij=cij-(ui +vj). Si xij es variable básica, entonces hij = 0 y cij=ui+vj .

u1+v1=10

u1+v2=0

u2+v2=7

u2+v3=9

u2+v4=20

u3+v4=18

23

Simplex de Transporte

Paso 4

1 2 3 4 O ui

1 0 10 0 0 + 20 -2 11

15 -7 5 - 10 + - -

2 -5 12 0 7 0 9 0 20

25 0 - 5 - 15 5 +

3 -15 0 -1 4 + 16 0 18

5 -2 - + - - 5 -

D 5 15 15 10

vj 17 7 9 20 C=410

Entra la variable con el hij más negativo. Si no existe ningún negativo, se llegó al óptimo. Con la variable entrante se forma un circuito.

Entra

24

Simplex de Transporte

Paso 5

1 2 3 4 O ui

1 0 10 0 0 + 20 -2 11

15 -7 5 - 10 + - -

2 -5 12 0 7 0 9 0 20

25 0 - 5 - 15 5 +

3 -15 0 -1 4 + 16 0 18

5 -2 - + - - 5 -

D 5 15 15 10

vj 17 7 9 20

C=410

Se determina la variable que sale de entre los xij que presentan un - . Se escoge el de menor valor, y en caso de empate se elige el de mayor costo. toma el valor del xij que sale.

Sale

=5

25

Simplex de Transporte

Paso 6

1 2 3 4 O ui

1 0 10 0 0 + 20 -2 11

15 -7 0 15 - -

2 -5 12 0 7 0 9 0 20

25 0 - 0 15 10

3 -15 0 -1 4 + 16 0 18

5 -2 5 - - 0

D 5 15 15 10

vj 17 7 9 20

C=335

Se actualizan los valores de los xij sumando o restando en los casos que corresponda y se recalcula el costo. Se vuelve al paso 2.

u1+v1=10

u1+v2=0

u2+v2=7

u2+v3=9

u2+v4=20

u3+v1=0

u3+v4=18

26

Simplex de Transporte

Paso 7

1 2 3 4 O ui

1 0 10 0 0 + 20 + 11

15 0 0 15 - -

2 -5 12 0 7 0 9 0 20

25 7 - 0 15 10

3 0 0 + 4 + 16 + 18

5 -10 5 - -

D 5 15 15 10

vj 10 0 2 20

C=335

Se actualizan los valores de los xij sumando o restando en los casos que corresponda y se recalcula el costo. Se vuelve al paso 2.

u1+v1=10

u1+v2=0

u2+v2=7

u2+v3=9

u2+v4=20

u3+v1=0

27

Método

de Vogel

Solución óptimo:

1 2 3 4 O

1 10 0 20 11

15 - 15 - -

2 12 7 9 20

25 0 - 15 10

3 0 4 16 18

5 5 0 - -

D 5 15 15 10

C=335