O problema da mochila compartimentada e aplicações

Autor(es)

Fabiano do Prado Marques

• Tipo de documento: Tese de Doutorado
• Imprenta: São Carlos. , gráficos, ilustrações, tabelas.
• Instituição: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
• Data de defesa: 2004-11-29

Membros da banca

Marcos Nereu Arenales; Carlos Eduardo Ferreira; Reinaldo Morabito Neto; Cid Carvalho de Souza; Horacio Hideki Yanasse

• Orientador: Marcos Nereu Arenales
• Área do conhecimento: Engenharias - Engenharia de Produção
• Indexada em: Banco de Dados Bibliográficos da USP-DEDALUS
• Localização: Universidade de São Paulo. Instituto de Ciências Matemáticas e de Computação. Biblioteca Prof. Achille Bassi; ICMSC/T; M357pm

Resumo

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. (AU)

• Processo FAPESP: 00/00020-1 - O problema da mochila compartimentada e aplicações
• Beneficiário: Fabiano do Prado Marques
• Modalidade de apoio: Bolsas no Brasil - Doutorado