Inv de operaciones
Páginas: 5 (1218 palabras)
Publicado: 27 de mayo de 2011
MÉTODO HÚNGARO PARA LA ASIGNACIÓN
EL algoritmo Húngaro es un algoritmo de optimización el cual resuelve problemas de asignación en tiempo . La primera versión conocida del método Húngaro, fue inventado y publicado por Harold 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 elalgoritmo 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 construye una solución del problema primal partiendo de una solución no admisible (quecorresponde a una solución admisible del dual) haciéndola poco a poco más admisible.
Algoritmo
Dada la matriz de costes , se construye encontrando el valor mínimo de cada fila y restando ese valor a cada elemento de la fila.
Se encuentra el valor mínimo de cada columna y se resta a cada elemento de la columna.
A partir de se considera "grafo de las igualdades" a tal que estáconstituido por todas las copias tales que . En otras palabras, verificamos si para todas las filas existe una columna con costo 0 que no ha sido asignada a otra fila.
Determinar sobre un matching de cardinalidad máxima.
Si
Si todas las filas tienen a lo menos una intersección con costo cero que no ha sido ocupada por otra fila, estamos en el óptimo. Termina el algoritmo.
Considero y seetiquetan las filas que no han sido acopladas o asignadas por el algoritmo de matching máximo.
Se etiquetan en las columnas que tienen los ceros en correspondencia o asignadas a las filas etiquetadas (con *).
Etiquetar las filas que no han sido ya etiquetadas y acopladas o asignadas por el algoritmo de matching máximo con las columnas ya etiquetadas (con *).
Repetir los pasos y hasta que nohalla más filas o columnas que etiquetar.
Borrar las filas etiquetadas y las columnas NO etiquetadas. Para esto puede trazar una línea recta en las columnas y filas borradas.
Sea el elemento de de valor mínimo entre aquellos costos no borrados (o tarjados) en el paso anterior.
Restar a cada elemento no borrado y sumarlo a los elementos doblemente borrados (o donde haya intersección o crucesentre las líneas marcadas en el paso )
Volver al paso .
Ejemplo
En un cierto punto del algoritmo tenemos el grafo y la matriz .
Matching máximo del grafo de las igualdades.
En tengo un arco tengo un en .
Es matching máximo pero no es perfecto, pues la fila 3 está sin asignar. Volvemos al paso del algoritmo.
El matching de las columnas y esta acopladasal de las filas y
Resto a los elementos no borrados de y sumo a los elementos doblemente borrados de .
Volvemos al paso , para recrear el grafo de las igualdades y calcular de nuevo el matching máximo.
Ejemplo 2 Problema de minimización
Enunciado del problema: En una empresa existen N tareas a realizar y N personas que pueden realizarlas. Tenemos unamatriz N×N que contiene el coste de asignar a cada trabajador en cada tarea, en el presente caso, se supone que existen cuatro operarios (a, b, c y d) y cuatro tareas a realizar (1,2,3 y 4). El problema estriba en encontrar que tarea debemos asignar a cada trabajador para que el coste total sea mínimo. En primer lugar debemos partir de una matriz como la siguiente:
Donde a, b, c y d son lostrabajadores que deben ejecutar las distintas tareas 1, 2, 3 y 4. En la matriz a1 representa el coste en que se incurre si el trabajador A, desarrolla la tarea 1, a2, a3, a4 muestra el coste en que se incurre cuando el trabajador A ejecuta las tareas 1, 2, 3, 4 respectivamente. De la misma forma sucede para el resto de los trabajadores. La matriz es cuadrada de manera que cada trabajador puede...
EL algoritmo Húngaro es un algoritmo de optimización el cual resuelve problemas de asignación en tiempo . La primera versión conocida del método Húngaro, fue inventado y publicado por Harold 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 elalgoritmo 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 construye una solución del problema primal partiendo de una solución no admisible (quecorresponde a una solución admisible del dual) haciéndola poco a poco más admisible.
Algoritmo
Dada la matriz de costes , se construye encontrando el valor mínimo de cada fila y restando ese valor a cada elemento de la fila.
Se encuentra el valor mínimo de cada columna y se resta a cada elemento de la columna.
A partir de se considera "grafo de las igualdades" a tal que estáconstituido por todas las copias tales que . En otras palabras, verificamos si para todas las filas existe una columna con costo 0 que no ha sido asignada a otra fila.
Determinar sobre un matching de cardinalidad máxima.
Si
Si todas las filas tienen a lo menos una intersección con costo cero que no ha sido ocupada por otra fila, estamos en el óptimo. Termina el algoritmo.
Considero y seetiquetan las filas que no han sido acopladas o asignadas por el algoritmo de matching máximo.
Se etiquetan en las columnas que tienen los ceros en correspondencia o asignadas a las filas etiquetadas (con *).
Etiquetar las filas que no han sido ya etiquetadas y acopladas o asignadas por el algoritmo de matching máximo con las columnas ya etiquetadas (con *).
Repetir los pasos y hasta que nohalla más filas o columnas que etiquetar.
Borrar las filas etiquetadas y las columnas NO etiquetadas. Para esto puede trazar una línea recta en las columnas y filas borradas.
Sea el elemento de de valor mínimo entre aquellos costos no borrados (o tarjados) en el paso anterior.
Restar a cada elemento no borrado y sumarlo a los elementos doblemente borrados (o donde haya intersección o crucesentre las líneas marcadas en el paso )
Volver al paso .
Ejemplo
En un cierto punto del algoritmo tenemos el grafo y la matriz .
Matching máximo del grafo de las igualdades.
En tengo un arco tengo un en .
Es matching máximo pero no es perfecto, pues la fila 3 está sin asignar. Volvemos al paso del algoritmo.
El matching de las columnas y esta acopladasal de las filas y
Resto a los elementos no borrados de y sumo a los elementos doblemente borrados de .
Volvemos al paso , para recrear el grafo de las igualdades y calcular de nuevo el matching máximo.
Ejemplo 2 Problema de minimización
Enunciado del problema: En una empresa existen N tareas a realizar y N personas que pueden realizarlas. Tenemos unamatriz N×N que contiene el coste de asignar a cada trabajador en cada tarea, en el presente caso, se supone que existen cuatro operarios (a, b, c y d) y cuatro tareas a realizar (1,2,3 y 4). El problema estriba en encontrar que tarea debemos asignar a cada trabajador para que el coste total sea mínimo. En primer lugar debemos partir de una matriz como la siguiente:
Donde a, b, c y d son lostrabajadores que deben ejecutar las distintas tareas 1, 2, 3 y 4. En la matriz a1 representa el coste en que se incurre si el trabajador A, desarrolla la tarea 1, a2, a3, a4 muestra el coste en que se incurre cuando el trabajador A ejecuta las tareas 1, 2, 3, 4 respectivamente. De la misma forma sucede para el resto de los trabajadores. La matriz es cuadrada de manera que cada trabajador puede...
Leer documento completo
Regístrate para leer el documento completo.