O problema da mochila compartimentada e aplicações

Resumo

Neste projeto será estudado um problema de otimização combinatória que pode ser formulado da seguinte forma: Um alpinista deve carregar sua mochila com m possíveis itens de sua utilidade. A cada item o alpinista atribui um valor de utilidade v[i] e seu peso l[i]. O máximo peso que o alpinista suporta em sua jornada é de L. Além disso, muitos itens são de categorias distintas (alimentos, utensílios, roupas, calçados, etc.) e devem estar em compartimentos separados dentro da mochila. Os compartimentos da mochila são flexíveis, permitindo que o alpinista carregue maior peso em alimentos do que em roupas, por exemplo. Entretanto, as capacidades dos compartimentos (incógnitas) são limitadas inferior e superiormente caso estes sejam criados. O problema do alpinista consiste em determinar as capacidades adequadas de cada compartimento e como estes devem ser carregados de modo que o valor de utilidade total (soma dos valores de utilidade de cada item selecionado) seja máximo. É interessante observar que, embora este problema com descrição muito semelhante ao clássico problema da mochila, não aparece nos artigos de revisão dos problemas da mochila e é muito pouco estudado na literatura, apesar de surgir naturalmente em aplicações práticas. Apesar da simplicidade de sua descrição, sua modelagem matemática introduz não linearidade e é de difícil solução. (AU)