Balanceado[editar]Se dice que un problema de asignacin se encuentra balanceado, si los recursos totales son iguales a las demandas totales, en caso contrario se dice que no est balanceado el problema.Adems en el modelo,m=n(obtener una matriz cuadrada), en dondemnmero de renglones ynes nmero de columnas.Para lograr que el modelo este balanceado se pueden agregar trabajadores/tareas ficticias con costos de cero.

4.3.3. Modelo de asignacion pura.Considere un caso especial del problema de transporte en que se cumple: m = n; es decir, el nmero de orgenes es igual a los destinos; adems= b j =1.El modelo as definido es asignacin pura, se refiere a la accin de asignar uno a uno; esto es, en forma biunvoca. Se entiende asignar n candidatos a n acciones requeridas, conociendo la medida de desempeo, que puede ser costo, beneficio o rendimiento. El problema consiste en asignar de forma idnea para conseguir el mejor resultado general. Por ejemplo, la asignacin de personas a operar mquinas, para las cuales se tiene la informacin de la capacidad individual al trabajar con ellas, se acepta como asignacin pura de operarios a mquinas. Otro ejemplo, se refiere a la asignacin de competidores para desempearse en la competencia de algn evento deportivo, desde luego, con diferente eficiencia individual; aqu tambin se asigna un competidor para ocupar cada relevo de la carrera o cada posicin en un juego colectivo.

C i j = costo o valor del desempeo individual de i en la accin j.Sujeta a las restricciones:X i j = 1; desde i = 1 hasta i = n; de j = 1 hasta j= n.

Figura 4-59. Matriz de asignacin pura.MTODO HNGARO para la asignacin.La ms conocida tcnica de solucin para el problema de asignacin pura es el mtodo hngaro, desarrollado a partir del teorema que demostr el matemtico hngaro Knig en 1916. Este mtodo utiliza la propiedad de reduccin de matrices para reducir la matriz original de costo,hasta que los costos C i jasociados con la asignacin ptima, sean ceroy todos los otros costos sean no negativos.En cada iteracin del mtodo hngaro, se reduce la matriz de tal manera quehaya al menos un cero en cada rengln y columna, comprobando con el teorema de Knig si se ha alcanzado la solucin ptima. Si el nmero mnimo de renglones y/o columnas necesarios para cubrir todos los ceros es n, entonces existe una asignacin ptima (no necesariamente nica).Ejemplo 4-8. Mtodo Hngaro en la asignacin (ASIGNA1).La siguiente matriz contiene los costos para operar n=4 mquinas, por n=4 personas as calificadas en su empresa. Optimice la asignacin idnea.

Figura 4-60. Matriz de costos en ejemplo ASIGNA1.Paso 1 .Seleccione en cada rengln i de la matriz, el menor costo C i j, (menor C i j = U i ), luego rstelo en cada elemento del rengln.

Figura 4-61. Paso 1 Mtodo Hngaro, ejemplo ASIGNA1.Paso 2. Seleccione en cada columna j de la matriz resultante en el paso 1, el costo menor C i j, (menor Cij=Vj) y rstelo en cada elemento de la misma columna.

Figura 4-62. Paso 2 Mtodo Hngaro, ejemplo ASIGNA1.Paso 3.Sombree los renglones y/o columnas de la matriz, de tal modo que sean los mnimos necesarias para cubrir todos los ceros.

Figura 4-63. Paso 3 Mnimo sombreado de renglones y/o columnas cubriendo todos los ceros en ejemplo ASIGNA1.Paso 4.Seleccione entre los costos no sombreados, el nmero menor C i j, (= U i j) o bien, el menor C i j,(= V i j), yrstelo a todos los costos no sombreados; despus, sume el mismo a los costos ubicados en la interseccin de los renglones y columnas sombreados. Este pasose repite hasta lograr la solucin ptima.

Figura 4-64. Paso 4 Mtodo Hngaro,(mnimo Cij no sombreado) en ejemplo ASIGNA1.Se tiene la solucin ptima cuando el mnimo necesario de renglones y columnas sombreadas para cubrir los ceros es n. En este problema el mnimo es n =4.

Figura 4-65. Paso 4 Mtodo Hngaro, renglones y/o columnas sombreados necesarios para cubrir los ceros n = 4, ejemplo ASIGNA1.Entonces la asignacin ptima es la que muestra la tabla siguiente:

