Modelo de Redes
4.3 Problemas de Asignación
Definición del Problema
* m trabajadores deben ser asignados a m trabajos.
* Un costo unitario (o ganancia) Cij es asociado al trabajador i
que realizara el trabajo j.
* Minimizar el costo total ( o maximizar la ganancia total) de la
asignación de trabajadores a sus respectivos empleos que le
corresponde a cada uno, tratando de que esta asignación
sea la óptima posible.
Electrónica Ballston
Existen 5 diferentes proyectos eléctricos sobre 5 líneas
de producción que necesitan ser inspeccionadas.
El tiempo para realizar una buena inspección de un
área de pende de la línea de producción y del área de
inspección.
La gerencia desea asignar diferentes áreas de
inspección a inspectores de productos tal que el
tiempo total utilizado sea mínimo.
Datos
* Tiempo de inspección en minutos para la línea de
ensamble de cada área de inspección.
Area de Inspección
A B C D E
1 10 4 6 10 12
Linea 2 11 7 7 9 14
Ensamble 3 13 8 12 14 15
4 14 16 13 17 17
5 19 17 11 20 19
RED QUE REPRESENTA EL PROBLEMA
Línea de ensamble Área de Inspección
S1=1 1 A D1=1
S2=1 2 B D2=1
S3=1 3 C D3=1
S4=1 4 D D4=1
S5=1 5 E D5=1
Supuestos restricciones
* El número de trabajadores es igual al número de empleos.
* Dado a que el problema esta balanceado, cada trabajador es
asignado sólo una vez y cada trabajo tiene exactamente un solo
trabajador.
* Para un problema desbalanceado se debe agregar un
trabajador “ficticio” (en el caso de que existan más trabajos que
trabajadores) o un empleo “ficticio” (en el caso de que existan
más trabajadores que trabajos), quedando así el problema
balanceado.
Solución mediante el método
Húngaro
Problema:
El profesor Michell ha terminado 4 capítulos de su libro y esta pensando
en pedir ayuda para terminarlo. El ha elegido a 4 secretarias que
podrían tipearle cada uno de sus capítulos. El costo asociado refleja la
velocidad de la secretaria y la exactitud con la que realiza el trabajo.
Además los capítulo difieren en la cantidad de hojas y en la
complejidad. ¿Qué puede hacer el profesor si conoce la siguiente tabla:
Capítulos
Secretaría 13 14 15 16
Juana 96 99 105 108
María 116 109 107 96
Jackeline 120 102 113 111
Edith 114 105 118 115
Restricciones del Método
* Solo problemas de minimización.
* Número de personas a asignar m es igual al número de lugares
m.
* Todas las asignaciones son posibles
* Una asignación por persona y una persona por asignación
Matriz de Costos
Capítulos
Secretaría 13 14 15 16
Juana 96 99 105 108
María 116 109 107 96
Jackeline 120 102 113 111
Edith 114 105 118 115
Restar el Menor valor de cada fila
Capítulos
Secretaría 13 14 15 16
Juana 0 3 9 12
María 20 13 11 0
Jackeline 18 0 11 9
Edith 9 0 13 10
Restar el menor valor de cada columna en la matriz
anterior
Capítulos
Secretaría 13 14 15 16
Juana 0 3 0 12
María 20 13 2 0
Jackeline 18 0 2 9
Edith 9 0 4 10
Trazar el mínimo número de líneas que cubran los
ceros de la matriz obtenida en el punto anterior.
Capítulos
Secretaría 13 14 15 16
Juana 0 3 0 12
María 20 13 2 0
Jackeline 18 0 2 9
Edith 9 0 4 10
Si el número de líneas es igual al número de filas se
esta en la solución óptima, sino identificar el menor
valor no rayado restarselo a los demás números no
rayados y sumarlo en las intersecciones.
Pare este caso corresponde al valor 2
Capítulos
Secretaría 13 14 15 16
Juana 0 5 0 14
María 18 13 0 0
Jackeline 16 0 0 9
Edith 7 0 2 10
Las asignaciones corresponde a los valores donde
existen 0
Juana Cap. 13
María Cap. 16
Jackeline Cap. 15
Edith Cap. 14
*Costo Asignación: 96 + 96 +113 +105 =410
Casos especiales
* Cuando un trabajador no puede realizar un empleo en
particular
* Cuando un trabajador puede ser asignado a más de un
trabajo.
* Un problema de maximización.
