O problema da mochila compartimentada e aplicações

• Ano de defesa: 2004
• Autor(a) principal: Marques, Fabiano do Prado
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Não disponível; Npt available
• Link de acesso: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-07072015-155114/

Este trabalho aborda o Problema da Mochila Compartimentada que é uma variação do clássico problema da mochila e pode ser enunciado considerando-se a seguinte situação hipotética: um alpinista deve carregar sua mochila com possíveis itens de seu interesse. A cada item atribui-se o seu peso e um valor de utilidade (até aqui, o problema coincide com o clássico Problema da Mochila). Entretanto, os itens são de agrupamentos distintos (alimentos, medicamentos, utensílios, etc.) e devem estar em compartimentos separados na mochila. Os compartimentos da mochila são flexíveis e têm capacidades limitadas. A inclusão de um compartimento tem um custo fixo que depende do agrupamento com que foi preenchido, além de introduzir uma perda da capacidade da mochila. O problema consiste em determinar as capacidades adequadas de cada compartimento e como esses devem ser carregados, maximizando o valor de utilidade total, descontado o custo de incluir compartimentos. Neste trabalho propomos um modelo de otimização não linear inteiro para o problema e algumas heurísticas para sua resolução, para as quais apresentamos os resultados computacionais obtidos. Uma aplicação prática que surge no corte de bobinas de aço, sujeito à laminação é detalhada.