• Author / Uploaded
• eraffolecca

Citation preview

E. Raffo Lecca

11 El problema del transporte El presente capítulo está dedicado al problema de transporte. Este es una importante extensión de la programación lineal, con origen económico y físico. El clásico problema de transporte fue planteado y resuelto por F. L. Hitchcock en 1941, con anterioridad a la formulación del concepto de la programación lineal, mucho antes que George Dantzig planteara el método simplex. El problema del transporte se caracteriza por lo siguiente:    

Una cantidad fija en cada nodo de destino, denominada demanda. Una cantidad fija en cada nodo de origen, denominada oferta. El costo de envío desde un origen a un destino, es proporcional a la cantidad enviada. El costo total, la suma de las contribuciones unitarias. El total de la oferta es igual al total de la demanda.

11.1 Introducción al problema del transporte A finales de los años 40, Koopmans desarrolla una tesis doctoral sobre el problema del embarque marítimo en la flota holandesa. En los tiempos napoleónicos el matemático francés Gaspar Monge (1781) describe el problema de abastecimiento en el ejército de Napoleón.

11.1.1

Estructura del problema de transporte

Suponga que se desea enviar cantidades desde orígenes o almacenes a destinos o mercados. Por cada origen i-ésimo, se tiene la oferta ai, i =1,2,..., m, y por cada destino jésimo, la demanda es bj, j =1,2,..., n. Existe un costo de transporte o flete por cada bien que se envía. El costo total del envío es minimizando, en el considerando que se envía las unidades disponibles y se reciben las unidades requeridas. En la figura 11.1 se presenta el problema de la asignación de los puntos o centros de orígenes hacia los centros de destino. El total de la oferta es igual al total de la demanda:

E. Raffo Lecca m

n

 a  b i

i 1

j

j 1

1

1

...

... ...

bj

j

ai i

... ... n m

Figura 11.1 Si el costo de enviar una unidad desde i a j es cij, el problema será determinar unidades de i a j, xij, de acuerdo a sus necesidades y disponibilidades, con la finalidad de minimizar los costos totales. m

n

Min z   cijxij i 1 j 1

sujeto a n

x

ij

 ai , ai  0 , i  1,...,m

j 1 m

x

ij

 bj

, bj  0 , j  1,...,n

i 1

xij  0 i  1,...,m

j  1,...,n

El primer juego de restricciones (uno por cada nodo de origen, totalizando m) efectúa el siguiente balance: Cantidad que se envía en i = oferta en i El segundo juego de restricciones (uno por cada destino, totalizando n) efectúa el balance siguiente: Cantidad que se recibe en j = demanda en j

E. Raffo Lecca La estructura especial de un problema de transporte es como sigue:

x11  x12    x1n x 21  x 22    x 2 n 

= a1 = a2 xm1  xm 2    xmn

x11

+  + x m1

+ x 21 x12

= am = b1

+  + x m2

+ x 22

= b2

 x1n

+  + x mn

+ x2n

= bn

c11x11   c1nx1n  c21x21   c2nx2n   cm1xm1   cmnxmn El modelo de transporte permite una forma tabular, tal como se presenta el problema en la siguiente figura: 1

2

1 c11

...

n

c12 x11

c1n

a1

x12

2 c21

x1n

c22 x21

c2n

a2

x22

x2n

... m cm1

cm2 xm1

b1

cmn

am

xm2 b2

xmn ...

bn

De donde se desprende que cada variable xij se encuentra acotada. 0  xij  min {ai,bj} i, j Un problema de transporte, es de la forma: Min z = cx s.a: Ax = b x0 y para m =2 y n =3, la matriz A es x11 1 1

x12 1

x13 1

x21

x22

x23

1 1

1

1

E. Raffo Lecca 1

1 1

1

y su tablero es : 1 c11

c12

c13

x11

x12

2 c21

c22

c23

x21

x22

10

20 x13 5 x23

5

10

Cuando Ud. empieza una solución factible, desde el origen 1 y el nodo, se tiene que x11 = min {ai , bj}; si a1 < b1 , entonces x11= a1 y a1 es cero, b1 queda como b1 - a1 y viceversa. En cada asignación se elimina una fila o columna; pero al final se eliminan ambos. Entonces se obtiene una solución factible con (m+n-1) valores de xij diferentes de cero. Frecuentemente se tiene más ofertas que demandas; en estos casos la demanda es satisfecha completamente: n

