03-Mochila




Otimização em logística - carregamento de contêineres

O problema da mochila é um problema de otimização combinatória. Dado um conjunto de itens, cada qual com um peso e em valor, determine o número de itens a ser incluso em uma “mochila de tamanho fixo” de forma que o peso total seja menor ou igual ao limite de capacidade e o valor da soma dos itens da mochila seja o maior possível. Esse problema ocorrem em problemas de alocação de recursos, onde há restrições de orçamento, por exemplo.

Assim, problemas da mochila envolvem a escolha de um ou mais itens a serem colocados em uma ou mais mochila de forma a maximizar a função utilidade.  Exemplos de problemas da mochila envolvem: mochila 0-1, mochila inteira e múltiplas mochilas.

Mochila 0-1: Usado, por exemplo, na seleção de projetos. Dentre uma gama extensa, um número limitado de projetos deve ser escolhido, em função do limite de capital de investimento. Cada projeto possui um custo e um retorno esperado. O problema consiste em selecionar os projetos que maximizam o retorno total esperado sem ultrapassar o limite de capital.

Mochila inteira: Esse problema é muito similar ao problema da mochila 0-1, no entanto, pode-se levar diversas unidades do mesmo item na mochila.

Múltiplas mochilas: Esse problema ocorre em carregamento de containeres, navios ou em problemas de corte. Múltiplos itens devem ser colocados em um número específico de “mochilas” com capacidades distintas. Cada item possui seu valor e peso. O problema consiste em selecionar subconjuntos distintos dos itens de forma que o lucro total seja maximizado e as capacidades de cada mochila seja respeitada.




FONTE:

Arenales, M. Armentano, V. Morabito, R. Yanasse, H. Pesquisa Operacional para cursos de engenharia, Ed. Campus, 2007