Figura 4-66. Asignacin ptima en ejemplo ASIGNA1.Solucin ptima: X11= 1, X23= 1, X32= 1, X44= 1Z = C11X11+ C23X23+ C32X32+ C44X44= 1(1) + 10(1) + 5(1) + 5(1) = 21En la solucin ptima, la suma de las costos Ui restados de renglones i en paso 1, ms las costos V j restados de columnas j en paso 2, ms el costo U i j V i j, restado y / o sumado, en paso 4, proporciona el correspondiente valor ptimo. As el costo es:Z ptimo =U i +V j +U i j +V i j, para toda i, para toda j.U i = U1+ U2+ U3+ U4+ U32= 1 + 7 + 4 + 5 + 1 = 18V j = V1+ V2+ V3+ V4= 0 + 0 + 3 + 0 = 3U i +V j = 18 + 3 = 21Ejemplo 4-9. Mtodo Hngaro en la asignacin (ASIGNA2).La siguiente matriz muestra costos C i j de n = 5 candidatos i ( i = 1,2,...,5 ) as calificados, en el desempeo de n = 5 actividades j ( j = 1,2,..,5 ). Con el mtodo hngaro calcule la asignacin ptima.

Figura 4-67. Matriz de costos en ejemplo ASIGNA2.Paso 1. Reste el menor ( U i ) de los costos C i j en cada rengln:

Figura 4-68. Paso 1 Mtodo Hngaro en ejemplo ASIGNA2.Paso 2.- Reste el menor ( V j ) de los costos C i j en cada columna:

Figura 4-69. Paso 2 Mtodo Hngaro en ejemplo ASIGNA2.Paso 3.-Sombree los renglones y columnas de la matriz, de tal modo que sean los mnimos necesarios para cubrir todos los ceros. La asignacin es ptima con n = 5 renglones y/o columnas. De lo contrario se contina el mtodo con el paso 4.Paso 4.- Selecciones entre los costos no sombreados, el nmero menor C ij, (= Uij) o bien, el menor Cij, (= Vij), yrstelo a todos los costos sin sombrear; despus, sume el mismo a los costos ubicados en la interseccion de los renglones y columnas sombreados. Repita este paso hasta conseguir n = 5 (renglones y/o columnas sombreados), la solucin ptima.

Figura 4-70. Paso 4 Mtodo Hngaro en ejemplo ASIGNA2.En la asignacin de la tabla anterior solo se sombrean 3 renglones y una columna con ceros, pero se necesitan 5, entonces se repite el paso 4 hasta conseguirlo.

Figura 4-71. Paso 4 Mtodo Hngaro. Renglones y columnas sombreados n = 4, ejemplo ASIGNA2.

Figura 4-72. Paso 4 Mtodo Hngaro. Se logra sombrear n = 5 renglones y columnas, ejemplo ASIGNA2.La ltima asignacin resulta con los 5 renglones y columnas sombreadas cubriendo los ceros de la tabla.Aqu se detiene el proceso y se interpreta laasignacin ptima localizando, al menos un cero en cada rengln y en cada columna. Estos ceros indican el costo idneo asignado a la persona i en el desempeo de la actividad j, como se muestra en la siguiente matriz.

Figura 4-73. Asignacin ptima en ejemplo ASIGNA2.Asignacin ptima: X15= 1, X23= 1, X32= 1, X44= 1, X51= 1Z ptima = C15X15+ C23X23+ C32X32+ C44X44+ C51X51Z ptima = 3(1) + 2(1) + 4(1) + 3(1) + 9(1) = 21Z ptimo =U i +V j +U i j +V i j = 3+2+2+2+6+0+2+0+1+0+2+1 = 21Ejemplo 4-10. Mtodo Hngaro en la asignacin (ASIGNA3).La siguiente matriz muestra costos C i j de n = 4 candidatos i (i = 1, 2, ..., 4) as calificados, en el desempeo de n=4 actividades j (j = 1, 2, .., 4). Con el mtodo hngaro calcule la asignacin ptima.

Figura 4-74. Tablas del ejemplo ASIGNA3.Asignacin ptima: X14= 1, X22= 1, X33= 1, X41= 1Z ptima = C14X14+ C22X22+ C33X33+ C41X41Z ptima = 6(1)+1(1)+2(1)+1(1) = 10; otra asignacin ptima del problema es:

Figura 4-75. Asignacin ptima en ejemplo ASIGNA3.Asignacin ptima: X13= 1, X22= 1, X34= 1, X41= 1Z ptima = C14X14+ C22X22+ C33X33+ C41X41= 7(1) +1(1) +1(1) +1(1) = 10En ambas cumple:Z ptimo=Ui +Vj +Uij +Vij = 5+1+1+1+0+0+1+0+1 = 10PROBLEMAS DE ASIGNACIN

