El Metodo de Asignación

METODO DE ASIGNACION

Es una matriz cuadrada de n*n, donde cada elemento representa el costo de asignar el enésimo trabajador al enésimo trabajo; renglones = trabajadores.

Es la matriz que se obtiene después de haber restado el elemento más pequeño a cada renglón (reducción de renglones) y restarle a esa nueva matriz el elemento más pequeño a cada columna (reducción de columnas)

Sean un conjunto de fragmentos F = {F1 , F2,..., Fn} y una red formada por el conjunto de sitios S = {S1, S2,..., Sm} en la cual un conjunto de aplicaciones Q = {q1, q2,..., qq} se ejecutan.

Método de solución de los problemas de programación lineal donde se obtiene una solución factible y óptima (en donde se pueden obtener resultados como solución múltiple, solución no acotada, o que el problema no tenga solución).

ALGORITMO HÚNGARO, PASO 1

Antes que nada cabe recordar 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)

ALGORITMO HÚNGARO, PASO 2

Una vez se cumple el procedimiento anterior se debe construir una nueva matriz n*m, en la cual se consignarán los valores resultantes de la diferencia entre cada costo y el valor mínimo de la fila a la cual cada costo corresponde (valor mínimo hallado en el primer paso).

ALGORITMO HÚNGARO, PASO 3

Este paso consiste en realizar el mismo procedimiento de los dos pasos anteriores referidos ahora a las columnas, es decir, se halla el valor mínimo de cada columna, con la diferencia que este se halla de la matriz resultante en el segundo paso

ALGORITMO HÚNGARO, PASO 4

A continuación se deben de trazar líneas 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 número de líneas posibles

ALGORITMO HÚNGARO, PASO 5

Este 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 líneas

Objetivos de este Método (Alcance)

Al aplicar el método de asignación, la gerencia está buscando una ruta de distribución o una asignación que optimizará algún objetivo; éste puede ser la minimización del costo total, la maximización de las utilidades o la minimización del tiempo total involucrado.

Historia

Técnicas de Solución

El problema de asignación tuvo su origen en la revolución industrial, ya que el surgimiento de las máquinas hizo que fuera necesario asignar una tarea a un trabajador.

Pero no es hasta 1955 cuando Harold W. Kuhn plantea el Método húngaro.

Son varios los métodos para resolver el problema de asignación. Entre ellos están el método del simplex, algoritmo de transporte, método Húngaro,

ramificación y acotación, método del simplex dual.

Características

Método Húngaro

Algoritmo de transporte

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

Como el problema de asignación es una subclase del problema de transporte,es posible aplicar el algoritmo de transporte para su resolución.

• El problema de asignación debe estar equilibrado, es decir que la demanda y la oferta debe ser igual a 1.

• Si el numero de agentes y tareas son iguales y el coste total para todas las tareas es igual a la suma de los costes de cada agente ( o a la suma de los costes de cada tarea, que es lo mismo en este caso), entonces el problema es llamado Problema de Asignación Lineal.

Que es el método de asignación

Elementos del problema de asignación

Tabla de transporte:

Otra forma de plantear el problema de transporte ( recordemos que el problema de asignación es un caso especial del de transporte) es mediante una tabla llamada tabla de transporte, la cual tiene forma de matriz donde los renglones representan las fuentes y las columnas los destinos o trabajos.

Diferencias entre el Modelo de Transporte y el de Asignación

Matriz de costos

Método simplex

Matriz de costo reducida

Distribución óptima

El método de asignación también es un caso especial del modelo de transporte. Conocido como la Técnica de flood o el método Húngaro de asignación. El problema de asignación debe su nombre a la aplicación particular de asignar hombres a trabajos (o trabajos a máquinas), con la condición de que cada hombre puede ser asignado a un trabajo y que cada trabajo tendrá asignada una persona.

Los problemas de asignación presentan una estructura similar a los de transporte, pero con dos diferencias: asocian igual número de orígenes con igual número de demandas y las ofertas en cada origen es de valor uno, como lo es la demanda en cada destino.

La restricción importante para cada agente es que será asignado a una y solo una tarea.

Al hacer una asignación a menudo

deben cumplirse estas condiciones:

Para comprender mejor el tema veamos u ejemplo a continuación ...

• Cada elemento del primer grupo debe asignarse a exactamente un elemento del segundo grupo.
• Cada elemento del segundo grupo debe asignarse a exactamente un elemento del primer grupo.
• Su forma de programación es lineal.
• Se basa en tablas, se solucionan problemas de manera repetitiva (sumas y restas) para minimizar o maximizar.
• Requiere que a cada trabajador es le asigne una tarea especifica.