Navegando por Autor "Faria, Alexandre Frias"

Agora exibindo 1 - 1 de 1
  • Imagem de Miniatura
    Item
    Algoritmos e modelos matemáticos para o problema da k-partição de números
    (Centro Federal de Educação Tecnológica de Minas Gerais, 2017-02-16) Faria, Alexandre Frias; Souza, Sérgio Ricardo de; Silva, Carlos Alexandre; http://lattes.cnpq.br/8465270749629421; http://lattes.cnpq.br/3677015295211434; http://lattes.cnpq.br/7284035698082266; Souza, Sérgio Ricardo de; Silva, Carlos Alexandre; Coleho, Alessandra Martins; Cardoso, Rodrigo Tomás Nogueira
    Esta dissertação de mestrado apresenta uma formulação matemática e algoritmos para a versão de otimização do Problema da k-Partição de Números. Este problema consiste em distribuir os elementos de uma sequência numérica em k subconjuntos disjuntos, de modo que os resultados das somas dos elementos de cada subconjunto fiquem contidos no menor intervalo possível. A formulação matemática proposta é baseada em dois problemas semelhantes da literatura. Elimina-se a multiplicidade de soluções do modelo de programação inteira, reduzindo ao mínimo o número de variáveis. Mostra-se a NP-completude do problema estudado. Estudam-se algoritmos heurísticos, aproximados e exatos da literatura aplicáveis aos problemas relacionados. Aplica-se a meta-heurística ILS (Iterated Local Search) à solução gerada por um algoritmo aproximado. A estratégia utilizada é aplicar método guloso em todas as fases do algoritmo, tanto na inicialização quanto para a escolha de movimentos do ILS. Propõe-se uma melhoria de métodos exatos Branch-and-Bound aplicados ao problema e presentes na literatura . Esta modificação refina os limitantes do método, usando a relaxação do modelo matemático e ILS propostos. Insere-se um critério de busca para que os nós mais promissores tenham prioridade. Os resultados mostram a solução do ILS superando as soluções de heurísticas construtivas listadas na literatura. A qualidade da solução do ILS é certificada por métodos exatos, um da literatura e outro com as melhorias propostas neste trabalho. As modificações do algoritmo exato se mostram eficazes em uma comparação entre a solução alcançada sobre o número de nós explorados nas duas versões.