CUADRO COMPARATIVO Y EJEMPLOS Método de Vogel

ESQUINA NORESTE

COSTO MINIMO

VOGEL

HUNGARO

SEMEJANZAS

permite asegurar que exista una solución básica factible inicial (no artificial).

Que este es un algoritmo desarrollado con el objetivo de resolver problemas de transporte o distribución.

Como antes mencionado este método es más óptimo que el método anterior, ya que la solución que este encuentra se le puede decir que es una solución óptima o más cercana a la óptima.

El método húngaro es un método de optimización de problemas de asignación, conocido como tal gracias a que los primeros aportes al método clásico definitivo fueron de Dénes König y Jenő Egerváry dos matemáticos húngaros

DIFERENCIAS

Método de Vogel produce la mejor solución básica de inicio y el de la Esquina Noroeste la peor, sin embargo, el Método de la Esquina Noroeste implica el mínimo de cálculos.

Arroja mejores resultados que métodos como el de la esquina noroeste, dado que se enfoca en las rutas que presentan menores costos.

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.

La principal ventaja del método Vogel es que utiliza una serie de penalizaciones para calcular el coste mínimo, así como que su cálculo es sencillo. Por otro lado, el principal inconveniente es que requiere de mayores esfuerzos que otros y, en base a esto, no aporta un criterio para decidir si la solución es la mejor.

El algoritmo que usaremos para resolver el Problema de Asignación, el método húngaro, es un algoritmo primal-dual. Comienza con una solución dual factible y una solución primal infactible (parcial), ambas soluciones verificando las condiciones de holguras complementarias, donde menos de n filas son asignadas.

PASOS DEL METODO

El Método de la Esquina Noroeste comienza en la celda (ruta) correspondiente a la esquina noroeste, o superior izquierda, de la tabla (variable [pic 1]). A continuación, una descripción de los pasos:

Paso 1: Asignar todo lo posible a la celda seleccionada y ajustar las cantidades asociadas de oferta y demanda restando la cantidad asignada.

Paso 2: Salir de la fila o la columna cuando se alcance oferta o demanda cero, y tacharlo, para indicar que no se pueden hacer más asignaciones a esa fila o columna. Si una fila y una columna dan cero al mismo tiempo, tachar sólo uno (la fila o columna) y dejar una oferta (demanda) cero en la fila (columna) que no se tachó.

Paso 3: Si queda exactamente una fila o columna sin tachar, detenerse. En caso contrario, avanzar a la celda de la derecha si se acaba de tachar una columna, o a la de abajo si se tachó un reglón. Seguir con el Paso 1.

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 0 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.

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».

En el primer paso es siempre importante verificar que el problema dado este balanceado, lo que se quiere decir con esto es que ya sea tanto la oferta como la demanda sean iguales entre ellos.

Continuando con el segundo paso, se construirá una matriz de transporte, en este paso se supone que el problema ya deberá estar balanceado.

En el tercer paso, se aplica unas reglas necesarias para la solución del método

Finalmente se podría decir que el algoritmo está dado por acabado, pero también existe una manera de analizar si la solución es factible. Para poder realizar esto se utilizará una función de m + n - 1 = Numero de asignaciones. En donde tenemos que m = número de filas, yn = número de columnas.

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.

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).

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 este 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».

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 número de líneas es inferior al número de filas o columnas se debe de proceder con el paso 5.

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 paso

ORIGE DELEEEEEE  N DEL METODO

Se genera en 1947 donde se presenta un sistema llamado utilización de esquina de transporte, estas aportaciones contribuyeron al desarrollo de los métodos que indican un numero de orígenes y otros destinos.

El objetivo es determinar el programa de transporte que minimice el costo total y que satisfaga la oferta y la demanda

El origen de los modelos de transporte date del año 1941 cuando L.F. Hitchcock presento un estudio titulado The Distribution of a product from several Sources to Numerous Localities que se considera la primera contribución importante para la solución de problemas de transporte. En 1947 T.C Koopmans presento un estudio no relacionado con el de Hitchcock llamado Optimum utilization of the Transportation System. Esas dos contribuciones han ayudado al desarrollo de modelos de transporte que comprenden muchos sitios de embarque y puntos de destino.

Con la llegada de la Revolución Industrial, los problemas empresariales crecieron. Entre ellos, los de asignación de tareas y costos. Por esta razón, surgieron algunos métodos que permitían hacerlo de forma eficiente. Así, en 1955, Harold W. Kuhn plantea el método húngaro, a la vez que comienzan a desarrollarse otros similares en la rama de administración de operaciones.

