Submitted by Irene Nascimento (irene.kessia@ufpe.br) on 2015-03-09T17:42:27Z No. of bitstreams: 2 DISSERTAÇÃO Ana Flávia Medeiros Dias.pdf: 1959210 bytes, checksum: a36e597c6718b1b9ed2d16af32b62898 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-09T17:42:27Z (GMT). No. of bitstreams: 2 DISSERTAÇÃO Ana Flávia Medeiros Dias.pdf: 1959210 bytes, checksum: a36e597c6718b1b9ed2d16af32b62898 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2012 / CNPQ / O problema da seleção de portfólio de projetos pode ser modelado como um problema de programação inteira 0-1, conhecido como o problema da mochila. Esta dissertação realiza uma revisão bibliográfica sobre a utilização de métodos de MCDA no problema da seleção e otimização do portfólio. Apresenta o modelo de portfólio de projetos com agregação aditiva e um sistema computacional desenvolvido para realizar a otimização do problema, então uma Simulação de Monte Carlo para a análise de sensibilidade sobre a agregação aditiva. Em seguida aplica este modelo em problemas simulados para analisar a robustez do modelo. Realizaram-se simulações com problemas de portfólios multicritério aleatórios, identificando quatro comportamentos do problema de portfólio em relação à robustez quando o portfólio ótimo é obtido pela agregação aditiva.

O Problema da Mochila Compartimentada é uma extensão do Problema da Mochila, em que os itens solicitados são divididos em classes, de modo que a mochila deve ser subdividida em compartimentos, os quais têm capacidades limitadas e são carregados com itens da mesma classe. Além disso, a construção de um compartimento tem um custo fixo e ocasiona uma perda no espaço da mochila. O objetivo consiste em maximizar a soma dos valores dos itens, descontado o custo fixo de inclusão de compartimentos. Neste trabalho, são abordados dois métodos de solução. A primeira abordagem é uma heurística, que consiste na combinação de duas heurísticas da literatura. A segunda abordagem é o método Geração de Colunas, que além de fornecer um novo limitante superior para o Problema da Mochila Compartimentada, ao final do método o problema mestre foi resolvido com as variáveis definidas como inteiras, obtendo uma solução factível. Em ambos os métodos, o modelo não-linear é decomposto em dois modelos lineares, no qual, um gera compartimentos e o outro os seleciona. Os resultados obtidos com as duas abordagens foram comparados com um limitante superior e se mostraram bastante satisfatórios / The Compartmentalized Knapsack Problem is an extension of the classical Knapsack Problem, where the ordered items are partitioned into classes, in such way that the knapsack must be divided into compartments, each one having limited capacity. In addition, the building of a compartment has a fixed cost and involves a loss of the overall capacity. The objective is to maximize the sum of the items utility value, minus the fixed costs of the compartments. This dissertation presents two solving methods. The first approach is a heuristic method, which is a combination of two heuristics from the literature. The second approach is a Column Generation method, that apart from it gives a new upper bound to the Compartmentalized Knapsack Problem, in the end of the method the master problem was solved with the variables defined as integer, that supplies a feasible solution. In both methods, the mathematical non linear model is decomposed into two linear models, one generates the compartments, and the other selects them to compose the knapsack. The results obtained with these two approaches were compared with an upper bound and they showed very efficient

Nesse trabalho, estudamos um problema de otimização combinatorial conhecido por Problema da Mochila Compartimentada, que é uma extensão do clássico Problema da Mochila. O problema consiste em determinar as capacidades adequadas de vários compartimentos que podem vir a ser alocados em uma mochila e como esses compartimentos devem ser carregados, respeitando as restrições de capacidades dos compartimentos e da mochila. Busca-se maximizar o valor de utilidade total. O problema é muito pouco estudado na literatura, apesar de surgir naturalmente em aplicações práticas. Nesse estudo, propomos uma modelagem matemática não linear para o problema e verificamos algumas heurísticas para sua resolução. / In this work, we studied a combinatorial optimization problem called the Clustered Knapsack Problem, that is an extension of the standard Knapsack Problem. The problem is to determine the right capacities of several clusters which can be allocated in a knapsack and how these clusters should be placed so as to respect the constraints on the capacities of the clusters and the knapsack. The objective is to maximize a total utility value. The problem has seldom been studied in the literature, even though it appears naturally in practical applications. In this study, we propose a non-linear model for the problem and we insert some heuristics for its resolution.

O Problema da Mochila Compartimentada é uma extensão do Problema da Mochila, em que os itens solicitados são divididos em classes, de modo que a mochila deve ser subdividida em compartimentos, os quais têm capacidades limitadas e são carregados com itens da mesma classe. Além disso, a construção de um compartimento tem um custo fixo e ocasiona uma perda no espaço da mochila. O objetivo consiste em maximizar a soma dos valores dos itens, descontado o custo fixo de inclusão de compartimentos. Neste trabalho, são abordados dois métodos de solução. A primeira abordagem é uma heurística, que consiste na combinação de duas heurísticas da literatura. A segunda abordagem é o método Geração de Colunas, que além de fornecer um novo limitante superior para o Problema da Mochila Compartimentada, ao final do método o problema mestre foi resolvido com as variáveis definidas como inteiras, obtendo uma solução factível. Em ambos os métodos, o modelo não-linear é decomposto em dois modelos lineares, no qual, um gera compartimentos e o outro os seleciona. Os resultados obtidos com as duas abordagens foram comparados com um limitante superior e se mostraram bastante satisfatórios / The Compartmentalized Knapsack Problem is an extension of the classical Knapsack Problem, where the ordered items are partitioned into classes, in such way that the knapsack must be divided into compartments, each one having limited capacity. In addition, the building of a compartment has a fixed cost and involves a loss of the overall capacity. The objective is to maximize the sum of the items utility value, minus the fixed costs of the compartments. This dissertation presents two solving methods. The first approach is a heuristic method, which is a combination of two heuristics from the literature. The second approach is a Column Generation method, that apart from it gives a new upper bound to the Compartmentalized Knapsack Problem, in the end of the method the master problem was solved with the variables defined as integer, that supplies a feasible solution. In both methods, the mathematical non linear model is decomposed into two linear models, one generates the compartments, and the other selects them to compose the knapsack. The results obtained with these two approaches were compared with an upper bound and they showed very efficient

Nesse trabalho, estudamos um problema de otimização combinatorial conhecido por Problema da Mochila Compartimentada, que é uma extensão do clássico Problema da Mochila. O problema consiste em determinar as capacidades adequadas de vários compartimentos que podem vir a ser alocados em uma mochila e como esses compartimentos devem ser carregados, respeitando as restrições de capacidades dos compartimentos e da mochila. Busca-se maximizar o valor de utilidade total. O problema é muito pouco estudado na literatura, apesar de surgir naturalmente em aplicações práticas. Nesse estudo, propomos uma modelagem matemática não linear para o problema e verificamos algumas heurísticas para sua resolução. / In this work, we studied a combinatorial optimization problem called the Clustered Knapsack Problem, that is an extension of the standard Knapsack Problem. The problem is to determine the right capacities of several clusters which can be allocated in a knapsack and how these clusters should be placed so as to respect the constraints on the capacities of the clusters and the knapsack. The objective is to maximize a total utility value. The problem has seldom been studied in the literature, even though it appears naturally in practical applications. In this study, we propose a non-linear model for the problem and we insert some heuristics for its resolution.