UNIDAD IV I de Operaciones - Barbara Hernandez

INTEGRANTE
BARBARA HERNANDEZ
C.I: 28.291.393
IF-01 T3 - REPITENCIA
INVESTIGACION DE OPERACIONES
PROFESOR: RONALD BERMUDEZ
MODELO DE ASIGNACION
El modelo de asignación es un tipo especial de problema de programación lineal en el que
los asignados son recursos que se destinan a la realización de tareas. Por ejemplo, los
asignados pueden ser empleados a quienes se tiene que dar trabajo. La asignación de
personas a trabajos es una aplicación común del problema de asignación. Sin embargo, los
asignados no tienen que ser personas. También pueden ser máquinas, vehículos o plantas, o
incluso periodos a los que se asignan tareas.
 El objetivo del modelo es determinar la asignación óptima (de costo mínimo) de
trabajadores a puestos.
 Para que se ajuste a la definición de un problema de asignación, es necesario que
este tipo de aplicaciones se formule de manera tal que se cumplan los siguientes
supuestos:
 El número de asignados es igual al número de tareas. (Este número se denota por n.)
 A cada asignado se le asigna sólo una tarea.

 Cada tarea debe realizarla sólo un asignado.
 Existe un costo cij asociado con el asignado i (i 5 1, 2, . . . , n) que realiza la tarea j (
j 1, 2, . . . , n).
 El objetivo es determinar cómo deben hacerse las n asignaciones para minimizar los
costos totales.
 Se puede resolver el modelo de asignación en forma directa como modelo normal
de transporte. Sin embargo, el hecho de que todas las ofertas y las demandas son
iguales a 1, condujo al desarrollo de un algoritmo sencillo de solución llamado
método húngaro.
CARACTERISTICAS DEL METODO DE ASIGNACION
METODO HUNGARO
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 Dénes
König y Jenő Egerváry 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.
Es importante resaltar que el método húngaro trabaja en una matriz de costos n*m (en este
caso conocida como matriz m*m, dado que el número de filas es igual al número de
columnas n = m).
Para resolver problemas de asignación, aplicando el método Húngaro, se requiere seguir los
siguientes algoritmos o pasos:
 Paso 1
En la matriz original de costo, identificar el mínimo de cada renglón y restarlo de todos los
elementos del renglón.
 Paso 2
En la matriz que resulte del paso 1, identificar el mínimo de cada columna, y restarlo de
todos los elementos de la columna.
 Paso 2.1
Si no se puede asegurar una asignación factible (con todos los elementos cero) con los
pasos 1 y 2,
a). Trazar la cantidad mínima de líneas horizontales y verticales en la última matriz
reducida que cubran todos los elementos cero.
b). Seleccionar el elemento mínimo no cubierto, restarlo de todo elemento no cubierto y a
continuación sumarlo a todo elemento en la intersección de dos líneas.
c). Si no se puede encontrar una asignación factible entre los elementos cero que resulten,
repetir el paso 2.1. En caso contrario, seguir en el paso 3 para determinar la asignación
óptima.
 Paso 3
Identificar la solución óptima como la asignación factible asociada con los elementos cero
de la matriz obtenida en el paso 2.
EJEMPLO
Un equipo de 3 mecánicos debe ser asignado para la realización de 3 tareas, donde cada
mecánico debe hacer una tarea. Se requiere encontrar la asignación de costo mínimo para lo
cual se dispone de los costos asociados a que el mecánico i realice la tarea j.
PASO 1: En la matriz original de costo, identificar el mínimo de cada renglón y restarlo de
todos los elementos del renglón.

PASO 2: En la matriz que resulte del paso 1, identificar el mínimo de cada columna, y
restarlo de todos los elementos de la columna.
PASO 3: Identificar la
solución óptima como la asignación factible asociada con los elementos cero de la matriz
obtenida en el paso 2.
Las celdas con valor cero y color cafés son la solución óptima. En consecuencia el
mecánico 1 realiza la tarea 2, el mecánico 2 asuma la tarea 1 y el mecánico 3 la tarea 3.
Cada mecánico realiza exactamente una tarea y el costo total de dicha asignación (valor
óptimo) es de Q9+Q10+Q8=Q27.

UNIDAD IV I de Operaciones - Barbara Hernandez

Cargado por

Copyright:

Formatos disponibles

UNIDAD IV I de Operaciones - Barbara Hernandez

Cargado por

Información del documento

Descripción original:

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

UNIDAD IV I de Operaciones - Barbara Hernandez

Cargado por

Copyright:

Formatos disponibles

INTEGRANTE

incluso periodos a los que se asignan tareas.

 El objetivo del modelo es determinar la asignación óptima (de costo mínimo) de

 Para que se ajuste a la definición de un problema de asignación, es necesario que

 A cada asignado se le asigna sólo una tarea.

 Existe un costo cij asociado con el asignado i (i 5 1, 2, . . . , n) que realiza la tarea j (

 Se puede resolver el modelo de asignación en forma directa como modelo normal

iguales a 1, condujo al desarrollo de un algoritmo sencillo de solución llamado

CARACTERISTICAS DEL METODO DE ASIGNACION

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

continuación está diseñado para la resolución de problemas de minimización únicamente.

siguientes algoritmos o pasos:

elementos del renglón.

todos los elementos de la columna.

a). Trazar la cantidad mínima de líneas horizontales y verticales en la última matriz

reducida que cubran todos los elementos cero.

b). Seleccionar el elemento mínimo no cubierto, restarlo de todo elemento no cubierto y a

continuación sumarlo a todo elemento en la intersección de dos líneas.

de la matriz obtenida en el paso 2.

cual se dispone de los costos asociados a que el mecánico i realice la tarea j.

PASO 1: En la matriz original de costo, identificar el mínimo de cada renglón y restarlo de

todos los elementos del renglón.

restarlo de todos los elementos de la columna.

También podría gustarte