Elproblema de asignacines una variacin del problema 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, lo que supone que la oferta y la demanda estn perfectamente alineadas, de hecho ambas son iguales a uno (1).Mltiples son los casos en los que como ingenieros industriales podemos hacer uso del problema de asignacin para resolver diversas situaciones, entre los que cabe mencionar se encuentran la asignacin de personal a maquinas, herramientas a puestos de trabajos, horarios a maestros, candidatos a vacantes, huspedes a habitaciones, comensales a mesas, vendedores a zonas territoriales etc.En el modelo de asignacin la idea fundamental de resolucin es qu fuente satisface mejor el destino?, y dado que hemos asociado el modelo a una gran diversidad de circunstancias esta pregunta puede plantearse en mltiples contextos, como qu candidato es el idneo para la vacante?, o qu personal es el indicado para la lnea productiva?, o qu personal es el mejor para ejecutar determinada tarea?. Una caracterstica particular del modelo de asignacin es que para su resolucin no se hace necesario que el nmero de fuentes sea igual al nmero de destinos, lo cual es muy comn en la vida real teniendo en cuenta su aplicacin, pues generalmente la cantidad de aspirantes es exageradamente superior al nmero de vacantes (lgicamente haciendo referencia a la aplicacin del modelo al contexto de oferta y demanda laboral).MTODO HNGAROApartndonos un poco de la idea expresada en mdulos anteriores respecto a la facilidad de resolver problemas atinentes a la investigacin operativa en especial aquellos de transporte mediante el uso de herramientas tecnolgicas como lo son WinQSB, LINGO, TORA, STORM, Excel etc.. vale la pena ya sea para fines acadmicos o de cultura ingenieril realizar la resolucin del problema de asignacin mediante el algoritmo que se cre para tal fin, como lo es elMtodo Hngaro.El mtodo Hngaro es un mtodo de optimizacin de problemas de asignacin, conocido como tal gracias a que los primeros aportes al mtodo clsico definitivo fueron deDnes Knig y Jen Egervry dos matemticos hngaros. El algoritmo tal como se detallar a continuacin est diseado para la resolucin de problemas deminimizacinnicamente, ser entonces cuestin de agregar un paso adicional para abordar ejercicios de maximizacin.ALGORITMO HNGARO, PASO 1Antes que nada cabe recordar que el mtodo hngaro trabaja en una matriz de costos n*m (en este caso conocida como matriz m*m, dado que el nmero de filas es igual al nmero de columnas n = m), una vez construida esta se debe encontrar el elemento ms pequeo en cada fila de la matriz.ALGORITMO HNGARO, PASO 2Una vez se cumple el procedimiento anterior se debe construir una nueva matriz n*m, en la cual se consignarn los valores resultantes de la diferencia entre cada costo y el valor mnimo de la fila a la cual cada costo corresponde (valor mnimo hallado en el primer paso).ALGORITMO HNGARO, PASO 3Este paso consiste en realizar el mismo procedimiento de los dos pasos anteriores referidos ahora a las columnas, es decir, se halla el valor mnimo de cada columna, con la diferencia que este se halla de la matriz resultante en el segundo paso, luego se construir una nueva matriz en la cual se consignarn los valores resultantes de la diferencia entre cada costo y el valor mnimo de la columna a la cual cada costo corresponde, matriz llamada "Matriz de Costos Reducidos".ALGORITMO HNGARO, PASO 4A continuacin se deben de trazar lneas horizontales o verticales o ambas (nicamente de esos tipos) con el objetivo de cubrir todos los ceros de la matriz de costos reducidos con el menor nmero de lneas posibles, si el nmero de lineas es igual al nmero de filas o columnas se ha logrado obtener la solucin ptima (la mejor asignacin segn el contexto de optimizacin), si el nmero de lneas es inferior al nmero de filas o columnas se debe de proceder con el paso 5.ALGORITMO HNGARO, PASO 5Este paso consiste en encontrar el menor elemento de aquellos valores que no se encuentran cubiertos por las lineas del paso 4, ahora se restar del restante de elementos que no se encuentran cubiertos por las lneas; a continuacin este mismo valor se sumar a los valores que se encuentren en las intersecciones de las lineas horizontales y verticales, una vez finalizado este paso se debe volver al paso 4.RESOLUCIN DE UN PROBLEMA DE ASIGNACIN MEDIANTE EL MTODO HNGAROEL PROBLEMALa compaa de manufactura "Jimnez y Asociados" desea realizar una jornada de mantenimiento preventivo a sus tres mquinas principales A, B y C. El tiempo que demanda realizar el mantenimiento de cada mquina es de 1 da, sin embargo la jornada de mantenimiento no puede durar ms de un da, teniendo en cuenta que la compaa cuenta con tres proveedores de servicios de mantenimiento debe de asignarse un equipo de mantenimiento a cada mquina para poder cumplir con la realizacin del mantenimiento preventivo. Teniendo en cuenta que segn el grado de especializacin de cada equipo prestador de servicios de mantenimiento el costo de la tarea vara para cada mquina en particular, debe de asignarse el equipo correcto a la mquina indicada con el objetivo de minimizar el costo total de la jornada. Los costos asociados se pueden observar en la siguiente tabla:

Bryan Antonio Salazar LopezPASO 1Encontramos el menor elemento de cada fila

Bryan Antonio Salazar LpezPASO 2Construimos una nueva matriz con las diferencias entre los valores de la matriz original y el elemento menor de la fila a la cual corresponde.

Bryan Antonio Salazar LpezPASO 3En la matriz construida en el paso anterior se procede a efectuar el paso 1 esta vez en relacin a las columnas, por ende escogemos el elemento menor de cada columna. Igualmente construimos una nueva matriz con la diferencia entre los valores de la matriz 2 y el elemento menor de la columna a la cual corresponde cada valor.

Bryan Antonio Salazar LpezPASO 4En este paso trazaremos la menor cantidad de combinaciones de lneas horizontales y verticales con el objetivo de cubrir todos los ceros de la matriz de costos reducidos.

Bryan Antonio Salazar LpezComo se puede observar el menor nmero de lneas horizontales y/o verticales necesarias para cubrir los ceros de la matriz de costos reducidos es igual a 2, por ende al ser menor que el nmero de filas o columnas es necesario recurrir al paso 5.PASO 5En este paso seleccionamos el menor elemento de los elementos no subrayados.

Luego se procede a restarse de los elementos no subrayados y a adicionarse a los elementos ubicados en las intersecciones de las lneas, en este caso existe una nica interseccin (3).

Bryan Antonio Salazar LpezAhora ya efectuado este paso pasamos al paso 4.

Bryan Antonio Salazar LpezAhora observamos cmo se hace necesario trazar tres lneas (la misma cantidad de filas o columnas de la matriz) por ende se ha llegado al tabulado final, en el que por simple observacin se determina las asignaciones ptimas.

Bryan Antonio Salazar LpezPor ende la asignacin que representa el menor costo para la jornada de mantenimiento preventivo determina que el Equipo 1 realice el mantenimiento de la Mquina 1, el Equipo 2 realice el mantenimiento de la Mquina 3 y el Equipo 3 realice el mantenimiento de la Mquina 2, jornada que tendr un costo total de 17 unidades monetarias.RESOLUCIN DE UN PROBLEMA DE MAXIMIZACIN MEDIANTE EL MTODO HNGAROEL PROBLEMAUna organizacin de recoleccin de caf cuenta con tres equipos de siembra y cosecha del mismo (equipos 1, 2, 3). Estos equipos de trabajo se encuentran entrenados para trabajar en condiciones particulares del proceso, condiciones como lo son el tipo de suelo, las condiciones del clima y el tipo de grano. La organizacin cuenta con cuatro terrenos disponibles para efectuar el proceso de siembra y cosecha (terrenos A, B, C, D), estos terrenos tienen condiciones particulares de suelo, clima y tipo de grano. Cada equipo cuenta con la capacidad de efectuar el proceso en solo uno de los terrenos disponibles, salvo elequipo 2, que cuenta con una serie de herramientas tecnolgicas que le permiten realizar la siembra y cosecha del grano en dos de los terrenos disponibles. Se ha contratado a un Ingeniero Industrial con el objetivo de realizar las asignaciones precisas que maximicen la cantidad de sacos de caf cosechados en total. El siguiente tabulado muestra la capacidad (en cientos de sacos) de cosecha de caf de cada uno de los equipos dependiendo de cada uno de los terrenos.

RESOLUCINEn este problema debemos recordar un concepto fundamental para la aplicacin del mtodo hngaro, este concepto nos dice que el nmero de filas debe ser exactamente igual al nmero de columnas. Por ende, la accin a realizar debera ser crear un equipo ficticio, el cual nos deje el tabulado balanceado y a este asignarle un nmero de sacos cosechados equivalente a cero en cada uno de los terrenos. Sin embargo el problema nos indica que uno de los equipos se encuentra en capacidad de que se le asignen dos terrenos, en este caso crearemos un equipo 2 alternativo (Equipo 2B) el cual nos balancear el tabulado y nos har prescindir del equipo ficticio pensado inicialmente. A este equipo 2B que crearemos le corresponder la misma capacidad de cosecha del equipo 2 (en adelante equipo 2A) segn el terreno, lgicamente.

Una vez balanceado el tabulado debemos de cuestionarnos acerca del criterio de optimizacin, pues recordemos que el mtodo hngaro se encuentra diseado para ejercicios de minimizacin. En este caso nuestro objetivo es maximizar, por lo que tendremos que aplicar un paso adicional.Lo primero que debemos hacer es ubicar el mayor valor del tabulado inicial.

En este caso este valor es 15, por lo cual procederemos a realizar la siguiente operacin con cada uno de los valores:Restaremos a 15, el valor de cada una de las celdas y este valor quedar en cada una de las celdas correspondientes.

Ahora nuestro tabulado inicial quedar de la siguiente manera:

A partir de este tabulado ya podemos aplicar el algoritmo del mtodo hngaro como se aplicara en un caso e minimizacin (normalmente).Ahora encontramos el menor elemento de cada fila.

y se lo restamos a todas las celdas de la fila.

Ahora efectuamos este mismo paso, pero esta vez con las columnas. Elegimos el menor de los valores de cada columna y se lo restamos a cada una de las celdas de la columna correspondiente.

Ahora procedemos a cubrir la mayor cantidad de ceros, con la menor cantidad de lneas, si el nmero de lneas que empleemos es igual al grado de la matriz (en este caso matriz grado 4, 4x4) habremos llegado al final del ejercicio.

Dado que el nmero de lneas es igual al grado de la matriz, hemos concluido el algoritmo. Lo nico que quedar ser asignar a cada equipo el terreno en el que el intercepto es igual a 0 (cero).

Las asignaciones, como es lgico debern iniciarse por el equipo al cual solo corresponda un terreno, en este caso al Equipo 3 le corresponde el Terreno A. De esta manera al Equipo 1 le corresponde el Terreno D. Mientras tanto el Equipo 2 se encargar de la cosecha en los terrenos B y C. Segn el tabulado del problema (recordemos que es de maximizacin), la cantidad de sacos (expresada en cientos de sacos) ser as:

RESOLUCIN DE UN PROBLEMA DE ASIGNACIN MEDIANTE PROGRAMACIN LINEALEL PROBLEMALa compaa de manufactura "Jimnez y Asociados" desea realizar una jornada de mantenimiento preventivo a sus tres mquinas principales A, B y C. El tiempo que demanda realizar el mantenimiento de cada mquina es de 1 da, sin embargo la jornada de mantenimiento no puede durar ms de un da, teniendo en cuenta que la compaa cuenta con tres proveedores de servicios de mantenimiento debe de asignarse un equipo de mantenimiento a cada mquina para poder cumplir con la realizacin del mantenimiento preventivo. Teniendo en cuenta que segn el grado de especializacin de cada equipo prestador de servicios de mantenimiento el costo de la tarea vara para cada mquina en particular, debe de asignarse el equipo correcto a la mquina indicada con el objetivo de minimizar el costo total de la jornada. Los costos asociados se pueden observar en la siguiente tabla:

VARIABLES DE DECISINLas variables de decisin de este tipo de problemas es igual a las variables de cualquier modelo de transporte tradicional, es decir variables Xi,jdonde i {Equipo de mantenimiento 1,2,3} y j {Mquina 1,2,3}, y corresponden a variables binarias en las cuales el valor 1 significa la asignacin de un equipo de mantenimiento a una mquina en particular.RESTRICCIONESDado que un equipo de mantenimiento no puede ser asignado a ms de una maquinaria, esta caracterstica debe de restringirse mediante las siguientes inecuaciones.X1,1+ X1,2+ X1,3= 1X2,1+ X2,2+ X2,3= 1X3,1+ X3,2+ X3,3= 1Adems debe restringirse el hecho de que cada mquina solo requiere de un equipo de mantenimiento, por endeX1,1+ X2,1+ X3,1= 1X1,2+ X2,2+ X3,2= 1X1,3+ X2,3+ X3,3= 1Adems se hace necesario que para efectos de resolucin en cualquier paquete de herramientas se especifique que estas variables corresponden al conjunto de los enteros (por obvias razones) y que deben ser mayores que cero (dado que es un problema de minimizacin esta restriccin se hace muy necesario).Xi,j 0Xi,j {Z}FUNCIN OBJETIVOZMIN= 10X1,1+ 9X1,2+ 5X1,3+ 9X2,1+ 8X2,2+ 3X2,3+ 6X3,1+ 4X3,2+ 7X3,3INGRESANDO LOS DATOS A WINQSB

RESULTADOS OBTENIDO MEDIANTE EL WINQSB

Por ende la asignacin que representa el menor costo para la jornada de mantenimiento preventivo determina que el Equipo 1 realice el mantenimiento de la Mquina 1, el Equipo 2 realice el mantenimiento de la Mquina 3 y el Equipo 3 realice el mantenimiento de la Mquina 2, jornada que tendr un costo total de 17 unidades monetarias.RESOLUCIN DE UN PROBLEMA DE ASIGNACIN MEDIANTE WINQSB - NETWORK MODELINGLa facilidad de resolver un problema de asignacin mediante WinQSB es an mayor a la que se incurre medianteprogramacin lineal, y esta metodologa justifica el pensar en que el mtodo hngaro es sumamente anacrnico nicamente contemplado para fines histricos y acadmicos. En el mdulo NETWORK MODELING del paquete de herramientas WinQSB se puede resolver el modelo tan solo traspasando los costos de una matriz n*m a otra que brinda el mdulo n*m.INGRESANDO LOS DATOS A WINQSB - NETWORK MODELING

RESULTADOS OBTENIDOS MEDIANTE WINQSB - NETWORK MODELING

Por ende la asignacin que representa el menor costo para la jornada de mantenimiento preventivo determina que el Equipo 1 realice el mantenimiento de la Mquina 1, el Equipo 2 realice el mantenimiento de la Mquina 3 y el Equipo 3 realice el mantenimiento de la Mquina 2, jornada que tendr un costo total de 17 unidades monetarias.De esta manera se hace evidente cual es la alternativa predilecta para resolver problemas de asignacin.

1. PROBLEMA DE LA ASIGNACION Muchas de las situaciones en la vida exigen una de dos respuestas posibles: si o no. As Muchas de las situaciones en la vida exigen una de dos respuestas posibles: si o no. As es que podemos representar stas posibilidades con los valores 0 (no) y 1 (si), y aprovechar las matemticas para que nos den una mano ante decisiones difciles; a esto es lo que solemos llamar -por obvias razones- Programacin Binaria. Una de las muchsimas aplicaciones de la Programacin Binaria, es el problema de la Asignacin. Este mtodo analiza el problema de asignar un cierto nmero de recursos a un determinado nmero de tareas, con base en algn tipo de valoracin para cada recurso. Cada recurso, podr ser asignado a una sola tarea. El PA consiste en asignar recursos a tareas en funcin de un objetivo ligado a la eficiencia del sistema. Un ejemplo tpico es el de asignacin de personas a turnos horarios, o el de asignar personas a mquinas 2. El esquema tabular del PA es: 3. Formulacin del Programa Minimizar el costo total de operacin de modo que: cada tarea se asigne a una y slo una mquina cada mquina realice una y slo una tarea X ij : 1 si la tarea i se hace con la mquina j c ij : costo de realizar la tarea i con mquina j n tareas m mquinas Si hay ms mquinas que tareas se formula con desigualdades, y se resuelve con tareas ficticias 4. METODO HUNGARO Existen 5 operarios (A, B, C, D y C) que tienen que llenar 5 cargos (I, II, III, IV y V). La matriz de costos que caracteriza el problema de asignacin es la siguiente Determinar la asignacin ptima 5. 1- Se calcula C ij = C ij elemento mas pequeo de cada columna 2. Se calcula C* ij = C ij elemento mas pequeo de cada fila 6. 3. Procederemos a encontrar el nmero mnimo de recta r que cubren todos los ceros de la matriz C* 4. En este caso = 1 (elemento mnimo no cubierto por las rectas). Se resta a todos los elementos no cubiertos por las rectas- Se suma a todos los elementos en las intersecciones entre 2 rectas y se vuelve al paso 3. La matriz C* se transforma en Vemos que r = 4 que es diferente de m=5, por consiguiente no se ha llegado al ptimo 7. 5. Determinamos la asignacin ptima Se observa que r = 5 = m =5, por consiguiente se ha llegado al ptimo 8. O bien: A es asignado a V B es asignado a II C es asignado a I D es asignado a IV E es asignado a III El costo total del programa en ambos casos es Z = $ 18 Hay dos soluciones ptimas: A es asignado a IV B es asignado a II C es asignado a I D es asignado a V E es asignado a III 9. Encuentre la asignacin que minimice el tiempo total. CASO 1: MATRIZ NO CUADRADA Cuatro trabajadores requieren el uso de una cualesquiera de las de las maquinas A, B, C y D. Los tiempos tomados por cada maquina para realizar cada trabajo son mostradas en la matriz siguiente: 10. CASO 2: ASIGNACIONES IMPOSIBLES El El hospital de Chiclayo ha comprado tres mquinas nuevas de diferentes tipos. Existen cuatro lugares dentro de la planta de quirfanos en donde se podra instalar cada una de estas mquinas. Algunos de ellos son ms adecuados que otros para una mquina en particular por su cercana a las mesas de ciruga que tendran un flujo intenso de trabajo hacia estas mquinas y desde ellas. Por lo tanto el objetivo es asignar las nuevas mquinas a los lugares disponibles de manera que se minimice el costo total del manejo de materiales. En la tabla siguiente se proporciona el costo estimado por unidad de tiempo del manejo de los materiales en cuestin con cada una de las mquinas en los sitios respectivos. El lugar 2 no se considera adecuado para la mquina 2. No habr flujo de trabajo entre las nuevas mquinas. El costo estimado por unidad de tiempo es el siguiente: 11. CASO 3: MAXIMIZACION Se desea instalar 4 fabricas: una de papel, otra de vidrio, fibra artificial y llantas. Se ha tomado la decisin de invertir en una fabrica para Arequipa, Huancayo, Iquitos y Chiclayo, para lo cual es necesario conocer el tipo de fabrica en cada una de estas ciudades. La matriz que se muestra a continuacin muestra las utilidades netas mensuales en miles de $. Haga la asignacin ptima 12. PROBLEMA PROPUESTO Una lnea area tiene vuelos redondos entre las ciudades A y B. La tripulacin con base en la ciudad A(B) y que vuela a la ciudad B(A) debe regresar a la ciudad A(B) en un vuelo posterior el mismo da o al siguiente. Una tripulacin con base en la ciudad A puede regresar en un vuelo con destino a B slo si hay cuando menos 90 minutos entre el tiempo de llegada en B y el tiempo de salida del vuelo con destino a A. El objetivo consiste en emparejar los vuelos de manera que se minimice el tiempo de escala total de todas las tripulaciones. Resuelva el problema como un modelo de asignacin mediante el uso del itinerario dado DESDE A DESDE A VUELO A B VUELO B A 1 6.00 8.30 10 7.30 9.30 2 8.15 10.45 20 9.15 11.15 3 13.30 16.00 30 16.30 18.30 4 15.00 17.30 40 20.00 22.00 El Problema de la Asignacines un problema clsico de la Investigacin de Operaciones y es un caso particular delProblema del Transporte. Este problema se trata deasignaruna serie deRecursosa una serie detareas. Tiene una limitante y es que a cada tarea se le puede asignar slo un recurso, pueden sobrar recursos o podran sobrar tareas pero no se le puede asignar dos recursos a una misma tarea, o tres... por ejemplo si se tienen tres operarios con diferentes tiempos de operacin en cuatro mquinas el modelo nos dira como asignar los tres operarios a tres mquinas (nos sobrara una) de manera que se minimice el tiempo total, pero no nos dira como asignar dos operarios a dos mquinas y el otro operario a las otras dos mquinas... si el Problema en la Vida Real se puede simplificar de esa manera, o de hecho es requerido que sea as (un recurso para una tarea), pues como se dice aqu: "santo y bueno", pero sino ser necesario modelarlo como unPrograma Lineal y resolverlo con el Simplex. Ejemplos de Asignaciones: Operarios a Tareas, Mquinas a Operarios, Nadadores a Estilos, Novias a das de la semana, etc, etc, etc. El Problema de la Asignacin se basa en una informacin comparativa para tomar la decisin de que asignar a que, por ejemplo una matriz de costos, una matriz de tiempos, de ingresos, etc. Cuando la matriz no est balanceada, es decir, cuando no es cuadrada, cuando sobran filas o columnas, se debe balancear para que tenga solucin mediante la inclusin de filas o columnas ficticias, con valores de cero en dicha matriz.

Formulacin de Programacin Lineal: Ejemplo: Existen cuatro operarios que se pueden asignar al trabajo con tres mquinas. Un estudio de tiempos y movimientos ha arrojado los siguientes tiempos por operario para las tres mquinas. Indicar que operario debe trabajar en que mquina y cul de ellos no ser asignado a ninguna. Como la matriz no esta balanceada, es necesario incluir una mquina ficticia:(esto es fundamental para asegurar que haya una respuesta. Si la matriz no est balanceada, el problema no ser factible de resolver)

Xij = Se debe asignar el operario i a la mquina j? S o no?En matemticas existen dos nmeros cuyas propiedades hacen que puedan representar estas respuestas son el 1 y el 0, debido a que todo nmero multiplicado por 1 da el mismo nmero entonces el 1 se puede reemplazar por la respuesta S y como todo nmero multiplicado por cero da cero entonces se puede reemplazar por la respuesta No.As por ejemplo: 10X11+ 7X12+ 9X13 + 0X14 representa el tiempo sumado que empleara el operario1 en operar las mquinas, pero solo una variable de las tres anteriores puede tomar el valor de S, o sea de 1 las dems tendrn que tomar el valor de 0, y eso es debido a que el operario 1 slo puede ser asignado a una mquina, lo que significara que el tiempo que utilice el operario 1 puede ser ya sea de "10" de "7" o de "9". Con base en esto podemos formular la funcin objetivo: Min Z = 10X11+ 7X12 + 9X13 7X21+ 5X22 + 8X23 9X31+ 8X32+ 10X33 8X41+ 9X42+ 7X43 Restricciones: Como cada operario slo puede estar asignado a una mquina.... X11+ X12+ X13+ X14= 1X21+ X22+ X23+ X24= 1X31+ X32+ X33+ X34= 1X41+ X42+ X43+ X44= 1 Y como cada mquina solo puede tener un operario asignado... X11+ X21 + X31+ X41= 1X12+ X22 + X32+ X42= 1X13+ X23+ X33+ X43= 1X14+ X24 + X34+ X44= 1 Xij = 1 o 0 para toda i,j. Al resolver utilizando Software, por ejemplo el Solver del Excel, la respuesta que se obtiene es la siguiente: Esto significa que el Operario 1 queda asignado a la Mquina Ficticia (es decir, es el que sobra), el operario 2 se asigna a la mquina 2, el operario 3 se asigna a la mquina 1 y el operario 4 se asigna a la mquina 3.

