Texto completo
| |
| Autor(es): |
Aline Aparecida de Souza Leão
Número total de Autores: 1
|
| Tipo de documento: | Dissertação de Mestrado |
| Imprenta: | São Carlos. |
| Instituição: | Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) |
| Data de defesa: | 2009-03-02 |
| Membros da banca: |
Marcos Nereu Arenales;
Robinson Samuel Vieira Hoto;
Cláudio Nogueira de Meneses
|
| Orientador: | Marcos Nereu Arenales |
| Resumo | |
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 (AU) | |
| Processo FAPESP: | 07/01746-5 - Geração de colunas para o problemas de corte em duas fases |
| Beneficiário: | Aline Aparecida de Souza Leão |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |