Trabalho Prático de Pesquisa Operacional para Computa o

Trabalho Prático de Pesquisa
Operacional para
Computação

Problema 0-1 de Múltiplas Mochilas (PMM)

Lucas Nascimento Oliveira
Rodrigo Ribeiro Caputo

 Introdução
 Descrição do problema Proposto
 Implementação
 Resultado dos Testes
 Análise dos Testes

Introdução
O problema da mochila constitui uma classe de problemas dos mais estudados em otimização combinatória e em subproblemas de outros problemas práticos. O nome surgiu devido o modelo de uma situação em que é necessário carregar uma mochila com capacidade limitada, com um conjunto objetos de pesos e valores diferentes. O objetivo é ocupar a mochila com o maior valor possível, não ultrapassando o seu peso máximo. Definir o subconjunto de objetos cujo peso não ultrapasse o limite da mochila e ao mesmo tempo maximizando o seu valor total, corresponde a resolver o problema da mochila. Muitos problemas reais podem ser formulados com o problema da mochila ou uma variação deste.
Normalmente este problema é resolvido com programação dinâmica, obtendo então a resolução exata do problema, mas também é possível usar um procedimento de separação e evolução, outras técnicas também existem, como usar um algoritmo guloso ou um algoritmos genéticos para soluções aproximadas.

Descrição do problema proposto
Problema 0-1 de Múltiplas Mochilas (PMM)
Neste problema, teremos um conjunto de itens,com um peso wj e um valor de retorno pj. Também teremos um conjunto de mochilas, com uma capacidade capi.
O objetivo nesse problema é maximizar o valor de retorno dos itens alocados às mochilas. A modelagem de programação inteira deste problema é:

Onde a variável de decisão xij assumirá o valor 1 se o item j for alocado à mochila i, e assumirá 0 caso ocorra o contrário. O primeiro conjunto de restrições assegura que cada mochila i não excederá a capacidade a capacidade cap i , o segundo conjunto de restrições impede que um mesmo item j seja alocado a mais de uma

mochila.
Para realização, foram utilizados 2 métodos: Best Bound