Introdução
Formato LP
Formato MathProg
Programação Linear Inteira
GNU Linear Programming Kit
Eduardo Camargo de Siqueira
Pesquisa Operacional
Análise e Desenvolvimento de Sistemas
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
CONTEÚDO
1 Introdução
2 Formato LP
3 Formato MathProg
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
GLPK
GNU Linear Programming Kit.
Resolvedor de problemas lineares, incluindo problemas de pro-
gramação inteira.
Código aberto, disponível gratuitamente.
Farta documentação.
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
INSTALAÇÃO DO GLPK
Windows:
- http://gusek.sourceforge.net/gusek.html.
Linux (debian/ubuntu e derivadas):
- sudo apt-get install glpk.
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
AJUDA DO GLPK
Pacote disponível em: http://www.gnu.org/software/glpk/.
Manuais em PDF (diretório doc).
Exemplos (diretório examples).
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
FORMATOS CONHECIDOS
Formatos conhecidos para entrada de programas lineares:
MPS - Mathematical Programming System:
Padrão da indústria.
Pouco intuitivo, confuso e com limitações.
LP - CPLEX LP le format :
Padrão criado para uso com o resolvedor CPLEX.
Mais fácil e prático do que o formato MPS.
Aceito nos principais resolvedores modernos.
Arquivos podem ser convertidos para MPS.
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
FORMATO LP
COMPONENTES
Função-objetivo.
Restrições.
Informações de variáveis.
Limites.
Variáveis inteiras genéricas.
Variáveis binárias.
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
PROBLEMA DA DIETA
Suponha que uma certa dieta esteja restrita a leite desnatado, carne
magra de boi, carne de peixe e uma salada. Sabendo-se que os requi-
sitos nutricionais são expressos em termos de vitaminas e controlados
por suas quantidades mínimas. O objetivo é determinar a quantidade
de cada alimento que deverão ser ingeridos diariamente, de modo que
os requisitos nutricionais sejam satisfeitos a custo mínimo.
Vitamina Leite (litro) Carne (kg) Peixe (kg) Salada (100g) Requisito
mínimo
A 2 mg 2 mg 10 mg 20 mg 11 mg
C 50 mg 20 mg 10 mg 30 mg 70 mg
D 80 mg 70 mg 10 mg 80 mg 250 mg
Custo 2 reais 4 reais 1,5 real 1 real
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
PROBLEMA DA DIETA
Variáveis de decisão:
xi = quantidade do alimento do tipo i , sendo i = 1 (leite), i =
2 (carne), i = 3 (peixe) e i = 3 (salada).
Função objetivo:
Min f (x ) = 2x1 + 4x2 + 1, 5x3 + x4
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
PROBLEMA DA DIETA
Restrições:
Demanda de vitamina A:
2x1+ 2x2 + 10x3 + 20x4 ≥ 11
Demanda de vitamina C:
50x1
+ 20x2 + 10x3 + 30x4 ≥ 70
Demanda de vitamina D:
80x1 + 70x2 + 10x3 + 80x4 ≥ 250
Restrições de Não-negatividade:
x1 ; x2 ; x3 ≥ 0
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
PROBLEMA DA DIETA - FORMATO LP
dieta.lp
Minimize
Obj : 2 x1 + 4 x2 + 1 . 5 x3 + x4
Subject to
VitaminaA : 2 x1 + 2 x2 + 10 x3 + 20 x4 >= 1
VitaminaC : 50 x1 + 20 x2 + 10 x3 + 30 x4 >= 70
VitaminaD : 80 x1 + 70 x2 + 10 x3 + 80 x4 >= 250
End
RESOLVENDO
glpsol cpxlp dieta.lp -o solucao.txt
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
MODELOS DE PROGRAMAÇÃO LINEAR INTEIRA
CAPITÃO CAVERNA S.A.
A Capitão Caverna S.A., localizada em Pedra Lascada, aluga 3 tipos
de barcos para passeios marítimos: jangadas, supercanoas e arcas
com cabine. A companhia fornece juntamente com o barco um ca-
pitão para navegá-lo e uma tripulação que varia de acordo com a
embarcação: uma para jangadas, duas para supercanoas e três para
arcas. A companhia tem 4 jangadas, 8 supercanoas e 3 arcas e em
seu corpo de funcionários: 10 capitães e 18 tripulantes. O aluguel
é por diárias e a Capitão Caverna lucra $50 por jangada, $70 por
supercanoa e $100 por arca. Faça um modelo de programação ma-
temática que determine o esquema de aluguel que maximiza o lucro.
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
CAPITÃO CAVERNA S.A.
Variáveis de decisão:
xi = número de embarcações do tipo i a serem alugadas, sendo
i = 1 (jangada), i = 2 (supercanoa) e i = 3 (arca com cabine).
Função objetivo:
Max f (x ) = 50x1 + 70x2 + 100x3
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
CAPITÃO CAVERNA S.A.
Restrições:
Número de capitães:
x1 + x2 + x3 ≤ 10 (Há somente 10 capitães)
Número de tripulantes:
x1 + 2x2 + 3x3 ≤ 18 (Há somente 18 tripulantes)
Quantidade de jangadas:
x1 ≤ 4 (O número de jangadas está limitado a 4)
Quantidade de supercanoas:
x2 ≤ 8 (Há apenas 8 supercanoas)
Quantidade de arcas com cabine:
x3 ≤ 3 (Há apenas 3 arcas com cabine disponíveis)
Integralidade e não-negatividade:
x1 ; x2 ; x3 ∈ Z+
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
CAPITÃO CAVERNA S.A.
Max f (x ) = 50x1 + 70x2 + 100x3
sujeito a
x1 + x2 + x3 ≤ 10
x1 + 2x2 + 3x3 ≤ 18
x1 ≤4
x2 ≤8
x3 ≤3
x1 ; x2 ; x3 ∈ Z+
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
CAPITÃO CAVERNA S.A. - FORMATO LP
caverna.lp
Maximize
Obj : 50 x1 + 70 x2 + 100 x3
Subject to
Capitaes : x1 + x2 + x3 <= 10
Tripulantes : x1 + 2 x2 + 3 x3 <= 18
Jangada : x1 <= 4
Supercanoa : x2 <= 8
Arcas : x3 <= 3
General
x1
x2
x3
End
RESOLVENDO
glpsol cpxlp caverna.lp -o sol.txt
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
CAPITÃO CAVERNA S.A. - SOLUÇÃO
sol.txt
Problem :
Rows : 5
Columns : 3 (3 i n t e g e r , 0 b i n a r y )
Non− z e r o s : 9
Status : INTEGER OPTIMAL
Objective : Obj = 680 (MAXimum)
No . Row name Activity Lower bound Upper bound
−−−−−− −−−−−−−−−−−− −−−−−−−−−−−−− −−−−−−−−−−−−− −−−−−−−−−−−−−
1 Capitaes 10 10
2 Tripulantes 18 18
3 Jangada 4 4
4 Supercanoa 4 8
5 Arcas 2 3
No . Column name Activity Lower bound Upper bound
−−−−−− −−−−−−−−−−−− −−−−−−−−−−−−− −−−−−−−−−−−−− −−−−−−−−−−−−−
1 x1 ∗ 4 0
2 x2 ∗ 4 0
3 x3 ∗ 2 0
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
CAPITÃO CAVERNA S.A. - FORMATO LP
caverna.lp
Maximize
Obj : 50 x1 + 70 x2 + 100 x3
Subject to
Capitaes : x1 + x2 + x3 <= 10
Tripulantes : x1 + 2 x2 + 3 x3 <= 18
Bounds
0 <= x1 <= 4
0 <= x2 <= 8
0 <= x3 <= 3
General
x1
x2
x3
End
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
CAPITÃO CAVERNA S.A. - SOLUÇÃO
sol.txt
Problem :
Rows : 2
Columns : 3 (3 i n t e g e r , 0 b i n a r y )
Non− z e r o s : 6
Status : INTEGER OPTIMAL
Objective : Obj = 680 (MAXimum)
No . Row name Activity Lower bound Upper bound
−−−−−− −−−−−−−−−−−− −−−−−−−−−−−−− −−−−−−−−−−−−− −−−−−−−−−−−−−
1 Capitaes 10 10
2 Tripulantes 18 18
No . Column name Activity Lower bound Upper bound
−−−−−− −−−−−−−−−−−− −−−−−−−−−−−−− −−−−−−−−−−−−− −−−−−−−−−−−−−
1 x1 ∗ 4 0 4
2 x2 ∗ 4 0 8
3 x3 ∗ 2 0 3
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
CAPITÃO CAVERNA S.A. - ALTERAÇÕES
Agora a companhia passa a ter 5 jangadas, 6 supercanoas e 5
arcas e em seu corpo de funcionários: 5 capitães e 10 tripulantes.
Ainda mais, se o lucro do aluguel fosse $45 por jangada, $80
por supercanoa e $90 por arca.
O que mudaria no modelo?
É possível fazer um modelo genérico para esse problema.
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
CAPITÃO CAVERNA S.A. - ALTERAÇÕES
Max f (x ) = 45x1 + 80x2 + 90x3
sujeito a
x1 + x2 + x3 ≤5
x1 + 2x2 + 3x3 ≤ 10
x1 ≤5
x2 ≤6
x3 ≤5
x1 ; x2 ; x3 ∈ Z+
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
CAPITÃO CAVERNA S.A. - MODELO GENÉRICO
Para fazer um modelo genérico desse PPLI, façamos as seguintes
convenções:
emb : Conjunto dos diferentes tipos de embarcação = {Jan-
gada, Supercanoa, Arca}.
li : Lucro proporcionado pelo aluguel da embarcação do tipo i .
capi : Número de capitães necessários para comandar a embar-
cação do tipo i .
tripi : Número de tripulantes necessários para trabalhar na em-
barcação do tipo i .
dispi : Número disponível de embarcações do tipo i .
ntrips : Número de tripulantes disponíveis.
ncapitaes : Número de capitães disponíveis.
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
CAPITÃO CAVERNA S.A. - MODELO GENÉRICO
O modelo genérico relativo ao problema em questão pode ser assim
formulado:
Max f (x ) = li xi
X
i ∈emb
sujeito a
capi xi ≤ ncapitaes
X
(Número de capitães)
i∈ emb
tripi xi ≤ ntrips
X
(Número de tripulantes)
i ∈emb
xi ≤ dispi ∀i ∈ emb
xi ∈ Z+ ∀i ∈ emb
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
FORMATO MathProg
Formato de mais alto nível, incluindo abstrações:
Comandos
Conjuntos
Parâmetros
Facilita a geração de problemas grandes e complexos.
Permite a separação entre o modelo e os dados.
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
CAPITÃO CAVERNA S.A. - MODELO GENÉRICO
O modelo genérico relativo ao problema em questão pode ser assim
formulado:
Max f (x ) = li xi
X
i ∈emb
sujeito a
capi xi ≤ ncapitaes
X
(Número de capitães)
i∈ emb
tripi xi ≤ ntrips
X
(Número de tripulantes)
i ∈emb
xi ≤ dispi ∀i ∈ emb
xi ∈ Z+ ∀i ∈ emb
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
CAPITÃO CAVERNA S.A. - FORMATO MathProg
caverna.mod
set E; / ∗ C o n j u n t o de Embarcações ∗ /
param l {E } ; /∗ L u c r o p o r Embarcação ∗ /
param cap {E } ; /∗ C a p i t ã e s p o r Embarcação ∗ /
param t r i p {E } ; /∗ T r i p u l a n t e s p o r Embarcação ∗ /
param d i s p {E } ; /∗ D i s p o n i b i l i d a d e p o r Embarcação ∗ /
param ntrips ; /∗ T o t a l de t r i p u l a n t e s ∗ /
param ncaps ; /∗ T o t a l de c a p i t ã e s ∗ /
v a r x { e i n E} >= 0 i n t e g e r ; / ∗ I n t e g r a l i d a d e e não− n e g a t i v i d a d e ∗ /
s . t . c a p i t a e s : sum{ e i n E} cap [ e ] ∗ x [ e ] <= n c a p s ;
/ ∗ R e s t r i ç ã o de C a p i t ã e s ∗ /
s . t . t r i p u l a n t e s : sum{ e i n E} t r i p [ e ] ∗ x [ e ] <= n t r i p s ;
/ ∗ R e s t r i ç ã o de T r i p u l a n t e s ∗ /
s . t . e m b a r c a c o e s { e i n E } : x [ e ] <= d i s p [ e ] ;
/ ∗ R e s t r i ç ã o de Embarcações ∗ /
m a x i m i z e l u c r o : sum{ e i n E} l [ e ] ∗ x [ e ] ; / ∗ L u c r o do a l u g u e l ∗ /
end ;
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
CAPITÃO CAVERNA S.A. - FORMATO MathProg
caverna.dat (1/2)
data ;
/ ∗ L u c r o p o r Embarcação ∗ /
param : E : l :=
Jangadas 50
S u p e r c a n o a s 70
Arcas 100 ;
/ ∗ C a p i t ã e s p o r Embarcação ∗ /
param : cap :=
Jangadas 1
Supercanoas 1
Arcas 1 ;
/ ∗ T r i p u l a n t e s p o r Embarcação ∗ /
param : t r i p :=
Jangadas 1
Supercanoas 2
Arcas 3 ;
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
CAPITÃO CAVERNA S.A. - FORMATO MathProg
caverna.dat (2/2)
/ ∗ D i s p o n i b i l i d a d e p o r Embarcação ∗ /
param : d i s p :=
Jangadas 4
Supercanoas 8
Arcas 3 ;
param n t r i p s := 1 8 ; / ∗ T o t a l de t r i p u l a n t e s ∗ /
param n c a p s := 1 0 ; / ∗ T o t a l de c a p i t ã e s ∗ /
end ;
RESOLVENDO
glpsol -m caverna.mod -d caverna.dat -o cavernaSol.txt
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
CAPITÃO CAVERNA S.A. - SOLUÇÃO
cavernaSol.txt
Problem : caverna
Rows : 6
Columns : 3 (3 i n t e g e r , 0 b i n a r y )
Non− z e r o s : 12
Status : INTEGER OPTIMAL
Objective : l u c r o = 680 (MAXimum)
No . Row name Activity Lower bound Upper bound
−−−−−− −−−−−−−−−−−− −−−−−−−−−−−−− −−−−−−−−−−−−− −−−−−−−−−−−−−
1 capitaes 10 10
2 tripulantes 18 18
3 embarcacoes [ Jangadas ]
4 4
4 embarcacoes [ Supercanoas ]
4 8
5 embarcacoes [ Arcas ]
2 3
6 lucro 680
No . Column name Activity Lower bound Upper bound
−−−−−− −−−−−−−−−−−− −−−−−−−−−−−−− −−−−−−−−−−−−− −−−−−−−−−−−−−
1 x [ Jangadas ] ∗ 4 0
2 x [ Supercanoas ]
∗ 4 0
3 x [ Arcas ] ∗ 2 0
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
Comando set
set I ; /∗ declara conjunto que será informado depois ∗/
set I := 1..10; /∗ d e c l a r a um c o n j u n t o p r e e n c h e n d o
com num . d e 1 a 10 ∗ /
s e t A := T r i g o Q u e i j o F i g a d o S a l m a o E s p i n a f r e ;
/ ∗ d e c l a r a e i n f o r m a e l e m e n t o s d e um c o n j u n t o ∗ /
set Cidades ;
set Capitais within idades ;
/∗ c o n j u n t o c a p i t a i s f i c a r e s t r i t o a ser
um s u b c o n j u n t o d e c i d a d e s ∗ /
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
Comando param
param n ;
/∗ p a r â m e t r o que será informado depois ∗/
param c , > 0 ;
/∗ p a r â m e t r o que será informado depois e deve ser positivo ∗/
param n , i n t e g e r , > 0 ;
/∗ p a r â m e t r o que s e r á i n f o r m a d o depois e
d e v e s e r p o s i t i v o e i n t e i r o ∗/
param c {A } ;
/∗ p a r â m e t r o que d e v e s e r informado para cada
e l e m e n t o do c o n j u n t o A ∗ /
param : c :=
elementoDeA1 valorDeCparaA1
elementoDeA2 valorDeCparaA2
... ;
/∗ v a l o r do p a r â m e t r o c p a r a c a d a e l e m e n t o de A ∗/
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
Comando var
var x >= 0 ; / ∗ uma variável positiva ∗/
v a r x { I , J } , i n t e g e r , >= 0 ;
/ ∗ c r i a uma v a r i á v e l x p a r a c a d a p a r ( i , j) de I e J,
v a r i á v e l i d e n t i f i c a d a p o r x [ i , j ] ∗/
v a r z { i i n I , j i n J } >= i + j ;
/ ∗ c r i a uma v a r i á v e l z p a r a c a d a p a r ( i , j ) de I e J,
v a r i a v e l i d e n t i f i c a d a por z [ i , j ] ,
c a d a v a r i á v e l p o d e a s s u m i r v a l o r minimo i +j ∗/
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
Comando Adição de Restrições
s . t . r : x + y + z , >= 0 , <= 1 ;
/ ∗ r e s t r i ç ã o com nome r , r e s t r i n g i n d o o somatório
de x + y + z p a r a o i n t e r v a l o [ 0 , 1 ] ∗/
s . t . c a p a c i d a d e : sum{ i i n I } p [ i ] ∗ x [ i ] <= c ;
/ ∗ uma r e s t r i ç ã o g e r a d a s o b r e o s o m a t ó r i o da v a r i á v e l
x [ i ] m u l t i p l i c a n d o uma c o n s t a n t e p [ i ] ∗ /
s . t . e s t o q u e F i n a l { p i n P} :
e s t o q u e [ 1 2 , p ] + c o m p r a s [ 1 2 , p ] ∗ v e n d a s [ 1 2 , p ] >= 5 0 0 ;
/ ∗ uma r e s t r i ç ã o s e r á g e r a d a p a r a c a d a p r o d u t o p ∗/
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
FIM
Dúvidas?
Obrigado pela atenção!
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
