Investigacin Operativa II Marlon Villa Villa

EL MTODO DE TRANSPORTE Es un mtodo de programacin lineal que nos permite asignar artculos de un conjunto de orgenes a un conjunto de destinos de tal manera que se optimice la funcin objetivo.

Esta tcnica se utiliza especialmente en organizaciones que producen el mismo producto en numerosas plantas y que enva sus productos a diferentes destinos (Centros de distribucin, almacenes). Tambin se aplica en distribucin, anlisis de localizacin de plantas y programacin de la produccin. Se han desarrollado diferentes enfoques para resolver este problema de distribucin, tales como: El mtodo de la esquina noroeste, el mtodo modificado de la esquina noroeste (celda mnima), mtodo del trampoln (Cruce de arroyo, stepping stone), mtodo de la distribucin modificada (MODI), mtodo de aproximacin de Vogel y el mtodo simplex. Para que un problema pueda ser solucionado por el mtodo de transporte, este debe reunir tres condiciones:

1) La funcin objetivo y las restricciones deben de ser lineales. 2) Los artculos deben de ser uniformes e intercambiables, los coeficientes de todas las variables en la ecuacin deben de ser 0 o 1. 3) La suma de las capacidades de las fuentes debe ser igual a la suma de los requerimientos de los destinos, si alguna desigualdad existe una variable de holgura deber ser aadida. El objetivo de l modelo de programacin es minimizar el costo. MTODO DEL COSTO MNIMO El mtodo del costo mnimo o de los mnimos costos es un algoritmo desarrollado con el objetivo de resolver problemas de transporte, arrojando mejores resultados que mtodos como el de la esquina noroeste, dado que se enfoca en las rutas que presentan menores costos. El diagrama de flujo de este algoritmo es mucho ms sencillo que los anteriores se trata de asignar la mayor cantidad de unidades posibles (sujeta a las restricciones de oferta y/o demanda) a la celda menos costosa de toda la matriz hasta finalizar el mtodo ALGORITMO DE RESOLUCIN PASO 1: De la matriz se elige la ruta (celda) menos costosa (en caso de un empate, este se rompe arbitrariamente) y se le asigna la mayor cantidad de unidades posible, cantidad que se ve restringida ya sea por las restricciones de oferta o de demanda. En este mismo paso se procede a ajustar la oferta y demanda de la fila y columna afectada, restndole la cantidad asignada a la celda. PASO 2: En este paso se procede a eliminar la fila o destino cuya oferta o demanda sea 0 despus del "Paso 1", si dado el caso ambas son cero arbitrariamente se elige cual eliminar y la restante se deja con demanda u oferta cero (0) segn sea el caso. PASO 3: Una vez en este paso existen dos posibilidades, la primera que quede un solo rengln o columna, si este es el caso se ha llegado al final el mtodo, "detenerse". La segunda es que quede ms de un rengln o columna, si este es el caso iniciar nuevamente el "Paso 1". MTODO DE DISTRIBUCIN MODIFICADA El Mtodo Modi nos ofrece la oportunidad de calcular costos marginales basados en los valores de las variables de decisin del modelo, pero aunado a esto tambin nos indica la celda no bsica en la cual se deben realizar los ajustes para obtener una mejor solucin. ALGORITMO A partir de una solucin factible calculada por cualquier mtodo (MEN, VAM O MCM ): Paso 1. Calcular los multiplicadores (Ui, Vj) y los costos marginales (c.m) Los multiplicadores (Ui, Vj) estn asociados a toda celda bsica y su expresin es: Ci,j = Ui + Vj Esto es un sistema de m+n1 ecuaciones y m+n incgnitas. Los valores de los multiplicadores se obtienen suponiendo un valor arbitrario para uno de los multiplicadores y se calcula el resto, resolviendo los m+n1 multiplicadores restantes. Los costos marginales estn asociados a toda celda no bsica, con la expresin: C.M = Cij (Ui + Vj) Si todos los costos marginales son no negativos, la solucin es ptima. Termina. Paso 2. Si existe por lo menos un c.m. negativo, tomar la celda con mayor valor negativo. Crear un circuito con todos los vrtices en celdas de variables bsicas. Es decir, encontrar la trayectoria de la variable no bsica que entrar a la solucin. Paso 3. Ajustar el valor de Xij en las celdas del circuito, comenzando por sumar la variable a la celda seleccionada en el Paso 2, en el sentido de las manecillas del reloj, y alternando una resta y suma de en cada celda de la trayectoria hasta regresar a la celda primera, resolver una desigualdad (0) para y ajustar la solucin. En todo caso volver al Paso 1. Debemos recordar que # Filas + # columnas -1 # celdas llenas Si se cumple la igualdad es una solucin NO DEGENERADA Si no se cumple es una solucin DEGENERADA

