Tabla resumen: Problema de Asignación
1.-Historia del Modelo
En 1792 no hubo una única propuesta de método de asignación: Alexander Hamilton propuso uno alternativo al propuesto por Jefferson, también para asignar sillas a los estados de la Unión. A los pocos años, en 1850, se lo adoptaba para la asignación de representantes del parlamento de los Estados Unidos hasta 1900 por sugerencia de Samuel Vinton, representante de Ohio, por lo cual se conoce como el método de Vinton. Después de muchas discusiones, el método fue elegido por el Presidente Roosevelt en 1941 para asignar representantes en el Congreso de los Estados Unidos; las discusiones siguieron con el aporte de muchos otros matemáticos a fin de comparar los diferentes métodos de asignación. Para detalles, ver Huntington (1941) y Balinski y Young (1975).
2.- Elemento
Tiene que estar balanceada nuestra matriz de costos, es decir que sea cuadrada, en caso de agregar renglones o columnas estas tiene un valor de cero.
Buscamos minimizar el costo.
Cada uno de los agentes debe ser asignado a una tarea.
Cada tarea debe ser asignada a un agente.
Todas las ofertas y las demandas son iguales a 1.
3.- Ejemplo
El número de personas a asignar m es igual al número de lugares n.
Todas las asignaciones son posibles.
Algunos de ellos son:
1.- Trabajos a trabajadores.
2.- Máquinas a tareas.
3.- Calificaciones a alumnos.
4.- Método de Solución
El problema de solución es un caso particular del problema de transporte.
1.- Simplex
2.- Técnica de Transporte.
3.- Método Húngaro.
Pasos del Método Húngaro:
1.- Reducción en renglones: Elabore en una nueva matriz eligiendo el costo mínimo de cada renglón y restándolo de cada costo de ese renglón.
2.- Reducción en columna: Elija el elemento de costo mínimo en cada columna y résteselo a cada columna.
3.-.Determine si la matriz es reducida: Encuentre el número mínimo de líneas rectas que se puede trazar sobre los renglones y columnas para cubrir todos los ceros. Si este es igual al de renglones (o columnas) se dice que la matriz es reducida y se tiene la solución óptima.
4.-Reducciones posteriores: Encuentre la menor de las celdas no cubiertas (sin línea recta).Resté el valor de esta celda a todas las celdas no cubiertas.
5.- Localización de la solución óptima: Las celdas de costo cero se eligen, una por columna y renglón, a fin de hallar una solución óptima. Se suman los costos originales de las celdas con asignación para saber el costo total.
4.- Programas existentes
1.-WinQSB
2.- Invop
3.- Excel Solver
4.- Tora
5.- Lindo
6.- QM2
Referencia de la Página:
http://www.matematicaelectoral.cl/Metodos/Historia.htm http:www.ccee.edu.uy/ensenian/catmetad/material/apoyoModelo%2Asignacion.pdf
No hay comentarios:
Publicar un comentario