255740
Description
Mind Map by Lizzi_Flor, updated more than 1 year ago
|
Created by Lizzi_Flor
over 10 years ago
|
|
Metaheurísticas de Relajación
- Modelos modificados en los que es más
sencillo encontrar buenas soluciones o en los
que los procedimientos son más eficientes.
- Una relajación de un problema es un modelo
simplificado obtenido al eliminar, debilitar o
modificar restricciones (u objetivos) del
problema real.
- Relajaciones del problema
- 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.
- Ejemplo
- Para un problema de programación lineal entera, su relajación lineal
consiste en ignorar la restricción de que las variables sean enteras.
- 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.
- 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.
- Para un problema de programación lineal entera, su relajación lineal
consiste en ignorar la restricción de que las variables sean enteras.
- Ejemplo
- 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.
- Relajación del objetivo
- 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.
- 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.
- 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.
- 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.
- Metaheurísticas que emplean
la relajación de restricciones
- Método de relajación Lagrangiana
- Método de restricciones subordinadas
- Ventajas
- Se aplica a cada descomposición de un modelo y llega a una
muy aproximada solución para resolver problemas
- Permite desarrollar límites sobre el valor de la función objetivo
óptima de manera rápida
- Resuelve núcleos de sub-problemas como modelos independentes
- Se aplica a cada descomposición de un modelo y llega a una
muy aproximada solución para resolver problemas
- Restricciones
- El problema relajado sea más sencillo de
resolver que el problema original
- 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
- El problema relajado sea más sencillo de
resolver que el problema original
- Método de relajación Lagrangiana
- Relajaciones del problema
- Estrategias para el empleo de relajaciones
del problema en el diseño de heurísticas.
Want to create your own Mind Maps for free with GoConqr? Learn more.