Dissertação

Problema da Mochila Multicritério : Aspectos algorítmicos e Implementação Informática Aspectos algorítmicos e Implementação Informática EVALUATED

A maior parte dos artigos publicados sobre o problema da mochila foram dedicados para o único critério. Nesta tese abordamos o problema da mochila tendo em consideração vários critérios. Existem poucos artigos publicados sobre este assunto, embora o problema seja aplicável em várias situações práticas como: controlo orçamental, selecção de projectos de investimento entre outros. O objectivo deste estudo foi de explorar eficientemente o algoritmo de etiquetagem numa abordagem multicritério, de forma a resolver instâncias, do problema da mochila, cada vez maiores e num menor espaço/intervalo de tempo, pois existe uma grande necessidade de encontrar algoritmos eficazes, que calculam as soluções não dominadas rapidamente. O propósito desta tese é implementar de modo exacto, um algoritmo para a resolução do problema da mochila multicritério 0 - 1 (com mais de 2 critérios), após a conversão do modelo do problema da mochila num problema do caminho mais longo multicritério numa rede acíclica. A metodologia proposta nesta tese usa eficientemente o algoritmo de etiquetagem e não necessita que o decisor realize qualquer tipo de julgamento sobre a relevância dos objectivos. A maior vantagem do uso deste algoritmo foi de calcular rapidamente as soluções não dominadas para certas instâncias do problema da mochila multicritério, conforme mostram os resultados computacionais. Contudo, devido a determinadas limitações computacionais este método revelou-se incapaz de resolver instâncias mais exigentes.
Problema da Mochila, Optimização Combinatória Multiobjectivo, Algoritmo de Etiquetagem.

Maio 28, 2008, 10:30

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

José Rui De Matos Figueira

Departamento de Engenharia e Gestão (DEG)

Professor Associado