Geração de colunas para problemas de corte em duas fases

Autor(es)

Aline Aparecida de Souza Leão

• 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
• Data de defesa: 02-03-2009

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
• Linha de fomento: Bolsas no Brasil - Mestrado