O Problema da mochila compartimentada e aplicações

Pesquisa Operacional

Fabiano Do Prado Marques¹  Marcos Nereu Arenales¹ 

关键词: problemas da mochila;    problemas de corte e empacotamento;    otimização inteira e combinatória;    knapsack problems;    cutting and packing problems;    integer and combinatorial optimization;   

DOI  :  10.1590/S0101-74382002000300001

来源: SciELO

【 摘 要 】

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.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License