Metaheurísticas de Relajación

Description

Investigación de Operaciones Mind Map on Metaheurísticas de Relajación, created by Lizzi_Flor on 10/06/2013.
Lizzi_Flor
Mind Map by Lizzi_Flor, updated more than 1 year ago
Lizzi_Flor
Created by Lizzi_Flor almost 9 years ago
126
0

Resource summary

Metaheurísticas de Relajación
  1. Modelos modificados en los que es más sencillo encontrar buenas soluciones o en los que los procedimientos son más eficientes.
    1. Una relajación de un problema es un modelo simplificado obtenido al eliminar, debilitar o modificar restricciones (u objetivos) del problema real.
      1. Relajaciones del problema
        1. Las buenas relajaciones son las que simplifican el problema y hacen más eficientes los procedimientos de solución, pero cuya resolución proporciona muy buenas soluciones del problema original.
          1. Ejemplo
            1. Para un problema de programación lineal entera, su relajación lineal consiste en ignorar la restricción de que las variables sean enteras.
              1. Se aplican procedimientos eficientes de programación lineal, como el método del Simplex, a dicha relajación y se propone una solución entera muy próxima a la solución del problema relajado.
        2. Relajación del objetivo
          1. Modifican la función objetivo para obtener, de forma más rápida, valoraciones aproximadas (por exceso o por defecto) de la calidad de la solución que orientan la búsqueda, al menos en los estados iniciales.
            1. Para estos problemas es muy útil encontrar funciones sencillas de calcular que den una idea aproximada de la calidad de las soluciones sin necesidad de una evaluación ajustada de la función objetivo.
          2. Metaheurísticas que emplean la relajación de restricciones
            1. Método de relajación Lagrangiana
              1. Método de restricciones subordinadas
                1. Ventajas
                  1. Se aplica a cada descomposición de un modelo y llega a una muy aproximada solución para resolver problemas
                    1. Permite desarrollar límites sobre el valor de la función objetivo óptima de manera rápida
                      1. Resuelve núcleos de sub-problemas como modelos independentes
                      2. Restricciones
                        1. El problema relajado sea más sencillo de resolver que el problema original
                          1. La relajación debe ser buena en sentido de que el valor de la solución del problema relajado debe ser suficientemente cercano al del problema original
                      3. Estrategias para el empleo de relajaciones del problema en el diseño de heurísticas.
                        Show full summary Hide full summary

                        Similar

                        Investigación de Operaciones
                        neneeduardo
                        INVESTIGACION DE OPERACIONES
                        Maryan Acuña
                        Programación No Lineal.
                        kayzer01
                        HISTORIA INVESTIGACION DE OPERACIONES
                        Maryan Acuña
                        Sistema de líneas de espera
                        kayzer01
                        Jesus Garcia
                        jesus nestor garcia
                        Modelos de Inventarios
                        kayzer01
                        Procesos Estocásticos
                        María Fernanda Bonelli Márquez
                        Interpretación Económica de la dualidad
                        JORGE GARCIA BONILLA
                        Investigación de Operaciones
                        Marlene Velasco
                        Aplicacion de la simulacion de Monte Carlo en el calculo de riesgo usando Excel
                        Gleidy Sairitupac Condori