Dissertação
{pt=Problema da Mochila Multicritério : Aspectos algorítmicos e Implementação Informática} {pt=Aspectos algorítmicos e Implementação Informática} EVALUATED
{pt=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., en=Most of the existing papers regarding the Knapsack problem deal with a single criterion model. In this thesis we study the knapsack problem from a multiple criteria perspective. There are not many articles published on this topic, though this model describes several real-life applications such as, capital budgeting problems, project selection problems and others. The motivation for this study was to explore efficiently the labeling algorithm in a multiple criteria approach, that enable us to obtain non-dominated solutions quickly and to solve bigger instances than usually, because there is an emerging need for new algorithms able to compute non-dominated solutions quickly. The aim of this thesis is to implement an exact algorithm to solve the multiple criteria 0-1 knapsack problem (more than two criteria). Beforehand, we convert the multiple criteria knapsack model into a multiple criteria longest path over an acyclic network. The methodology proposed in this thesis efficiently uses the labelling algorithm and the decision maker does not have to judge the objectives about their priority. The advantage of this approach is to compute non-dominated solutions for multiple criteria 0 -1 knapsack problems quickly for certain instances, as shown by the computational results. However, this exact approach is not able to solve hard instances.}
maio 28, 2008, 10:30
Publicação
Obra sujeita a Direitos de Autor
Orientação
