algoritmo de transporte 1 julio vargas herbas

de 28MATERIA DE INVESTIGACION DE OPERACIONES DE JULIO VARGAS HERBAS 72633488

REALIZADO POR LIC. ADM JULIO VARGAS HERBAS [email protected] 72633488

ALGORITMO DE TRANSPORTE

MÉTODO DE LA ESQUINA NOROESTE

El método de la esquina Noroeste es un algoritmo heurístico capaz de solucionar problemasde transporte o distribución mediante la consecución de una solución básica inicial quesatisfaga todas las restricciones existentes sin que esto implique que se alcance el costoóptimo total.Este método tiene como ventaja frente a sus similares la rapidez de su ejecución, y esutilizado con mayor frecuencia en ejercicios donde el número de fuentes y destinos sea muyelevado. Su nombre se debe al génesis del algoritmo, el cual inicia en la ruta, celda o esquinaNoroeste. Es común encontrar gran variedad de métodos que se basen en la mismametodología de la esquina Noroeste, dado que podemos encontrar de igual manera el métodoe la esquina Noreste, Sureste o Suroeste.

ALGORITMO DE RESOLUCIÓN DE LA ESQUINA NOROESTESe parte por esbozar en forma matricial el problema, es decir, filas que representen fuentes ycolumnas que representen destinos, luego el algoritmo debe de iniciar en la celda, ruta oesquina Noroeste de la tabla (esquina superior izquierda).

Julio Vargas Herbas

JULIO VARGAS HERBAS

mailto:[email protected]



PASO 1:En la celda seleccionada como esquina Noroeste se debe asignar la máxima cantidad de unidadesposibles, cantidad que se ve restringida ya sea por las restricciones de oferta o de demanda. En estemismo paso se procede a ajustar la oferta y demanda de la fila y columna afectada, restándole lacantidad asignada a la celda.

PASO 2:En este paso se procede a eliminar la fila o destino cuya oferta o demanda sea 0 después del "Paso 1",si dado el caso ambas son cero arbitrariamente se elige cual eliminar y la restante se deja condemanda u oferta cero (0) según sea el caso.

PASO 3:Una vez en este paso existen dos posibilidades, la primera que quede un solo renglón o columna, sieste es el caso se ha llegado al final el método, "detenerse". La segunda es que quede más de unrenglón o columna, si este es el caso iniciar nuevamente el "Paso 1".

EJEMPLO DEL MÉTODO DE LA ESQUINA NOROESTEPor medio de este método resolveremos el problema de transporte propuesto y resuelto en módulos anterioresmediante programación lineal.

EL PROBLEMA #1Una empresa energética colombiana dispone de cuatro plantas de generación para satisfacer la demanda diariaeléctrica en cuatro ciudades, Cali, Bogotá, Medellín y Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80,30, 60 y 45 millones de KW al día respectivamente. Las necesidades de las ciudades de Cali, Bogotá, Medellíny Barranquilla son de 70, 40, 70 y 35 millones de Kw al día respectivamente.Los costos asociados al envío de suministro energético por cada millón de KW entre cada planta y cada ciudadson los registrados en la siguiente tabla.

Julio Vargas Herbas

Formule un modelo de programación lineal que permita satisfacer las necesidades de todas las ciudades altiempo que minimice los costos asociados al transporte.




SOLUCIÓN PASO A PASO

Julio Vargas Herbas

Ahora la cantidad asignada a la esquina noroeste es restada a la demanda de Cali y a la oferta de la "Planta 1",en un procedimiento muy lógico. Dado que la demanda de Cali una vez restada la cantidad asignada es cero (0),se procede a eliminar la columna. El proceso de asignación nuevamente se repite.

Julio Vargas Herbas

Continuamos con las iteraciones.




Julio Vargas Herbas

En este caso nos encontramos frente a la elección de la fila o columna a eliminar (tachar), sin embargo podemosutilizar un criterio mediante el cual eliminemos la fila o columna que presente los costos más elevados. En estecaso la "Planta 2".

Nueva iteración.

Julio Vargas Herbas

Una vez finalizada esta asignación, se elimina la "Planta 3" que ya ha sido satisfecha con la asignación de 60unidades, por ende nos queda una sola fila a la cual le asignamos las unidades estrictamente requeridas y hemosfinalizado el método.




Julio Vargas Herbas

El cuadro de las asignaciones (que debemos desarrollarlo paralelamente) queda así:

Julio Vargas Herbas

Los costos asociados a la distribución son:




Julio Vargas Herbas

