4.4 Seleccion de Ruta [Autoguardado]

7/26/2019 4.4 Seleccion de Ruta [Autoguardado]

1/54

4.4. Seleccin de rutas de trans


2/54

Dado que los costos de transportacin normalmente se hallatercio y dos tercios de los costos logsticos totales, mejorar la

mediante la mxima utilizacin del equipo de transportacinpersonal es una preocupacin importante.

Ballou, R. (2004) Logstica. Administracin de la cadena de suministro. Quinta edicin. Mxico: PEducacin. Pg. 225


3/54

Un problema frecuente en la tomade decisiones es reducir los costos de

transportacin y mejorar el servicio alcliente encontrando los mejorescaminos que debera seguir unvehculo en una red de carreteras,lneas ferroviarias, lneas deembarque o rutas de navegacin

area que minimicen el tiempo o ladistancia.

Ballou, R. (2004) Logstica. Administracin de la cadena de suministro. Quinta edicin. MxEducacin. Pg. 225


4/54

Mtodos de

transporte


5/54

El origen de los mtodos de transporte data del ao 19

que F.L. Hitchocock present un estudio titulado Ladistribun producto desde diversos orgenes a numerosas localidacree que esta exposicin fue la primera contribucin impara la resolucin de los problemas de transporte. En 19Koopmans present un estudio, sin ninguna relacin cHitchcock, al que llamo Utilizacin ptima del sist

transporte. Ambas aportaciones contribuyeron al desarromtodos de transporte que implican un nmero dado de fuembarque y otro de puntos de destino.

Thierauf, R. (1993) Introduccin a la Investigacin de Operaciones. Mxico: Limusa. P


6/54

Aunque los mtodos de transporte determinan patronesde embarque, por medio de stos se pueden resolver

problemas que no tienen nada que ver con el tra

Asignacin demquinas: ofrece la forma de asignar mquirdenes de fbrica ms adecuadas para las respectivas mtiende a minimizar los costos y/o a cumplir con fechas de

especficas.

Asignacin de trabajadores: optimiza la distribucin trabajadores con base en puntuaciones de prueba, de manerasigne el individuo adecuado al trabajo correcto.



7/54

Un problema de transporte incluye m fuentes (fbricas), a cadlas cuales corresponde una disponibilidad dea(i= 1,2,,m) unun producto homogneo y n destinos (bodegas), cada uno de requierenb(j=1,2,,n) unidades de este productos. Los nmerson enteros positivos. El costo

cde transportar una unidad de

de la fuente i al destino j se da para cada i y para cada j. El odesarrollar un programa de transporte que cumpla todas las dempartir del inventario actual y con un costo total de embarque mn

FORMA ESTNDAR

Bronson, R. (1993) Investigacin de Operaciones. Mxico:McGraw Hill. Pg. 68


8/54

Destinos

1 2 3 n Suministro

1

2

. . .. .. .

m Demanda

Orgenes


9/54

Se considera que el suministro y la demanda total son iguale

Bronson, R. (1993) Investigacin de Operaciones. Mxico:McGraw Hill. Pg. 68

=

=

Se garantiza la ecuacin creando ya sea un destino ficticdemanda igual al excedente (exceso, sobrante), si la demanmenor que el suministro total; o un origen ficticio con un igual al faltante, si la demanda total excede al suministro tota


10/54

Sea el nmero (desconocido) de unidades que se embarcaral destino j. Entonces, el modelo matemtico para este p

: =

=

: =

= 1, ,

=

= ( 1, ,

: .Bronson, R. (1993) Investigacin de Operaciones. Mxico:McGraw Hill. Pg. 68


11/54

Una solucin bsica inicial

Prawda, J. (2004) Mtodos y modelos de investigacin de operaciones I: Modelos determiMxico:Limusa. Pg. 263

Cuando un problema de transporte est desbalanceaaadiendo ya sea en orgenes o destinos artificiales, sebalancea y as se satisface la condicin necesaria y suficiepara que el problema tenga solucin.

Una vez que un problema de transporte esta balancease requiere una solucin inicial que sea bsica y factible. varios mecanismos para lograr esta solucin. Se presendos;el mtodo de esquina noroeste (extremo noroccidentael mtodo de Vogel.


12/54


13/54

Esquina Noroeste

Prawda, J. (2004) Mtodos y modelos de investigacin de operaciones I: Modelos determiMxico:Limusa. P . 264

Paso 1. En la posicin (1,1), que es la esquina noroeste de la my de ah el nombre de este mtodo) asgnese el mn (,) la oferta

y de la demanda

.Obviamente, alguna de es

cantidades se convertir en cero.

Paso 2. Sise convierte en cero, psese a la posicin (2,1) y , (-,,). Si por otro lado esel que se convcero en el paso anterior, se pasa a la posicin (1,2) y

(

,,

).

Paso 3. Continese con la misma lgica hasta llegar a la p(m,n). La matriz de flujos que se obtenga ser factible y bsiel problema de transporte.


14/54

Mtodo de Vogel


El mtodo de Vogel proporcionar una solucin inicial bsica ms cercana al punto ptimo.

Paso 1. Constryase una matriz de costos y de flujos asociproblema balanceado y vyase al paso 3.

Paso 2.Utilcese el remanente (RAE, que queda o sobra) de lade costos y flujos una vez que estos ltimos se hayan asignado.

Paso 3. Se entiende pordiferencia de fila (de columna) a la difque hay entre los dos nmeros ms pequeos que existen en(columna). Calclese todas las diferencias de fila y de columnmatriz de costos.


15/54

Mtodo de Vogel


Paso 4. Seleccinese aquella fila o columna con mayor dife

empates se deciden arbitrariamente.

Paso 5.Localcese el costo ms pequeo en la matriz de cofila o columna seleccionada en el paso anterior. Sea esta .

Paso 6. En la matriz de flujo hgase ( , )posicin(, )se identific en el paso anterior. Hgase la ofea y la demandaigual a .


16/54

Mtodo de Vogel


Paso 7. Si 0, llnese la filaide la matriz de flujos a excepcin de la posicin(,) y elimnese esa fila de consideracin futura. Por otro lado, si 0, llnese la de la matriz de flujos con ceros, a excepcin de la posicielimnese esa columna de cualquier consideracin futura. Repaso 2.


17/54

Una vez que se ha determinado la tabla inicial mediante lde la esquina noroeste o mediante algn otro mtodo de s

inicial, se debe comprobar si la solucin es o no es degen(cantidades a emb

La degeneracin es una condicin en la cual no es evaluar todas las casillas vacas (no usadas), debido a que seun nmero menor de casillas o sea, se llenan menos que requerimientos (renglones y columnas) menos uno. Tambdegeneracin surge por tener demasiadas casillas

La frmula para verificar si hay degeneracin es m+n-1,mes el nmero de renglones ynel de columnas.


Prueba de degeneracin


18/54

Mtodo de Vogel


Paso 7. Si 0, llnese la filaide la matriz de flujos a excepcin de la posicin(,) y elimnese esa fila de consideracin futura. Por otro lado, si 0, llnese la de la matriz de flujos con ceros, a excepcin de la posicielimnese esa columna de cualquier consideracin futura. Repaso 2.


19/54

Paso 1. Balancear el problema original, a fin de que se consig

condicin necesaria y suficiente para obtener una solucin pt

=

=

Algoritmo de transporte

Paso 2. Generar una solucin inicial que sea bsica y factibsea utilizando el mtodo de Vogel o de la esquina noro



20/54

Paso 3. Constryase una matriz de costo ij asociada a la solbsica factible que se tenga, d

ij Cij, si Xij est en la base,ij 0, si Xij no est en la base.


Paso 4. Con esta matriz de costos, calclese el valor de todavariables duales, i=1, , m y , j=1, , n, utilizando la frmula

+ = 0, i = 1, , m; j = 1, , n.

Prawda, J. (2004) Mtodos y modelos de investigacin de operaciones I: Modelos determiMxico:Limusa. P . 271-272


21/54


Paso 4. Como hay m+n variables ( m variables, y n variablesolamente m+n-1 ecuaciones+ = 0, existe un gralibertad. Esto equivale a darle un valor arbitrario (se recomievalor cero) a cualquiera de las variables duales y as qued

resolver un sistema m+n-1 ecuaciones con m+n-1 variables.

Paso 5. Los parmetros se calculan por medioecuacin, +. Como se estn usando las regminimizacin, si 0 para toda i y j, la solucin actual es pticaso contrario, laXij correspondiente a la ms positiva ent

base.



22/54


Paso 5. Para guardar consistencia con la programacin l

utilizan las reglas de maximizacin. En este caso

(+)

Si todas las 0, la solucin actual es ptima. Econtrario, se introduce a la base la Xij correspondiente a lams negativa.

Prawda, J. (2004) Mtodos y modelos de investigacin de operaciones I: Modelos determiMxico:Limusa. Pg. 272


23/54


Paso 6. Si la variable Xij entra a la base con un cierto valo,la oferta y la demanda se desequilibrarn en un vamenos de que exista, un mecanismo de compensacin. Asealar cul es ste, se ilustra el desequilibrio menConsidrese que la solucin bsica factible actual es la que a continuacin:



24/54

Prawda, J. (2004) Mtodos y modelos de investigacin de operaciones I: Modelos determi

Mxico:Limusa. Pg. 272

1 j n Ofer

1

. .

. .

. .

i

. .

. .m

Demanda


25/54


Mxico:Limusa. Pg. 272-273

La solucin es bsica, porque m + n 1 = 5(una suposicin),factible porque:

+ = =

+ =

+

=

= + = 0, 0, 0, 0, 0

1

j

n 1 .

.

i .

. m

Demanda Flujos


26/54



Se supone que

es la ms negativa ypor consiguiente, entra a la nueva basecon un determinadovalor 0.

Tabularmente se tienelo siguiente:

1 j

1 . .

i .

.

m Demanda


27/54



Si >0, 0, esta nueva solucin ya no es bsica, porque hay m+ncaso) elementos en la base y no m+n-1, como deberan haber. tampoco es factible, porque por un lado la oferta del origenies mde hecho es

+ + >

Y por el otro lado, la demanda del destinoj, es

+ + >


28/54


Mxico:Limusa. Pg. 273 - 274

Existe un desequilibrio

que nicamente puededesaparecer si se resta ysuma unidades enciertas partes de la matrizde flujos. Un pequeoanlisis permite construir

un circuito, tal como semuestra a continuacin,

+

-

- 1 j

1

. .

i .

.

m Demanda


29/54



en donde en ciertas partes se ha sumado el valor de y en otrasrestado. Lo importante es que se ha regenerado la factibilidad, mlo bsico. En efecto

+ + + + + + +

+ + + ,

+

-

-1 j

1 .

.

i .

.

m Demanda


30/54



que son iguales a las condiciones vistas anteriormente (factibilidauna nueva solucin sea bsica, es decir, que solamente exi

elementos en la base, debe ser lo suficientemente grande como el valor de uno o varios flujos bsicos a cero. Si se analiza la matrizve queaumenta, los siguientes flujos disminuyen:

, , Por lo tanto,

, , El circuito formado anteriormente y el valor de , corresp

ecuaciones (3.9) y (3.10) respectivamente. Este circuito esnico.


31/54



Por lo tanto, elPaso 6se puede resumir como sigue:

6-a) Construir uncircuito nicoque contiene a la variableque ebase.6-b)= ,dondees el mnimo de todos los vectores bsicos e

que disminuyen su valor a la medida queaumenta.

Regrese alPaso 3con esta nueva solucin.

EJEMPLO


32/54



Resuelva el problema de transporte que tiene 3 orgenes con c40, 60 y 90 unidades respectivamente; 5 destinos con demandas de40 y 60 unidades respectivamente y los costos unitarios dados entabla:

EJEMPLO

1 2 3 4 5 Ofe

1 20 19 14 21 16 4

2 15 20 13 19 16 6

3 18 15 18 20 no surte 9

Demanda 30 40 70 40 60

Or

genes

Destinos

Costos

EJEMPLO


33/54



Por razones fsicas el origen 3 no puede surtir al destino 5.Solucin. Primero, como el origen 3 no surte al destino 5, se haceen queMes un nmero positivo muy grande.

EJEMPLO

1 2 3 4 5 Ofe

1 20 19 14 21 16 4

2 15 20 13 19 16 6

3 18 15 18 20 M 9

Demanda 30 40 70 40 60

Or

genes

Destinos

Costos


34/54



Paso 1.

El problema esta desbalanceado, puesto que la oferta total esdemanda total en 50 unidades. En efecto

= 190


35/54

1 2 3 4 5 Of

1 20 19 14 21 16

2 15 20 13 19 16

3 18 15 18 20 M

0 0 0 0 0 Demanda 30 40 70 40 60



Destinos

Costos

Orgenes

Origen artif icial


36/54



Paso 2.

Utilizando elmtodo de Vogelse obtiene la siguiente solucin bsica con costo total de $ 3,010.

1 2 3 4 5 O

1 40

2 30 20 10

3 40 50

4 40 10

Demanda 30 40 70 40 60

Destinos

Or

genes

Flujos


37/54



Paso 3.

Se construye una matriz decostos ijdonde 16 15 15 18 13 0 16 0,

el resto de las 0. Se asocialas variables duales con losorgenes ( 1, , 4) y las ( 1, , 5)con los destinos.

1 2 3 4

1

2 15 13

3 15 18

4 0

Demanda

Destinos

Orgenes

Costos


38/54



Paso 4.

Dndole a un valor arbitrario de cero, se pueden calcular lo, .

+ = 0 15 0 15 13 0 13 16 0 16

Conocidos, se pueden calcular, . En efecto, 16 16 0 0 16 16 18 13 5

Paso 4.


39/54



De manera similar, se obtienen los valores de las variables duales

0 16 16 15 5 10

Ya que se dispone de un grado de libertad, se escogiarbitrardio un valor arbitrario. En este caso 0.

En resumen

0 15 0 10 5 13 16 16

16


40/54



Paso 5.

Utilizando la frmula (+ ) para toda i, j quebase se obtienen los indicadores en optimidad.

20 (0+15)= 5 18 (5+15)= -2 19 (0+10)= 9 20 (5+16)= -1 14 (0+13)= 1 M (5+16)= M 21 (0+16)= 5 0 (-16+15)= 1

20

(0+10)= 10

0

(-16+10)= 6

19 (0+16)= 3 0 (-16+13)= 3

Como -2 < 0 es la ms negativa, entra a la base.


41/54



Paso 6.

El circuito correspondiente a las ecuaciones (3.9) queda rtabularmente a continuacin.

1 2 3 4 5 Ofe

1 40 4

2 30 20 10 6

3 40 50 9

4 40 10 5

Demanda 30 40 70 40 60

-

-

+

Destinos

Orgenes

Flujos


42/54



El valor de proviene del mnimo de aquellos flujos que diaumentar,es decir

30,50 30Por lo tanto, la nueva solucin es:

1 2 3 4 5 Oferta

1 40 40

2 50 10 60

3 30 40 20 904 40 10 50

Demanda 30 40 70 40 60

Destinos

Orgenes

Flujos


43/54



El costo asociado a esta nueva solucin es

$3,010 + ( ) $,3010 + 30 2

$2,950.

Se regresa al paso 3.


44/54



Paso 3 y 4.

Tabularmente serepresenta la nueva matrizcon elementos

y a los

valores dualesy.

1 2 3 4

1

2 13

3 18 15 18

4 0

Demanda

Destinos

Orgenes

Costos


45/54

Dndole aun valor arbitrario de cero, se pueden calcuvalores de, .

+ = 0 18 0 18 15 0 15 18 0 18

Conocidos, se puede calcular. En efecto, 13 18 5


46/54



De manera similar, se obtienen los valores de las variables duales 16 5 21 16 21 5

0 21 21 0 (21) 21Ya que se dispone de un grado de libertad, se escogiarbitrar

dio un valor arbitrario. En este caso 0.En resumen

5 18 5 15 0 18 21 21

21


47/54



Paso 5.

Utilizando la frmula (+ ) para toda i, j quebase se obtienen los indicadores en optimidad.

20 (-5+18)= 7 19 (-5+21) 19 (-5+15)= 9 20 (0+21)= 14 (-5+18)= 1 M (0+21)= 21 (-5+21)= 5 0 (-21+18)=

1

5 (-5+18)= 2

0

(-21+15)=

20 (-5+15)= 10 0 (-21+18)=

Como -1 < 0 es la ms negativa, entra a la base.

P 6


48/54



Paso 6.

El circuito correspondiente a las ecuaciones (3.9) queda rtabularmente a continuacin.

1 2 3 4 5 Ofe

1 40 4

2 50 10 6

3 30 40 20 9

4 40 10 5

Demanda 30 40 70 40 60

-

- +

Destinos

Orgenes

Flujos


49/54



El valor de proviene del mnimo de aquellos flujos que diaumentar,es decir

10,20 10Por lo tanto, la nueva solucin es:

1 2 3 4 5 Oferta

1 40 40

2 60 60

3 30 40 10 10 904 40 10 50

Demanda 30 40 70 40 60

Destinos

Orgenes

Flujos


50/54



El costo asociado a esta nueva solucin es

$2,950 + ( ) $2,950 + 10 1

$2,940.

Se regresa al paso 3.


51/54



Paso 3 y 4.

Tabularmente serepresenta la nueva matrizcon elementos y a losvalores dualesy.

1 2 3 4

1

2 13

3 18 15 18 20

4 0

Demanda

Destinos

Orgenes

Costos

=18 =15 =18 =

Paso 5.


52/54



Tabularmente se representa a la matriz con los elementos (+).

1 2 3 4 5 O

1 6 8 0 5

2 2 10 4 1

3 M-20

4 2 5 2

Demanda 30 40 70 40 60

Destinos

Orgenes

Costos


53/54



Como todas las para iyjque no estn en la bpositivas, la solucin anterior es ptima. En resumen, la sptima es:

a) 40, 60, 30, 40, 10, 20, 10,

b) las restantesson ceros,c) el costo mnimo de transportes es de $2,940.

La solucin ptima se ilustra a continuacin: Destin


54/54



1

2

3

4

1

2

3

4

5

Oferta Orgenes

40

90

50

60

40

60

30

40

10

10

30

20

Documents

4.4 Seleccion de Ruta [Autoguardado]