Portal de Periódicos da CAPES

Artigo Acesso aberto Produção Nacional Revisado por pares

BIBTEX RIS

O Problema da mochila compartimentada e aplicações

2002; Sociedade Brasileira de Pesquisa Operacional; Volume: 22; Issue: 3 Linguagem: Português

10.1590/s0101-74382002000300001

1678-5142

Fabiano do Prado Marques, Marcos Nereu Arenales,

Computational Geometry and Mesh Generation

O Problema da Mochila Compartimentada é 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 compossí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. Uma aplicação prática de relevância deste problema aparece no corte de bobinas de aço, sujeito à laminação, detalhado em apêndice.