IO U.2.3 Problemas de Asignaciขn.

Investigació n de
Operaciones I
Ing. Gabriela María Sánchez Angulo.

2.3 Problemas de
Asignació n
Problemas de Asignación
(Método Húngaro)
Los problemas de asignación tienen por objetivo asignar agentes o personal, a

trabajos o máquinas, de tal forma que se minimicen los costos de esa
asignación.
Reglas a cumplir
• M = N Tiene que ser una matriz cuadrada

• Un trabajo para una máquina uno para uno
Método Húngaro
El método Húngaro es un método de optimización de problemas de

asignación, conocido como tal gracias a que los primeros aportes al
método clásico definitivo fueron de dos matemáticos húngaros. El
algoritmo tal como se detallará a continuación está diseñado para la
resolución de problemas de minimización únicamente.
Pasos a seguir:
1. Se identifica el menor costo por cada renglón

2. Restar a cada costo el menor costo identificado por renglón.
3. Se identifica el menor costo por cada columna.
4. Restar a cada costo el menor costo identificado por columna.
5. Asignar si es posible (solución factible), de lo contrario, tachar los
ceros con el menor número de líneas, si el número de líneas es igual
al número de filas o columnas se ha logrado obtener la solución
óptima (la mejor asignación según el contexto de optimización), si el
número de líneas es inferior al número de filas o columnas se deben
de seguir los siguientes pasos:
a) Determinar el número menor no tachado, restar este número, de todos

los números no tachados.
b) Sumar este número a los números tachados con dos líneas
(intersección).
c) Asignar si es posible solución factible, de lo contrario, tachar
nuevamente.
Ejemplo 1
Para asignar una solución nos tenemos que basar en los 0 de la matriz,
verificando si para cada trabajo hay una máquina asignada. Los 0 son
los que nos marcan las asignaciones de trabajos.
En este ejemplo, el trabajo 1 se asignará a la máquina 1, ya que es en donde
está el 0. El trabajo 2 puede ser asignado a la máquina 2 o a la máquina 3.
Cuando existen dos 0 en un trabajo, nos tenemos que pasar al siguiente
trabajo y asignarlo a una máquina, para poder entonces, asignar el trabajo 2.
El trabajo 3 se asignará a la máquina 2, por lo tanto el trabajo 2 será asignado
para la máquina 3.
ASIGNACIÓN
Trabajo 1 a Máquina 1
Por último obtenemos el costo de asignar los trabajos a las máquinas,
sumando los costos en donde fueron asignados trabajos.
COSTO = 5 + 12 + 13
COSTO = $ 30
Ejemplo 2
1. Identificamos el costo menor por renglón
2. Restar a cada costo el menor costo identificado

3. Se identificada el costo menor por cada columna
4. Restar a cada costo, el menor costo identificado por columna.

5. Asignar si es posible (solución factible).
5. Asignar si es posible (solución factible).
En este ejemplo aún no podemos asignar solución factible, ya que el Trabajo 1

y 3, solo se pueden asignar a la máquina 1, por lo tanto, tachar los ceros con el
menor número de líneas, si el número de líneas es igual al número de filas o
columnas se ha logrado obtener la solución óptima (la mejor asignación
según el contexto de optimización).
Si el número de líneas es inferior al número de filas o columnas se deben de
seguir los siguientes pasos:
a) Determinar el número menor no tachado, restar este número, de todos
los números no tachados.
b) Sumar este número a los números tachados con dos líneas (intersección).
c) Asignar si es posible solución factible, de lo contrario, tachar nuevamente.
Para asignar la solución factible, verificamos que para cada trabajo haya una
máquina. Iniciamos con el trabajo 1 que se asignará a la máquina 1. El trabajo
2 puede ser asignado a la máquina 2 y a la 3, por lo tanto, paso al trabajo 3. El
trabajo 3 puede ser asignado a la máquina 1 y 2, pero la máquina 1 ya está
asignada al trabajo 1, por lo tanto el trabajo 3 se asigna a la máquina 2.
Regreso al trabajo 2 que será asignado a la máquina 3. Por último asigno el
trabajo 4 a la máquina 4, ya que no puedo asignarlo la máquina 3, porque
dicha máquina ya tiene un trabajo asignado.
Por último obtenemos el costo de asignar los trabajos a las máquinas,
sumando los costos en donde fueron asignados trabajos.
COSTO = 1 + 10 + 5 + 5
COSTO = $21
Ejemplo 3
Asignación Costo
Ejemplo 4
Asignación Costo
Ejemplo 4
Asignación Costo

IO U.2.3 Problemas de Asignaciขn.

Cargado por

Copyright:

Formatos disponibles

IO U.2.3 Problemas de Asignaciขn.

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

IO U.2.3 Problemas de Asignaciขn.

Cargado por

Copyright:

Formatos disponibles

Investigació n de

Ing. Gabriela María Sánchez Angulo.

Los problemas de asignación tienen por objetivo asignar agentes o personal, a

• M = N Tiene que ser una matriz cuadrada

El método Húngaro es un método de optimización de problemas de

1. Se identifica el menor costo por cada renglón

a) Determinar el número menor no tachado, restar este número, de todos

2. Restar a cada costo el menor costo identificado

4. Restar a cada costo, el menor costo identificado por columna.

En este ejemplo aún no podemos asignar solución factible, ya que el Trabajo 1

También podría gustarte