Detalhes bibliográficos
| Ano de defesa: |
2015 |
| Autor(a) principal: |
GUTIERRES, Julio Cesar Mosquera |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Não Informado pela instituição
|
| Programa de Pós-Graduação: |
Programa de Pós-Graduação: Mestrado - Engenharia de Produção
|
| Departamento: |
IEPG - Instituto de Engenharia de Produção e Gestão
|
| País: |
Não Informado pela instituição
|
| Link de acesso: |
https://repositorio.unifei.edu.br/jspui/handle/123456789/357
|
Resumo: |
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. |
