Detalhes bibliográficos
| Ano de defesa: |
1990 |
| Autor(a) principal: |
Silva, Helenice de Oliveira Florentino |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Biblioteca Digitais de Teses e Dissertações da USP
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
http://www.teses.usp.br/teses/disponiveis/55/55134/tde-20022019-110621/
|
Resumo: |
Neste trabalho abordamos a teoria da relaxação lagrangeana para resolução de problemas de programação linear inteira, a qual tem sido extensivamente usada e apresentado resultados satisfatórios. Esta abordagem busca reformular um problema inteiro, fazendo deste um problema mais simples. Para tal, relaxa-se algumas restrições, colocando-as como um termo \"penalidade\" na função objetivo, criando assim o chamado \"problema lagrangeano\". É formulado o problema dual, o qual pode ser resolvido pelo método subgradiente ou variações deste. A relaxação lagrangeana tem mostrado muita eficiência também quando usada para gerar limitantes para o algoritmo \"Branch-and-Bound\". Em muitos casos tais limitantes são melhores que os dado pela relaxação linear, gerando uma árvore de tamanho reduzido. Esta técnica lagrangeana tem sido aplicada com sucesso a um grande número de problemas importantes de pesquisa operacional, por exemplo: rotas, localização, sequenciamento, designação, cobertura entre outros. |
