Scribd
Cargar
102 vistas5 páginas

Optimización con Método Húngaro

El método húngaro es un algoritmo para resolver problemas de asignación que consta de 5 pasos: 1) restar el menor número de cada columna, 2) restar el menor número de cada fila, 3) trazar líneas para eliminar ceros, 4) restar/sumar el menor número no tachado, 5) asignar ceros restantes de forma óptima. Se presentan dos problemas de asignación para ilustrar el método.

Cargado por

GABY
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
102 vistas5 páginas

Optimización con Método Húngaro

El método húngaro es un algoritmo para resolver problemas de asignación que consta de 5 pasos: 1) restar el menor número de cada columna, 2) restar el menor número de cada fila, 3) trazar líneas para eliminar ceros, 4) restar/sumar el menor número no tachado, 5) asignar ceros restantes de forma óptima. Se presentan dos problemas de asignación para ilustrar el método.

Cargado por

GABY
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

MÉTODO HUNGARO

1 En cada columna se determina el número menor, y se


procede a restarlo de cada elemento de la columna.
2 En la nueva matriz se procede a determinar el número
menor de cada fila y se procede a restarlo de cada
elemento de la fila.
3 Luego en la matriz resultante se empieza a trazar
líneas a columnas y/o filas, con la finalidad de
desechar o tachar los ceros con el mínimo número de
líneas. Si el número de líneas mínimo trazado es igual
al número de filas o columnas de la matriz, entonces
nos encontramos en la solución óptima
Si el número mínimo de líneas trazadas es menor,
entonces se debe continuar con el paso número 4.
MÉTODO HUNGARO
4 Se elige el menor valor de la matriz que no ha sido
tachado y se procede con los siguientes pasos:
4.1 A los elementos no tachados se le resta el elemento
elegido.
4.2 A los elementos que se encuentran en la intersección de
dos líneas (tachados en cruz) se le aumenta el elemento
elegido. Se procede con los pasos 3 y 4 hasta la obtención
de la solución óptima.
5 Luego se procede a la asignación correspondiente a la
solución óptima, pasando a asignar a aquella fila o
columna que tenga un solo cero en primera instancia,
sino existiera se busca fila o columna con dos ceros y
así sucesivamente. Una vez hecha la asignación se
eliminan los otros ceros de la fila y columna de la
celda asignada, volviéndose a repetir el paso 5 desde el
inicio hasta la asignación completa de la matriz.
PROBLEMA Nº 1
Se tiene tres proyectos (1, 2, 3) para
localizarlos en las ciudades A, B, C.
Las utilidades que reportarían el
proyecto 1 en las ciudades A, B, C son
de 10, 15, 9; el proyecto 2 en las
ciudades A, B, C son de 9, 18 5 y el
proyecto 3 en las ciudades A, B, C son
de 6, 14, 3. Responder a las siguientes
preguntas:)
PROBLEMA Nº 1
1. ¿Cuál es el beneficio total?
a) 30 b) 35 c) 31 d) 33 e) ninguna
2. ¿Cuál es la asignación óptima?
a) 1A, 2B, 3C b) 1B, 2A, 3C c) 1C, 2B, 3A
d) 1A, 2C, 3B e) ninguna
3. Si en la ciudad A solo se puede realizar el
proyecto 1, cual sería la asignación óptima
a) 3C, 2B b) 3B, 2C c) 2B, 3C
d) ninguna
PROBLEMA Nº 2
Se tiene la siguiente matriz con las utilidades
que puede proporcionar la ejecución de los
siguientes proyectos por diversas compañías. Si
la asignación es única, utilizar el método
húngaro para obtener la solución que maximice
los beneficios.
Cía \ Proy. 1 2 3 4
A 20 15 15 10
B 30 10 30 15
C 15 20 15 20
D 20 10 30 25

También podría gustarte