dc.creator |
GUTIERRES, Julio Cesar Mosquera |
|
dc.date.issued |
2015-12-11 |
|
dc.identifier.citation |
GUTIERRES, Julio Cesar Mosquera. Revisitando o Método de Ranking de Pontos Extremos para o Problema da Mochila Linear. 2015. 66 f. Dissertação (Mestrado em Engenharia de Produção) – Universidade Federal de Itajubá, Itajubá, 2015. |
pt_BR |
dc.identifier.uri |
https://repositorio.unifei.edu.br/jspui/handle/123456789/357 |
|
dc.description.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. |
pt_BR |
dc.language.iso |
pt_BR |
pt_BR |
dc.title |
Revisitando o Método de Ranking de Pontos Extremos para o Problema da Mochila Linear. |
pt_BR |
dc.type |
Dissertação |
pt_BR |
dc.place |
Itajubá |
pt_BR |
dc.pages |
66 p. |
pt_BR |
dc.keywords.portuguese |
Mochila linear |
pt_BR |
dc.keywords.portuguese |
Otimização combinatória |
pt_BR |
dc.keywords.portuguese |
Método de ranking de pontos extremos |
pt_BR |
dc.keywords.portuguese |
Branch-and-bound-simplex |
pt_BR |
dc.keywords.portuguese |
Branch-and-bound-Dantzig |
pt_BR |
dc.orientador.principal |
LEME, Rafael Coradi |
|
dc.place.presentation |
Universidade Federal de Itajubá |
pt_BR |
dc.pg.programa |
Engenharia de Produção |
pt_BR |
dc.pg.area |
Otimização |
pt_BR |
dc.date.available |
2016-03-01T19:09:25Z |
|
dc.date.accessioned |
2016-03-01T19:09:25Z |
|
dc.publisher.department |
IEPG - Instituto de Engenharia de Produção e Gestão |
|
dc.publisher.program |
Programa de Pós-Graduação: Mestrado - Engenharia de Produção |
|