Artigo feito em colaboração com Valéria Nicéria
A Pesquisa Operacional, ou PO, ganhou destaque durante a Segunda Guerra Mundial. Devido ao contexto de guerra, os recursos eram escassos, levando à convocação de cientistas de diversas áreas para encontrar soluções eficazes para os problemas enfrentados. Esses esforços resultaram em grande sucesso com os métodos utilizados. Ao longo dos anos, a Pesquisa Operacional se desenvolveu de forma consistente e rapidamente se expandiu para diversas áreas de atuação.
A Programação Linear (PL) é uma das técnicas mais utilizadas da Pesquisa Operacional. Nela, buscamos obter a solução ótima para uma dada situação, pressupondo uma relação linear entre as características do problema. Sendo assim, é uma técnica utilizada para solucionar problemas dos mais variados tipos, como por exemplo:
- Definição de mix de produção
- Mistura de matérias-primas
- Planejamento de investimentos
- Rotas de veículos
Já a otimização é o processo para encontrar a melhor solução possível para um dado problema, seja o valor máximo ou mínimo, dependendo do objetivo. Um problema de otimização é um dos maiores focos da Pesquisa Operacional, área que envolve o uso de uma série de técnicas com embasamento lógico-científico para auxiliar na tomada de decisão.
Existem diversos softwares diponíveis para resolver problemas de Programação Linear, mas iremos utilizar a linguagem R. Esta é uma linguagem livre e possui diversos pacotes disponíveis para resolução de problemas de otimização. Nesse sentido, os pacotes que iremos utilizar serão o IpSolve e IpSolveAPI, caso não os tenha instalados em seu computador, basta utilizar o código abaixo para fazer a instalação.
# Instalando o pacote Lpsolve
install.packages ("lpSolve")
# Instalando o pacote LpSolveAPI
install .packages ("lpSolveAPI")Declarando o problema
Para ficar mais fácil o entendimento da Programação Linear, vamos utilizar o exemplo de otimização linear encontrado no livro Modeling and Solving Linear Programming with R. Sendo um problema de produção de duas cadeiras, segue o enunciado do problema:
Uma empresa produz dois modelos de cadeiras: 4P e 3P. O modelo 4P precisa de 4 pernas, 1 assento e 1 encosto. Por outro lado, o modelo 3P precisa de 3 pernas e 1 assento. A empresa tem um estoque inicial de 200 pernas, 500 assentos e 100 encostos. Se a empresa precisar de mais pernas, assentos e encostos, pode comprar blocos de madeira padrão, cujo custo é de 80 reais por bloco.
A empresa pode produzir 10 assentos, 20 pernas e 2 encostos de um bloco de madeira padrão. O custo de produção do modelo 4P é de 30 reais por cadeira, enquanto o custo do modelo 3P é de 40 reais por cadeira. Por fim, a empresa informou que a quantidade mínima de cadeiras a serem produzidas é de 1000 unidades por mês. Sendo necessário definir um modelo de programação linear, que minimize o custo total (os custos de produção das duas cadeiras, mais a compra de novos blocos de madeira).
Características das Cadeiras
| Modelo Cadeira | Número de Pernas | Número de assentos | Número de Encostos | Custo da Produção |
| 4P | 4 | 1 | 1 | R$30 |
| 3P | 3 | 1 | 0 | R$40 |
Estoque inicial
| Número de pernas | Número de assentos | Número de encostos |
| 200 | 500 | 100 |
1 bloco de madeira: custo de 80 reais
| Produz – Nº de pernas | Produz – Nº de assentos | Produz – Nº de encostos |
| 20 | 10 | 2 |
Agora que temos um problema a ser resolvido, precisamos identificar os 3 componentes principais.
1º) Variáveis de Decisão: São as variáveis utilizadas no modelo.
- modelo 4P: € 30 (Custo de produção unid. do modelo 4P)
- modelo 3P: € 40 (Custo de produção unid. do modelo 3P)
- bloco madeira: € 80 (Custo da unid. bloco de madeira)
2º) Função objetivo: É uma função matemática que representa o principal objetivo do tomador de decisão. Ela pode ser de dois tipos: minização ou maximização
custo = 30 + modeloAP + 40 + modelo3P + 80 * blocoMadeira = MIN(custo)
3º) Restrições: São as regras que dizem o que podemos (ou não) fazer e/ou quais são as limitações dos recursos ou
atividades associadas ao modelo.
- modelo_4P + modelo_3P <= 500estoque + 10um bloco de madeira (Nº de acentos)
- 4 * modelo_4P + 3 * modelo_3P <= 200estoque + 20um bloco de madeira (Nº de pernas)
- modelo_4P <= 100estoque + 2um bloco de madeira (Nº de Encostos)
- modelo_4P + modelo_3P >= 1000 (Quantidade mínima de cadeiras)
Implementando a solução no R
Vamos usar o pacote lpSolve para encontrar a solução para o nosso problema
# Carregando o pacote LpSoLlve
library (lpSolve)
# Definindo as constantes da função objetivo
constantes_objetivo <- c(30, 40, 80)
# Criando uma matriz com as restrições
restricoes <- matrix(c(
1, 1, -10, # Nº de ocentos
4, 3, -20, # Nº de pernas
1, 0, -2, # Nº de Encostos
1, 1, 0 # Quantídade míntma de cadeiras
), nrow = 4 , byrow = TRUE )
# Valores que ficam do lado direito da restríção
valores_restricao <- c(500, 200, 100, 1000)
# Definindo as equações ou inequações da restrição
direcao_restricao <- c("<=”, “<=", “<=”, ">=")
# Encontrando a solução ótima
solucao_otima <- lp(
direction = "min", # Objetiva
objective.in = constantes_objetivo,
const.mat = restricoes,
const.dir = direcao_restricao,
const.rhs = valores_restricao,
all.int = T
)
# Status da sotução
status_solucao <- solucao_otima$status
# Solução do problema
solucao_problema <- solucao_otima$solution
names(solucao_problema) <- c(“Cadeira 4P”, “Cadeira 3P", “Bloco Madeira”)
# Custo total
custo_total <- solucao_otima$objvalVisualizando a solução
# Status da solução
# 0 = sucesso, 2 = nenhuma solução viável
print(paste("Status da solução:", ifelse(status_solucao == 0, “Sucesso.”, “Nenhuma Solução Víável.”)))
## [1] "Status da solução: Sucesso.”
# Solução do problema
print(solucao_problema)
## Cadeira 4P Cadeira 3P Bloco Madeira
## 420 580 161
# Verificando o custo total
print(paste("Custo total:", custo total))
## [1] "Custo total: 48680”Outro pacote disponível para linguagem R é o IpSolveAPI que permite visualizar um relatório de resolução do problema de Programação Linear, segue abaixo o código da resolução do problema utilizando esse pacote:
# Carregando o pacote LpSolveAPI
library(lpsolveAPI)
# Definindo que o problema terá 4 restrições com 3 variáveis
problema <- make.lp(nrow = 4, ncol = 3)
# Definindo o tipo de problema que será resolvido 'minimização'
lp.control(problema, sense="min")
## $anti.degen
## [1] “fixedvars” “stalling"
##
## $basis.crash
## [1] "none”
##
## $bb.depthlimit
## [1] -50
##
## $bb. floorfirst
## [1] “automatic”
##
## $bb.rule
## [1] "pseudononint” “greedy" “dynanic" "rcostfixing"
##
## $break.at.first
## [1] FALSE
##
## $break.at.value
## [1] -1e+30
##
## $epsilon
## epsb epsd epsel epsint epsperturb epspivot
## 1e-10 1e-09 1e-12 1e-07 1e-05 2e-07
##
## $improve
## [1] "dualfeas" "thetagap"
##
## $infinite
## [1] 1e+30
##
## $maxpivot
## [1] 250
##
## $mip.gap
## absolute relative
1e-11
1e-11
##
## $negrange
## [1] -1e+06
##
## $obj.in.basis
## [1] TRUE
##
## $pivoting
## [1] "devex" "adaptive"
##
## $presolve
## [1] "none"
##
## $scalelimit
## [1] 5
##
## $scaling
## [1] "geometric" "equilibrate" "integers"
##
## $sense
## [1] "minimize"
##
## $simplextype
## [1] "dual" "primal"
##
## $timeout
## [1] @
##
## $verbose
## [1] "neutral"
# Definindo o tipo das variáveis de decisão
set.type(problema, 1:3, type=c("integer"))
# Definindo as constantes da função objetivo
constantes objetivo <- c(38, 40, 30)
set.objfn(problema, constantes_objetivo)
# Adicionando as restrições
add.constraint(problema, c(1, 1, -10), "<=", 500) add.constraint(problema, c(4, 3, -20), "<", 200) add.constraint (problema, c(1, 0, -2), "<", 100) add.constraint(problema, c(1, 1, 0), ">", 1000)
# Visualizando o relatório do problema print(problema)
## Model name:
## C1 C2 C3
## Minimize 30 40 80
## R1 0 0 0 free 0
## R2 0 0 0 free 0
## R3 0 0 0 free 0
## R4 0 0 0 free 0
## R5 1 1-10 <= 500
## R6 4 3-20 <= 200
## R7 1 0 -2 <= 100
## R8 1 1 0 >=1000
## Kind Std Std Std
## Type Int Int Int
## Upper Inf Inf Inf
## Lowen 0 0 0
#Resolvendo o problema
solve(problema) # Status da solução: 0 = sucesso, 2 nenhuma solução viável
## [1] 0
# Obtendo os valores das variáveis
get.variables(problema)
## [1] 420 580 161
# Obtendo o valor da função objetivo get.objective (problema) # Custo total
## [1] 48680 Por fim, o resultado foi completamente resolvido utilizando a Linguagem R, das duas formas que apresentamos. Ainda restou alguma dúvida? Deixe aqui nos comentários. Até a próxima!
