Programação linear simples com variáveis inteiras em R, usando lpSolve

No post anterior ( https://www.supplychaindataanalytics.com/solving-a-simple-linear-programming-problem-using-lpsolve-in-r/ ) demonstrei como um problema de otimização linear simples pode ser modelado e resolvido usando o pacote lpSolve em R.

Neste post quero adicionar o tópico de modelagem de variáveis inteiras.

No post anterior maximizamos a função objetivo 2x + 3y, com a restrição de que x + y <= 3. Quando ambas as variáveis são contínuas não negativas, a solução é y=3 com valor ótimo da função objetivo igual a 9.

Neste post adicionamos como outra restrição, que y deve ser um inteiro. Além disso, ajusto a restrição inicial de modo que agora x + y <= 3,9. Usando o pacote lpSolve em R a restrição da variável inteira pode ser considerada especificando o parâmetro int.vec, representando um vetor com os índices das variáveis inteiras a serem consideradas pelo problema. Neste caso o índice é 2, pois y é um inteiro.

Começo resolvendo um problema simples de programação linear semelhante ao anterior, só que x + y <= 3,9 (em vez de 3,0). A função objetivo permanece inalterada – portanto, este é o problema não inteiro (servindo como referência):

library(lpSolve)
f.obj <- c(2,3)                           # vetor coeficiente da função objetivo
f.con <- matrix(c(1,1),nrow=1,byrow=TRUE) # matriz de coeficientes para matriz de restrições
f.dir <- c("<=")                          # vetor de direção de restrição
f.rhs <- c(3.9)                           # valores de restrição
#f.intvec <- NA                           # índices das variáveis que devem ser inteiros

solution <- lp(direction = "max",
               objective.in = f.obj,
               const.mat = f.con, 
               const.dir = f.dir, 
               const.rhs = f.rhs)

solution
## Success: the objective function is 11.7

A solução ótima para o problema não inteiro com a restrição x + y <= 3,9 tem o seguinte ótimo (= máximo).

solution$solution

## [1] 0.0 3.9

Agora, eu modelo e resolvo o modelo acima mais uma vez – mas com y sendo especificado como uma variável inteira.

library(lpSolve)
f.obj <- c(2,3)                           # vetor coeficiente da função objetivo
f.con <- matrix(c(1,1),nrow=1,byrow=TRUE) # matriz de coeficientes para matriz de restrições
f.dir <- c("<=")                          # vetor de direção de restrição
f.rhs <- c(3.9)                           # valores de restrição
f.intvec <- c(2)                          # índices das variáveis que devem ser inteiros

solution <- lp(direction = "max",
               objective.in = f.obj,
               const.mat = f.con, 
               const.dir = f.dir, 
               const.rhs = f.rhs,
               int.vec = f.intvec)

solution

## Success: the objective function is 10.8

O valor máximo da função objetivo, considerando a restrição de inteiro adicional, diminuiu. O ponto ideal agora é:

solution$solution

## [1] 0.9 3.0

Como podemos ver, a solução ótima não é mais que y seja 3,9, mas sim que y seja igual a 3 – o que é de fato um valor inteiro!

Se você estiver interessado em programação linear, confira meus outros posts sobre este tópico . Além disso, por favor – se estiver interessado – confira meus posts sobre programação não linear e quadrática . Por fim, você também pode estar interessado em ler meu post sobre programação linear em Python, usando o módulo SciPy.