UNIVERSIDAD AUTONOMA DE CHIHUAHUA

FACULTAD DE INGENIERIATRABAJO
MATERIA: INVESTIGACION DE OPERACIONES

MAESTRO: ING WENDY GUZMAN

TRABAJO: PROBLEMA DE ASIGNACION Y METODO HUNGARO ALUMNO: ALAN MENDOZA MOLINA 245040

PROBLEMA DE ASIGNACION
El problema de asignacin tuvo su origen en la revolucin industrial, ya que el surgimiento de las mquinas hizo que fuera necesario asignar una tarea a un trabajador. Thomas Jefferson en 1792 lo sugiri para asignar un representante a cada estado, pero formalmente aparece este problema en 1941, cuando F.L. Hitchcook publica una solucin analtica del problema, pero no es hasta 1955 cuando Harold Kuhn plantea el Mtodo hngaro, que fue posteriormente revisado por James Munkres en 1957; dicho mtodo est basado fundamentalmente en los primeros trabajos de otros dos matemticos hngaros: Dnes Kning y Jen Egervary. Hoy en da en pleno apogeo de la globalizacin este problema surge cada vez con mayor frecuencia el uso de este problema de la rama de la investigacin de operaciones, podemos decir que es la aplicacin del mtodo cientfico para asignar los recursos o actividades de forma eficaz, en la gestin y organizacin de sistemas complejos, su objetivo es ayudar a la toma de decisiones. En su forma ms general, el problema es como sigue: Hay un nmero de agentes y un nmero de tareas. Cualquier agente puede ser asignado para desarrollar cualquier tarea, contrayendo algn coste que puede variar dependiendo del agente y la tarea asignados. Es necesario para desarrollar todas las tareas asignar un solo agente a cada tarea para que el coste total del asignacin sea minimizado. Este tipo de problemas son lineales, con una estructura de transporte, slo que la oferta en cada origen es de valor uno y la demanda en cada destino es tambin de valor uno. Sera muy ineficiente resolver este tipo de problemas por medio del mtodo simplex o por medio del de transporte. Debido a la estructura propia de los problemas de asignacin, existen mtodos de solucin llamados algoritmos de asignacin que son ms eficientes que el simplex o que el mtodo de transporte. Los problemas de asignacin presentan una estructura similar a los de transporte, pero con dos diferencias: asocian igual nmero de orgenes con igual nmero de demandas y las ofertas en cada origen es de valor uno, como lo es la demanda en cada destino. La restriccin importante para cada agente es que ser designado a una y solo una tarea. El problema de asignacin presenta las siguientes caractersticas: El Problema de Asignacin debe estar equilibrado, es decir, que las ofertas y las demandas sean igual a 1. Un elemento importante para el problema de asignacin es la matriz de costos, si el nmero de renglones o columnas no son iguales el problema esta

desbalanceado y se puede obtener una solucin incorrecta, para obtener una solucin correcta la matriz debe ser cuadrada. Si el nmero de agentes y tareas son iguales y el coste total de la asignacin para todas las tareas es igual a la suma de los costes de cada agente (o la suma de los costes de cada tarea, que es lo mismo en este caso), entonces el problema es llamado problema de asignamiento lineal. Normalmente, cuando hablamos de problema de asignacin sin ninguna matizacin adicional, nos referimos al problema de asignamiento lineal. Oferta: Cantidad que representa la disponibilidad del artculo en la fuente/fbrica de donde proviene. Demanda: Cantidad de artculos que necesita recibir el destino para cumplir sus necesidades.

Ejemplos:
Machineco tiene cuatro maquinas y cuatro tareas por completar. Cada mquina se debe asignar para completar una tarea. El tiempo requerido para preparar cada mquina para completar cada tarea se muestra en la siguiente tabla. Machineco desea reducir el tiempo de preparacin total necesario para completar las cuatro tareas.

En la empresa Sinco se tienen tres vacantes, que ya han sido solicitadas por tres profesionistas, Jorge, Karen y Armando. El gerente de recursos humanos, Martin, pidi propuestas de salarios a cada uno de los profesionistas para las actividades de capturista de datos, programador y analista de base de datos, que todos los solicitantes podran realizar. Se sobreentiende que despus los tres aceptarn la decisin de Martn sobre quin hace qu actividad. La tabla siguiente resume las propuestas recibidas por lo que cobra un profesionista por realizar las diferentes actividades por hora. Capturista de datos Programador Analista de base de datos Jorge 160 110 100 Karen 100 160 110 Armando 110 130 90

