Use este identificador para citar ou linkar para este item:
https://repositorio.unifei.edu.br/jspui/handle/123456789/357
Tipo: | Dissertação |
Título: | Revisitando o Método de Ranking de Pontos Extremos para o Problema da Mochila Linear. |
Autor(es): | GUTIERRES, Julio Cesar Mosquera |
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. |
metadata.dc.publisher.department: | IEPG - Instituto de Engenharia de Produção e Gestão |
metadata.dc.publisher.program: | Programa de Pós-Graduação: Mestrado - Engenharia de Produção |
Citação: | 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. |
URI: | https://repositorio.unifei.edu.br/jspui/handle/123456789/357 |
Data do documento: | 11-Dez-2015 |
Aparece nas coleções: | Dissertações |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
dissertacao_gutierres_2015.pdf | 769,9 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.