Estudo do problema do conjunto fechado de peso máximo: aspectos matemáticos, algoritmos e aplicações

Abstract

Em diversas situações, faz-se necessário selecionar um subconjunto de itens de uma ampla coleção, mantendo-se a relação que existe entre alguns dos itens, de tal forma que se um item for selecionado, todos os seus sucessores também devem ser selecionados. A cada item é associado um peso e o objetivo é selecionar o conjunto que maximiza a soma dos pesos dos itens selecionados. Este problema é conhecido como problema do conjunto fechado de peso máximo e apresenta diversas aplicações em áreas como gestão de produção e operações, manutenção, defesa e gerenciamento de projetos. O problema do conjunto fechado de peso máximo se assemelha ao problema da mochila, um conhecido problema NP-completo. No entanto, o problema do conjunto fechado de peso máximo pode ser resolvido através de algoritmos polinomiais. Este trabalho é um estudo de revisão bibliográfica acerca do problema do conjunto fechado de peso máximo com foco em três aspectos: desenvolvimento matemático, algoritmos e aplicações. Em termos matemáticos, os resultados importantes são a unimodularidade total da matriz de restrições, a reducibilidade para o problema do corte mínimo e a relação com outros problemas combinatórios. Analisamos as principais características de três algoritmos para o problema do conjunto fechado de peso máximo, indicando o mais eficiente. Além disso, discutimos brevemente algumas das aplicações do problema, sobretudo em áreas de interesse da engenharia de produção. Acreditamos que este trabalho preenche uma lacuna na literatura, aprofundando o entendimento sobre o problema do conjunto fechado de peso máximo e detalhando suas características mais importantes. Com uma formulação abrangente e flexível, o problema em questão pode ser utilizado em diversas áreas da engenharia de produção. Entendemos que o conteúdo desta pesquisa é uma ferramenta necessária para uma maior utilização do problema e para a formulação de novas aplicações.