Algoritmo Hngaro: El Algoritmo Hngaro sirve para reemplazar los mtodos tradicionales de la Programacin Binaria, que implican muchos clculos, aprovechando la forma especial que tienen los problemas de Asignacin. Los siguientes pasos que se presentan a continuacin son para minimizar, pero con algunas modificaciones se puede emplear tambin para maximizar. Si la matriz no est balanceada, balancearla incluyendo las filas o columnas ficticias necesarias. De cada elemento de la matriz restar el mnimo valor de cada fila De cada elemento de la matriz restar el mnimo valor de cada columna Realizar la Asignacin de la siguiente manera: Cada cero que se encuentre en la matriz significa que se puede asignar esa fila a esa columna, pero una vez hecha esta asignacin, ya no se tendr en cuenta todos los dems ceros de esa misma fila y esa misma columna, debido a que slo se puede asignar una fila a una columna.Buscar de arriba a abajo la fila que tenga menos ceros, pero que mnimo tenga uno. (Pues si no tiene ninguno significa que esa fila no se puede asignar a ninguna columna) y asignar esa fila a la columna donde esta el cero (puede ser el primer cero que encuentre de izquierda a derecha). Tachar esa fila y esa columna para indicar que ya fueron asignados, para que los dems ceros de esa fila y esa columna no se tengan en cuenta. Repetir este paso hasta que haga todas las asignaciones que ms pueda. Si todas las filas quedaron asignadas a todas las columnas el problema ha finalizado y esa es la solucin ptima, sino ser necesario utilizar el mtodo de Flood (tambin se llama condicin de Kning) que se explica a continuacin. Mtodo de Flood. Sealar todas las filas que no tienen una asignacin. (Cuando digo sealar puede ser una pequea X a la izquierda de la fila o arriba de la columna) Sealar todas las columnas que tengan un cero en la columna sealada. Sealar todas las filas que tienen una asignacin en las columnas indicadas. Repetir estos pasos hasta que no pueda sealarse ms columnas o filas. Dibujar una lnea por cada fila NO sealada y por cada columna SI sealada. Encontrar el mnimo valor de los elementos no cubiertos y restarlo a todos los elementos no cubiertos, y sumar este valor a cada elemento que se encuentre en la interseccin de una lnea horizontal con una lnea vertical. Realizar la Asignacin... si no es ptima hacer flood, iterar hasta que se pueda hacer la asignacin. MODELOS DE ASIGNACIN

Los problemas de asignacin se ocupan de asignar trabajadores a tareas sobre una base de uno a uno. Se considera el nmero de trabajadores igual al nmero de tareas (condicin que puede garantizarse creando trabajadores o tareas ficticias) y se conoce el tiempo Cij que necesita el trabajador i para terminar la tarea j. El objetivo es asignar a cada trabajador una tarea de manera que todas las tareas se terminen en un tiempo total mnimo. El problema de asignacin puede transformarse en un problema de transporte al considerar a los trabajadores como orgenes y a las tareas como destinos con todos los suministros y demandas igual a uno. Mtodo hngaro El algoritmo que se utiliza para resolver el problema de asignacin es el mtodo hngaro que consta de cuatro pasos: 1. Localice el menor elemento de cada rengln y rstelo a los dems elementos del mismo rengln. Reptase este procedimiento para cada columna donde el mnimo por columna se determina despus de las restas de los renglones. 2. Determine si existe una asignacin factible que involucre costos cero en la matriz revisada de costos. Si existe tal asignacin es ptima. Si no existe contine con el paso 3. 3. Cubra todos los ceros en la matriz revisada de costos con el menor nmero de lneas horizontales y verticales que sea posible. Cada lnea horizontal debe pasar por todo el rengln y cada lnea vertical por toda la columna. Localice el nmero menor que no est cubierto por una lnea en la matriz de costos. Reste el valor de este nmero a cada elemento no cubierto por una lnea y smelo a cada elemento cubierto por dos lneas. 4. Repita el procedimiento del paso 2. Ejemplo 1. Una cadena de restaurantes de servicio rpido desea construir cuatro tiendas. Anteriormente, la compaa ha empleado 6 diferentes compaas y, estando satisfecha con todas ellas, las ha invitado a concursar para cada trabajo. Las ofertas finales en miles de dlares son las que se muestran. tienda constructoras

Ya que la cadena desea tener listos los nuevos establecimientos tan pronto como sea posible otorgar cuando ms un trabajo a cada compaa constructora, que asignacin da como resultado un costo total mnimo para la cadena de restaurantes? Ejemplo 2. Una competencia de relevos de 400 metros incluye a cuatro diferentes nadadores quienes nadan sucesivamente 100 metros de dorso, pecho, mariposa y libre. Un entrenador tiene 6 nadadores muy veloces cuyos tiempos esperados en segundos en los eventos individuales se dan en la tabla Cmo deber el entrenador asignar los nadadores a los relevos a fin de minimizar la suma de sus tiempos?