Uno de los problemas principales surge en el transporte. El objetivo es cómo decidir rutas, tiempos o destinos, basándonos en la necesidad de minimizar los costos y poder satisfacer la demanda con la oferta disponible. William R. Vogel propone, para ello, el método que recibe su nombre. Un método que, por medio de un algoritmo, resuelve los problemas relacionados con los transportes y su asignación.

La primera versión conocida del método húngaro, fue inventado y publicado por Harold W. Kuhn en 1955. Este fue revisado por James Munkres en 1957, y ha sido conocido desde entonces como el algoritmo húngaro, el algoritmo de la asignación de Munkres, o el algoritmo de Kuhn-Munkres.

El algoritmo desarrollado por Kuhn está basado fundamentalmente en los primeros trabajos de otros dos matemáticos húngaros: Dénes Kőnig y Jenő Egerváry. La gran ventaja del método de Kuhn es que es fuertemente polinómico (ver Complejidad computacional para más detalles).

El algoritmo húngaro construye una solución del problema primal partiendo de una solución no admisible (que corresponde a una solución admisible del dual) haciéndola poco a poco más admisible.

BREVE   BIOGRAFIA B bBIOGRAFIA DEL CREADOR DEL METODO

Franck Lauren Hitchcock, nació el 6 de marzo de 1875 en Nueva York.

En el año de 1941 presentó un estudio titulado “La distribución de un producto desde diversos orígenes a numerosas localidades”. Se cree que esta investigación fue la primera contribución para la resolución de los problemas de transporte.

También fue un experto en química matemática y cuaterniones.

Realizo la licenciatura en Harvard en 1896, realizo sus estudios en física y matemáticas.

En 1904-1906 fue profesor de química en la Universidad Estatal de Dakota del Norte, Fargo, y luego se trasladó a convertirse en un profesor de matemáticas en el Massachusetts Institute of Technology

En 1910 completó su doctorado en Harvard con una tesis titulada “Funciones vectoriales de un punto”.

Hitchcock falleció en el año de 1957.

Franck Lauren Hitchcock, nació el 6 de marzo de 1875 en Nueva York.

En el año de 1941.

Realizo la licenciatura en Harvard en 1896, realizo sus estudios en física y matemáticas.

En 1904-1906 fue profesor de química en la Universidad Estatal de Dakota del Norte, Fargo, y luego se trasladó a convertirse en un profesor de matemáticas en el Massachusetts Institute of Technology

En 1910 completó su doctorado en Harvard con una tesis titulada “Funciones vectoriales de un punto”.

Hitchcock falleció en el año de 1957.

Tjalling Koopmans

(Tjalling Charles Koopmans; Graveland, 1910 - New Haven, Connecticut, 1985) Economista estadounidense de origen neerlandés que obtuvo el premio Nobel de Economía de 1975, junto a Leonid V. Kantoróvich, por sus contribuciones a la econometría y a la teoría de la asignación óptima de recursos.

Nace el 15 de noviembre de 1964 en Sac City, Iowa, Muere el 26 de agosto de 2010 en el Mercy Hospice, Johnston, Iowa tras una larga y valiente lucha contra el cáncer.

Se gradúa en 1959 como el mejor alumno. Crece en una granja al oeste de Wall Lake, Iowa.

Trabajó en la Northwestern Bell / Qwest por 25 años, y en Principal Financial de 12 años como analista de telecomunicaciones. Se jubila a los 62 viviendo la vida al máximo.

Harold William Kuhn (Santa Mónica, California, 29 de julio de 1925 – Nueva York, 2 de julio de 2014) fue un matemático estadounidense que estudió teoría de juegos. Ganó el Premio de Teoría John von Neumann en 1980 junto con David Gale y Albert W. Tucker.

Profesor emérito de matemáticas en la Universidad de Princeton, es conocido por las condiciones Karush-Kuhn-Tucker, para el desarrollo de póker Kuhn, así como la descripción del método húngaro para el problema de asignación. Recientemente, sin embargo, un artículo de Carl Gustav Jacobi, publicado póstumamente en 1890 en latín, se ha descubierto que anticipa por muchas décadas el algoritmo húngaro.

APLICACIONES

se aplica a una estructura especial de problemas de Programación Lineal llamada Modelo de Transporte, la cual permite asegurar que exista una solución básica factible inicial (no artificial)

Minimizar los costos de transporte de las fábricas a los almacenes o de los almacenes a las tiendas minoristas.

