programaao-linear-inteira-gnu-linear-programming-kit

Prévia do material em texto

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).
Lista de Discussão: help-glpk@gnu.org.
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
Min imize
Obj : 2 x1 + 4 x2 + 1 .5 x3 + x4
Sub j e c t 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
Sub j e c t to
Cap i t a e s : x1 + x2 + x3 <= 10
T r i p u l a n t e s : x1 + 2 x2 + 3 x3 <= 18
Jangada : x1 <= 4
Supercanoa : x2 <= 8
Arcas : x3 <= 3
Gene ra l
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
S ta tu s : INTEGER OPTIMAL
Ob j e c t i v e : Obj = 680 (MAXimum)
No . Row name A c t i v i t y Lower bound Upper bound
−−−−−− −−−−−−−−−−−− −−−−−−−−−−−−− −−−−−−−−−−−−− −−−−−−−−−−−−−
1 Cap i t a e s 10 10
2 T r i p u l a n t e s 18 18
3 Jangada 4 4
4 Supercanoa 4 8
5 Arcas 2 3
No . Column name A c t i v i t y 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
Sub j e c t to
Cap i t a e s : x1 + x2 + x3 <= 10
T r i p u l a n t e s : x1 + 2 x2 + 3 x3 <= 18
Bounds
0 <= x1 <= 4
0 <= x2 <= 8
0 <= x3 <= 3
Gene ra l
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
S ta tu s : INTEGER OPTIMAL
Ob j e c t i v e : Obj = 680 (MAXimum)
No . Row name A c t i v i t y Lower bound Upper bound
−−−−−− −−−−−−−−−−−− −−−−−−−−−−−−− −−−−−−−−−−−−− −−−−−−−−−−−−−
1 Cap i t a e s 10 10
2 T r i p u l a n t e s 18 18
No . Column name A c t i v i t y 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 - ADS6GNU 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) =
∑
i∈emb
lixi
sujeito a∑
i∈emb
capixi ≤ ncapitaes (Número de capitães)∑
i∈emb
tripixi ≤ ntrips (Número de tripulantes)
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) =
∑
i∈emb
lixi
sujeito a∑
i∈emb
capixi ≤ ncapitaes (Número de capitães)∑
i∈emb
tripixi ≤ ntrips (Número de tripulantes)
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
s e t E ; /∗ Conjunto de Embarcações ∗/
param l {E} ; /∗ Lucro por Embarcação ∗/
param cap{E} ; /∗ Cap i t ã e s por Embarcação ∗/
param t r i p {E} ; /∗ T r i p u l a n t e s por Embarcação ∗/
param d i s p {E} ; /∗ D i s p o n i b i l i d a d e por Embarcação ∗/
param n t r i p s ; /∗ Tota l de t r i p u l a n t e s ∗/
param ncaps ; /∗ Tota l de c a p i t ã e s ∗/
va 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 ] <= ncaps ;
/∗ Re s t r i ç ã o de Cap 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 ;
/∗ Re s t r i ç ã o de T r i p u l a n t e s ∗/
s . t . embarcacoes {e i n E} : x [ e ] <= d i s p [ e ] ;
/∗ Re s t r i ç ã o de Embarcações ∗/
maximize l u c r o : sum{e i n E} l [ e ] ∗ x [ e ] ; /∗ Lucro 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 ;
/∗ Lucro por Embarcação ∗/
param : E : l :=
Jangadas 50
Supercanoas 70
Arcas 100 ;
/∗ Cap i t ã e s por Embarcação ∗/
param : cap :=
Jangadas 1
Supercanoas 1
Arcas 1 ;
/∗ T r i p u l a n t e s por 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 por Embarcação ∗/
param : d i s p :=
Jangadas 4
Supercanoas 8
Arcas 3 ;
param n t r i p s := 18 ; /∗ Tota l de t r i p u l a n t e s ∗/
param ncaps := 10 ; /∗ Tota 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 : cave rna
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
S ta tu s : INTEGER OPTIMAL
Ob j e c t i v e : l u c r o = 680 (MAXimum)
No . Row name A c t i v i t y Lower bound Upper bound
−−−−−− −−−−−−−−−−−− −−−−−−−−−−−−− −−−−−−−−−−−−− −−−−−−−−−−−−−
1 c a p i t a e s 10 10
2 t r i p u l a n t e s 18 18
3 embarcacoes [ Jangadas ]
4 4
4 embarcacoes [ Supercanoas ]
4 8
5 embarcacoes [ Arcas ]
2 3
6 l u c r o 680
No . Column name A c t i v i t y 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
s e t I ; /∗ d e c l a r a con jun to que s e r á in fo rmado depo i s ∗/
s e t I := 1 . . 1 0 ; /∗ d e c l a r a um con jun to preenchendo
com num . de 1 a 10 ∗/
s e t A := Tr igo Que i j o F igado Salmao E s p i n a f r e ;
/∗ d e c l a r a e in fo rma e l ementos de um con jun to ∗/
s e t C idades ;
s e t C a p i t a i s w i t h i n i d a d e s ;
/∗ con jun to c a p i t a i s f i c a r e s t r i t o a s e r
um subcon jun to de c i d a d e s ∗/
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
Comando param
param n ;
/∗ parâmetro que s e r á in fo rmado depo i s ∗/
param c , > 0 ;
/∗ parâmetro que s e r á in fo rmado depo i s e deve s e r p o s i t i v o ∗/
param n , i n t e g e r , > 0 ;
/∗ parâmetro que s e r á in fo rmado depo i s e
deve s e r p o s i t i v o e i n t e i r o ∗/
param c{A} ;
/∗ parâmetro que deve s e r in fo rmado para cada
e lemento do con jun to A ∗/
param : c :=
elementoDeA1 valorDeCparaA1
elementoDeA2 valorDeCparaA2
. . . ;
/∗ v a l o r do parâmetro c para cada e lemento de A ∗/
Pesquisa Operacional - ADS6 GNU Linear Programming Kit
Introdução
Formato LP
Formato MathProg
Comando var
va r x >= 0 ; /∗ uma v a r i á v e l p o s i t i v a ∗/
va 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 para cada par ( 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 por x [ i , j ] ∗/
va 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 para cada par ( 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 ] ,
cada v a r i á v e l pode a s sum 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ó r i o
de x + y + z para o i n t e r v a l o [ 0 , 1 ] ∗/
s . t . c apac i dade : sum{ i i n I } p [ i ] ∗ x [ i ] <= c ;
/∗ uma r e s t r i ç ã o gerada sob r e o somató r i o da v a r i á v e l
x [ i ] mu l t i p l i c a n d o uma con s t an t e p [ i ] ∗/
s . t . e s t o q u eF i n a l {p i n P} :
e s toque [ 12 , p ] + compras [ 12 , p ] ∗ vendas [ 12 , p ] >= 500 ;
/∗ uma r e s t r i ç ã o s e r á gerada para cada produto 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
	Introdução
	Formato LP
	Formato MathProg