En la optimización matemática y campos relacionados, la relajación es una estrategia de modelado . Una relajación es una aproximación de un problema difícil a un problema cercano que es más fácil de resolver. Una solución del problema relajado proporciona información sobre el problema original.
Por ejemplo, una relajación de programación lineal de un problema de programación de enteros elimina la restricción de integralidad y, por lo tanto, permite soluciones racionales no enteras. Una relajación lagrangiana de un problema complicado en la optimización combinatoria penaliza las violaciones de algunas restricciones, lo que permite resolver un problema relajado más fácil. Las técnicas de relajación complementan o complementan los algoritmos de optimización combinatoria de ramificación y enlace ; La programación lineal y las relajaciones lagrangianas se utilizan para obtener límites en algoritmos de bifurcación y límite para la programación de enteros. [1]
La estrategia de modelado de relajación no debe confundirse con métodos iterativos de relajación , como la sobre relajación sucesiva (SOR); Los métodos iterativos de relajación se utilizan para resolver problemas en ecuaciones diferenciales , mínimos cuadrados lineales y programación lineal . [2] [3] [4] Sin embargo, se han utilizado métodos iterativos de relajación para resolver las relajaciones lagrangianas. [5]
Definición
Una relajación del problema de minimización.
es otro problema de minimización de la forma
con estas dos propiedades
- para todos .
La primera propiedad establece que el dominio factible del problema original es un subconjunto del dominio factible del problema relajado. La segunda propiedad establece que la función objetivo del problema original es mayor o igual que la función objetivo del problema relajado. [1]
Propiedades
Si es una solución óptima del problema original, entonces y . Por lo tanto, proporciona un límite superior en .
Si además de los supuestos anteriores, , , se cumple lo siguiente: Si una solución óptima para el problema relajado es factible para el problema original, entonces es óptima para el problema original. [1]
Algunas técnicas de relajación
- Relajación de programación lineal
- Relajación lagrangiana
- Relajación semidefinida
- Relajación y dualidad sustitutas
Notas
- ↑ a b c Geoffrion (1971)
- ^ Murty, Katta G. (1983). "16 métodos iterativos para desigualdades lineales y programas lineales (especialmente 16.2 métodos de relajación y 16.4 algoritmos SOR iterativos que preservan la dispersión para programación lineal)". Programación lineal . Nueva York: John Wiley & Sons, Inc. págs. 453–464. ISBN 978-0-471-09725-9. Señor 0720547 .
- ^ Goffin, J.-L. (1980). "El método de relajación para resolver sistemas de desigualdades lineales". Matemáticas. Oper. Res . 5 (3): 388–414. doi : 10.1287 / moor.5.3.388 . JSTOR 3689446 . Señor 0594854 .
- ^ Minoux, M. (1986). Programación matemática: teoría y algoritmos . Egon Balas (prólogo) (Traducido por Steven Vajda de la edición francesa (1983 París: Dunod)). Chichester: una publicación de Wiley-Interscience. John Wiley & Sons, Ltd. págs. Xxviii + 489. ISBN 978-0-471-90170-9. Señor 0868279 . (2008 Segunda ed., En francés: Programmation mathématique: Théorie et algorítmes . Ediciones Tec & Doc, París, 2008. xxx + 711 pp.. SEÑOR2571910 )
- ^ Los métodos de relajación para encontrar soluciones factibles a los sistemas de desigualdad lineal surgen en la programación lineal y en la relajación lagrangiana. Error de harvtxt de Goffin (1980) : objetivos múltiples (2 ×): CITEREFGoffin1980 ( ayuda ) y Minoux (1986) error de harvtxt: objetivos múltiples (2 ×): CITEREFMinoux1986 ( ayuda ) | loc = Sección 4.3.7, págs. 120-123 cite Shmuel Agmon (1954) y Theodore Motzkin e Isaac Schoenberg (1954), y LT Gubin, Boris T. Polyak y EV Raik (1969).
Referencias
- G. Buttazzo (1989). Semicontinuidad, relajación y representación integral en el cálculo de variaciones . Pitman Res. Notas en matemáticas. 207. Harlow: Longmann.
- Geoffrion, AM (1971). "Dualidad en programación no lineal: un desarrollo orientado a aplicaciones simplificado". Revisión SIAM . 13 (1). págs. 1-37. JSTOR 2028848 ..
- Goffin, J.-L. (1980). "El método de relajación para resolver sistemas de desigualdades lineales". Matemáticas. Oper. Res . 5 (3): 388–414. doi : 10.1287 / moor.5.3.388 . JSTOR 3689446 . Señor 0594854 .
- Minoux, M. (1986). Programación matemática: teoría y algoritmos ((Con prólogo de Egon Balas) Traducido por Steven Vajda de la edición francesa (1983 Paris: Dunod)). Chichester: una publicación de Wiley-Interscience. John Wiley & Sons, Ltd. págs. Xxviii + 489. ISBN 978-0-471-90170-9. Señor 0868279 . (2008 Segunda ed., En francés: Programmation mathématique: Théorie et algorítmes . Ediciones Tec & Doc, París, 2008. xxx + 711 pp.. SEÑOR2571910 ) |
- Nemhauser, GL ; Rinnooy Kan, AHG; Todd, MJ , eds. (1989). Optimización . Manuales de Investigación de Operaciones y Ciencias de la Gestión. 1 . Amsterdam: North-Holland Publishing Co. págs. Xiv + 709. ISBN 978-0-444-87284-5. Señor 1105099 .
- WR Pulleyblank , combinatoria poliédrica (págs. 371–446);
- George L. Nemhauser y Laurence A. Wolsey, Programación de enteros (págs. 447–527);
- Claude Lemaréchal , Optimización no diferenciable (págs. 529–572);
- Rardin, Ronald L. (1998). Optimización en investigación de operaciones . Prentice Hall. ISBN 978-0-02-398415-0.
- Roubíček, T. (1997). Relajación en la teoría de la optimización y el cálculo variacional . Berlín: Walter de Gruyter. ISBN 978-3-11-014542-7.