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 disponí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

Estoque inicial

1 bloco de madeira: custo de 80 reais

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.

$\sin x$

\begin{equation}
\int_0^\infty \frac{x^3}{e^x-1}\,dx = \frac{\pi^4}{15}
\label{eq:sample}
\end{equation}

$\sum_{i=0}^n i^2 = \frac{(n^2+n)(2n+1)}{6}$

$$\sum_{i=0}^n i^2 = \frac{(n^2+n)(2n+1)}{6}$$

• 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$objval

Visualizando 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:

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!

# 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