PROBLEMA DE ASIGNACIÓN
El problema de asignación es encontrar
un emparejamiento de peso máximo en un grafo bipartido ponderado. Es uno de los
problemas fundamentales de optimización combinatoria de la rama de optimización
o investigación operativa en matemática.
Una descripción apropiada de lo
que trata de lograr el modelo de asignación es:
“La mejor persona para el
trabajo”
El problema de asignación tiene
que ver con la designación de tareas a empleados, de territorios a vendedores,
de contratos a postores o de trabajos a plantas, etc. En otras palabras, a la
disposición de algunos recursos(máquinas o personas) para la realización de
ciertos productos a 'costo mínimo.
Una definición más formal
pudiera ser:
Problema de Asignación: Caso
particular del problema de Transporte donde los asignados son recursos destinados
a la realización de tareas, los asignados pueden ser personas, máquinas,
vehículos, plantas o períodos de tiempo. En estos problemas la oferta en cada
origen es de valor 1 y la demanda en cada destino es también de valor 1.
El problema de asignación tuvo
su origen en la revolución industrial, ya que el surgimiento de las máquinas
hizo que fuera necesario asignar una tarea a un trabajador.
Thomas Jefferson en 1792 lo
sugirió para asignar un representante a cada estado, pero formalmente aparece
este problema en 1941, cuando F.L. Hitchcook publica una solución analítica del
problema, pero no es hasta 1955 cuando Harold W. Kuhn plantea el Método
húngaro, que fue posteriormente revisado por James Munkres en 1957; dicho
método está basado fundamentalmente en los primeros trabajos de otros dos
matemáticos húngaros: Dénes Köning y Jenö Egervary.
Hoy en día en pleno apogeo de la
globalización este problema surge cada vez con mayor frecuencia el uso de este
problema de la rama de la investigación de operaciones, podemos decir que es la
aplicación del método científico para asignar los recursos o actividades de
forma eficaz, en la gestión y organización de sistemas complejos, su objetivo
es ayudar a la toma de decisiones.
EL algoritmo Húngaro es un
algoritmo de optimización el cual resuelve problemas de asignación en
tiempo O(n^3\,). 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.
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.
El algoritmo modela un problema
de asignación como una matriz de costes n×m, donde cada elemento representa el
coste de asignar el enésimo trabajador al emésimo trabajo. Por defecto, el
algoritmo realiza la minimización de los elementos de la matriz; de ahí que en
caso de ser un problema de minimización de costes, es suficiente con comenzar
la eliminación de Gauss-Jordan para hacer ceros (al menos un cero por línea y
por columna). Sin embargo, en caso de un problema de maximización del
beneficio, el coste de la matriz necesita ser modificado para que la
minimización de sus elementos lleve a una maximización de los valores de coste
originales. En un problema de costes infinito, el coste inicial de la matriz
puede ser remodelado restando a cada elemento de cada línea el valor máximo del
elemento de esa línea (o análogamente columna ). En un problema de coste
infinito, todos los elementos son restados por el valor máximo de la matriz
entera. En la matriz se tiene que realizar un conjunto de operaciones que nos
permitirán conocer con mejor eficacia el resultado final de la problemática
planteada.
