Busca avançada
Ano de início
Entree


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

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
Data de defesa:
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