investigacion de operaciones


|


INTRODUCCION


EL algoritmo o método 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.
El algoritmo 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.
Este algoritmo se usa para resolver problemas de minimización, ya que es más eficaz que el empleado para resolver el problema del transporte por el alto grado de degeneración que pueden presentar los problemas de asignación.






Harold W. Kuhn
Harold William Kuhn (nacido en 1925) es un matemático americano que estudió teoría de juegos. Él ganó elpremio Premio de Teoría John von Neumann en 1980 junto con David Gale y Albert W. Tucker. Un 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 en1890 en latín, se ha descubierto que anticipa por muchas décadas el algoritmo húngaro.
Él es conocido por su asociación con John Forbes Nash, como estudiante graduado compañero, un amigo de toda la vida y colega, y una figura clave para lograr que Nash la atención del Premio Nobel comité que llevó a 1994 de Nash Premio Nobel de Economía. Kuhn y Nash ambos tenían un antiguo vínculo y lacolaboración con Albert W. Tucker , quien fue asesor de Nash disertación. Kuhn co-editó The Essential John Nash, y es reconocido como el consultor de matemáticas en la adaptación de película 2001 de la vida de Nash, Una mente maravillosa.
Su hijo mayor es historiador Clifford Kuhn, que destaca por su erudición en la América del Sur y para la recogida de la historia oral. Otro hijo, Nick Kuhn, es unprofesor de matemáticas en la Universidad de Virginia. Su hijo menor, Jonathan Kuhn, es Director de Arte y Antigüedades de la ciudad de Nueva York Departamento de Parques y Recreación.





Problemas de asignación


El problema 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 decirser 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 diversas situaciones, entre los que cabe mencionar se encuentran la asignación de personal a maquinas, herramientas apuestos de trabajos, horarios a maestros, candidatos a vacantes, huéspedes a habitaciones, comensales a mesas, vendedores a zonas territoriales etc.
En el modelo de asignación la idea fundamental de resolución es ¿qué fuente satisface mejor el destino?, y dado que hemos asociado el modelo a una gran diversidad de circunstancias esta pregunta puede plantearse en múltiples contextos, como ¿quécandidato es el idóneo para la vacante?, o ¿qué personal es el indicado para la línea productiva?, o ¿qué personal es el mejor para ejecutar determinada tarea?. Una característica particular del modelo de asignación es que para su resolución no se hace necesario que el número de fuentes sea igual al número de destinos, lo cual es muy común en la vida real teniendo en cuenta su aplicación, pues...