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