Resolvendo problemas usando lpSolve em R

Neste post eu mostro como conduzir otimização linear simples em R. Você também pode encontrar outros posts escritos por mim que abordam outras tarefas de otimização linear, como o problema de transporte (pode ser resolvido com lp.transport), o problema de atribuição ( podem ser resolvidos com lp.assign) e programação linear inteira (também problemas lineares inteiros mistos podem ser resolvidos em R).

A programação linear é amplamente aplicada para modelar problemas de localização de instalações. lpSolve é uma extensão disponível em R que fornece acesso a uma interface baseada em C para resolver problemas de programação linear. Como a interface é desenvolvida em C ela tem desempenho máximo, minimizando o tempo necessário para resolver problemas de programação linear sem ter que trocar de ambiente de programação ou linguagem de programação.

Neste post dou um exemplo de problema de programação linear simples resolvido com lpSolve.

A função objetivo é maximizar a receita definida pela função f(x,y) = 2x + 3y, sujeita às restrições de que x, y são não negativos e x + y não maior que 3.

Como a Internet lhe mostrará, este problema é fácil de resolver, ou seja, desenhando um gráfico de linhas ou aplicando o algoritmo simplex. Não vou explicar os algoritmos ou a metodologia para resolver problemas lineares em detalhes, mas darei um breve exemplo de como esse simples problema pode ser modelado e resolvido usando lpSolve no R. Em seguida, mostrarei uma ilustração gráfica que verifica o resultado.

Eu carrego o pacote lpSolve (já tendo instalado) e modelo o problema, usando a API lpSolve:

library(lpSolve)
f.obj <- c(2,3)                           # coefficient vector of objective function
f.con <- matrix(c(1,1),nrow=1,byrow=TRUE) # coefficient matrix for constraint matrix
f.dir <- c("<=")                          # constraint direction vector
f.rhs <- c(3)                             # constraint values

Agora vamos resolver o problema linear:

solution <- lp("max",f.obj,f.con,f.dir,f.rhs)
solution

## Success: the objective function is 9

A solução ótima é a seguinte (valor x e y ideal para o problema em questão):

solution$solution

## [1] 0 3

Agora vamos verificar graficamente o resultado. Eu defino duas linhas que visualizo usando geom_line do pacote ggplot2. A primeira linha representa a restrição de que x + y não deve ser maior que 3, a segunda linha representa a função objetivo. A linha da função objetivo representa seu valor máximo alcançável, ou seja, o valor ótimo. A linha para a restrição representa seus casos obrigatórios, ou seja, quando é igual a exatamente 3. Em termos mais simples: “objetivo de linha”: 2x + 3y = 9 “restrição de linha”: x + y = 3

library(ggplot2)
plot_df <- as.data.frame(matrix(nrow=4,ncol=3))
colnames(plot_df) <- c("x","y","type")
plot_df$x <- c(0,3,0,9/2)
plot_df$y <- c(3,0,9/3,0)
plot_df$type <- c("line constraint","line constraint", "line objective", "line objective")
ggplot(plot_df) + geom_path(mapping = aes(x=x,y=y,color=type))

Considerando que x+y=3, você consegue ver que a solução ótima para este problema deve ser x=0, y=3 – e que isso maximiza a função objetivo?

Se você estiver interessado em programação não linear (por exemplo, descida de gradiente com nloptr) ou otimização quadrática (quadprog) em R, vá em frente e confira também minhas outras postagens sobre esses tipos de tarefas de otimização.