viernes, 2 de septiembre de 2011

Tabla de Resumen del Problema de Asignación

Historia del modelo



En 1941 F. L. Hitchcock publica una solución analítica a este problema
En 1972 Thomas Jefferson quien lo sugirió para asignar a cada representante por estado.
Debe su nombre a asignar hombres a trabajos
La estructura particular del problema hace que las soliciones  sean degeneradas y permitió a los matematicos húngaros Köning y Egerváry demostrar un teorema esencial para el desarrollo del Método Húngaro.
Los representantes del método de trabajos o tareas formaron el primer
movimiento pedagógico del siglo XX. Los nombres más conocidos en
Estados Unidos son John Dewey (cuya filosofía educacional es la base de
este método); William Kilpatrick, Helen Parkhurst (Plan Dalton) y Carleton
Washburne (Plan Winnetka). En otros países europeos son Maria
Montessori (Italia), Adolph Ferriere (Suiza), Ovide Decroly (Bélgica),
Celestin Freinet (Francia) y Kerschensteiner, Gaudig y Peter Peterson
(con el Plan Jena) en Alemania.
Más adelante se desarrolló el “método del texto conductor”, OIT que
difundió como “cartillas de trabajo”, especialmente para la formación de
profesionales (nivel superior). En el perfeccionamiento en el trabajo (por
ejemplo, de los docentes) en la enseñanza a distancia se han utilizado
variantes del método de trabajo o de tareas en forma de “aprendizaje
mediante la realización de tareas” que puedan estar asociadas al mismo
trabajo de la persona que se perfecciona.




Elementos



·         Consiste en asignar recursos a tarea en función de un objetivo ligado a la eficiencia del sistema
·         Minimizar el costo total de operación de modo que: cada tarea asigne a una y sólo una máquina, cada máquina realice una y sólo una tarea


·         Matriz de costos
·  
 Debe ser balanceado para que la matriz de costos sea cuadrada

Ejemplo

Un ejemplo típico es el de asignación de personas a turnos horarios, o el de asignar personas a maquinas.

En un cierto punto del algoritmo tenemos el grafo G y la matriz C' .

Problema de 5 operarios y 5 cargos
Problema de departamento 1 a 3
Problema con máquinas, 4 áreas, 4 máquinas 

Método de Solución

Método Simplex
Técnica del transporte

Método Húngaro
  1. Determine la tabla de costo de oportunidad:
    1. Reste el elemento del costo más bajo en cada columna de la tabla de costo dada, de todo los elementos en esa columna.
    2. Reste el asiento más bajo en cada renglón de la tabla obtenida en la parte 1.1 de todos los números en ese renglón.
  2. Determine si se puede hacer una asignación óptima: El procedimiento es dibujar líneas rectas (verticales y horizontales) a través de la tabla de costos total de oportunidad, de tal manera que se minimice el número de líneas necesarias para cubrir todos los cuadros CERO. Si el número de líneas dibujadas es menor que el número de renglones o columnas, no se puede hacer una asignación óptimas y el problema no está resuelto.
  3. Revise la tabla de costo total de oportunidad.
    1. Seleccione el número más pequeño en la tabla no cubierto, por una línea recta y reste este número de todos los números no cubiertos por una línea recta.
    2. Añada este mismo número a los números que están en la intersección de dos líneas cualesquiera. Regrese al paso 2.


Programas existentes 

El programa InvOp (361 kb)
Win QSB
TORA
LINDO
SB2





1 comentario: