Otimização Utilizando o R

Silvio Silva
05/05/2017

Universidade Federal de Santa Catarina

UFSC

Software R - Pacotes

Modeling and solving linear programming with R - Livro

lpSolve - lpSolveAPI

Programação linear, inteira, mista e binárias.

Modelo de Transporte

Modelo de Designação
Rglpk - programação linear em grande escala (LP), programação linear inteira mista (MILP) e outros problemas relacionados.
Rsymphony - programas lineares de inteiros e mistos.

TSP - heurística para o problema do caixeiro viajante
tbart - heurística para o problema de p-mediana

Otimização linear

Em um problema de otimização temos uma função objetivo e um conjunto de restrições, ambos relacionados às variáveis de decisão. Os valores possíveis às variáveis de decisão são delimitados pelas restrições impostas sobre essas variáveis, formando um conjunto discreto (finito ou não) de soluções factíveis a um problema. O problema pode ser de minimização ou de maximização da função objetivo.

wikipedia

Programação Linear

\[ Max (Min) f(x) = cx \\ \]sujeito a\[ Ax = b\\ x > 0 \]

Onde o vetor $ c $ é a variável custo, $ x $ é o vetor da variável de decisão, $ b $ é o vetor de recursos e $ A = \{a_{ij}\} $ e conhecida como matriz tecnológica.

Exemplo

Uma empresa fabrica dois tipos de brinquedos, B1 e B2, que utilizam dois recursos: plástico (até 1.000 quilos estão disponíveis) e horas de produção (até 40 horas estão disponíveis).

O Departamento de Marketing colocou algumas restrições: não fabricar mais de 700 dúzias do total de brinquedos (B1 e B2), o número de dúzias de B1 fabricadas não deve exceder em 350 o número de dúzias do brinquedo B2.

A Manufatura passou as seguintes informações: cada dúzia do brinquedo B1 usa 2 quilos de plástico e 3 minutos de produção e cada dúzia do brinquedo B2 usa 1 quilo de plástico e 4 minutos de produção. O lucro estimado na venda do B1 é $8,00/dúzia e para o B2 é $5,00/dúzia.

(Adaptado de Lawrence e Pasternack, 2002)

Modelagem

Max $ 8x_1 + 5x_2 $ (Lucro semanal)

Sujeito a

$ 2x_1 + 1x_2 ≤ 1000 $ (Plástico)

$ 3x_1 + 4x_2 ≤ 2400 $ (Tempo de Produção - Minutos)

$ x_1 + x_2 ≤ 700 $ (Produção Total)

$ x_1 - x2 ≤ 350 $ (Mix)

$ x_1,x_2 ≥ 0 $ (Não-negatividade)

Entrada de dados - Pacote - lpSolve

# Entrada de dados

f.obj <- c(8, 5)
f.con <- matrix (c(
2, 1,
3, 4,
1, 1,
1,-1),
nrow=4, byrow=TRUE)
f.dir <- c("<=", "<=","<=","<=")
f.rhs <- c(1000, 2400,700,350)

Solução lpSolve

library(lpSolve)

# função lp

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

modelo

Success: the objective function is 4360

modelo$solution

[1] 320 360

Utilizando o pacote lpSolveAPI

Exemplo 2

\[ Max \ Z = 3x_1 + 5x_2 \] sujeito a \[ \begin{aligned} x_1 ≤ 4\\ 2x_2 ≤ 12 \\ 3x_1 + 2x_2 ≤ 18\\ x_1,x_2 > 0 \end{aligned} \]

Solução lpSolveAPI

library(lpSolveAPI)

lp <- make.lp(0,2)

name.lp(lp, "Exemplo lp")

#lp.control(lp, sense="max")

set.objfn(lp, c(-3,-5))

add.constraint(lp, c(1, 0), "<=", 4)

add.constraint(lp, c(0, 2), "<=", 12)

add.constraint(lp, c(3, 2), "<=", 18)

Solução lpSolveAPI

lp

Model name: Exemplo lp
            C1    C2        
Minimize    -3    -5        
R1           1     0  <=   4
R2           0     2  <=  12
R3           3     2  <=  18
Kind       Std   Std        
Type      Real  Real        
Upper      Inf   Inf        
Lower        0     0

Solução lpSolveAPI

solve(lp)

[1] 0

get.objective(lp)

[1] -36

get.variables(lp)

[1] 2 6

#get.constraints(lp)

plot(lp)

plot of chunk unnamed-chunk-6

Modelo de Transporte

O Problema de transporte consiste em determinar o menor custo (ou maior lucro) em transportar produtos de várias origens para vários destisnos.

Modelo

\[ Min f(x) = \sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij}x_{ij} \\ \] sujeito a \[ \sum_{j=1}^{n}x_{ij} = a_i \ (i= 1,2,...,m)\\ \sum_{i=1}^{m}x_{ij} = b_j \ (j= 1,2,...,n)\\ x_{ij} > 0 \ (i= 1,2,...,m) \ (i= 1,2,...,n) \]

Problema de Transporte

————	Custo de transporte (U$$)	———
————	Deposito	———

Fabrica	1	2	3	4	Oferta
1	464	513	654	687	75
2	352	416	690	791	125
3	995	982	388	685	100
Demanda	80	65	70	85	300

(Hillier, Lieberman, pagina 310)

Entrada de dados

custo <- matrix(c(
464, 513, 654, 687,
352, 416, 690, 791,
995, 982, 388, 685
),nrow=3, byrow=TRUE)

row.signs <- rep ("<=", 3)
row.rhs <- c(75,125,100)
col.signs <- rep (">=", 4)
col.rhs <- c(80,65,70,85)

LpSolve

library(lpSolve)

# função lp.transport

