Características | Observación |
Historia del modelo | 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). La primera versión del metodo Hungaro, fue inventado y publicado por Harold Kuhn en 1955. Este fue revisado por James Munkres en 1957, y a sido conocedo desde entonces como el metodo Hungaro. |
Elementos | Es un caso particular del problema de transporte. Matriz de costos cuadrada (problema balanceado). La restricción más importante es que para cada agente se le asigna una y solo una tarea. El modelo de Asignación, requiere que que la matriz de costos sea cuadrada, es por ello que podemos agregar renglones o columnas con costos cero( para que sea cuadrada). Tiene que estar balanceado. Este consiste en determinar la asiganción óptima de agentes u objetos visibles a n tareas. Son indivisibles en el sentido de que ningún agente se puede dividir en varias tareas. La restricción importante, para que cada agente es que será designado a una y solo una tarea. Tratamos de minimizar los costos por asignación de recursos para el desempeño de las actividades.  Xi,j=0 o Xij=1 Estos pueden ser : · Oficinas a personal · Vehiculos a rutas · Vendedores a regiones · Productos a fabricas |
Ejemplo | En el problema siguiente, el objetivo es asignar personas a labores particulares mientras se minimiza el costo total. La función objetivo considera el costo que implica que cada persona realice una actividad en particular. La restricción dice que cada persona debe ser asignada a una actividad, y cada actividad debe ser asignada a solo una persona.  Luego de correr el problema en cualquier paquete que proporcione soluciones de programación lineal, los resultados son: Persona 1 debería ir al trabajo 3 Persona 2 debería ir al trabajo 4 Persona 3 debería ir al trabajo 5 Persona 4 debería ir al trabajo 1 Persona 5 debería ir al trabajo 2 El costo total es $55. |
Método de Solución | Los metodos de solucion son: · Metodo simplex · Tecnica de transporte · Metodo Hungaro Los Pasos del metodo Hngaro son: Paso 1.- Empiece por encontrar el elemento mas pequeño en cada renglón de la matriz de costos. Construya una nueva matriz, al restar de cada costo, el costo mínimo de su renglón. Encuentre, para esta nueva matriz el costo mínimo en cada columna. Construya una nueva matriz ( la matriz de costos reducidos ) al restar de cada costo el costo mínimo de su columna. Paso 2.- Dibuje el mínimo numero de líneas (horizontales o verticales ) que se necesitan para cubrir todos los ceros en la matriz de costos reducidos. Si se requieren m líneas para cubrir todos los ceros, siga con el paso 3. Paso 3.- Encuentre el menor elemento no cero (llame su valor k en la matriz de costos reducidos, que no esta cubiertos por las líneas dibujadas en el paso 2. Ahora reste k de cada elemento no cubierto de la matriz de costos reducidos y sume k a cada elemento de la matriz de costos reducidos cubierto por dos líneas. Regrese al paso 2. Un problema de asignación es un problema de transporte balanceado en el que todas las ofertas y demandas son iguales a 1; así se caracteriza por el conocimiento del costo de asignación de cada punto de oferta a cada punto de demanda. La matriz de costos del problema de asignación se llama: matriz de costos. Como todas las ofertas y demandas para el problema de asignación son números enteros, todas las variables en la solución óptima deben ser valores enteros. |
Programas existentes | · Tora · Lingo · Goms · Matlab · QMZ · Solver (Excel) · INVOP |
Referencias:
No hay comentarios:
Publicar un comentario