Problemas da Mochila

Angela Fernanda Noeli Pimentel

PONTIFÍCIA UNIVERSIDADE CATÓLICA DE GOIÁSMESTRADO EM ENGENHARIA DE PRODUÇÃO E SISTEMAS

Definição - Problemas da Mochila

Problemas da Mochila envolvem a escolha de itens a serem colocados em uma ou mais mochilas de forma a maximizar uma função de utilidade.

Mochila 0-1

Mochila Inteira

Múltiplas Mochilas

Empacotamento em Mochilas

Tipos de Problemas da Mochila

Um viajante levará consigo apenas uma mochila para sua viagem. Sua mochila possui uma dada capacidade e deve ser preenchida com alguns objetos que lhe sejam úteis durante a viagem. Cada objeto possui um peso e um dado valor para o viajante e este possui apenas uma unidade de cada objeto a ser escolhido. Quais objetos devem ser levados pelo viajante em sua mochila de forma a maximizar o valor da mochila?

Mochila 0-1

Seja wj o peso do j-ésimo objeto e pj seu valor Se o objeto xj aparece na mochila, então xj = 1,

caso contrário xj = 0. Se denotarmos por c a capacidade da

mochila, e por n a quantidade de objetos disponíveis para escolha e F(c) como o maior valor obtido para a mochila de capacidade c usando n objetos, então o problema pode ser formulado como:

Mochila 0-1

Mochila 0-1

F(c) = max ∑ pjxj (pj > 0)

sujeito a ∑ wjxj ≤ c (wj, c > 0 )

onde: xj = 1 ou xj = 0

n

j=1

n

j=1

Mochila Inteira

+

Considera-se a necessidade de utilizar várias mochilas com capacidades distintas.

Este problema ocorre em carregamento de

contêineres e em situações de corte nas indústrias de papel e aço.

Múltiplas Mochilas

Objetiva determinar o número mínimo de mochilas de mesma capacidade b que empacotem n itens de peso wj, j=1, ..., n.

Este é um dos diversos problemas de empacotamento, que envolvem também o arranjo de objetos em dispositivos bidimensionais e tridimensionais, tais como nos problemas de carregamentos de produtos sobre paletes ou dentro de contêineres ou caminhões.

Empacotamento em Mochilas

Considere n projetos e um capital b para investimento.

O projeto j tem um custo aj e um retorno esperado pj. O problema consiste em selecionar os projetos que maximizam o retorno total esperado sem ultrapassar o limite de capital.

Defina as variáveis

xj =

Mochila 0-1 – Seleção de Projetos

1 se o projeto j é selecionado

0 caso contrário

Mochila 0-1 – Seleção de Projetos

n

j=1

n

j=1

Considere um capital para investimento b = 100, n = 8 projetos, e os seguintes vetores de parâmetros:

p= [pj]= [41 33 14 25 32 32 9 19]

a= [aj]= [47 40 17 27 34 23 5 44]

Mochila 0-1 – Seleção de Projetos

Mochila 0-1 – Seleção de Projetos

Solução ótima é dada por: x2 = x4 = x6 = x7 = 1 com valor 99

Solução utiliza 95 unidades de capital: 47 + 27 + 23 + 5 = 95

Mochila 0-1 – Seleção de Projetos

M. Arenales, V Armentano, R. Morabito e H. Yanasse. Pesquisa Operacional. Rio de Janeiro: Elsevier, 2007

UNIVERSIDADE DE SÃO PAULO. Instituto de Matemática e Estatística. São Paulo. Disponível em: <http://www.ime.usp.br/~regis/Publications/wscad2002.pdf >.

Referências