Doc. Concillman rene a un equipo de relevos para el relevo de 400 metros. Cada nadador debe nadar 100 metros de brazada de pecho, dorso, mariposa o estilo libre. Doc. cree que cada nadador obtendr los tiempos en segundos dados en la tabla. Qu nadador debe nadar que estilo? Nadador Libre Pecho Mariposa Dorso Gary 54 54 51 53 Mark 51 57 52 52 Jim 50 53 54 56 Chet 56 54 55 53

METODO HUNGARO
Pasos para el mtodo hngaro: Paso 1: Encontrar primero el elemento ms pequeo en cada fila de la matriz de costos m*m; se debe construir una nueva matriz al restar de cada costo el costo mnimo de cada fila; encontrar para esta nueva matriz, el costo mnimo en cada columna. A continuacin se debe construir una nueva matriz (denominada matriz de costos reducidos) al restar de cada costo el costo mnimo de su columna. Paso 2: Consiste en trazar el nmero mnimo de lneas (horizontales o verticales o ambas nicamente de esas maneras) que se requieren para cubrir todos los ceros en la matriz de costos reducidos; si se necesitan m lneas para cubrir todos los ceros, se tiene una solucin ptima entre los ceros cubiertos de la matriz. Si se requieren menos de m lneas para cubrir todos los ceros, se debe continuar con el paso 3. El nmero de lneas para cubrir los ceros es igual a la cantidad de asignaciones que hasta ese momento se pueden realizar. Paso 3: Encontrar el menor elemento diferente de cero (llamado k) en la matriz de costos reducidos, que no est cubierto por las lneas dibujadas en el paso 2; a continuacin se debe restar k de cada elemento no cubierto de la matriz de costos reducidos y sumar k a cada elemento de la matriz de costos reducidos cubierto por dos lneas (intersecciones). Por ltimo se debe regresar al paso 2. Pas 4: En caso de no encontrar una solucin factible con los pasos anteriores aplicar entonces este:

1) Trace el nmero mnimo de lneas horizontales y verticales en la ltima matriz reducida que cubrir TODAS las entradas cero. 2) Selecciones el elemento no cubierto ms pequeo y rstelo de todos los elementos no cubiertos; despus, smelos a todos los elementos en la interseccin de dos lneas. 3) Si no es posible encontrar una asignacin factible entre las entradas cero resultantes, repita es paso. De lo contrario regrese al paso 3 para determinar la asignacin ptima.

Ejemplos:
Machineco tiene cuatro maquinas y cuatro tareas por completar. Cada mquina se debe asignar para completar una tarea. El tiempo requerido para preparar cada mquina para completar cada tarea se muestra en la siguiente tabla. Machineco desea reducir el tiempo de preparacin total necesario para completar las cuatro tareas.

Paso 1: Reste el numero ms pequeo de cada rengln a cada nmero del rengln. Esto se llama reduccin de rengln.

Paso 2: Reste el nmero mas pequeo de la nueva matriz a cada nmero de la columna. Esto se llama reduccin de columna.

Al momento de realizar los dos pasos anteriores la matriz nueva recibe el nombre de matriz reducida de costos. Paso 3: Pruebe si se puede hacer una asignacin ptima, se hace mediante la determinacin del nmero mnimo de lneas necesarias para cubrir todos los ceros.

Como el nmero de lneas no es igual al nmero de renglones no es posible hacer una asignacin, en este caso se contina con el mtodo. Paso 4: Reste el nmero no cubierto ms pequeo de todos los nmeros no cubiertos de la matriz. Sume el nmero no cubierto ms pequeo a los nmeros que se encuentren en interseccin de lneas. Los nmeros cruzados pero que no se encuentran en interseccin de lneas permanece igual.

Paso 5: Repetir los pasos 3 y 4 hasta que el nmero de lneas sea igual al nmero de renglones de la matriz.

Como el nmero de lneas es igual al nmero de renglones se tiene una solucin ptima. Se puede pasar al ltimo paso. Paso 6: Se hacen las asignaciones una a una en las posiciones que tienen elemento cero. Comience con los renglones y columnas que tienen slo un cero. Cada rengln y columna necesita recibir eXactamente una asignacin, despus contine con los renglones y columnas que no han sido asignados.
Contine hasta que todos los renglones y columnas estn asignados.

