problemas de asignacion.docx
TRANSCRIPT
-
7/30/2019 PROBLEMAS DE ASIGNACION.docx
1/7
PROBLEMAS DE ASIGNACION:
1. 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 tabla adjunta.
Determinar la asignacin de empleados a las tareas que reducen el tiempo
total requerido para efectuar las cuatro tareas:
*Nota: Los guiones indican que la persona no puede hacer esa tarea particular.
Solucin:
Nuevo cuadro de asignacin de tiempos:
Elaboramos la matriz de costos balanceada:
22 18 30 18 018 M 27 22 0
26 20 28 28 0
16 22 M 14 0
21 M 25 28 0
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
Tiem o horas
Persona Tarea 1 Tarea 2 Tarea 3 Tarea 4 Ficticio
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
Tiem o horas
T1 T2 T3 T4 T5
P1P2
P3
P4
P5
-
7/30/2019 PROBLEMAS DE ASIGNACION.docx
2/7
Construimos una nueva matriz restando de cada costo el costo mnimo en su
fila (stos aparecen con rojo en la matriz anterior).
22 18 30 18 018 M 27 22 0
26 20 28 28 0
16 22 M 14 0
21 M 25 28 0
Construimos una nueva matriz restando de cada costo el costo mnimo en su
columna (stos aparecen con rojo en la matriz anterior).
6 0 5 4 02 M 2 8 0
10 2 3 14 0
0 4 M 0 0
5 M 0 14 0
Verificamos la optimalidad trazando el menor nmero de lneas que puedan
pasar a travs de todos los ceros. Las lneas pueden ser horizontales o
verticales, pero no diagonales. Si el nmero de lneas trazadas es igual al
nmero de filas o columnas de la matriz se habr determinado la solucin
ptima.
6 0 5 4 02 M 2 8 0
10 2 3 14 0
0 4 M 0 0
5 M 0 14 0
El tablero no es ptimo
Seleccionamos el elemento ms pequeo de entre los que no fueron cruzados
por las lneas, restarlo de estos que no fueron cruzados y sumarlo a aquellos
que son cruzados por dos lneas (intersecciones), los dems permanecen
inalterables.
T1 T2 T3 T4 T5
P1P2
P3
P4
P5
T1 T2 T3 T4 T5
P1P2
P3
P4
P5
T1 T2 T3 T4 T5
P1P2
P3
P4
P5
-
7/30/2019 PROBLEMAS DE ASIGNACION.docx
3/7
6 0 5 4 20 M 0 6 0
8 0 1 12 0
0 4 M 0 2
5 M 0 14 2
Verificamos la optimalidad.
6 0 5 4 20 M 0 6 0
8 0 1 12 0
0 4 M 0 2
5 M 0 14 2
El tablero es ptimo
Asignacin: La asignacin se debe hacer en las celdas donde haya ceros
cuidando que cada rengln y cada columna tengan una sola asignacin.
Asignar:
La persona 1 realiza la tarea 2.
La persona 2 realiza la tarea 1.
La persona 4 realiza la tarea 4.
La persona 5 realiza la tarea 3.
La persona 3 no realiza ninguna tarea.
La suma de los mejores tiempos correspondientes es de 75 horas.
T1 T2 T3 T4 T5
P1P2
P3
P4
P5
T1 T2 T3 T4 T5
P1P2
P3
P4
P5
-
7/30/2019 PROBLEMAS DE ASIGNACION.docx
4/7
2. Una compaa recibe ofertas para cuatro trabajos de construccin. Tres
personas realizaron ofertas en relacin con los trabajos. Sus ofertas (en
miles de dlares) se dan en la tabla adjunta (un * indica que la persona no
realiz una oferta para un determinado trabajo). La persona 1 puede hacerslo un trabajo, pero las personas 2 y 3 pueden llevar a cabo dos tareas.
Determine la asignacin de costo mnimo de persona a trabajos.
Como las personas 2 y 3 puede llevar a cabo dos tareas, entonces:
Nuevo cuadro de asignacin de tareas:
Persona 1 2 3 4
1 50 46 42 40
2 51 48 44 *
3 * 47 45 45
Traba o
Persona 1 2 3 4
1 50 46 42 40
2.1 51 48 44 *
2.2 51 48 44 *
3.1 * 47 45 45
3.2 * 47 45 45
Traba o
Persona 1 2 3 4 Ficticio
1 50 46 42 40 0
2.1 51 48 44 * 0
2.2 51 48 44 * 0
3.1 * 47 45 45 0
3.2 * 47 45 45 0
Traba o
-
7/30/2019 PROBLEMAS DE ASIGNACION.docx
5/7
Elaboramos la matriz de costos balanceada:
50 46 42 40 051 48 44 M 0
51 48 44 M 0
M 47 45 45 0
M 47 45 45 0
Construimos una nueva matriz restando de cada costo el costo mnimo en su
fila (stos aparecen con rojo en la matriz anterior).
50 46 42 40 051 48 44 M 051 48 44 M 0
M 47 45 45 0
M 47 45 45 0
Construimos una nueva matriz restando de cada costo el costo mnimo en su
columna (stos aparecen con rojo en la matriz anterior).
0 0 0 0 01 2 2 M 0
1 2 2 M 0
M 1 3 5 0
M 1 3 5 0
Verificamos la optimalidad trazando el menor nmero de lneas que puedan
pasar a travs de todos los ceros. Las lneas pueden ser horizontales o
verticales, pero no diagonales. Si el nmero de lneas trazadas es igual al
nmero de filas o columnas de la matriz se habr determinado la solucin
ptima.
T1 T2 T3 T4 T5
P1P2.1
P2.2
P3.1
P3.2
T1 T2 T3 T4 T5
P1P2.1
P2.2
P3.1
P3.2
T1 T2 T3 T4 T5
P1P2.1
P2.2
P3.1
P3.2
-
7/30/2019 PROBLEMAS DE ASIGNACION.docx
6/7
0 0 0 0 01 2 2 M 0
1 2 2 M 0
M 1 3 5 0
M 1 3 5 0
El tablero no es ptimo
Seleccionamos el elemento ms pequeo de entre los que no fueron cruzados
por las lneas, restarlo de estos que no fueron cruzados y sumarlo a aquellos
que son cruzados por dos lneas (intersecciones), los dems permanecen
inalterables.
0 0 0 0 10 1 1 M 0
0 1 1 M 0
M 0 2 4 0
M 0 2 4 0
Verificamos la optimalidad.
0 0 0 0 10 1 1 M 0
0 1 1 M 0
M 0 2 4 0
M 0 2 4 0
El tablero no es ptimo
Seleccionamos el elemento ms pequeo de entre los que no fueron cruzados
por las lneas, restarlo de estos que no fueron cruzados y sumarlo a aquellos
que son cruzados por dos lneas (intersecciones), los dems permanecen
inalterables.
T1 T2 T3 T4 T5
P1P2.1
P2.2
P3.1
P3.2
T1 T2 T3 T4 T5
P1P2.1
P2.2
P3.1
P3.2
T1 T2 T3 T4 T5
P1P2.1
P2.2
P3.1
P3.2
-
7/30/2019 PROBLEMAS DE ASIGNACION.docx
7/7
1 1 0 0 20 1 0 M 0
0 1 0 M 0
M 0 1 3 0
M 0 1 3 0
Verificamos la optimalidad.
1 1 0 0 20 1 0 M 0
0 1 0 M 0
M 0 1 3 0
M 0 1 3 0
El tablero es ptimo
Asignacin: La asignacin se debe hacer en las celdas donde haya ceros
cuidando que cada rengln y cada columna tengan una sola asignacin.
Asignar:
La persona 1 realiza el trabajo 4.
La persona 2 realiza los trabajos 1 y 3.
La persona 3 realiza el trabajo 2.
La suma de los mejores costos correspondientes es de 182 miles de dlares.
T1 T2 T3 T4 T5
P1P2.1
P2.2
P3.1
P3.2
T1 T2 T3 T4 T5
P1P2.1
P2.2
P3.1
P3.2