Artigo - Atena Editora

Artigo

Baixe agora

Livros

Otimização via Branch-and-Bound: Teoria, Algoritmos e Exemplos de Aplicação

Este capítulo apresenta uma análise teórica e aplicada do método Branch-and-Bound (B&B) e sua relevância na otimização de sistemas de engenharia elétrica, com ênfase na resolução de problemas de programação linear inteira (PLI). O B&B é um método estruturado que organiza a busca pela solução ótima por meio da subdivisão do problema original em subproblemas menores, utilizando relaxações, heurísticas e estratégias de poda para eliminar regiões inviáveis do espaço de busca. Esse processo reduz significativamente o esforço computacional e melhora a eficiência da resolução. Inicialmente, são discutidos os fundamentos teóricos do método, abordando sua estrutura algorítmica e critérios de avaliação, bem como as estratégias de busca empregadas para garantir soluções ótimas. Em seguida, é demonstrada uma aplicação prática utilizando o software LINDO (Linear Interactive and Discrete Optimizer), ferramenta amplamente utilizada na pesquisa operacional. Para validar a eficácia do método, um estudo de caso detalhado é apresentado, envolvendo a resolução de um problema de maximização em PLI, com construção da árvore de enumeração, definição de limites superiores e inferiores e eliminação de subproblemas inviáveis. Os resultados confirmam que o método B&B é uma abordagem robusta e eficaz para a resolução de problemas combinatórios e de alocação de recursos, sendo amplamente utilizado na engenharia, ciência de dados e pesquisa operacional. Sua capacidade de explorar seletivamente o espaço de busca e evitar a enumeração exaustiva o torna essencial para a obtenção de soluções ótimas em sistemas complexos.
Ler mais

Otimização via Branch-and-Bound: Teoria, Algoritmos e Exemplos de Aplicação

  • DOI: https://doi.org/10.22533/at.ed.654112526022

  • Palavras-chave: Otimização; Programação Linear Inteira; Branch-and-Bound.

  • Keywords: Optimization; Integer Linear Programming; Branch-and-Bound.

  • Abstract: This chapter presents a theoretical and applied analysis of the Branch-and-Bound (B&B) method and its relevance in optimizing electrical engineering systems, with a focus on solving integer linear programming (ILP) problems. B&B is a structured approach that organizes the search for the optimal solution by subdividing the original problem into smaller subproblems, leveraging relaxations, heuristics, and pruning strategies to eliminate infeasible regions of the search space. This process significantly reduces computational effort and enhances solution efficiency. Initially, the theoretical foundations of the method are discussed, including its algorithmic structure, evaluation criteria, and search strategies employed to ensure optimal solutions. Subsequently, a practical application is demonstrated using the LINDO (Linear Interactive and Discrete Optimizer) software, a widely used tool in operations research. To validate the method's effectiveness, a detailed case study is presented, addressing the resolution of a maximization problem in ILP. The study involves constructing the enumeration tree, defining upper and lower bounds, and eliminating infeasible subproblems. The results confirm that the B&B method is a robust and effective approach for solving combinatorial optimization and resource allocation problems, making it widely applicable in engineering, data science, and operations research. Its ability to selectively explore the search space while avoiding exhaustive enumeration makes it essential for obtaining optimal solutions in complex systems.

  • Joelson Lopes da Paixão
  • Gabriel Henrique Danielsson
  • Alzenira da Rosa Abaide
Fale conoscoWhatsapp