Problema de Asignación
Un problema de asignación es un problema de transporte equilibrado en el que los
diferentes suministros y las diversas demandas son iguales a 1.
Supuestos del problema de asignación son:
1. El número de asignados es igual al número de tareas.
2. A cada colaborador se le asigna sólo una tarea.
3. Cada tarea debe realizarla sólo un colaborador.
4. Existe un costo cij asociado con el colaborador i (i=1, 2, 3, …,n) que realiza la
tarea j (j=1, 2, 3, …, n).
5. El objetivo es determinar cómo deben hacerse las n asignaciones para minimizar
los costos totales.
Cualquier problema que satisface estos supuestos se puede resolver en forma eficiente
mediante el algoritmo húngaro diseñado especialmente para problemas de asignación.
Algoritmo húngaro
Paso 1. Encontrar el elemento mínimo en cada renglón de la matriz de costos nxn.
Construir una nueva matriz restando de cada costo el costo mínimo en su renglón. Para
esta nueva matriz, determinar el costo mínimo en cada columna. Construir una nueva
matriz (llamada matriz de costos reducida) restando de cada costo el costo mínimo en la
columna.
Paso 2. Trazar un número mínimo de líneas (horizontales, verticales o ambas) que son
necesarias para cubrir todos los ceros en la matriz de costos reducida. Si se requieren n
líneas, entonces se llegó a una solución óptima entre los ceros cubiertos en la matriz. Si
son necesarias menos líneas, entonces se aplica le paso 3.
Paso 3. Identificar el mínimo costo entre los costos no cubiertos con alguna línea
horizontal o vertical. Se resta este costo a los costos que no están cubiertos por las
líneas. Además, su suma este mínimo costo a los costos que se cruzan dos veces o que
son cubiertos por dos líneas. Si el número de líneas es igual al número de asignados,
entonces se tiene una solución óptima, sino se repite el paso 3.
Ejemplo: Problema de asignación de máquinas
Machineco tiene cuatro máquinas y cuatro tareas que completar. Cada máquina se debe
asignar para completar una tarea. El tiempo requerido para preparar cada máquina para
completar cada tarea se muestra en la tabla 1. Machineco desea reducir el tiempo de
preparación total necesario para completar las cuatro tareas.
Tabla 1. Tiempos de preparación para Machineco (tiempo en horas)
Máquina Tarea 1 Tarea 2 Tarea 3 Tarea 4
1 14 5 8 7
2 2 12 6 5
3 7 8 3 9
4 2 4 6 10
Solución:
1er paso. Identificar el mínimo costo por renglón y restarlo al resto de los valores.
Máquin Tarea Tarea Tarea Tarea Mínim
a 1 2 3 4 o
1 14 5 8 7 5
2 2 12 6 5 2
3 7 8 3 9 3
4 2 4 6 10 2
Matriz reducida por renglón
Máquin Tarea Tarea Tarea Tarea Mínim
a 1 2 3 4 o
1 9 0 3 2 5
2 0 10 4 3 2
3 4 5 0 6 3
4 0 2 2 8 2
Identificar el mínimo costo por columna y restarlo al resto de los valores
Máquin Tarea Tarea Tarea Tarea
a 1 2 3 4
1 9 0 3 2
2 0 10 4 3
3 4 5 0 6
4 0 2 2 8
Mínimo 0 0 0 2
Matriz reducida por columna
Máquin Tarea Tarea Tarea Tarea
a 1 2 3 4
1 9 0 3 0
2 0 10 4 1
3 4 5 0 4
4 0 2 2 6
Mínimo 0 0 0 2
2do paso. Trazar el mínimo número de líneas horizontales o verticales para cubrir todos
los ceros en la matriz.
Máquin Tarea Tarea Tarea Tarea
a 1 2 3 4
1 9 0 3 0
2 0 10 4 1
3 4 5 0 4
4 0 2 2 6
Como el número de líneas es menor al número de tareas (son cuatro tareas), entonces no
se tiene una solución óptima y se requiere aplicar el paso 3.
3er paso. Identificar el mínimo costo entre los valores no cubiertos por las líneas. Se resta
este al resto de los costos y se suma a los costos en las intersecciones de las rectas. Se
vuelven a trazar las líneas horizontales y/o verticales para cubrir todos los ceros.
El mínimo costo entre los valores no cubiertos es el 1, por lo tanto se resta este valor a los
demás.
Máquin Tarea Tarea Tarea Tarea
a 1 2 3 4
1 10 0 3 0
2 0 9 3 0
3 5 5 0 4
4 0 1 1 5
Como el número de líneas es igual al número de tareas, se tiene una solución óptima.
¿Cómo leer la solución? O ¿cómo asignar las máquinas a las tareas? La asignación se
realiza en las celdas donde se tiene el valor de cero; aunque, se debe primero asignar las
tareas donde sólo haya un cero en el renglón o columna. Así, por ejemplo, en la columna
de la tarea 3 sólo hay un cero en la celda x33, por lo que x33=1; en la columna 2 de la tarea
2, también sólo existe un cero en la celda x12, por lo que x12=1. En el cuarto renglón sólo
existe un cero en la celda x41, por lo que x41=1 y finalmente x24=1.
Resolviendo el mismo problema como un modelo transporte.
Máquina Tarea 1 Tarea 2 Tarea 3 Tarea 4 Suministro
1 14 5 8 7 1
2 2 12 6 5 1
3 7 8 3 9 1
4 2 4 6 10 1
Demanda 1 1 1 1
Máquina Tarea 1 Tarea 2 Tarea 3 Tarea 4 Suministro
1 0 1 0 0 1 = 1
2 0 0 0 1 1 = 1
3 0 0 1 0 1 = 1
4 1 0 0 0 1 = 1
1 1 1 1
= = = =
Demanda 1 1 1 1 15
Seguir con esta política de asignación de máquinas para realizar las tareas, se esperaría
que se tardaran 15 horas en todas las operaciones. Solución óptima Z = 15, x12=1, x24=1,
x33=1 y x41=1.
Ejemplo 2.
Se cuenta con cinco empleados para llevar a cabo cuatro tareas. El tiempo que toma a
cada persona realizar cada tarea se da en la siguiente tabla. Determine la asignación de
empleados a las tareas que reduce el tiempo total requerido para efectuar las cuatro
tareas.
Tabla 1.
Persona Tarea 1 Tarea 2 Tarea 3 Tarea 4
1 22 18 30 18
2 18 - 27 22
3 26 20 28 28
4 16 22 - 14
5 21 - 25 28
Resolución a través del método húngaro
1er paso. Dado que el número de personas es mayor al número de tareas, se debe
equilibrar el problema generando una tarea ficticia. La tarea ficticia tendrá un tiempo de
realización de 0, porque esta tarea no la tendría que realizar el trabajador cuando se le
asigne.
Person Tarea Tarea Tarea Tarea Tarea
a 1 2 3 4 ficticia
1 22 18 30 18 0
2 18 - 27 22 0
3 26 20 28 28 0
4 16 22 - 14 0
5 21 - 25 28 0
También, dado que la persona 2 no puede realizar la tarea 2, señalada con un guion,
entonces se considera que tendría un costo muy alto, o un costo M.
Person Tarea Tarea Tarea Tarea Tarea
a 1 2 3 4 ficticia
1 22 18 30 18 0
2 18 M 27 22 0
3 26 20 28 28 0
4 16 22 M 14 0
5 21 M 25 28 0
El costo mínimo en todos los renglones es 0, por lo que no se realiza la matriz reducida
por renglón, porque daría el mismo valor.
Se identifica el mínimo costo por columna
Person Tarea Tarea Tarea Tarea Tarea
a 1 2 3 4 ficticia
1 22 18 30 18 0
2 18 M 27 22 0
3 26 20 28 28 0
4 16 22 M 14 0
5 21 M 25 28 0
Mínimo 16 18 25 14 0
Matriz reducida por columna
Person Tarea Tarea Tarea Tarea Tarea
a 1 2 3 4 ficticia
1 6 0 5 4 0
2 2 M 2 8 0
3 10 2 3 14 0
4 0 4 M 0 0
5 5 M 0 14 0
Mínimo 16 18 25 14 0
2do paso. Trazar las rectas para cubrir todos los ceros
Person Tarea Tarea Tarea Tarea Tarea
a 1 2 3 4 ficticia
1 6 0 5 4 0
2 2 M 2 8 0
3 10 2 3 14 0
4 0 4 M 0 0
5 5 M 0 14 0
Como el número de líneas es menor al número de tareas, entonces se debe aplicar el
paso 3.
3er paso. Se identifica el mínimo valor entre los tiempos no cubiertos. El mínimo valor es
2, el cual se resta a los costos no cubiertos y se suman en las intersecciones. Se vuelven
a trazar las líneas horizontales y verticales.
Person Tarea Tarea Tarea Tarea Tarea
a 1 2 3 4 ficticia
1 6 0 5 4 2
2 0 M 0 6 0
3 8 0 1 12 0
4 0 4 M 0 2
5 5 M 0 14 2
Como el número de rectas es igual al número de tareas, se tiene una solución óptima.
Para hacer la asignación se puede observar que el único 0 en la columna 4 es x44 por lo
que x44=1, en el renglón 1 el único cero está en x12, por lo que x12=1 y en el renglón 5,
x53=1. El resto de las asignaciones podrían ser arbitrarias, x21=1 y x35=1.
Resolviendo como un problema de transporte
Tarea Suministr
Persona Tarea 1 Tarea 2 Tarea 3 Tarea 4
ficticia o
1 22 18 30 18 0 1
2 18 10000 27 22 0 1
3 26 20 28 28 0 1
4 16 22 10000 14 0 1
5 21 10000 25 28 0 1
Demand
1 1 1 1 1
a
Tarea Suministr
Persona Tarea 1 Tarea 2 Tarea 3 Tarea 4
ficticia o
1 0 1 0 0 0 1 = 1
2 1 0 0 0 0 1 = 1
3 0 0 0 0 1 1 = 1
4 0 0 0 1 0 1 = 1
5 0 0 1 0 0 1 = 1
1 1 1 1 1
= = = = =
Demand
1 1 1 1 1
a 75
El tiempo total con esta asignación sería de 75 horas.