INVESTIGACIÓN DE
OPERACIONES
Unidad II
Programación Lineal
Tema: El problema de asignación
Objetivos
• Desarrollar modelos de programación lineal
aplicando métodos específicos.
El problema de asignación
• El modelo de asignación es un tipo especial de problema de programación
lineal en el que los asignados son recursos que se destinan a la realización de
tareas. Por ejemplo, los asignados pueden ser personas que pueden realizar
ciertas actividades (trabajo). Sin embargo, los asignados no tienen que ser
necesariamente personas. También pueden ser máquinas, vehículos o
plantas, o incluso periodos a los que se asignan tareas.
• “La mejor persona para el puesto” es una buena descripción del modelo de
asignación.
• Para que se ajuste a la definición de un problema de asignación, es necesario
que se cumplan los siguientes condiciones:
a) El número de asignados es igual al número de tareas. (Este número se
denota por n)
b) A cada asignado se le asigna solo una tarea.
c) Cada tarea debe realizarla solo por un asignado.
El problema de asignación
d) Existe un costo 𝑐𝑖𝑗 asociado con el asignado 𝑖 (𝑖 = 1,2 … , 𝑛) que realiza la
tarea 𝑗 (𝑗 = 1,2 … , 𝑛).
e) El objetivo es determinar cómo deben hacerse las n asignaciones para
minimizar los costos totales.
Las asignaciones se representarán por las variables binarias:
1, 𝑠𝑖 𝑒𝑙 𝑎𝑠𝑖𝑔𝑛𝑎𝑑𝑜 𝑖 𝑟𝑒𝑎𝑙𝑖𝑧𝑎 𝑙𝑎 𝑡𝑎𝑟𝑒𝑎 𝑗
𝑥𝑖𝑗 =
0, 𝑠𝑖 𝑒𝑙 𝑎𝑠𝑖𝑔𝑛𝑎𝑑𝑜 𝑖 𝑛𝑜 𝑟𝑒𝑎𝑙𝑖𝑧𝑎 𝑙𝑎 𝑡𝑎𝑟𝑒𝑎 𝑗
Es recomendable que los costos se indiquen en una matriz:
𝑐11 𝑐12 ⋯ 𝑐1𝑛
𝑐21 𝑐22 ⋯ 𝑐2𝑛
𝐶= ⋮ ⋮ ⋮ ⋮
𝑐𝑛1 𝑐𝑛2 ⋯ 𝑐𝑛𝑛
El problema de asignación
Luego el costo total será:
𝑍 = 𝑐11 𝑥11 + 𝑐12 𝑥12 + ⋯ + 𝑐𝑛𝑛 𝑥𝑛𝑛
Como cada asignado debe realizar una sola tarea, por ejemplo tenemos para
el primer asignado:
𝑥11 + 𝑥12 + ⋯ + 𝑥1𝑛 =1
De manera similar cada tarea solo puede ser realizada por un asignado, por
ejemplo para la primera tarea tenemos:
𝑥11 + 𝑥21 + ⋯ + 𝑥𝑛1 =1
El problema de asignación
por lo cual el modelo matemático del problema es:
𝑀í𝑛 𝑍 = 𝑐11 𝑥11 + 𝑐12 𝑥12 + ⋯ +𝑐1𝑛 𝑥1𝑛 + 𝑐21 𝑥21 + ⋯ +𝑐2𝑛 𝑥2𝑛 … + 𝑐𝑛𝑛 𝑥𝑛𝑛
s.a:
𝑥11 + 𝑥12 + ⋯ + 𝑥1𝑛 =1
𝑥21 + 𝑥22 + ⋯ + 𝑥2𝑛 =1
⋮
𝑥𝑛1 + 𝑥𝑛2 + ⋯ + 𝑥𝑛𝑛 =1
𝑥11 + 𝑥21 + ⋯ + 𝑥𝑛1 =1
𝑥12 + 𝑥22 + ⋯ + 𝑥𝑛2 =1
⋮
𝑥1𝑛 + 𝑥2𝑛 + ⋯ + 𝑥𝑛𝑛 =1
𝑥𝑖𝑗 = 0 𝑜 1 , 𝑖 = 1, … , 𝑛; 𝑗 = 1, … , 𝑛
El problema de asignación
Para resolver este tipo de problemas, utilizaremos el método Húngaro.
Método Húngaro
1) En la matriz original de costo, identificar el mínimo de cada renglón y restarlo
de todos los elementos del renglón.
2) En la matriz que resulte del paso 1, identificar el mínimo de cada columna, y
restarlo de todos los elementos de la columna.
3) Trazar la cantidad mínima de líneas horizontales o verticales en la última
matriz reducida que cubran todos los elementos cero:
a) Si la cantidad mínima de rectas trazadas es igual a n, tenemos la solución;
se identifica la solución óptima como la asignación factible asociada con los
elementos cero de la matriz final.
b) En caso contrario seleccionamos el elemento mínimo no cubierto, restarlo
a todo elemento no cubierto y a continuación sumarlo a todo elemento en la
intersección de líneas, volvemos al paso 3.
El problema de asignación
Nota
• La asignación no siempre es única, pero el costo mínimo si es único.
• El trazado de rectas horizontales o verticales tampoco es único, mientras sea
la menor cantidad de rectas trazadas el procedimiento es correcto.
El problema de asignación
Ejemplo 1:
Un equipo de 3 mecánicos debe ser asignado para la realización de 3 tareas,
donde cada mecánico debe hacer una tarea. Se requiere encontrar la
asignación de costo mínimo para lo cual se dispone de los costos asociados a
los mecánicos con las tareas:
Tarea 1 Tarea 2 Tarea 3
Mecánico 1 15 10 9
Mecánico 2 9 15 10
Mecánico 3 10 12 8
Solución:
La matriz de costos obtenida es:
15 10 9
C = 9 15 10
10 12 8
El problema de asignación
Restando los menores de cada fila obtenemos:
15 10 9 9 6 1 0
9 15 10 9 ⟹ 0 6 1
10 12 8 8 2 4 0
Restando los menores de cada columna obtenemos:
6 1 0 6 0 0
0 6 1 ⟹ 0 5 1
2 4 0 2 3 0
0 1 0
Ahora trazamos la menor cantidad de rectas que cubran los ceros:
6 0 0
0 5 1
2 3 0
El problema de asignación
Como son tres la cantidad mínima de rectas trazadas (igual a n) , ya tenemos
la solución, buscamos los ceros únicos por fila, y la variable asociada a dicha
posición toma el valor de 1:
Fila 2: 𝑥21 = 1
Fila 3: 𝑥33 = 1
Por defecto 𝑥12 = 1
Ahora tomamos los costos correspondientes y hallamos el costo mínimo:
𝐶𝑜𝑠𝑡𝑜 𝑚í𝑛𝑖𝑚𝑜 = 𝑐12 + 𝑐21 + 𝑐33 = 10 + 9 + 8 = 27
El problema de asignación
Ejemplo 2:
Halle la asignación óptima, así como el costo correspondiente para el
problema cuyo matriz de costos es:
12 10 15 16
8 9 7 10
20 18 22 20
30 25 28 26
Solución:
Restando los menores de cada fila obtenemos:
12 10 15 16 10 2 0 5 6
8 9 7 10 7 ⟹ 1 2 0 3
20 18 22 20 18 2 0 4 2
30 25 28 26 25 5 0 3 1
El problema de asignación
Restando los menores de cada columna obtenemos:
2 0 5 6 1 0 5 5
1 2 0 3 ⟹ 0 2 0 2
2 0 4 2 1 0 4 1
5 0 3 1 4 0 3 0
1 0 0 1
Ahora trazamos la menor cantidad de rectas que cubran los ceros:
1 0 5 5
0 2 0 2
1 0 4 1
4 0 3 0
Como son tres la cantidad mínima de rectas trazadas (distinto a n) , buscamos
el menor elemento no cubierto, en este caso es 1 restamos a los elementos
no cubiertos y sumamos a los de la intersección:
El problema de asignación
0 0 4 4
0 3 0 2
0 0 3 0
4 1 3 0
Volvemos a trazar la menor cantidad de rectas que cubran los ceros:
0 0 4 4
0 3 0 2
0 0 3 0
4 1 3 0
Como son cuatro la cantidad mínima de rectas trazadas (igual a n) , tenemos
la solución; buscamos los ceros únicos por fila, y la variable asociada a dicha
posición toma el valor de 1:
Fila 4: 𝑥44 = 1
El problema de asignación
Buscamos los ceros únicos por columna, y la variable asociada a dicha
posición toma el valor de 1:
Columna 3: 𝑥23 = 1
Aun faltan los valores de dos variables, considerando la primera fila existen
dos ceros; si 𝑥11 = 1 entonces 𝑥32 = 1, si 𝑥12 = 1 entonces 𝑥31 = 1 .
Por lo tanto tenemos asignaciones distintas:
a) 𝑥11 = 1, 𝑥23 = 1, 𝑥32 = 1, 𝑥44 = 1
b) 𝑥12 = 1, 𝑥23 = 1, 𝑥31 = 1, 𝑥44 = 1
𝐶𝑜𝑠𝑡𝑜 𝑚í𝑛𝑖𝑚𝑜 = 𝑐11 + 𝑐23 + 𝑐32 + 𝑐44 = 12 + 7 + 18 + 26 = 63
𝐶𝑜𝑠𝑡𝑜 𝑚í𝑛𝑖𝑚𝑜 = 𝑐12 + 𝑐23 + 𝑐31 + 𝑐44 = 10 + 7 + 20 + 26 = 63
Bibliografía:
