CONCEPTO
Estos problemas ocurren en muchos contextos de la administración. En general consisten en el problema para determinar la asignación óptima de agentes objetos “indivisibles”, en el sentido de que ningún agente se puede dividir entre varias tareas. La restricción importante, para cada agente, es que será designado a una solo una tarea.
El problema de asignación puede resolverse como un problema de transporte en el cual la oferta de cada origen y la demanda de cada destino son iguales a 1, o con le método simplex, sin embargo el método Húngaro resuelve este tipo de asignaciones de una manera mas sencilla.
El enfoque general de este alogaritmo consiste en "reducir" la matriz de costos mediante una serie de operaciones aritmeticas.
- EJEMPLO DE CASO DE MINIMIZACIÓN
El presidente de Industrias RACR-Europa, cuya gerencia general se encuentra en Bruselas, ha decidido este año, como parte de su auditoria anual, que cada uno de los cuatro vicepresidentes visite e inspeccione una de las plantes de ensamblaje durante las dos primeras semanas de junio. Las plantas de ensamble esta ubicadas el Leipzig, Alemania; Nancy, Francia; Lieja, Bélgica y Tilburgo, Holanda. En este tipo de problemas utilizaremos el método de aignación o método húngaro, el cuál consiste en los siguientes pasos:
PASO 1 Elaboración de la tabla de costos por asignación.
PASO 2 Restar el valor mas pequeño de cada uno de los demás valores de la columna:
En la priemra columna Leipzig, el valor más pequeño es 11. Este valor se le resta a los demás valores de la columna.
En la segunda columna Nancy, el valor más pequeño es 10.
En la tercera columna Lieja, el valor más pequeño es 10.
El la cuarta columna Tilburgo, el valor más pequeño es 11.
PASO 3. Resta el valor más pequeño de cada renglon de los demàs valores de ese renglon.
En el primer renglon, el valor más pequeño es 0.
En el segundo renglon, el valor más pequeño es 0.
En el tercer renglon, el valor más pequeño es 4.
En el cuarto renglon, el valor más pequeño es o.
PASO 4. Se traza el minimo número de líneas que puedan pasar através de todos los ceros de la tabla. Las lineas diagonales no se permiten. En algunos casos este paso causa dificultades, ya que ordinariamente hay muchas formas de trazar estas lineas. Las diferentes alternativas son posibles siempre y cuando el número de lineas sea mínimo.Por ejemplo se pueden trazar las líneas en la tabla de la siguente manera :
Este trazado abarca todos los ceros de la tabla, pero se realizó con 3 lineas únicamente, por lo tanto este trazado es mejor.
PASO 5. Despues de trzar el número mínimo de líneas se hace la prueba de optimalidad. Si en número de líneas es igual a n (número de renglones o columnas), es la solución óptima. Si el número de líneas es menor a n, se requiere continuar con el proceso hasta calcular la solución óptima. En la tabla, el número de líneas es de 3 y el de renglones/columnas 4, por lo tanto hay que continuar con el procedimiento, el cual consiste de los siguientes pasos:
De los valores que no se tacharon, se selecciona el mínimo, en este ejemplo el mínimo es 3. Este valor se debe restar a todos los valores que no están cruzados por ninguna linea.
También se debe sumar esta cantidad a todos los valores situdos en la intersección de líneas.
Todos los demás valores (los que están cruzadoz únicamente por una línea), permanecen inalterados.
PASO 6. Esta tabla es posible solución, por l otanto hay que realizar el procedimiento a partir del paso 4.
Trazando el mínimo número de líneas para cubrir todos los ceros, se obtiene lo siguiente
La prueba de optimalidad: ¿número de líneas= número de reglón/columna? En este caso hay 3 líneas y 4 renglones/columnas, por lo tanto hay que continuar con el procedimiento.
Se elige el mínimo valor de los valores de la tabla que no estàn cruzados. En este caso 1.
Se resta valor a todos los valores de la tabla no cruzados de la tabla y se suma a los valores de las casillas situadas en la intersección de líneas, los demás valores permanecen inalterados.
El resultado de la nueva tabla es:
Es una nueva posible solución, por lo tanto, se repite el procedimiento a partir del cuarto paso.
Se traza el mínimo número de líneas que cubran todos los ceros de la tabla.
Se realiza la prueva de optimalidad, como el núero de líneas es igual al número de rengloes, el proceso termina. La solución óptima se localiza en la casilla que contiene cero, lo cual significa que es la asignación de la intersección.
La casilla del primer renglón , segunda columna tiene un cero, como es la intesección de Finanzas y Nancy, quiere decir que se asignará la Ciudad de Nancy, Francial al vicepresidente de Finanzas.
Como habrá renglones que tengan más de 2 ceros, se recomienda que se comience con los renglones de un solo cero, de esa manera podremos eliminar esa asignación y continuar con las que queda.
- EJEMPLO CASO MAXIMIZACIÓN
Un administrador enfrenta el problema de asignar cuatro nuevos métodos a tres medios de producción. La asignación de nuevos métodos aumenta las utilidades, según las cantidades mostradas en la siguiente tabla. Determinar la asignación óptima si solo puede asignarse un método a un medio de producción
El procedimiento a seguir es el explicado en el caso de minimización, excepto que después del paso 1 se deberá realizar un paso intermedio el cual consiste, en:
- Selccionar de toda la tabla del paso 1 el término númerico mayor.
- Seleccionado este término, se debe restar todos los demas valores de la tabla original.
- En caso de que la tabla no tenga igual número de renglones que de columnas se debe completar dicha matriz en renglones o columnas, según faltaren para que éstos sean iguales. Los costos o términos numéricos de las casillas deberán ser cero.
PASO 1. Realizar tabla inical.
PASO ADICIONAL: Selecionar el máximo valor de la tabla (13.5) y restar a todos los valores de la tabla, así como complementar el número de columnas, ya que hay cuatro renglones y solo 3 columnas.
Máximo valor de la tabla 13.5
PASO 2. A partir de aquí, y con esta tabla, se realiza el procedimiento exactamente igual que si fuera minimización.
Si nos damos cuenta la ñ ahorra ya paso a la base.