– Determinar la ubicación de costo mínimo de una nueva fábrica, almacén u oficina de ventas.

– Determinar el cronograma de producción de costo mínimo que satisfaga la demanda de la empresa con las limitaciones de producción.

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

El método húngaro es aplicado con más frecuencia en las áreas de producción de las empresas, para ver cuál de las maquinas en operación puede presentar problemas o algún fallo que afecta a la producción

EJEMPLOS

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 por cada millón de KW entre cada planta y cada ciudad son los registrados en la siguiente tabla.

[pic 2]

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.

Solución paso a paso

[pic 3]

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.

[pic 4]

Continuamos con las iteraciones.

[pic 5]

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:

[pic 6]

Una vez finalizada esta asignación, se elimina la «Planta 3» que 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.

[pic 7]

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

[pic 8]

Los costos asociados a la distribución son:

[pic 9]

El costo total es evidentemente superior al obtenido mediante Programación Lineal y el Método de Aproximación de Vogel, 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.

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 por cada millón de KW entre cada planta y cada ciudad son los registrados en la siguiente tabla.

[pic 10]Seleccionamos la celda con menor valor, es decir la menos costosa, para asignarle la mayor cantidad posible.

[pic 11]

Luego 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.

[pic 12]

[pic 13]

[pic 14]

[pic 15]

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. [pic 16]

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

[pic 17]

Los costos asociados a la distribución son:

[pic 18]

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

Imaginemos que tenemos una serie de plantas productivas, que deben suministrar bienes a ciertos destinos. En primer lugar, creamos la tabla inicial de doble entrada que muestra los costes unitarios de cada opción. Por otro lado, las capacidades de oferta (O) y las necesidades de demanda (D) se muestran en la fila y columna correspondiente

En el primer paso, se calculan las penalizaciones (Pe1), como se explicó antes, y se elige la mayor de ellas, el tres (azul oscuro) de la casilla (Pe1, D3). Escogemos el menor valor de esa columna, que sería el cuatro (azul intermedio) de la casilla (P2, D3). En la tabla de la derecha, en la misma posición, se inserta el mayor valor posible según la demanda de esa columna, que es 30 (gris). Por tanto, sobrarían 10 en la oferta, ya que su máximo son 40.

Así pues, volvemos a realizar el proceso en el paso 2, una vez eliminada la columna D3. Calculamos la segunda penalización (Pe2), y repetimos los pasos anteriores. La fila elegida será la P1, con el menor valor de cinco y con un valor máximo en la tabla de oferta y demanda de cincuenta. En el paso 3, hacemos lo mismo, incluyendo la tercera penalización (Pe3).

Paso 1

Encontramos el menor elemento de cada fila

[pic 19]

Paso 2

Construimos una nueva matriz con las diferencias entre los valores de la matriz original y el elemento menor de la fila a la cual corresponde.

[pic 20]

Paso 3

En la matriz construida en el paso anterior se procede a efectuar el paso 1 esta vez en relación a las columnas, por ende, escogemos el elemento menor de cada columna. Igualmente construimos una nueva matriz con la diferencia entre los valores de la matriz 2 y el elemento menor de la columna a la cual corresponde cada valor.

[pic 21]

Paso 4

En este paso trazaremos la menor cantidad de combinaciones de líneas horizontales y verticales con el objetivo de cubrir todos los ceros de la matriz de costos reducidos.

[pic 22]

Como se puede observar el menor número de líneas horizontales y/o verticales necesarios para cubrir los ceros de la matriz de costos reducidos es igual a 2, por ende, al ser menor que el número de filas o columnas es necesario recurrir al paso 5.

Paso 5

En este paso seleccionamos el menor elemento de los elementos no subrayados.

[pic 23]

Luego se procede a restarse de los elementos no subrayados y a adicionarse a los elementos ubicados en las intersecciones de las líneas, en este caso existe una única intersección (3).

[pic 24]

Ahora ya efectuado este paso pasamos al paso 4.

[pic 25]

Ahora observamos cómo se hace necesario trazar tres líneas (la misma cantidad de filas o columnas de la matriz) por ende se ha llegado al tabulado final, en el que por simple observación se determina las asignaciones óptimas.

[pic 26]

Por ende, la asignación que representa el menor costo para la jornada de mantenimiento preventivo determina que el Equipo 1 realice el mantenimiento de la Máquina 1, el Equipo 2 realice el mantenimiento de la Máquina 3 y el Equipo 3 realice el mantenimiento de la Máquina 2, jornada que tendrá un costo total de 17 unidades monetarias.