O uso das relaxações lagrangeana e surrogate em problemas de programação inteira

Pesquisa Operacional

Luis Gonzalo Acosta Espejo¹  Roberto D. Galvão¹ 

关键词: relaxações;    surrogate e combinada Lagrangeana-surrogate;    limites para a programação inteira;    relaxations;    surrogate and combined Lagrangean-surrogate;    integer programming bounds;   

DOI  :  10.1590/S0101-74382002000300006

来源: SciELO

【 摘 要 】

As diferentes relaxações de um problema de programação inteira permitem que se obtenham limites da solução ótima do mesmo. Entre as relaxações mais usadas destacam-se as de programação linear, Lagrangeana, surrogate e combinada Lagrangeana-surrogate (L-S). O presente trabalho contém uma revisão bibliográfica destas relaxações, de métodos de solução para os duais respectivos e de relações teóricas existentes entre os duais. É dada ênfase especial à relaxação surrogate e a relaxações combinadas Lagrangeana-surrogate. Ilustra-se o uso de uma relaxação combinada L-S através da aplicação da mesma a um problema de localização hierárquico com restrições de cobertura.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License