Interpretacin de resultados

'z = 21

+ 5 + 3 + 5 = 15

En la empresa Sinco se tienen tres vacantes, que ya han sido solicitadas por tres profesionistas, Jorge, Karen y Armando. El gerente de recursos humanos, Martin, pidi propuestas de salarios a cada uno de los profesionistas para las actividades de capturista de datos, programador y analista de base de datos, que todos los solicitantes podran realizar. Se sobreentiende que despus los tres aceptarn la decisin de Martn sobre quin hace qu actividad. La tabla siguiente resume las propuestas recibidas por lo que cobra un profesionista por realizar las diferentes actividades por hora. Capturista de datos Programador Analista de base de datos Jorge 160 110 100 Karen 100 160 110 Armando 110 130 90 Reste el nmero ms pequeo de cada rengln, esto se llama reduccin de rengln. Introduzca los resultados en una nueva matriz

Reste el nmero ms pequeo de la nueva matriz a cada nmero de la columna, esto se llama reduccin de columna. Introduzca los nuevos datos en otra matriz.

Pruebe si puede hacer una asignacin ptima. Hgalo mediante la determinacin del nmero mnimo de lineas necesarias para cubrir todos los ceros ( horizontales y verticales). Si el nmero de lneas es igual al nmero de renglones entonces es posible hacer una asignacin.

En este caso tuvimos suerte, el nmero de lneas es igual al nmero de renglones de la matriz por lo tanto podemos hacer una asignacin. Nos pasamos al paso 6, les dej tambin los pasos que hubieramos tenido que realizar en caso de no fuera igual el nmero de renglones que de columnas. Si el nmero de lneas es menor que el nmero de renglones, modifique la matriz de la siguiente forma: a) Reste el nmero no cubierto ms pequeo de todos los nmeros no cubiertos de la matriz. b) Sume el nmero no cubierto ms pequeo a los nmeros que se encuentran en interseccin de lneas. c) Los nmeros cruzados pero que no se encuentren en interseccin de lneas permanecen igual. Repita los pasos 3 y 4 hasta que el nmero de lneas sea igual al nmero de renglones de la matriz. Haga las asignaciones una a una en las posiciones que tienen elementos cero, comience con los renglones y columnas que tienen un slo cero. Cada rengln y columna necesita recibir exactamente una asignacin, despus continue con los renglones y columnas que no han sido asignados, continue hasta que todos los renglones y columnas hayan sido asignados. En nuestro ejemplo asignamos las posiciones X21, X12 y X33. Interpretacin de resultados Profesionista Actividad 1 2 2 1 3 3

Doc. Concillman rene a un equipo de relevos para el relevo de 400 [Link] nadador debe nadar 100 metros de brazada de pecho, dorso, mariposa o estilo libre. Doc. cree que cada nadador obtendr los tiempos en segundos dados en la tabla. Qu nadador debe nadar que estilo? Nadador Libre Pecho Mariposa Dorso Gary 54 54 51 53 Mark 51 57 52 52 Jim 50 53 54 56 Chet 56 54 55 53 1. Se escribe la matriz de costos.

2. Se escoge el nmero mas pequeo de cada rengln y se le resta a cada numero del rengln y los resultados se pone en una nueva matriz. Queda de la siguiente manera:

3. De la nueva matriz se escoge el nmero mas pequeo de cada columna y se le resta a cada numero de la columna. Queda de la siguiente manera:

4. Procedemos a encontrar el nmero mnimo de rectas que cubren todos los ceros de la matriz.

[Link] el nmero de rectas es igual al nmero de renglones es posible hacer una asignacin, como en este caso son diferentes se hace el siguiente paso. 6. Se escoge el nmero mas pequeo no cubierto y se le resta a los demas nmeros no cubiertos. En los nmeros de interseccin de rectas se suma este nmero.

Procedemos a encontrar el nmero mnimo de rectas que cubren todos los ceros de la matriz.

Como el nmero de rectas es igual al nmero de renglones procedemos a asignar. Se escoge el cero donde solo este una vez en el rengln o la columna.

As queda la asignacin. Nadador Estilo 1 3 4 2 2 4 3 1