Asignacion Cuadratica
Páginas: 14 (3450 palabras)
Publicado: 3 de octubre de 2012
TECNOLOGICO DE ESTUDIOS SUPERIORES DE COACALCO
Materia: Planeación y Diseño de Instalaciones
Profesora: Ingeniera Paola Ovalle Palma
Tema: “Asignación Cuadrática”
Grupo: 2711
Carrera: Ingeniería Industrial
Fecha de Entrega: 3/Octubre/2010
Equipo: 9
Nombre de lo Alumno:
Bajaras Rojas Hazael
Cárdenas López Isaías
De la Rosa Cordero Rubén
Hernández Meza Karla Luz
MartínezLara Tomas
INTRODUCCION
El Problema de Asignación Cuadrática (QAP – Quadratic Assignment Problem) es un problema clásico de optimización combinatorio, en el cual se encuentra un vasto número de problemas de diseño y de distribución de recursos en diferentes campos, donde la decisión a tomar es una asignación de elementos de un conjunto en otro. El QAP es consideradocomo un problema complejo y dificultoso de resolver y puede establecerse como un conjunto de n elementos distintos que deben ser localizados (asignados) en n localidades distintas de forma óptima. Aunque se han propuesto numerosas heurísticas y procedimientos, los Algoritmos Evolutivos han emergido como una clase de búsqueda aleatoria de varios puntos concurrentemente sobre un espacio desoluciones factibles; tales algoritmos son inspirados por mecanismos de la evolución natural y mecanismos genéticos introducidos por J. Holland en los años 70 . Experimentos reales sobre algoritmos evolutivos para QAP se iniciaron a principios de los 90’s; David M. Tate y Alice E. Smith (1.992) establecen mecanismos de selección y reproducción, así como una posible codificación para problemas deAsignación Cuadrática . Para el año 1.995 B. R. Sarker y un grupo de colaboradores implementan un algoritmo secuencial: Depth – First Insertion Heuristic; para el problema de retrocesos de trabajos en la localización de una máquina en una línea unidimensional de flujo. Otra manera de tratar a los Algoritmos Genéticos es analizando su paralelismo intrínseco, tal como lo hizo G. Larrazábal en el año 1.996,cuando plantea un Algoritmo Genético Grano Grueso para un problema de alta dimensionalidad. Más tarde, Patrice Roger Calégari (1.999) en su trabajo de tesis doctoral, muestra la paralización eficiente de Algoritmos Evolutivos. Recientemente fue tratado un problema cuadrático de asignación de facilidades por N. Maneiro (2.001) empleando un algoritmo evolutivo simple ; el cual consistió en localizarun grupo de m máquinas de tal manera que se minimice el retroceso backtracking (es una estrategia para encontrar soluciones a problemas que satisfacen restricciones) dentro de una línea de flujo generalizado.
MARCO TEORICO
* QAP: Es un problema estándar en la teoría de locación. En éste se trata de asignar N instalaciones a una cantidad N de sitios o locaciones en dondese considera un costo asociado a cada una de las asignaciones.
* Método: Proceso o camino sistemático establecido para realizar una tarea o trabajo con el fin de alcanzar un objetivo predeterminado o procedimiento que se usa para realizar una tarea específica en la clase o módulo y procedimiento para alcanzar algo que se adopta para enseñar o educar.
* Algoritmos Evolutivos: Los AlgoritmosEvolutivos son heurísticas basadas en los principios de evolución natural y genética introducido por J. Holland en los años 70’s.
* Metodo Hungaro: Fue inventado y publicado por Harold Kuhn en 1955, una matriz de costes n×m, donde cada elemento representa el coste de asignar el enésimo trabajador al enésimo trabajo. Por defecto, el algoritmo realiza la minimización de los elementos de lamatriz; de ahí que en caso de ser un problema de minimización de costes, es suficiente con comenzar la eliminación de Gauss-Jordan para hacer ceros (al menos un cero por línea y por columna).
* Algoritmo: conjunto ordenado y finito de operaciones que permite hallar la solución de un problema. Método y notación en las distintas fórmulas del cálculo.
* Elitismo: El elitismo es un sistema...
Materia: Planeación y Diseño de Instalaciones
Profesora: Ingeniera Paola Ovalle Palma
Tema: “Asignación Cuadrática”
Grupo: 2711
Carrera: Ingeniería Industrial
Fecha de Entrega: 3/Octubre/2010
Equipo: 9
Nombre de lo Alumno:
Bajaras Rojas Hazael
Cárdenas López Isaías
De la Rosa Cordero Rubén
Hernández Meza Karla Luz
MartínezLara Tomas
INTRODUCCION
El Problema de Asignación Cuadrática (QAP – Quadratic Assignment Problem) es un problema clásico de optimización combinatorio, en el cual se encuentra un vasto número de problemas de diseño y de distribución de recursos en diferentes campos, donde la decisión a tomar es una asignación de elementos de un conjunto en otro. El QAP es consideradocomo un problema complejo y dificultoso de resolver y puede establecerse como un conjunto de n elementos distintos que deben ser localizados (asignados) en n localidades distintas de forma óptima. Aunque se han propuesto numerosas heurísticas y procedimientos, los Algoritmos Evolutivos han emergido como una clase de búsqueda aleatoria de varios puntos concurrentemente sobre un espacio desoluciones factibles; tales algoritmos son inspirados por mecanismos de la evolución natural y mecanismos genéticos introducidos por J. Holland en los años 70 . Experimentos reales sobre algoritmos evolutivos para QAP se iniciaron a principios de los 90’s; David M. Tate y Alice E. Smith (1.992) establecen mecanismos de selección y reproducción, así como una posible codificación para problemas deAsignación Cuadrática . Para el año 1.995 B. R. Sarker y un grupo de colaboradores implementan un algoritmo secuencial: Depth – First Insertion Heuristic; para el problema de retrocesos de trabajos en la localización de una máquina en una línea unidimensional de flujo. Otra manera de tratar a los Algoritmos Genéticos es analizando su paralelismo intrínseco, tal como lo hizo G. Larrazábal en el año 1.996,cuando plantea un Algoritmo Genético Grano Grueso para un problema de alta dimensionalidad. Más tarde, Patrice Roger Calégari (1.999) en su trabajo de tesis doctoral, muestra la paralización eficiente de Algoritmos Evolutivos. Recientemente fue tratado un problema cuadrático de asignación de facilidades por N. Maneiro (2.001) empleando un algoritmo evolutivo simple ; el cual consistió en localizarun grupo de m máquinas de tal manera que se minimice el retroceso backtracking (es una estrategia para encontrar soluciones a problemas que satisfacen restricciones) dentro de una línea de flujo generalizado.
MARCO TEORICO
* QAP: Es un problema estándar en la teoría de locación. En éste se trata de asignar N instalaciones a una cantidad N de sitios o locaciones en dondese considera un costo asociado a cada una de las asignaciones.
* Método: Proceso o camino sistemático establecido para realizar una tarea o trabajo con el fin de alcanzar un objetivo predeterminado o procedimiento que se usa para realizar una tarea específica en la clase o módulo y procedimiento para alcanzar algo que se adopta para enseñar o educar.
* Algoritmos Evolutivos: Los AlgoritmosEvolutivos son heurísticas basadas en los principios de evolución natural y genética introducido por J. Holland en los años 70’s.
* Metodo Hungaro: Fue inventado y publicado por Harold Kuhn en 1955, una matriz de costes n×m, donde cada elemento representa el coste de asignar el enésimo trabajador al enésimo trabajo. Por defecto, el algoritmo realiza la minimización de los elementos de lamatriz; de ahí que en caso de ser un problema de minimización de costes, es suficiente con comenzar la eliminación de Gauss-Jordan para hacer ceros (al menos un cero por línea y por columna).
* Algoritmo: conjunto ordenado y finito de operaciones que permite hallar la solución de un problema. Método y notación en las distintas fórmulas del cálculo.
* Elitismo: El elitismo es un sistema...
Leer documento completo
Regístrate para leer el documento completo.