• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Disertación de Maestría
DOI
https://doi.org/10.11606/D.55.2019.tde-20022019-110621
Documento
Autor
Nombre completo
Helenice de Oliveira Florentino Silva
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Carlos, 1990
Director
Tribunal
Arenales, Marcos Nereu (Presidente)
Guardia, Luis Ernesto Torres
Perin Filho, Clovis
Título en portugués
RELAXAÇÃO LAGRANGEANA EM PROGRAMAÇÃO INTEIRA
Palabras clave en portugués
Não disponível
Resumen en portugués
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.
Título en inglés
Lagrangian relaxation in integer optimisation
Palabras clave en inglés
Not available
Resumen en inglés
In this work we survey the lagrangean relaxation theory to solve integer linear programming problems, which has been extensively used and showed satisfactory results. This approach searches a new formulation for the original problem, in which some constraints are removed and replaced as a "penalty" term in the objective function. This new problem is cal led "lagrangean problem". So, the dual problem is formulated, which can be solved via the subgradient method or its variants. The Lagrangean relaxation has proved to be efficient, when used to obtain bounds for the Branch-and-Bound algorithm. In many cases these bounds are better than those provided by the linear relaxation. In general, it yields a reduced tree. This lagrangean technique has been successfully applied to number of important problems of operational research as, for example: routing, location, scheduling, assignment, set covering and others.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2019-02-20
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2024. Todos los derechos reservados.