Revisitando o Método de Ranking de Pontos Extremos para o Problema da Mochila Linear.

Abstract

O problema da mochila linear visa encontrar um subconjunto de itens que otimize uma função objetivo sem exceder uma capacidade de mochila dada. É um dos problemas mais estudados em otimização combinatória e que nas últimas décadas vem sendo muito utilizado nas áreas de produção e administração. Na literatura existem vários métodos para resolver efetivamente esse problema. Porém, o método de ranking de pontos extremos busca a solução do problema analisando os vértices adjacentes ao vértice que resolve o problema relaxado para encontrar soluções alternativas. Quando foi apresentado em 1973, mostrou resultados interessantes, mas não tem sido mais utilizado pelos pesquisadores há aproximadamente 40 anos. Nessa dissertação será retomado o conceito de ranking de pontos extremos com o objetivo de determinar se foi acertada a decisão dos pesquisadores de não utilizar mais esse método. Para tal propósito o desempenho do ranking de pontos extremos foi comparado com o desempenho de dois métodos branch-and-bound. Um utiliza o método simplex para resolver os problemas, branch-and-bound-simplex(BBS), enquanto o segundo utiliza o método proposto por Danztig para achar a solução do problema da mochila contínuo, branch-and-bound-Dantzig(BBD). Os resultados obtidos mostraram que o método BBD é o melhor dos três tanto em eficácia como em rapidez, já o ranking de pontos extremos se apresentou competitivo ao BBD em problemas com até 500 variáveis, piorando rapidamente à medida que o tamanho dos problemas aumentava. Os métodos BBD e de ranking de pontos extremos obtiveram sempre as respostas ótimas. O BBS, dependendo das características de alguns problemas, não atingiu o ótimo, sendo por esse fato considerado como o pior de todos. O que faz concluir que sim, é justificado ter deixado de usar o método de ranking de pontos extremos para resolver o problema da mochila linear já que existem outros métodos com desempenho melhor.