BONDADES DEL MÉTODO HÚNGARO EN LA TEORÍA DE ASIGNACIÓN

[pic 1]

[pic 2]

UNIVERSIDAD ESTATAL DE MILAGRO

FACULTAD DE INGENIERÍA

MATERIA:

INVESTIGACIÓN DE OPERACIONES

CURSO:

5TO SEMESTRE

TEMA:

BONDADES DEL MÉTODO HÚNGARO EN LA TEORÍA DE ASIGNACIÓN

ESTUDIANTE:

ANDY ARIEL ICAZA ALCOCER

DOCENTE:

ING. FRANCISCO GIRON.

ÍNDICE

BONDADES DEL MÉTODO HÚNGARO EN LA TEORÍA DE ASIGNACIÓN        3

ORIGEN DEL MÉTODO HÚNGARO        3

PASOS:        4

EJEMPLO        5

Bibliografía        6

BONDADES DEL MÉTODO HÚNGARO EN LA TEORÍA DE ASIGNACIÓN

El procedimiento húngaro es un algoritmo que posibilita reducir los precios en un problema de mejora con base en la programación lineal. 

La finalidad del procedimiento húngaro es hallar los gastos mínimos de un grupo de labores que tienen que ser llevadas a cabo por los individuos más idóneos.

ORIGEN DEL MÉTODO HÚNGARO

[pic 3]

Este ha sido inspeccionado por James Munkres en 1957, y fue conocido a partir de entonces como el algoritmo Húngaro, el algoritmo de la asignación de Munkres, o el algoritmo de Kuhn-Munkres. 

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 muy lento más admisible.

PASOS: 

Los pasos a continuar permiten hacer el procedimiento húngaro de una forma simple usando una hoja de cálculo. Además, este esquema que mostramos dejará ver de manera universal el proceso que desarrollaremos en detalle en el ejemplo final.

• Como pasos anteriores, se debe dedicar a los individuos (filas) a una secuencia de proyectos (columnas). Además, se debe calcular los diferentes costes de cada plan en funcionalidad de quién lo haga y edificar con esta información una matriz (C).
• En la matriz (C) buscamos el costo mínimo de cada fila. Restamos este a todos los recursos de la fila y realizamos la misma operación con las columnas. Aparecerá una totalmente nueva matriz (C`) con los resultados de las operaciones anteriores.
• Después creamos el «grafo de igualdades», que nos posibilita elegir las labores y proyectos con menor precio. El óptimo podrían ser esos recursos cuya consecuencia ha sido cero. Si se cumple que no hay ningún componente con costo cero asignado a bastante más de una fila el algoritmo finaliza.
• En caso opuesto, se debe hacer una totalmente nueva asignación. Se hace una totalmente nueva a matriz a la que se utilizan una secuencia de modificaciones, como observaremos en el ejemplo. Volvemos a producir el grafo y avanzamos hasta que nos quede una matriz que tenga por lo menos un cero en cada fila y en posiciones no reiteradas.
• Con esta información ya poseemos a los individuos y los proyectos indicados (los ceros) que optimizan el problema. Si una labor ya está asignada en una fila anterior, en la siguiente se desecha. Para calcular los gastos mínimos sumamos los costes de la matriz inicial que aparecen en la postura de estos ceros.

EJEMPLO 

Veamos un sencillo ejemplo del procedimiento húngaro de. Imaginemos que poseemos 3 trabajadores y se debe asignarlos a 3 proyectos. Creamos la matriz inicial (C) y los valores de los costes en cada celda. Para esto se debe usar la información disponible en la organización. Una hoja de cálculo puede apoyar.

...