O problema da mochila ou em inglês “knapsack” é um problema clássico de otimização combinatória.
O problema consiste em colocar em uma mochila o maior valor possível de itens com determinada capacidade de peso. A cada item é associado um peso e um valor. O valor pode ser a utilidade ou o preço. Ao ir para o camping espera-se que a mochila seja carregada da maior utilidade de itens possível, enquanto na mochila de um motoqueiro o desejado é transportar o maior valor possível. Dessa forma, o objetivo da otimização é ter o maior valor dentro da mochila, ou seja, maximizar o valor sem ultrapassar o peso. Alguns itens podem ser muito valiosos porém pesados, enquantos alguns itens leves podem ter valor pequeno. Um algoritmo trivial de otimização irá na tentativa e erro colocar itens na mochila até alcançar o peso permitido e ir trocando os itens procurando sempre maximizar o valor dentro da mochila.
Esse problema é generalizado para outras aplicações onde o peso pode ser qualquer variável de penalidade e o preço uma variável de maximização. Exemplos não faltam:
- Embarcar a maior quantidade de itens possíveis em um caminhão com custo de carga alto
- Alocar máquinas de produção visando o menor tempo possível e maior valor produzido
- Corte de chapas de madeira, metal, tecidos
- Empacotamento
- Investimento de Capital
CVXPY
CVXPY é um framework python para diversos otimizadores com uma linguagem própria e suporte a Numpy.
Para instalar o CVXPY use o pip:
pip install cvxpy
Um dos otimizadores disponíveis é o CBC um otimizador de programação linear inteiro open-source. O CBC pode ser usado em linha de comando sem ser necessário o CVXPY, mas neste caso será necessário aprender sua linguagem de entrada.
Também será necessário instalar o CVXOPT:
pip install cvxopt
Esse problema aparece em diversas áreas como a logística, computação e investimentos.
import cvxpy as cp
import numpy as np
Dados de entrada do problema
Valores = np.array([10,13,1,100,45,13,156,76,4,59,97,99])
Pesos = np.array([50,55,10,5,1,98,34,3,9,3,7,19])
Capacidade_Mochila = 100
Variaveis de decisão
Cada Item Xi terá valor 1 se estiver na mochila ou 0 se estiver fora cp.Variable cria uma variável no CVX ( não confunda cp com np ) do tipo boolean do tamanho da quantidade de itens
Xi = cp.Variable((Valores.size), boolean = True)
Constraints do problema
A soma total dos pesos dos itens escolhidos por Xi devem ser igual ou menor que a capacidade da mochila
constraints = [ Xi @ Pesos <= Capacidade_Mochila ]
Tambem pode ser escrito com o mesmo resultado como:
constraints = [ cp.sum( cp.multiply (Xi, Pesos ) ) <= Capacidade_Mochila ]
O Objetivo do problema é maximizar os valores na mochila
objective = cp.Maximize( Xi @ Valores )
finalmente chamamos o solver com verbose para acompanhar o progresso e a execução máxima de 1hr
prob = cp.Problem(objective, constraints)
prob.solve(solver=cp.CBC,verbose=True, maximumSeconds = 1 * 60 * 60)
print("Status : ", prob.status)
print("Valor encontrado: ", prob.value)
print("Valor de Xi : ", Xi.value)
O problema da mochila tem muitas aplicações práticas principalmente na logística. Imagine uma transportadora que precisa distribuir seus pacotes utilizando vans e caminhões. Cada pacote tem peso, tamanho, localidade, tempo de espera e valor. Um programa de otimização pode ajudar no preenchimento dos caminhões e em aplicações profissionais traçar a rota de distribuição de cada veículo.
Programas de otimização não acham o melhor valor, porque em geral é uma tarefa impossível (o mais correto seria improvável) de se achar, devido a explosão combinatória. Por isso são chamados ‘otimizadores’ pois eles buscam a melhor solução possível, ou seja, uma solução ótima.