Docente: Carlos Ortega Muoz
Modelos de Asignacin
Thomas Jefferson en 1792 enunci un problema de
asignacin para asignar un representante a cada estado
El problema de asignacin es una variacin delproblema original de transporte, variacin en la cual
las variables de decisin X(i,j) solo pueden tomar
valores binarios, es decir ser cero (0) o uno (1) en la
solucin ptima, y que supone adems que es un
problema de transporte balanceado, en el cual todas
las ofertas y todas las demandas son iguales a uno acuyo efecto se aplica el mtodo Hngaro
La primera versin conocida del
mtodo Hngaro, fue inventado y
publicado por Harold Kuhn en 1955.
Este fue revisado por James Munkres
en 1957, y ha sido conocido desde
entonces como el algoritmo Hngaro.
Este algoritmo est basado
fundamentalmente en los primeros
trabajos de otros dos matemticos
Hngaros: Dnes Knig y JenEgervry.
CASO APLICATIVO
El equipo olmpico de natacin rene a 4 relevos para los
400 metros de nado combinado. Cada nadador debe nadar
100 metros estilo pecho, espalda, mariposa o libre. La
entrenadora Ins cree que cada nadador realizara los
tiempos dados segn la siguiente tabla:
Qu nadador debe nadar que estilo?
Cul seria el tiempo total del equipo?
Tiempo (Segundos)
Espalda Pecho Mariposa Libre
Juan 54 54 51 53
Cristian 51 57 52 52
Laura 50 53 54 56
Carlos 56 54 55 53
PASO 1: ENCONTRAR LA TABLA DE
COSTOS DE OPORTUNIDAD
Tabla de costos: En general, las filas contienen los objetos o personas a las que se desea
asignar y las columnas comprenden las tareas
o cosas que se desea asignarles.
Luego, se elabora la tabla de costos de oportunidad: Los costos de oportunidad en filas
y columnas reflejan el costo que se sacrifica por
no hacer la seleccin de menor costo
SE RESTA EL NUMERO MAS PEQUEO DE
CADA FILA DE CADA NUMERO EN ELLA:
Tiempo (Segundos)
Espalda Pecho Mariposa Libre Valor minimo por fila
Juan 54 54 51 53 51
Cristian 51 57 52 52 51
Laura 50 53 54 56 50
Carlos 56 54 55 53 53
Tiempo (Segundos)
Espalda Pecho Mariposa Libre
Juan 3 3 0 2
Cristian 0 6 1 1
Laura 0 3 4 6
Carlos 3 1 2 0
SE RESTA EL NUMERO MAS PEQUEO DE
CADA COLUMNA DE CADA NUMERO EN ELLA:
Tiempo (Segundos)
Espalda Pecho Mariposa Libre
Juan 3 3 0 2
Cristian 0 6 1 1
Laura 0 3 4 6
Carlos 3 1 2 0
valor minimo por columna 0 1 0 0
Tiempo (Segundos)
Espalda Pecho Mariposa Libre
Juan 3 2 0 2
Cristian 0 5 1 1
Laura 0 2 4 6
Carlos 3 0 2 0
NO OPTIMA:
NUMERO DE LNEAS < NUMERO DE FILAS O
COLUMNAS
Se prueba la tabla de costos de oportunidad para ver si esposible hacer las asignaciones optimas trazando el menornumero de lneas posibles en las columnas y/o filas de modoque los ceros queden cubiertos:
Tiempo (Segundos)
Espalda Pecho Mariposa Libre
Juan 3 2 0 2Cristian 0 5 1 1Laura 0 2 4 6Carlos 3 0 2 0
Paso 2: Prueba para determinar si una asignacin es optima
PASO 3: REVISAR LA TABLA DE COTOS DE
OPORTUNIDADa) Restar el numero mas pequeo no cubierto por una lnea
Tiempo (Segundos)
Espalda Pecho Mariposa Libre
Juan 3 2 0 2
Cristian 0 5 1 1
Laura 0 2 4 6
Carlos 3 0 2 0
Tiempo (Segundos)
Espalda Pecho Mariposa Libre
Juan 4 2 0 2
Cristian 0 4 0 0
Laura 0 1 3 5
Carlos 4 0 2 0
b) Sumar este numero a cada interseccin de dos lneas cualesquiera
Para probar ahora en busca de una asignacin optima, seregresa al paso 2 y se busca el numero mnimo de lneasnecesario para cubrir todos los ceros de la tabla de costos deoportunidad revisada. Como se requieren 4 lneas para cubrirlos ceros se puede hacer una asignacin optima.
TABLA DE COSTOS DE OPORTUNIDAD REVISADA:
Tiempo (Segundos)
Espalda Pecho Mariposa Libre
Juan 4 2 0 2
Cristian 0 4 0 0
Laura 0 1 3 5
Carlos 4 0 2 0
Los costos totales de asignacin se calculan a partir de la tabla de costos original segn
los tiempos empleados:
Asignacin Tiempo(segundos)
Nombre Estilo
Juan Mariposa 51
Cristian Libre 50
Laura Espalda 52
Carlos Pecho 54
Tiempo total: 207
El equipo olmpico de natacin tendra un tiempomnimo de 207 segundos, es decir, 3 minutos y 27segundos
NOTA: PROBLEMAS DE MAXIMIZACIN
EN ASIGNACIN
Algunos problemas de asignacin son planteados en trminos de maximizar la recompensa, utilidad o eficacia
de una asignacin en lugar de minimizar los costos.
Es fcil obtener un problema de minimizacin equivalente mediante la conversin de todos los
nmeros que hay en la tabla en costos de oportunidad
EJEMPLO:La armada peruana desea asignar tres buques para patrullar
tres sectores del mar peruano. En algunas reas los buques
tienen que estar al acecho de barcos pesqueros ilegales, en
otros sectores detectar la presencia de submarinos enemigos,
por lo que el comandante califica cada buque en funcin de su
probable eficiencia en cada sector. Esta eficiencia relativa se
muestra en el siguiente cuadro:
BUQUESECTOR
A B C
1 20 60 50
2 60 30 80
3 80 100 90
Primero se convierte la tabla de maximizacin de eficiencia en una tabla de minimizacin de costos de oportunidad.
Se resta cada calificacin de 100, la mayor calificacin en toda la tabla. Los costos de oportunidad resultantes son los
siguientes:
BUQUESECTOR
A B C
1 80 40 50
2 40 70 20
3 20 0 10
BUQUESECTOR
A B C
1 20 60 50
2 60 30 80
3 80 100 90
LUEGO SE SIGUEN LOS PASOS 1 Y 2
DEL PROBLEMA DE ASIGNACIN:
BUQUESECTOR Valor
mnimoA B C
1 80 40 50 40
2 40 70 20 20
3 20 0 10 0
BUQUESECTOR
A B C
1 40 0 10
2 20 50 0
3 20 0 10
BUQUESECTOR
A B C
1 40 0 10
2 20 50 0
3 20 0 10
Valor mnimo
20 0 0
BUQUESECTOR
A B C
1 20 0 10
2 0 50 0
3 0 0 10
Del paso 3 el numero mnimo de rectas necesarias para cubrir todos los ceros en esta
tabla de costos de oportunidad totales es tres:
BUQUESECTOR
A B C
1 20 0 10
2 0 50 0
3 0 0 10
Ahora se puede mostrar la eficiencia total, que se calcula a partir
de los datos de eficiencia originales de la primera tabla:
AsignacinEficiencia
Buque rea
1 B 60
2 C 80
3 A 80
Eficiencia total: 220
EXPLICACIN DEL MTODO
HNGARO CON EL MTODO
SIMPLEX
El problema de asignacin en el que n trabajadores se
asignan a n puestos se puede presentar como modelo de
programacin lineal en la forma siguiente:
Sea Cij el costo de asignar el trabajador i al puesto j, y sea:
Entonces el modelo de programacin lineal es:
Minimizar Z =
Sujeto a:
20Investigacin de operaciones