Metodo de Aproximacion de Russell
-
Upload
mateo-patino -
Category
Documents
-
view
3.020 -
download
5
Transcript of Metodo de Aproximacion de Russell
METODO DE APROXIMACION DE RUSSELL
ERICK MATEO PATIO GOMEZRICARDO ANDRES LOZANO MOLINA
UNIVERSIDAD PILOTO DE COLOMBIAFACULTAD DE INGENIERIAPROGRAMA DE SISTEMASGIRARDOT2014METODO DE APROXIMACION DE RUSSELL.
ERICK MATEO PATIO GOMEZRICARDO ANDRES LOZANO MOLINA
Trabajo presentado para optar como nota para el segundo cortede la asignatura INVESTIGACION OPERACIONAL
JOS RAFAEL RINCN ARDILAIngeniero Industrial
UNIVERSIDAD PILOTO DE COLOMBIAFACULTAD DE INGENIERIAPROGRAMA DE SISTEMASGIRARDOT2014CONTENIDO
INTRODUCCION4METODO DE APROXIMACION DE RUSSELL51. PROCEDIMIENTO52. EJEMPLO63. EJERCICIO18CONCLUSIONES23BIBLIOGRAFIA24
INTRODUCCION
El siguiente trabajo tiene como fin familiarizarnos con otro ms de los mtodos de programacin lineal para la solucin inicial de los problemas de transporte, el mtodo de Russell. La caracterstica principal del trabajo es conocer bien el procedimiento, paso a paso para poder desarrollar el mtodo de manera adecuada para al final obtener la solucin ptima.A medida que se va entendiendo el procedimiento de mtodo de Russell, se observa que la cantidad de clculos que toca realizar hace que la solucin final sea muy cercana a la esperada, pero debido a esto, no lo hace el mtodo ms utilizado para la solucin de problemas de transporte, ya que muchas veces se prefiere la simplicidad, a cambio de un poco de cercana con la solucin ptima.
5
METODO DE APROXIMACION DE RUSSELL
Para cada rengln de origen que queda bajo consideracin, debe determinarse el mayor costo unitario de los que quedan en ese rengln. Para cada columna de destino que todava est bajo consideracin, se determina , el mayor costo unitario de los que hay en esa columna. Para cada variable que no haya sido seleccionada en estos renglones o columnas, se calcula se elige la variable con el mayor negativo de . 1. PROCEDIMIENTO
A continuacin se indicara el procedimiento que se debe seguir para encontrar una solucin inicial bsica factible, para un problema de transporte, por el mtodo de Russell.Paso 1: determinar para cada una de las filas de la tabla, el valor , para , en donde representa el valor mximo que toma el coeficiente en la fila Paso 2: determinar para cada una de las filas de la tabla, el valor para en donde representa el valor mximo que toma el coeficiente en la columna Paso 3: determinar para cada una de las celdas de la tabla, el siguiente ndice: Representa un indicador que nos dice que tan buena es la celda si se hiciera una asignacin sobre ella.
Paso 4: seleccionar la celda con el mayor Identificar la fila a la que pertenece esa celda con el subndice y la columna con el subndice . Sobre esta celda se har la asignacin.Sea , la cantidad de producto a asignar en la celda ( Por tanto: Es el valor ?Si la respuesta es si: recalcular el requerimiento que queda por satisfacer en el destino , de la siguiente forma: y elimine la fila Si la respuesta es no: recalcular la oferta disponible del origen , de la siguiente forma: y elimine la columna Paso 5: se tiene ya ( celdas asignadas (variables bsicas)?Si la respuesta es s : pare el procedimiento. Ya se encontr una solucin inicial bsica factibleSi la respuesta es no: vaya al paso 1, y repita el procedimiento. En el paso 1 no se toman en cuenta las filas o columnas que han sido eliminadas.2. EJEMPLO
Se tienen tres distribuidores mayoristas que surten de bicicletas a tres comerciantes detallistas. Las distancias recorridas entre cada uno de los proveedores y cada uno de los comerciantes, as como las capacidades de los almacenes y los consumos de los comerciantes, expresados en lotes de 10 bicicletas cada uno, se detallan en la siguiente tabla.DISTRIBUIDORESCOMERCIANTESDISPONIBILIDAD LOTES/BICI
123
125635
2510755
396420
DEMANDA EN LOTES DE BICICLETA304535110
Tabla 1. Capacidades de los almacenes y consumos de los comerciantesEl problema a resolver consiste en encontrar el numero ptimo de lotes de bicicletas que cada distribuidor debe de suplir a cada uno de los comerciantes, de tal manera que se minimice la distancia total recorrida entre distribuidores y comerciantes.La solucin a este problema se inicia disponiendo la informacin de la siguiente forma: DISTRIBUIDORESCOMERCIANTESOFERTA
12 5
3
1 2
6
35
2 5
6 10
4 7
55
3 9
20
REQUERIMIENTO
304535110
Tabla 2. Asignacin inicial del problemaPaso 1. Clculo de valores para las filasPaso 2. Calculo de los valores para las columnasPaso 3. Calculo de los indicadores de bondad para las celdasCELDA
(1 , 1)
(1 , 2)
(1 , 3)
(2 , 1)
CELDA
(2 , 2)
(2 , 3)
(3 , 1)
(3 , 2)
(3 , 3)
Paso 4. Seleccionar la celda con el mayor Observando los indicadores calculados en el paso anterior, se determina que la celda (2, 1) tiene el mayor . Por lo tanto, esta celda se convierte en la celda de asignacin.La mxima cantidad de lotes de bicicletas que se pueden transportar del distribuidor No. 2 al comerciante No. 1 es la siguiente:
Como , es necesario recalcular la oferta del distribuidor No. 2 de la manera siguiente:
Por lo tanto, se elimina la columna 1, esto quiere decir que est satisfecha toda la demanda del comerciante No. 1 la tabla de asignaciones anterior, se modifica de la siguiente manera:
DISTRIBUIDORESCOMERCIANTESOFERTA
12 5
3
1 2
6
35
2 30 5
6 10
4 7
25
3 9
20
REQUERIMIENTO
--------------4535
Paso 5. Como el nmero de casillas asignadas hasta el momento es 1, y este nmero es menor que , se sigue el proceso de asignacin, repitiendo el procedimiento anterior.Paso 6. Calculo de los valores para las filas
Paso 7. Calculo de los valores para las columnas.
Paso 8. Calculo de los indicadores de bondad para las celdas
CELDA
(1 , 2)
(1 , 3)
(2 , 2)
(2 , 3)
(3 , 2)
(3 , 3)
Paso 9. Seleccionar la celda con el mayor calculados en el paso anterior, se determina que la celda (1, 2) tiene el mayor . Por lo tanto, esta celda se convierte en la celda de asignacin.La mxima cantidad de lotes de bicicletas que se pueden transportar del distribuidor No 1 al comerciante No. 2 es la siguiente:
Como , es necesario recalcular el requerimiento del comerciante No. 2 de la manera siguiente:
Por lo tanto se elimina la fila 1. Esto quiere decir que ya el distribuidor No 1. Dispuso de toda su oferta. La tabla de asignaciones anterior, se modifica de la siguiente manera:DISTRIBUIDORESCOMERCIANTESOFERTA
12 5
3
1 2
35 6
---------------
2 30 5
6 10
4 7
25
3 9
20
REQUERIMIENTO
--------------1035
Paso 10. Como las casillas asignadas hasta el momento son 2, y este nmero es menor que , se sigue el proceso de asignacin.
Paso 11. Calculo de los valores para las filas
Paso 12. Calculo de los valores para las columnas
Paso 13. Calculo de los indicadores de bondad para las celdasCELDA
(2 , 2)
(2 , 3)
(3 , 2)
(3 , 3)
Paso 14. Seleccionar la celda con el mayor Observando los indicadores calculados en el paso anterior se determina que existen tres (3) celdas con el mismo valor de 10. Por tanto, si seleccionamos la celda (2, 2) como la celda de asignacin, la mxima cantidad de lotes de bicicletas que se pueden transportar del distribuidor No. 2 al comerciante No. 2, es la siguiente:
Como , es necesario recalcular la oferta del distribuidor No. 2 de la manera siguiente:
Se debe eliminar la columna correspondiente al requerimiento del comerciante No. 2 esto indica que toda la demanda del comerciante No. 2 ha sido satisfecha.La tabla de asignaciones anterior, se modifica de la siguiente manera:DISTRIBUIDORESCOMERCIANTESOFERTA
12 5
3
1 2
35 6
---------------
2 30 5
10 6 10
4 7
15
3 9
20
REQUERIMIENTO
-----------------------------35
Paso 15. Como las casillas asignadas son 3, y este nmero es menor que , es necesario seguir el proceso de asignacin.
Paso 16. Calculo de los valores para las filasObservando la tabla de asignaciones generada en el paso No. 14, se ve que ya no hace falta recalcular los valores , ni los valores , pues solo queda por satisfacer la demanda del comerciante No.3 Esto se logra asignando 15 lotes de bicicletas que le quedan disponibles al distribuidor No. 2 y 20 lotes que le quedan disponibles al distribuidor No. 3La tabla de asignaciones generada en el paso 14 se modifica de la siguiente forma:DISTRIBUIDORESCOMERCIANTESOFERTA
12 5
3
1 2
35 6
---------------
2 30 5
10 6 10
15 4 7
---------------
3 9
20---------------
REQUERIMIENTO
------------------------------------------
Paso 17. Como las casillas asignadas son 5, y este nmero es igual a , ya se encontr una solucin inicial bsica factible. Obsrvese en la tabla de asignaciones generada en el paso No. 16, que todas las demandas estn satisfechas, y todas las ofertas estn asignadas.Por tanto la solucin inicial bsica factible que se obtiene por el mtodo de RUSSELL es la siguiente: DISTRIBUIDORESCOMERCIANTESOFERTA
12 5
3
1 2
35 6
35
2 30 5
10 6 10
15 4 7
55
3 9
2020
REQUERIMIENTO
304535 110
La interpretacin de esta solucin inicial es la siguiente: El distribuidor No. 1 debe proveer 35 lotes de bicicletas al comerciante No.2 El distribuidor No. 2 debe proveer 30 lotes al comerciante No. 1, 10 lotes al comerciante No. 2 y 15 lotes al comerciante No. 3 El distribuidor No. 3 debe proveer toda su oferta disponible al comerciante No. 3Con este programa de transporte, la distancia total que se recorre entre distribuidores y comerciantes es la siguiente:Distancia Total recorrida = (35 * 5) + (30 * 5) + (10 * 10) + (15 * 7) + (20 * 4) Distancia Total recorrida = 175 + 150 + 100 + 105 + 80Distancia Total recorrida = 610 Kilmetros 3. EJERCICIO
PROTAC tiene cuatro plantas ensambladoras en Europa. Estn ubicadas en Leipzig, Alemania oriental (1); Nancy, Francia (2); Lieja, Blgica (3); Tilburgo, Holanda (4). Las maquinas ensambladoras usadas en esas plantas se producen en estados unidos y se embarcan a Europa. Llegaron a los puertos de msterdam (A), Amberes (B), Havre (C).Los planes de produccin del tercer trimestre (julio a septiembre) ya han sido formulados. Los requerimientos (la demanda en destinos) de motores disel E-4 son los siguientes:
PLANTACANTIDAD DE MOTORES
LEIPZING400
NANCY900
LIEJA200
TIBURGO500
La cantidad disponible de mquinas E-4 en los puertos a tiempo para usarse en el tercer trimestre se muestra enseguida:AMSTERDAM500
AMBERES700
EL HAVRE800
La meta de PROTAC es de minimizar los costos de transporte de los motores E-4, de los puertos a las plantas.Costo de transporte de un motor de un origen a un destino:AL DESTINO
DESDE EL ORIGEN1234
A121346
B641011
C109124
ASIGNACIN INICIAL.
DESDE ORIGEN
AL DESTINO
112
213
310412
4Suministros
A6
4
116
50013
B10
9
4
70011
C
80012
Requerimiento4009002005002000
12131211
1302118
17201311
14161219
PRIMERA ITERACIN DESDE ORIGEN
AL DESTINO
12344611
Suministros
A10126
9134
20010412
50013
B
70011
C
80012
Requerimiento4009002005002000
12131211
13018
172011
141619
SEGUNDA ITERACION DESDE ORIGEN
AL DESTINO
1234Suministros
A612
13
2004
6
30013
B10
7004
10
11
70011
C
9
12
4
80012
Requerimiento4009005002000
121312
13018
141619
TERCERA ITERACIONDESDE ORIGEN
AL DESTINO
1234Suministros
A12
13
2004
6
30013
B6
7004
10
11
70011
C10
9
12
5004
80012
Requerimiento4002005002000
121312
130
1416
CUARTA ITERACIONDESDE ORIGEN
AL DESTINO
1234Suministros
A12
13
2004
6
30013
B6
7004
10
11
70011
C10
2009
12
5004
30012
Requerimiento4002002000
121312
13
14
QUINTA ITERACIONDESDE ORIGEN
AL DESTINO
1234Suministros
A12
13
2004
6
30013
B6
7004
10
11
70011
C 10010
2009
12
5004
10012
Requerimiento4002000
121312
13
SEXTA ITERACIONDESDE ORIGEN
AL DESTINO
1234Suministros
A 30012
13
2004
6
30013
B6
7004
10
11
70011
C 10010
2009
12
5004
10012
Requerimiento3002000
121312
CONCLUSIONES
El tema de programacin lineal expone una gran variedad de tipos de problemas, el mtodo de aproximacin de Russell, en comparacin con otros mtodos produce una solucin inicial mejor debido a que la solucin obtenida por este mtodo est ms cercana a la ptima , ya que la distancia total recorrida aun es menor.En general se puede afirmar que el mtodo de Russell, produce mejores soluciones que otros mtodos, pero con ms cantidad de clculos. Debido a esto, es que el mtodo que ms se utiliza para la solucin inicial de los problemas de transporte es el mtodo de Vogel, ya que requiere de menos clculos para encontrar una solucin ptima.
BIBLIOGRAFIA
MOYA NAVARRO, Marcos Javier. Investigacin de operaciones, transporte y asignacin. Primera edicin. San Jos, C.R. Editorial EUNED. 1998. 276 paginas. ISBN-9977-64-544-2HILLER, Frederick S. LIEBERMAN, Gerald J. Introduccin a la investigacin de operaciones. Sptima edicin. Mxico D F. Editorial McGraw Hill. 1998. 998 paginas. ISBN-0-07-841447-4EPPEN, G.D. Investigacin de operaciones en la ciencia administrativa. 5a Edicin. Mxico D F. Editorial Prentice-Hall. 2000. 792 paginas. ISBN: 970-17-0270-0