Introducción 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. Los problemas de transporte y asignación son casos particulares de un grupo más grande de problemas, llamados problemas de flujo en redes.
Introducción El problema de asignación es un tipo especial de problema de programación lineal en el que los asignados son recursos destinados a la realización de tareas Ej. Empleados a trabajo Máquinas a tareas Períodos a tareas
Supocisiones de un problema de asignación
1. El número de asignados es igual al número de 2. 3.
4. 5.
tareas (se denota por n). (esto puede variar) Cada asignado se asigna exactamente a una tarea. Cada tarea debe realizarla exactamente un asignado. Existe un costo cij asociado con el asignado i (i=1,2,…,n). El objetivo es determinar cómo deben hacerse las asignaciones para minimizar los costos totales.
Caso Fowle Marketing Research Tiempos estimados de terminación del proyecto (días) Jefe de Cliente Proyecto 1 2 3 1. Terry 10 15 9 2. Carla 9 18 5 3. Roberto 6 14 3
Problema de la Fowle Representación en Red Jefes de Proyecto
Nodos de Origen
Asignaciones Posibles
Clientes
Nodos de Destino
Arcos
[1] J1
C1 [1]
[1] J2
18
C2 [1]
[1] J3
3
C3 [1]
Variables de decisión
1 si se asigna el jefe de proyecto i al cliente j xij 0 si no es así
Planteamiento matemático Sea Z tiempo total de terminación
M in Z 10 x11 15 x12 9 x13 9 x21 18 x22 5 x23 6 x31 14 x32 3 x33 Sujeta a las restriccio nes x11 x12 x13 1 x21 x22 x23 1 x31 x32 x33 1 x21
Representación de red para el problema general [1] S1
[1] S2
c21
c11 c12 c1n
c2n
c22
cm1 cm2 cmn [1] Sm
D1 [1]
D2 [1]
Dm [1]
Planteamiento matemático modelo general m
n
min Z cij xij i 1 j 1
sujeta a n
x j 1
ij
m
x j 1
ij
1 para i 1,2,..., m, 1 para j 1,2,..., n,
xij 0, para i y j ( xij binarias, para toda i y j ).
Problema Natación El entrenador de un equipo de natación debe asignar competidores para la prueba de 200 metros de relevo combinado que irán a las Olimpiadas Juveniles. Como muchos de sus mejores nadadores son rápidos en más de un estilo, no es fácil decidir qué nadador asignar a cada uno de los cuatro estilos. Los cinco mejores nadadores y sus mejores tiempos (en segundos) en cada estilo son los siguientes.
Dorso Pecho Mariposa Libre
Carlos 37.7 43.4 33.3 29.2
Tiempo de Nado Cristy David Antony 32.9 33.8 37 33.1 42.2 34.7 28.5 38.9 30.4 26.4 29.6 28.5