x

ij

 ai , i  1,..., m

j 1

m

x

ij

 bj , j  1,..., n

i 1

De m

n

a  b i

i 1

j

j 1

Se introduce la variable de holgura xi,n+1 , para que n

x

ij

 xi , n  1  ai , i  1,..., m

j 1

y m

n

i 1

j 1

bn  1   ai   bj La cantidad bn+1 es conocida como el exceso de oferta que será asignada a un destino ficticio, con un costo cero. ci,n+1 = 0

,i=1,.....,m

E. Raffo Lecca En el ejemplo, el total de oferta es mayor que el total de demanda, luego se introduce una columna ficticia con demanda igual al exceso de oferta, siendo cero los costos. En la tabla que aparece a continuación es para m =2 y n =3. 1 c11

c12

c13

x11

20

x12

2 c21

c22

x13 c23

x21

5

x22

10

x23

5

1

Quedando como: 1 c11

c12

c13

x11

x12

2 c21

0

c22

c23

x21

x22

10

20

x13

x14 0

5

x23

5

x24

1

9

Considere la otra variante n

x

 ai , i  1,..., m

ij

j 1

m

x

ij

 bj , j  1,..., n

i 1

O sea, el caso en que el total de la oferta es menor que la demanda total: m

n

 a  b i

i 1

j

j 1

Se introduce un origen ficticio con asignaciones oferta ficticia se expresará como : n

m

j 1

i 1

y costos

am  1   bj   ai

Sea el tablero de transporte: 1 c11

c12

c13

x11 2 c21

x12 c22

c23

x21 10

Que origina:

15 x13

x22 5

7 x23

11

= 0 ; la

E. Raffo Lecca 1 c11

c12

c13

x11 2 c21

x12 c22

c23

x21 3 0

x22 0

11.1.2

7 x23

0

x31

4

x32

10

15 x13

5

x33 11

Propiedades de la matriz A

La matriz A posee filas y columnas. La columna corresponde a la ) posición ( . Esta columna es la unión de dos vectores unitarios, el primero es el vector unitario en el conjunto de restricciones para el origen; y el segundo es el vector unitario en el conjunto de restricciones para el destino: ( )= Vectores que pertenecen al espacio

.

En el problema del transporte para el caso de matriz A es de 5 filas por 6 columnas:

(

se tiene que la

)

Sea una submatriz de orden k formada por k columnas y k filas, se encuentra que su determinante es :

|

|

|

|

|

|

Se observa que cada columna de contiene al menos cero, uno o dos unos. Si contiene una o más columnas de ceros entonces | | . Una propiedad de la matriz A es cada menor de A puede tener los valores de . Propiedad conocida como la propiedad unimodular (UM) de la matriz A.

E. Raffo Lecca Si B es una base de A entonces tiene determinante | | es entera.

y la solución

Teorema Sea A una matriz unimodular (UM) y b entero, entonces el poliedro tiene vértices enteros.

* |

+

Una matriz A es una matriz totalmente unimodular (TUM), si está formada de coeficientes enteros y el determinante de toda submatriz de orden k tiene determinante de . En un problema de transporte la solución es entera si las ofertas y destinos son valores enteros.

11.2 Técnicas de solución El proceso de optimización del método Simplex de la PL, se resume en lo siguiente: 1. 2. 3.

Solución inicial. Si los costos reducidos cumplen con el óptimo, entonces la BFS es óptima. En el caso de no cumplir con el óptimo, efectuar un cambio de base y efectuar la prueba.

BFS inicial

Métodos de solución inicial

No Cambiar BFS

Prueba de Optimalidad

Si

BFS óptima

Métodos de solución óptima

Figura 11.2: Algoritmo de transporte El algoritmo Simplex en transporte puede ser apreciado en dos fases:

E. Raffo Lecca  

Solución inicial. Solución óptima.

Existiendo para cada uno de ellos un gran conjunto de algoritmos.

11.2.1 Algoritmos de Solución inicial Existe una variedad de algoritmos que generan una BFS cercana o lejana al óptimo, dependiendo de que el procedimiento haga o no consideración de los costos. Destacan la regla de la esquina del Nor-Oeste, el Método de Aproximación de Vogel, columna mínima, fila mínima, matriz mínima y el Método de Russell. La regla de la "esquina del Nor-Oeste" o NCM (Northwest Corner Method), es un método que no considera la evaluación de costos. Es uno de los clásicos, de fácil aplicación y con una BFS lejana al óptimo. El nombre fue dado por G. Dantzig. Considere el siguiente tablero: 1 c11

c12

c13

x11

x12

2 c21

c22

c23

x21

x22

20

30 x13 5 x23

5

10

Ubicándose en la celda superior izquierda, se debe decidir entre 30 y 20, es decir i=1, j=1 x11 = min {a1, b1} = min {30, 20} = 20 Luego se ha cumplido con la demanda 1 y se pasa a la demanda 2, quedando por asignar una oferta de 10; a1 = a1 - x11 = 10 b1 = b1 - x11 = 0 1 c11

c12

c13

10

c22

c23

5

10 2 c21 0

i=1, j=2

5

10

E. Raffo Lecca x11 = min {a1, b2} = min {10, 5} =5 a1 = a1 -x21 = 5 b2 = b2 -x21 = 0 1 c11

c12 20

2 c21

c13

5

c23

5

5 c22

0

0

10

Nuevamente se pasa a la siguiente demanda y la oferta es actualizada. x13 = min {a1,b3} = min {5,10} =5 a1 = a1 -x31 = 0 b3 = b3 -x31 = 5 En este caso la demanda restante es 5; pasándose a la siguiente fila. 1 c11

c12

c13

20 2 c21

0

5 c22

5

0

c23 0

5 5

i = 2, j=3 x23 = min {a2,b3} =5 Resultando el tablero de solución inicial 1 c11

c12

c13

20 2 c21

5 c22

30 5

c23

5 5

20

5

10

E. Raffo Lecca I=1, J=1

Si

No

X(I,J)=A(I) A(I)=0, B(J)=B(J)-A(I) I=I+1

X(I,J)=B(J) B(J)=0, A(I)=A(I)-B(J) J=J+1

IF A(I) MoJ>N Si BFS inicial

Regla del Nor-Oeste

Figura 11.3: Regla NCM En todo el proceso de la regla NCM, no se hace uso de los costos. Evaluando z, se tiene, n

z   cijxij  90 i, j

xij 20 5 5 5

cij 3 1 2 3

xijcij 60 5 10 15 90

La regla de aproximación de Vogel o VAM (Vogel Aproximation Method) hace énfasis en los costos, incidiendo en aquellas celdas cuyos costos son muy diferenciados con respecto a sus inmediatos adyacentes. Con ese fin trata de minimizar el costo penal más grande con la finalidad de evitar su ocurrencia. Sea el modelo de transporte 1 3

2

1

10

2 4

2

1

5

3 1

2

2

15

10

15

5

E. Raffo Lecca La diferencia de costos entre el menor y su inmediato sucesor se encuentra en cada fila y columna. 1 3

2

1

2-1

2 4

2

1

2-1

2

2

2-1

2-2

1-1

3 1 * 3-1

Escoger en la fila o columna con mayor valor de diferencia y asignar en la celda de menor costo entre: { } 1 3

2

1

2 4

2

1

2

2

3 1

15

x31 10

Para el caso se elimina la columna 1 y se actualiza la fila 3. Se repite el proceso hasta encontrar (m +n - 1) variables: 1 3

2

1

2 4

2

1

3 1

2

2

2-2

1-1

x13

2-1 2-1 2-2

10

1 3

2

1 5

2 4

2

3 1

2

5

5

1 5

5 2

5

5

5

15 1 3

2

1

10

5 2 4

2

5 1

5

2

15

5 3 1

2 10 10

5 15

5

E. Raffo Lecca La solución inicial tiene z = 45. Para cada fila y columna calcular el costo penal de no incurrir en una asignación. En la fila o columna con el mayor costo penal, localizar la celda de menor costo: c(p, q)

Si

No

X(p, q)=A(p) A(p)=0, B(q)=B(q)-A(p)

X(p, q)=B(q) B(q)=0, A(p)=A(p)-B(q)

IF A(p) 0  Suponga la solución 1 3

2

1

10

5 2 4

5 2

1

5

2

15

5 3 1

2 5 10

10 15

5

Para las variables básicas se cumple que: u1 + v1 = c11 u1 + v3 = c13 u2 + v2 = c22 u3 + v1 = c31 u3 + v2 = c32 Haciendo que algún ui o vj sea igual a una cantidad, para solucionar que existen más incógnitas que ecuaciones se tiene: u1 = 0

entonces v1 = c11 = 3

v3 =c13 entonces v3 = 1 u3 + v1 = c31 entonces u3 = c31 - v1 = -2

E. Raffo Lecca u3 + v2 = c32 entonces v2 = c31 - u3 = 4 u2 + v2 = c22 entonces u2 = c22 - v2 = -2 Luego: z11 -c12 = u1 + v2 -c12 =0+4-2 =2 z21 - c21 = u2 + v1 - c21 = -2 + 3- 4 = -3 z23 - c23 = u2 + v3 - c23 = -2 + 1 - 1 = -2 z33 - c33 = u3 + v3 - c33 = -2 + 1 - 2 = -3 Variable de entrada x12; tal como ocurre con la aplicación del algoritmo del "cruce del arroyo". El nombre de método de los multiplicadores, se debe George B. Dantzig quién utilizó el nombre de multiplicadores Simplex, para denominar a las variables duales, de allí que en algunas bibliografías aparezcan como el método U-V (desde las variables duales ui , vj) o el método Simplex para transporte. Al asignar ui a la variable dual asociada a la restricción de origen i y vj, a la variable dual relativa a la restricción de destino j, se encuentra que al existir una ecuación redundante, cualquier ecuación puede ser considerada como tal; por tanto, se puede asignar un valor arbitrario a uno de los multiplicadores Simplex. Aquí se sugiere que: u1 = 0 El problema dual del problema de transporte es: m

n

i 1

j 1

max z   aiui   bjvj sujeto a ui  vj  cij ui, vj son irrestrictas

E. Raffo Lecca El siguiente teorema que viene a continuación, da una nueva luz con respecto a las variables duales. Teorema Cuando los costos cij son enteros y uno de los multiplicadores es un valor entero, todos los multiplicadores Simplex serán enteros.

11.4 Aplicaciones en transporte En la presente sección se presenta el uso del problema del transporte a algunas aplicaciones prácticas que se encuentran en la vida real. Una de ellas es el denominado transporte al tiempo [PRS76] y la otra es el problema del proveedor o caterer problem.

11.4.1

Transporte al tiempo

El departamento de producción se encuentra planeando la cantidad de unidades a producir en cada de uno de los siguientes cuatro trimestres. En cada trimestre se conoce la capacidad de producción , como la demanda respectiva . Si se incurre en un costo unitario de producción de unidades monetarias; y se permite dejar inventarios a un costo por unidad por trimestre. ¿Cuál es el plan de producción que minimice los costos totales de producción inventario? El problema visto como un transporte, posee orígenes el tiempo cuando se produce con sus capacidades de producción; y posee destinos el tiempo cuando se entrega para cumplir con la demanda o requerimientos. Por cada unidad que se deja en inventario a un trimestre se carga a los costos de producción el costo de inventario . Si se deja el inventario a dos trimestres, se carga el costo de ; y así sucesivamente. 1 c1

c1+h

c1+2h

c1+3h

P1

2

c2

c2+h

c2+2h

P2

c3

c3+h

P3

c4

P4

3 4 D1

D2

D3

D4

Figura 11.7: Tablero Simplex para el transporte al tiempo En la figura 11.7, se presenta el tablero Simplex de transporte para este problema, denominado transporte al tiempo. Se observa que las celdas oscurecidas significan asignación prohibida (un costo muy grande, infinito). Toda vez que la demanda no puede ser diferida. Esto significa por ejemplo, que si necesitaba en el trimestre del verano, no puede entregarlo en el trimestre del invierno.

E. Raffo Lecca Los datos referentes a la demanda, costo de producción por unidad, costo de inventario y capacidad de producción, se presentan en la tabla 11.1. Costo Costo Capacidad inventario Producción Demanda de ($/unid($/unidad) producción trimestre) 6 30 1 50 7 60 1 50 7 40 1 50 9 60 1 50

Trimestre 1 2 3 4

Tabla 11.1: Datos de producción 1 6

6+1

6+2

6+3

50

2

7

7+1

7+2

50

7

7+1

50

9

50

3 4 30

60

40

60

Figura 11.8: Tablero Simplex para el problema Como el transporte no está balanceado porque el total demandas es menor que el total de las capacidades de producción, se introduce una columna ficticia, con costos ceros para las variables de holgura. La columna tiene una demanda ficticia de 10, que es la cantidad del desbalance. 1 6

7

8

9

0

50

2

7

8

9

0

50

7

8

0

50

9

0

50

3 4 30

60

40

60

10

Figura 11.9: Tablero Simplex balanceado Para la BFS inicial se ha utilizado el método de la matriz mínima. La secuencia de asignaciones ha sido la siguiente: ( (

) )

E. Raffo Lecca ( ) ( ) (Se eliminan las dos, existe degeneración) ( 1 6 30 2

7

)

8

9

8

9

10 7

0 10 0

50

0

50

0

50

50

50 3

7

8 40

4

10 9 50

30

60

40

60

10

Aplicando los multiplicadores, se encuentra que todos los costos reducidos para las celdas no básicas tienen valor no positivo: óptimo.

1

30 1

10

50 2

2

40

3

3 10 50 4

4

Figura 11.10: Solución óptima

11.4.2

El problema del proveedor

El problema del proveedor o The Caterer Problem, es un famoso problema desde los anales de la literatura en Investigación de Operaciones, apareciendo en [JAC54], [DAN63], [HAD62] y otros. Los textos que aparecen en esta sección, han sido tomados mayormente desde Raffo Lecca [RAF99].

E. Raffo Lecca Un proveedor tiene un contrato para una serie de de almuerzos que se darán en un exclusivo club de Nueva York. Existen n almuerzos, uno por cada día en los n sucesivos días. El proveedor o caterer, deberá comprar servilletas especiales para esos almuerzos, porque el club tiene registrado un tipo especial de servilletas. En un día se necesitarán servilletas. Dos tipos de lavados de servilletas están disponibles para el caterer. El servicio regular toma p días (si se envía al fin del día k, este puede ser usado otra vez en el día ) y los costos son b centavos por servilletas. Un servicio rápido toma días a un costo centavos por servilleta. Las servilletas nuevas cuestan a centavos cada una. El caterer busca minimizar los costos asociados en comprar y lavar servilletas. El problema del proveedor o está asociado con la decisión de cuántas servilletas comprar y determinar cuántas enviar a los servicios regulares y rápidos cada día.

Compra 0

1

2

3

4

-D1

-D2

-D3

-D4

5

Figura 11.11: Situación del proveedor En la figura 11.11 se presenta la situación del proveedor para periodos, con los tiempos de servicios regular y rápido . Se asume que se puede comprar servilletas en una cantidad igual a la demanda, con tal fin se ha dispuesto del nodo cero; y del mismo modo el nodo , el quinto es un nodo ficticio que se utiliza para asignar las servilletas nuevas que no serán usadas porque el reciclaje es más barato. 1

2

3

4

5

0 1

75 0

15

E. Raffo Lecca 2

0

10

3

30

4

20 15

10

30

20

75

La solución óptima es comprar 15, 10 y 5 para los tres primeros días respectivamente. En la tabla 12.2, se presenta la gestión completa para el proveedor. También ver la implementación usando LINGO. 1

2

3

4

5

0

75 15

10

5

45

1

0

15

0

10

15 2 10 3

30 20

10

4

20 20 15

10

30

Día

Nuevas

1 2 3 4

15 10 5 0

20

Lavandería Rápido Regular 0 15 10 0 20 0 0 0

Tabla 11.2: Gestión del proveedor Implementación ! PROBLEMA DE TRANSPORTE; ! CATERER; ! E. RAFFO LECCA; SETS: ORIGEN/1..5/:OFERTA; DESTINO/1..5/:DEMANDA; TABLERO(ORIGEN,DESTINO):X,COSTO; ENDSETS DATA: OFERTA =75 15 10 30 20; DEMANDA=15 10 30 20 75; COSTO=4 4 4 4 0 100 2 1 1 0 100 100 2 1 0

75

E. Raffo Lecca 100 100 100 2 0 100 100 100 100 0; ENDDATA ! FUNCION OBJETIVO; MIN=@SUM(TABLERO:X*COSTO); ! RESTRICCION DE ORIGEN; @FOR(ORIGEN(I): @SUM(DESTINO(J):X(I,J))=OFERTA(I); ); ! RESTRICCION DE DESTINO; @FOR(DESTINO(J): @SUM(ORIGEN(I):X(I,J))=DEMANDA(J); );

[email protected]