O problema da mochila

  1. (Fácil)

Digamos que eu vá fazer uma viagem para a Europa. Tenho 6 itens, cada um com um peso e um valor.

Consigo carregar no máximo 60 kg na minha mochila. Quais os itens a levar, de forma a maximizar o valor na mochila, dentro da restrição?

  1. (Difícil) Agora, tenho mais de 30 itens, e consigo carregar 800 Kg. Desenvolver um algoritmo para resolver o problema (o solver do Excel é suficiente).

Solução

Este problema pode ser resolvido utilizando o solver.

Imagine uma variável de decisão binária (0 = não levo o item, 1 = levo o item).

ProblemaMochila_Solucao.xlsx

Queremos maximizar o valor a ser carregado.

A função objetivo será o somarproduto entre a variável binária e o valor de cada item.

A restrição será o somarproduto entre a variável binária e o peso de cada item, que deve ser menor ou igual ao peso máximo.

No solver, definir a função objetivo como a célula que calcula o valor transportado.

O range das variáveis de decisão deve estar em “Alterando células variáveis”.

São duas restrições.

– a variável de decisão deve ser binária

– o peso total (calculado na célula G7) deve ser menor do que a restrição de peso máximo.

O método de solução é LP Simplex, ou seja, um problema de otimização linear simples.

Se o solver não estiver habilitado, ir em Arquivos -> Opções -> Suplementos

Ir… em Suplementos do Excel, e habilitar o Solver.

O Desafio 1 é mais simples, dá para resolver no braço.

O Desafio 2 tem a mesma estrutura, e dá para resolver de forma similar. Vide arquivo ProblemaMochila_Solucao.xlsx.

Qual a aplicação deste tipo de problema no cotidiano?

Na indústria de papel e celulose, o problema do Trim deve ser resolvido todos os dias. Como eu corto o rolo jumbo de papel, nos diversos pedidos dos clientes, de forma a ter o maior aproveitamento possível do mesmo?

O problema da mochila pode ser utilizado de forma auxiliar, a gerar novos cortes, numa técnica chamada de “Geração de colunas”.

Ideias técnicas com uma pitada de filosofia

https://ideiasesquecidas.com/

Um comentário sobre “O problema da mochila

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s