MTODO DEL CRUCE DEL ARROYO (TRAMPOLIN) El mtodo del cruce del arroyo tambin llamado algoritmo de Stepping Stone o mtodo del paso a paso es un mtodo que nos ayuda a calcular cul sera la variacin del costo mnimo, adems a buscar la solucin ptima de un problema de transporte solucionado por algunos de los mtodos (Vogel, Costo mnimo, Esquina Noroeste entre otros). Este mtodo parte de una solucin factible, la cual es tomada de cualquiera de las soluciones que arrojan los mtodos de asignacin. El Cruce del Arroyo evala la solucin inicial y mediante iteraciones (procesos aritmticos) busca mejorarla hasta llegar a la solucin ptima. Si la solucin de partida es la ms desfavorable en trminos econmicos, el procedimiento se har ms dispendioso pues implica ms iteraciones hasta aproximarse a la solucin ptima. Por tal motivo entre mas acertado sea la solucin de la que partiremos, resultara mas confiable la solucin optima que resultara de nuestro procedimiento. CARACTERSTICAS 1. Se debe comenzar a resolver por las celdas vacas. 2. El nmero de casillas debe ser igual a m+n-1 3. Se deben trazar las lneas solo horizontal y verticalmente. 4. Se puede trazar lneas por celdas llenas o vacas sin utilizarlas. 5. El Circuito debe comenzar en una celda vaca y al recorrer las celdas ocupadas debe terminar en la misma celda vaca en la que comenz. 6. Cuando alguno de los ndices de mejoramiento arroja un resultado negativo, se toma el nmero menor de las celdas con signo negativo (-) y este valor se le suma a las celdas con signo positivo (+) y se resta a las celdas cuyo signo sea negativo(-). Estas sern las nuevas asignaciones. 7. Cuando los ndices de mejoramiento arrojan como resultado cero (0) o un numero positivo se puede concluir el ejercicio, es decir, se ha llegado a la solucin optima. IMPORTANCIA El Mtodo del Cruce del Arroyo nos permite encontrar la solucin optima a partir del resultado factible que arrojan las operaciones con los mtodos de transporte. PASOS DE APLICACIN Cuando se esta en la solucin factible inicial, obtenida por cualquiera de los mtodos de distribucin descritos anteriormente, los pasos a seguir son: 1. Se efectan recorridos cerrados en todas las casillas no asignadas de la tabla de solucin inicial. el recorrido debe iniciar en una casilla no asignada, haciendo su recorrido por varias casillas asignadas; en la casilla inicial ira un signo positivo(+), alternndose a uno negativo(-) y as sucesivamente en todas las casillas asignadas por donde se efecta el circuito. 2. Cuando se hallan efectuados todos los recorridos de las casillas no asignadas (donde los costos de las casillas asignadas, segn el recorrido tendr signo positivo o negativo). Si todos los costos marginales nos arrojan resultados positivos quiere decir que el ejercicio ha llegado a su final, ya que esto nos indica que hemos llegado al resultado optimo de la operacin. 3. Cuando se hallan efectuado todos los recorridos de las casillas no asignadas(donde los costos de las casillas asignadas, segn el recorrido tendr signo positivo o negativo). y los costos marginales nos arrojan algn resultado negativo se buscan las nuevas asignaciones y se procede a una nueva iteracin. 4. Se repite el paso 1,2 y 3 hasta que la suma de los recorridos de todas las casillas no asignadas sean positivas(+) o cero (0), que es la forma como sabremos que el ejercicio a llegado a su resultado optimo. MTODO DE DISTRIBUCIN MODIFICADA El Mtodo Modi nos ofrece la oportunidad de calcular costos marginales basados en los valores de las variables de decisin del modelo, pero aunado a esto tambin nos indica la celda no bsica en la cual se deben realizar los ajustes para obtener una mejor solucin. ALGORITMO A partir de una solucin factible calculada por cualquier mtodo (MEN, VAM O MCM ): Paso 1. Calcular los multiplicadores (Ui, Vj) y los costos marginales (c.m) Los multiplicadores (Ui, Vj) estn asociados a toda celda bsica y su expresin es: Ci,j = Ui + Vj Esto es un sistema de m+n1 ecuaciones y m+n incgnitas. Los valores de los multiplicadores se obtienen suponiendo un valor arbitrario para uno de los multiplicadores y se calcula el resto, resolviendo los m+n1 multiplicadores restantes. Los costos marginales estn asociados a toda celda no bsica, con la expresin: C.M = Cij (Ui + Vj) Si todos los costos marginales son no negativos, la solucin es ptima. Termina. Paso 2. Si existe por lo menos un c.m. negativo, tomar la celda con mayor valor negativo. Crear un circuito con todos los vrtices en celdas de variables bsicas. Es decir, encontrar la trayectoria de la variable no bsica que entrar a la solucin. Paso 3. Ajustar el valor de Xij en las celdas del circuito, comenzando por sumar la variable a la celda seleccionada en el Paso 2, en el sentido de las manecillas del reloj, y alternando una resta y suma de en cada celda de la trayectoria hasta regresar a la celda primera, resolver una desigualdad (0) para y ajustar la solucin. En todo caso volver al Paso 1. Debemos recordar que # Filas + # columnas -1 # celdas llenas Si se cumple la igualdad es una solucin NO DEGENERADA Si no se cumple es una solucin DEGENERADA MTODO DEL CRUCE DEL ARROYO (TRAMPOLIN) El mtodo del cruce del arroyo tambin llamado algoritmo de Stepping Stone o mtodo del paso a paso es un mtodo que nos ayuda a calcular cul sera la variacin del costo mnimo, adems a buscar la solucin ptima de un problema de transporte solucionado por algunos de los mtodos (Vogel, Costo mnimo, Esquina Noroeste entre otros). Este mtodo parte de una solucin factible, la cual es tomada de cualquiera de las soluciones que arrojan los mtodos de asignacin. El Cruce del Arroyo evala la solucin inicial y mediante iteraciones (procesos aritmticos) busca mejorarla hasta llegar a la solucin ptima. Si la solucin de partida es la ms desfavorable en trminos econmicos, el procedimiento se har ms dispendioso pues implica ms iteraciones hasta aproximarse a la solucin ptima. Por tal motivo entre mas acertado sea la solucin de la que partiremos, resultara mas confiable la solucin optima que resultara de nuestro procedimiento. CARACTERSTICAS 8. Se debe comenzar a resolver por las celdas vacas. 9. El nmero de casillas debe ser igual a m+n-1 10. Se deben trazar las lneas solo horizontal y verticalmente. 11. Se puede trazar lneas por celdas llenas o vacas sin utilizarlas. 12. El Circuito debe comenzar en una celda vaca y al recorrer las celdas ocupadas debe terminar en la misma celda vaca en la que comenz. 13. Cuando alguno de los ndices de mejoramiento arroja un resultado negativo, se toma el nmero menor de las celdas con signo negativo (-) y este valor se le suma a las celdas con signo positivo (+) y se resta a las celdas cuyo signo sea negativo(-). Estas sern las nuevas asignaciones. 14. Cuando los ndices de mejoramiento arrojan como resultado cero (0) o un numero positivo se puede concluir el ejercicio, es decir, se ha llegado a la solucin optima. IMPORTANCIA El Mtodo del Cruce del Arroyo nos permite encontrar la solucin optima a partir del resultado factible que arrojan las operaciones con los mtodos de transporte. PASOS DE APLICACIN Cuando se esta en la solucin factible inicial, obtenida por cualquiera de los mtodos de distribucin descritos anteriormente, los pasos a seguir son: 5. Se efectan recorridos cerrados en todas las casillas no asignadas de la tabla de solucin inicial. el recorrido debe iniciar en una casilla no asignada, haciendo su recorrido por varias casillas asignadas; en la casilla inicial ira un signo positivo(+), alternndose a uno negativo(-) y as sucesivamente en todas las casillas asignadas por donde se efecta el circuito. 6. Cuando se hallan efectuados todos los recorridos de las casillas no asignadas (donde los costos de las casillas asignadas, segn el recorrido tendr signo positivo o negativo). Si todos los costos marginales nos arrojan resultados positivos quiere decir que el ejercicio ha llegado a su final, ya que esto nos indica que hemos llegado al resultado optimo de la operacin. 7. Cuando se hallan efectuado todos los recorridos de las casillas no asignadas(donde los costos de las casillas asignadas, segn el recorrido tendr signo positivo o negativo). y los costos marginales nos arrojan algn resultado negativo se buscan las nuevas asignaciones y se procede a una nueva iteracin. 8. Se repite el paso 1,2 y 3 hasta que la suma de los recorridos de todas las casillas no asignadas sean positivas(+) o cero (0), que es la forma como sabremos que el ejercicio a llegado a su resultado optimo.