modeloTr<-lp.transport (custo, "min", row.signs, row.rhs, col.signs, col.rhs)

modeloTr

Success: the objective function is 142635

LpSolve

modeloTr$solution

     [,1] [,2] [,3] [,4]
[1,]    0   20    0   55
[2,]   80   45    0    0
[3,]    0    0   70   30

Problema de Designação

Consiste em designar cada uma das origens a cada um dos destino.

Designar pessoas para tarefa
Maquinas para localização
Produto para fabricas

Modelo

\[ Min f(x) = \sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij}x_{ij} \\ \] sujeito a \[ \sum_{j=1}^{n}x_{ij} = 1 \ (i= 1,2,...,m)\\ \sum_{i=1}^{m}x_{ij} = 1 \ (j= 1,2,...,n)\\ x_{ij} = \{0,1\} \ (i= 1,2,...,m) \ (i= 1,2,...,n) \]

Problema de Designação

—————-	—— Tarefas ——
—————-	—— colunas ——

Maquinas	1	2	3	4
1	3	4	4	2
2	7	3	5	1
3	4	6	2	5
4	1	2	1	1

(Golbarg, Luna; pagina 293)

Entrada de dados

custo.des <- matrix(c(
3, 4, 4, 2,
7, 3, 5, 1,
4, 6, 2, 5,
1, 2, 1, 1 
),4,  byrow=TRUE)

custo.des

     [,1] [,2] [,3] [,4]
[1,]    3    4    4    2
[2,]    7    3    5    1
[3,]    4    6    2    5
[4,]    1    2    1    1

Solução - LpSolve

library(lpSolve)

# função lp.assign

modeloDes<-lp.assign(custo.des)

modeloDes

Success: the objective function is 8

Solução - LpSolve

modeloDes$solution

     [,1] [,2] [,3] [,4]
[1,]    1    0    0    0
[2,]    0    0    0    1
[3,]    0    0    1    0
[4,]    0    1    0    0

Problema do Caixeiro Viajante

UFSC

https://gallery.shinyapps.io/shiny-salesman/

Pacote

TSP - heurística

Problema do Caixeiro Viajante

x<-rnorm(100)
y<-rnorm(100)

plot(x,y)

plot of chunk unnamed-chunk-14

Problema do Caixeiro Viajante

library(TSP)

# função ETPS

etsp<-ETSP(data.frame(x,y))
tour <- solve_TSP(etsp)
tour

object of class 'TOUR' 
result of method 'arbitrary_insertion+two_opt' for 100 cities
tour length: 39.8269

plot(etsp, tour)

plot of chunk unnamed-chunk-16

Exemplo - Passando por todos os IFs de SC

UFs

Modelo de P-Medianas

plot of chunk unnamed-chunk-17

Pacote

tbart - heurística de Teitz e Bart's

Modelo de P-Medianas

x<-rnorm(100)
y<-rnorm(100)

coor<-cbind(x,y)
plot(coor)

plot of chunk unnamed-chunk-19

P-Medianas

library(tbart)

coor<-cbind(x,y)

# função allocate

alocar <- allocate(coor,p=5)
diagrama <- star.diagram(coor,alloc=alocar)

plot(diagrama, axes = TRUE)
points(coor)

plot of chunk unnamed-chunk-21

IF's - Formandos do Ensino Fundamental e Ensino Médio

Exemplo: IF's - 2 Cidades - Mafra - Curitibanos

UFs

IF's - Taxa de Analfabetismo

UFs

Exemplo: IF's - 2 Cidades - Cerro Negro - São Cristovão do Sul

UFs

Localização de Centralizador de encomendas

UFs

22 Centralizadores

Custo da Operação = 1.390.098,00

6 Centralizadores

Custo da Operação = 1.390.098,00+71.250,40=1.461.339,04 UFs

1 Centralizadores

Custo da Operação = 1.461.339,04+59.549,69=1.520.888,73 UFs

Curitiba → Altônia

UFs

Curitiba → Nova Aurora

Custo da Operação=12.835,54 UFs

Curitiba → Nova Aurora → Cafezal do Sul

Custo da Operação=12.835,54 + 4.388,99= 17.224,52 UFs

Curitiba → Nova Aurora → Cafezal do Sul → Altônia

Custo da Operação=12.835,54 + 4.388,99 + 3.714,03 = 20.938,55 UFs

Obrigado

Referência

GOLDBARG, M. C.; LUNA, H. P. L. Otimização Combinatória e Programação linear: Modelos e Algoritmos: Rio de Janeiro: Campus, 2000.

HILLIER, F. S.; LIEBERMAN, G. J. Introdução à Pesquisa Operacional: Porto Alegre: AMGH, 2010.

Marins, Fernando Augusto Silva - Introdução à Pesquisa Operacional – São Paulo : Cultura Acadêmica : Universidade Estadual Paulista, Pró-Reitoria de Graduação, 2011.

Michel Berkelaar and others (2015). lpSolve: Interface to 'Lp_solve' v. 5.5 to Solve Linear/Integer Programs. R package version 5.6.13. http://CRAN.R-project.org/package=lpSolve

R Core Team (2015). R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria. URL https://www.R-project.org/.

Michael Hahsler and Kurt Hornik (2017). TSP: Traveling Salesperson Problem (TSP). R package version 1.1-5. http://CRAN.R-project.org/package=TSP

Chris Brunsdon (2015). tbart: Teitz and Bart's p-Median Algorithm. R package version 1.0. http://CRAN.R-project.org/package=tbart

Silva, Silvio Aparecido da. Otimização da localização de centralizadores e configuração de redes para distribuição de encomendas expressas.(Dissertação). PPGMNE. UFPR.Curitiba. 2011