El costo total es evidentemente superior al obtenido mediante Programación Lineal y el Método deAproximación de Vogel, lo cual demuestra lo enunciado en la descripción del algoritmo que cita que no obtienesiempre la mejor solución, sin embargo presenta un cumplimiento de todas las restricciones y una rapidez deelaboración, lo cual es una ventaja en problemas con innumerables fuentes y destinos en los cuales no nosimporte más que satisfacer las restricciones.

NOTA: Para hacer el circuito como la solución saldría degenerada asignamos un cero(0) en una de las celdasvacías donde exista el costo más pequeña para poder hacer el circuito.

http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/problema-del-transporte-o-distribuci%C3%B3n/

http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/m%C3%A9todo-de-aproximaci%C3%B3n-de-vogel/





MÉTODO DEL COSTO MÍNIMO

El método del costo mínimo o de los mínimos costos es un algoritmo desarrollado con el objetivo de resolverproblemas de transporte o distribución, arrojando mejores resultados que métodos como el de la esquinanoroeste, dado que se enfoca en las rutas que presentan menores costos. El diagrama de flujo de este algortimoes mucho más sencillo que los anteriores dado que se trata simplememente de la asignación de la mayorcantidad de unidades posibles (sujeta a las restricciones de oferta y/o demanda) a la celda menos costosa de todala matriz hasta finalizar el método.

ALGORITMO DE RESOLUCIÓN DEL COSTO MÍNIMOPASO 1:De la matriz se elige la ruta (celda) menos costosa (en caso de un empate, este se rompe arbitrariamente) y se leasigna la mayor cantidad de unidades posible, cantidad que se ve restringida ya sea por las restricciones deoferta o de demanda. En este mismo paso se procede a ajustar la oferta y demanda de la fila y columna afectada,restandole 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 después del "Paso 1", si dado elcaso ambas son cero arbitrariamente se elige cual eliminar y la restante se deja con demanda u oferta cero (0)según sea el caso.

PASO 3:Una vez en este paso existen dos posibilidades, la primera que quede un solo renglón o columna, si este es elcaso se ha llegado al final el método, "detenerse".La segunda es que quede más de un renglón o columna, si este es el caso iniciar nuevamente el "Paso 1".

EJEMPLO DEL MÉTODO DEL COSTO MÍNIMOPor medio de este método resolveremos el problema de transporte propuesto y resuelto en módulos anterioresmediante programación lineal.




EL PROBLEMAUna empresa energética colombiana dispone de cuatro plantas de generación para satisfacer la demanda diariaeléctrica en cuatro ciudades, Cali, Bogotá, Medellín y Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80,30, 60 y 45 millones de KW al día respectivamente. Las necesidades de las ciudades de Cali, Bogotá, Medellíny Barranquilla son de 70, 40, 70 y 35 millones de Kw al día respectivamente.

Los costos asociados al envío de suministro energético por cada millón de KW entre cada planta y cada ciudadson los registrados en la siguiente tabla.

Julio Vargas Herbas



Julio Vargas Herbas

Luego esa cantidad asignada se resta a la demanda de Bogotá y a la oferta de la "Planta 3", en un proceso muylógico. Dado que Bogotá se queda sin demanda esta columna desaparece, y se repite el primer proceso.




Julio Vargas Herbas

Nuevo proceso de asignación

Julio Vargas Herbas


Julio Vargas Herbas





Julio Vargas herbas

Una vez finalizado el cuadro anterior nos daremos cuenta que solo quedará una fila, por ende asignamos lasunidades y se ha terminado el método.

Julio Vargas Herbas

El cuadro de las asignaciones (que debemos desarrollarlo paralelamente) queda así:

Julio Vargas Herbas





Julio Vargas Herbas

En este caso el método del costo mínimo presenta un costo total superior al obtenido mediante ProgramaciónLineal y el Método de Aproximación Vogel, sin embargo comunmente no es así, además es simple dedesarrollar y tiene un mejor rendimiento en cuanto a resultados respecto al Método de la Esquina Noroeste.




http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/m%C3%A9todo-de-la-esquina-noroeste/




MÉTODO DE APROXIMACIÓN DE VOGEL

El método de aproximación de Vogel es un método heurístico de resolución de problemas de transporte capazde alcanzar una solución básica no artificial de inicio, este modelo requiere de la realización de un númerogeneralmente mayor de iteraciones que los demás métodos heurísticos existentes con este fin, sin embargoproduce mejores resultados iniciales que los mismos.

ALGORITMO DE RESOLUCIÓN DE VOGELEl método consiste en la realización de un algoritmo que consta de 3 pasos fundamentales y 1 más que asegurael ciclo hasta la culminación del método.

