By Institución: tec. De pabellón Alumno: Ricardo A. TEJEDA MATERIA: macroeconomía FACILITADOR: GARCIA MARYCARMEN UNIDAD III: TRABAJO DE INVESTIGACION 2 MÉTODO DE LA ESQ A Svipe nextp El método de la esqu heurístico capaz de s ritmo transporte o distribución mediante la consecución de una solución básica inicial que satisfaga 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 es utilizado con mayor frecuencia en ejercicios onde el número de fuentes y destinos sea muy elevado.
Se parte por esbozar en forma matricial el problema, es decir, filas que representen fuentes y columnas que representen destinos, luego el algoritmo debe de iniciar en la celda, ruta o esquina Noroeste de la tabla (esquina superior izquierda). Numero de pasos caso ambas son cero arbitrariamente se elige cual eliminar y la restante se deja con demanda u oferta cero (O) segun 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 el caso 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». EL PROBLEMA una empresa energética colombiana dispone de cuatro plantas de generación para satisfacer la demanda diaria elé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ín y 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 or cada millón de KW entre cada planta y cada ciudad son los registrados en la siguiente tabla. Formule un modelo de programación lineal que permita satisfacer las necesidades de todas las ciudades al tiempo que minimice los costos asociados al transporte. SOLUCION PASO A PASO 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 (O), se procede a eliminar la columna.
El proceso de asignación nuevamente se repite. Continuamos con las iteraciones. En est 12 En este caso nos encontramos frente a la elección de la fila o columna a eliminar (tachar), sin embargo podemos utilizar un criterio mediante el cual eliminemos la fila o columna que presente los costos más elevados. En este caso la «Planta 2». Nueva iteración. na vez finalizada esta asignación, se elimina la «Planta 3» que U ya ha sido satisfecha con la asignación de 60 unidades, por ende nos queda una sola fila a la cual le asignamos las unidades estrictamente requeridas y hemos finalizado el método.
El cuadro de las asignaciones (que debemos desarrollarlo paralelamente) queda así: Los costos asociados a la distribución son: El costo total es evidentemente superior al obtenido mediante Programación Lineal y el Método, lo cual demuestra lo enunciado en la descripción del algoritmo que cita que no obtiene siempre la mejor solución, sin embargo presenta un cumplimiento de todas las restricciones y una rapidez de elaboración, lo cual es una ventaja en problemas con innumerables fuentes y destinos en los cuales no nos importe más que satisfacer las restricciones.
MÉTODO DEL COSTO MÍNIMO El método del costo míni algoritmo desarrollado co nimos costos es un 30F 12 e resolver problemas ado que se enfoca en las rutas que presentan menores costos. El diagrama de flujo de este algoritmo es mucho más sencillo que los anteriores dado que se trata simplemente de la asignación de 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 método.
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, restándole la cantidad asignada a la celda.
PASO 2: En este paso se procede a eliminar la fila o destino cuya oferta o demanda sea O después 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) según sea el caso. una vez en este paso existen dos posibilidades, la primera que 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’.
PROBLEMA Una empresa energética colombiana dispone de cuatro plantas de generación para satisfacer la demanda diana eléctrica en 1,2,3 y 4 pued PAGF40F 12 eléctrica en cuatro ciudades, Cali, Bogotá, Medellin y Barranquilla. Las plantas 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ín y 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 ciudad son los registrados en la siguiente tabla. SOLUCIÓN PASO A PASO uego esa cantidad asignada se resta a la demanda de Bogotá y a la oferta de la «Planta 3», en un proceso muy lógico. Dado que Bogotá se queda sin demanda esta columna desaparece, y se repite el primer proceso. Nuevo proceso de asignación Una vez finalizado el cuadro anterior nos daremos cuenta que solo quedará una fila, por ende asignamos las unidades y se ha terminado el método.
En este caso el método de o presenta un costo total y tiene un mejor rendimiento en cuanto a resultados respecto al Método de la Esquina Noroeste. METODO DE APROXIMACION DE VOGEL El método de aproximación de Vogel es un método heurístico de resolución de problemas de transporte capaz de alcanzar una solución básica no artificial de inicio, este modelo requiere de la realización de un número generalmente mayor de iteraciones que los demás métodos heurísticos existentes con este fin, sin embargo produce mejores resultados iniciales que los mismos.
NUMERO DE PASOS PASO 1 Determinar para cada fila y columna una medida de penalización restando los dos costos menores en filas y columnas. PASO 2 Escoger la fila o columna con la mayor penalización, es decir ue de la resta realizada en el «Paso 1» se debe escoger el numero mayor. En caso de haber empate, se debe escoger arbitrariamente (a juicio personal). PASO 3 De la fila o columna de mayor penalización determinada en el paso anterior debemos de escoger la celda con el menor costo, y en esta asignar la mayor cantidad posible de unidades.
Una vez se realiza este paso una oferta o demanda quedará satisfecha por ende se tachará la fila o columna, en caso de empate solo se tachará 1, la restante quedará con oferta o demanda igual a cero PASO 4: DE CICLO Y EXCEPCIONES – Si queda sin tachar exactamente una fila o columna con cero ferta o demanda, detenerse. – Si queda sin tachar una fila o columna con oferta o demanda positiva, determine las variables básicas en la fila o columna con el método de 6 2 oferta o demanda positiva, determine las variables básicas en la fila o 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ásicas cero 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 se hayan agotado. Medellin y Barranquilla son de 70, 40, 70 y 35 millones de Kw al El primer paso es determinar las medidas de penalización y consignarlas en el tabulado de costos, tal como se muestra a continuación.
El paso siguiente es escoger la mayor penalización, de esta manera: El paso siguiente es escog mna el menor valor, y 7 2 en una tabla paralela se le or cantidad posible de menor valor, y en una tabla paralela se le asigna la mayor cantidad posible de unidades, podemos observar como el menor costo es «2» y que a esa celda se le pueden asignar como máximo 60 unidades «que es la capacidad de la planta 3». Dado que la fila de la «Planta 3» ya ha asignado toda su capacidad (60 unidades) esta debe desaparecer.
Se ha llegado al final del ciclo, por ende se repite el proceso Iniciamos una nueva iteración Continuamos con las iteraciones, Iniciamos otra iteración 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. De esta manera hemos llegado a la solución a la cual también llegamos mediante programación, definitivamente desarrollar la capacidad para modelar mediante programación lineal y apoyarse e una buena herramienta como WinQSB, STORM, LINGO, TORA etc. ermina siendo mucho más eficiente que la utilización de los métodos heur(sticos para problemas determinísticos, sin embargo cabe recordar que uno de los errores más frecuentes en los que caen los ingenieros industriales es en tratar de adaptar a sus organizaciones a los modelos establecidos, cabe recordar que son los modelos los que deben adaptarse a las organizaciones lo cual requiere de determinada habilidad para realizar de forma inmediata cambios innova s fines, en pocas palabras 80F 12 un ingeniero industrial req ambios innovadores para sus fines, en pocas palabras un ingeniero industrial requiere de un buen toque de HEURÍSTICA en su proceder. MÉTODO DE ASIGNACIÓN El Método de asignación es una variación del problema original de transporte, variación en la cual las variables de decisión X (i,j) solo pueden tomar valores binarios, es decir ser cero (0) o uno (1) en la solución óptima, lo que supone que la oferta y la demanda están perfectamente alineadas, de hecho ambas son iguales a uno (1).
Múltiples son los casos en los que como ingenieros industriales podemos hacer uso del problema de asignación para resolver iversas situaciones, entre los que cabe mencionar se encuentran la asignación de personal a maquinas, herramientas a puestos de trabajos, horarios a maestros, candidatos a vacantes, huéspedes a habitaciones, comensales a mesas, vendedores a zonas territoriales etc. PASOS ALGORITMO HUNGARO, PASO 1 Antes que nada cabe recordar que el método húngaro trabaja en una matriz de costos n*m (en este caso conocida como matriz m*m, dado que el número de filas es igual al número de columnas n = m), una vez construida esta se debe encontrar el elemento más pequeño en cada fila de la matriz.
ALGORITMO HUNGARO, PASO 2 Una vez se cumple el procedimiento anterior se debe construir una nueva matriz n*m, en la cual se consignarán los valores resultantes de la diferencia entre cada costo y el valor mínimo de la fila a la cual cada costo corresponde (valor mínimo hallado en el primer paso). ALGORITMO HUNGARO, PA fila a la cual cada costo corresponde (valor mínimo hallado en el ALGORITMO HUNGARO, PASO 3 Este paso consiste en realizar el mismo procedimiento de los dos pasos anteriores referidos ahora a las columnas, es decir, se halla el valor mínimo de cada columna, con la diferencia que ste se halla de la matriz resultante en el segundo paso, luego se construirá una nueva matriz en la cual se consignarán los valores resultantes de la diferencia entre cada costo y el valor mínimo de la columna a la cual cada costo corresponde, matriz llamada «Matriz de Costos Reducidos».
ALGORITMO HUNGARO, PASO 4 A continuación se deben de trazar líneas horizontales o verticales o ambas (únicamente de esos tipos) con el objetivo de cubrir todos los ceros de la matriz de costos reducidos con el menor número de líneas posibles, si el número de líneas es igual al número de filas o columnas se ha logrado obtener la solución ?ptima (la mejor asignación según el contexto de optimización), si el numero de líneas es inferior al número de filas o columnas se debe de proceder con el paso 5. ALGORITMO HUNGARO, PASO 5 Este paso consiste en encontrar el menor elemento de aquellos valores que no se encuentran cubiertos por las líneas del paso 4, ahora se restará del restante de elementos que no se encuentran cubiertos por las líneas; a continuación este mismo valor se sumará a los valores que se encuentren en las intersecciones de las líneas horizontales y verticales, una vez finalizado este paso se debe volver al pa 0 DF 12
