Asignación por el Método Húngaro

Los problemas de asignación
incluyen aplicaciones tales
como asignar personas a
tareas. Aunque sus
aplicaciones parecen diferir de
las del problema del
transporte, constituye un caso
particular.
Losproblemas de transporte y
asignación son casos
particulares de un grupo más
grande de problemas, llamados
problemas de flujo en redes

Asignación
por el Método
Húngaro



Mukti Ernani CorreaMendoza
Edgar Hernández
Martínez

Suposiciones de un Problema
de Asignación
1. El número de asignados es igual al número de
tareas (se denota por n). (esto puede variar).
 2. Cada asignado se asignaexactamente a una
tarea.
 3. Cada tarea debe realizarla exactamente un
asignado.
 4. Existe un costo cij asociado con el asignado i
(i=1,2,…,n).
 5. El objetivo es determinar cómo deben hacerse
lasasignaciones para minimizar los costos totales.


Pasos a Resolver


1. A todos los elementos de cada columna restar el
menor elemento de la columna. En la matriz
resultante, restar a todos loselementos de cada
fila el menor elemento de la fila. Así se garantiza
la obtención de por lo menos un cero en cada fila y
columna.



2. Con la matriz resultante, verificar la existencia
de una soluciónóptima. Para encontrarla se debe
asignar un cero a cada fila (comenzando por las
que tengan menor Nº de ceros), y cancelar los
demás ceros de esa fila y los ceros de la columna
en la que se encuentra esecero. Repetir esta
operación hasta que no queden ceros sin asignar o
cancelar. Si no existe solución óptima ir al paso 3. .

Pasos a Resolver
3. Realizar lo siguiente:
 a) Marcar con un * todas lafilas que no
contengan ceros asignados.
 b) Marcar todas las columnas que
contengan uno o más ceros cancelados en
alguna fila marcada.
 c) Marcar toda fila que tenga un cero
asignado en una columnamarcada.
 d) Repetir b) y c) hasta que no sea posible
marcar más filas o columnas.
 e) Poner un trazo (línea) sobre toda fila no
marcada y sobre toda columna marcada.


Pasos a Resolver
 Tomar...