PASO 1Determinar para cada fila y columna una medida de penalización restando los dos costos menores en filas ycolumnas.

PASO 2Escoger la fila o columna con la mayor penalización, es decir que de la resta realizada en el "Paso 1" se debeescoger el número mayor. En caso de haber empate, se debe escoger arbitrariamente (a juicio personal).

PASO 3De la fila o columna de mayor penalización determinada en el paso anterior debemos de escoger la celda con elmenor costo, y en esta asignar la mayor cantidad posible de unidades. Una vez se realiza este paso una oferta odemanda quedará satisfecha por ende se tachará la fila o columna, en caso de empate solo se tachará 1, larestante quedará con oferta o demanda igual a cero (0).

PASO 4: DE CICLO Y EXCEPCIONES- Si queda sin tachar exactamente una fila o columna con cero oferta o demanda, detenerse.

- Si queda sin tachar una fila o columna con oferta o demanda positiva, determine las variables básicas en la filao columna con el método de costos mínimos, detenerse.

- Si todas las filas y columnas que no se tacharon tienen cero oferta y demanda, determine las variables básicascero por el método del costo mínimo, detenerse.




- Si no se presenta ninguno de los casos anteriores vuelva al paso 1 hasta que las ofertas y las demandas sehayan agotado.

EJEMPLO DEL MÉTODO DE APROXIMACIÓN DE VOGEL

Por medio de este método resolveremos el ejercicio de transporte resuelto en módulos anteriores medianteprogramación lineal.

EL PROBLEMA

Una empresa energética colombiana dispone de cuatro plantas de generación para satisfacer la demanda diariaeléctrica en cuatro ciudades, Cali, Bogotá, Medellín y Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80,30, 60 y 45 millones de KW al día respectivamente. Las necesidades de las ciudades de Cali, Bogotá, Medellíny Barranquilla son de 70, 40, 70 y 35 millones de Kw al día respectivamente.


Bryan Antonio Salazar López



El primer paso es determinar las medidas de penalización y consignarlas en el tabulado de costos, tal como semuestra a continuación.

Julio Vargas herbas




El paso siguiente es escoger la mayor penalización, de esta manera:

julio Vargas Herbas

El paso siguiente es escoger de esta columna el menor valor, y en una tabla paralela se le asigna la mayorcantidad posible de unidades, podemos observar como el menor costo es "2" y que a esa celda se le puedenasignar como máximo 60 unidades "que es la capacidad de la planta 3".

Julio Vargas Herbas

Dado que la fila de la "Planta 3" ya ha asignado toda su capacidad (60 unidades) esta debe desaparecer.




Julio Vargas Herbas

Se ha llegado al final del ciclo, por ende se repite el proceso




Julio Vargas herbas

Iniciamos una nueva iteración




Julio Vargas Herbas

Continuamos con las iteraciones,




Julio Vargas Herbas

Iniciamos otra iteración




Julio Vargas Herbas

Al finalizar esta iteración podemos observar como el tabulado queda una fila sin tachar y con valores positivos,por ende asignamos las variables básicas y hemos concluido el método.




Julio Vargas Herbas


Julio Vargas Herbas




Julio Vargas Herbas

De esta manera hemos llegado a la solución a la cual también llegamos mediante programación lineal,definitivamente desarrollar la capacidad para modelar mediante programación lineal y apoyarse de una buenaherramienta como WinQSB, STORM, LINGO, TORA etc.. termina siendo mucho más eficiente que lautilización de los métodos heurísticos para problemas determinísticos; sin embargo cabe recordar que uno de loserrores más frecuentes en los que caen los ingenieros industriales es en tratar de adaptar a sus organizaciones alos modelos establecidos, cabe recordar que son los modelos los que deben adaptarse a las organizaciones locual requiere de determinada habilidad para realizar de forma inmediata innovaciones positivas para sus fines,en pocas palabras un ingeniero industrial requiere de un buen toque de HEURÍSTICA en su proceder.




PROBLEMA DEL TRANSPORTE ODISTRIBUCIÓN

El problema del transporte o distribución es un problema de redes especial en programación lineal que se fundaen la necesidad de llevar unidades de un punto específico llamado Fuente u Origen hacía otro punto específicollamado Destino. Los principales objetivos de un modelo de transporte son la satisfacción de todos losrequerimientos establecidos por los destinos y claro está la minimización de los costos relacionados con el plandeterminado por las rutas escogidas.

El contexto en el que se aplica el modelo de transporte es amplio y puede generar soluciones atinentes al área deoperaciones, inventario y asignación de elementos.

El procedimiento de resolución de un modelo de transporte se puede llevar a cabo mediante programación linealcomún, sin embargo su estructura permite la creación de múltiples alternativas de solución tales como laestructura de asignación o los métodos heurísticos más populares como Vogel, esquina noroeste o mínimoscostos.

JULIO VARGAS HERBAS




Julio Vargas Herbas

Los problemas de transporte o distribución son uno de los más aplicados en la economía actual, dejando comoes de prever múltiples casos de éxito a escala global que estimulan la aprehensión de los mismos.

PROBLEMA DE TRANSPORTE MEDIANTE PROGRAMACIÓN LINEAL

Como se mencionó anteriormente la programación lineal puede ser utilizada para la resolución de modelos detransporte, aunque no sea sensato resolver los modelos mediante el Método Simplex si puede ser de granutilidad la fase de modelización, la programación carece de la practicidad de los métodos de asignación, peropuede ser de gran importancia dependiendo de la complejidad de las restricciones adicionales que puedepresentar un problema particular.

EL PROBLEMA

Una empresa energética colombiana dispone de cuatro plantas de generación para satisfacer la demanda diariaeléctrica en cuatro ciudades, Cali, Bogotá, Medellín y Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80,30, 60 y 45 millones de KW al día respectivamente. Las necesidades de las ciudades de Cali, Bogotá, Medellíny Barranquilla son de 70, 40, 70 y 35 millones de Kw al día respectivamente.





Julio Vargas Herbas


SOLUCIÓN MEDIANTE PL

El modelo básico de transporte es el modelo en el cual la cantidad ofertada es igual a la cantidad demandada,como es el caso de este ejercicio, sin embargo trasladar esta suposición a la realidad es casi imposible por locual hace falta crear orígenes y/o destinos ficticios con el excedente de oferta y/o demanda.

Como ya lo hemos planteado en módulos anteriores el primer paso corresponde a la definición de las variables,regularmente se le denomina a las variables de manera algebraica Xi,j donde i simboliza a la fuente y j simbolizaal destino. En este caso i define el conjunto {Planta 1, Planta 2, Planta 3 y Planta 4}, y j define el conjunto{Cali, Bogotá, Medellín y Barranquilla}. Sin embargo es práctico renombrar cada fuente y destino por unnúmero respectivo, por ende la variable X1,2 corresponde a la cantidad de millones de KW enviados diariamentede la Planta 1 a la ciudad de Bogotá.

Julio Vargas Herbas




El segundo paso corresponde a la formulación de las restricciones de oferta y demanda, cuya cantidad seencuentra determinada por el factor entre fuentes y destinos, en este caso 16 restricciones.

Restricciones de oferta o disponibilidad, las cuales son de signo ≤:

X1,1 + X1,2 + X1,3 + X1,4 ≤ 80

X2,1 + X2,2 + X2,3 + X2,4 ≤ 30

X3,1 + X3,2 + X3,3 + X3,4 ≤ 60

X4,1 + X4,2 + X4,3 + X4,4 ≤ 45

Restricciones de demanda, las cuales son de signo ≥:

X1,1 + X2,1 + X3,1 + X4,1 ≥ 70

X1,2 + X2,2 + X3,2 + X4,2 ≥ 40

X1,3 + X2,3 + X3,3 + X4,3 ≥ 70

X1,4 + X2,4 + X3,4 + X4,4 ≥ 35

Luego se procede a formular la función objetivo, en la cual se relaciona el costo correspondiente a cada ruta.

ZMIN = 5X1,1 + 2X1,2 + 7X1,3 + 3X1,4 + 3X2,1 + 6X2,2 + 6X2,3 + 1X2,4 + 6X3,1 + 1X3,2 + 2X3,3 + 4X3,4 + 4X4,1 +3X4,2 + 6X4,3 + 6X4,4

Luego se puede proceder al uso de la herramienta WinQSB para resolver el modelo realizado, aquí están losresultados.




Julio Vargas Herbas

Julio Vargas Herbas

Este problema presenta una solución óptima alternativa, aquí los resultados.




Julio Vargas Herbas

Julio Vargas Herbas




Los análisis de dualidad y sensibilidad en los modelos de transporte resultan ser bastante interesantes, puespueden llegar a determinar aumentos de capacidad en las fuentes si el precio sombra de las rutas en relación aellas lo justifica.

INVEST IN BOLIVIA


algoritmo de transporte 1 julio vargas herbas

Documents