Ao fazer um trabalho para faculdade sobre o software de otimização GLPK percebi que a quantidade de conteúdo é pequena então, eu com a ajuda de meus colegas de faculdade Maurício Galdino e Vinícius Hastenreiter estamos disponibilizando o conteúdo de nosso artigo, esperamos que possa ajudar muitas pessoas.
1.
INTRODUÇÃO
Para
solucionar problemas de otimização é usado a programação linear
que é um método eficiente de um algoritmo simplex. A programação
linear é muito usada para solucionar problemas na área financeira e
outros segmentos. Para solucionar problemas de programação linear
são disponíveis várias ferramentas.
Uma destas ferramentas é o
GLPK que é um software livre que faz parte do projeto GNU. O GLPK
consiste em um pacote de softwares que possui várias funções
escritas em ANSI C para a resolução de problemas. Duas aplicações
são usadas, GLPSOL e TSPSOL. O GLPSOL é responsável por resolver
problemas de programação inteira mista e programação linear,
enquanto o TSPSOL resolve o problema do caixeiro viajante.
2. DEFINIÇÃO
O GLPK é um biblioteca open
source desenvolvido em linguagem de programação C, sua sigla
significa GNU Linear Programming Kit usado para solucionar problemas
de otimização, como foi dito ele é uma biblioteca e não possui
uma função main
que é um programa principal, o seu código implementa o algoritmo
simplex, ponto interior primitivo-dual, de ramificação e de
ligação, bem como muitos outros algoritmos. No GLPK podemos usar o
GUSEK como interface gráfica.
3.
FUNCIONAMENTO
O
GLPK é um software utilizado para resolver problemas de programação
linear, programação inteira mista e problemas correlacionados, que
utiliza a linguagem GNU MathProg modeling language, que tem funções
escritas em ANSI C que auxilia na resolução dos problemas, com
objetivo de fazer a modelagem. Suas principais informações para
otimização do problema, são:
Com essas informações
inseridas no programa, o GLPK executa um método simplex para
resolução do problema. É um método simples que caminha pelos
vértices a procura da melhor solução e para quando é encontrado
uma solução vizinha com o valor menor, essa seria a solução ótima
do problema. Em dois casos pode não existir a solução ótima, uma
quando não se encontra uma solução viável para o problema, isso
ocorre devido as restrições incompatíveis; ou quando não existe
máximo ou mínimo, ou seja, uma ou mais variáveis tendem ao
infinito e as restrições continuam sendo satisfeitas, fornecendo
resultados com valores sem limites para a função objetiva (SOUZA,
2009).
A duas formas de se utilizar o
GLPK, uma é como solver (aplicação glpsol) ou utilizando
aplicativo em C (GUSEK) que é a forma mais simples, os dados são
inseridos e ao compilar os resultados são mostrados numa janela,
pois ele trabalha com as bibliotecas que o pacote oferece para
resolver os problemas dinamicamente. A outra forma de se resolver o
problema através do solver glpsol, os dados deve ser descrito em
arquivo texto que é utilizado como entrada para a aplicação, é
escrito na linguagem de modelagem GNU Math Prog, essa linguagem
possui um conjunto de declarações e dados que são descritos no
documento lang.pdf4 que acompanha o pacote. Depois o texto é
traduzido de forma que as informações são lidas, logo os
resultados são apresentados no console.
4.
FORMATOS UTILIZADOS PELO GLPK
GLPK
é muito utilizado, pois ele suporta vários formatos para entrada
dos modelos a serem resolvidos preferencialmente deve ser escolhido
os seguintes:
GNU
(MathProg modeling language): (modelo descrito por meio da Linguagem
Mathpro), Modelo tem o objetivo de resolvedor sendo invocado
externamente (comando system). Isto é, uma das tarefas do seu
programa será construir dados a partir das instancias fornecidas,
sua função é escrita em ANSI C, que ajuda na modelagem do
problema.
LP CPLEX LP File Format: é
uma ferramenta para solucionar problemas de otimização linear,
geralmente referidas como problemas de Programação Linear (LP).
CPLEX LP, um formato orientado a linha que muitos usuários podem
achar mais natural. A entrada interativa (usando o formato CPLEX LP)
também é uma possibilidade para pequenos problemas.
Programa linear descrito no
formato CPLEX LP. Neste caso, seu programa deverá gerar o arquivo LP
a partir das instâncias e invocar externamente o resolvedor.
Componentes:
Algumas Vantagens de usar
CPLEX LP:
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.
Outros formatos podem ser
aceitos desde que o código correspondente esteja muito bem
comentado, de modo a explicitar as variáveis e restrições do seu
modelo.
5. EXEMPLO DE PROBLEMA DE PL
A
Giapetto’s Woodcarving Inc. fabrica dois tipos de brinquedos de
madeira: soldados e trens. Um soldado é vendido por $ 27 e utiliza $
10 de matéria-prima. Cada soldado que é fabricado aumenta os custos
de mão-de-obra e de despesas gerais variáveis do Giapetto em $ 14.
Um trem é vendido por $ 21 e utiliza $ 9 de matéria-prima. Cada
trem construído aumenta os custos de mão-de-obra e de despesas
gerais variáveis do Giapetto em $ 10. A fabricação de soldados e
trens de madeira requer dois tipos de mão-de-obra qualificada:
carpintaria e acabamento. Um soldado requer 2 horas de mão-de-obra
de acabamento e 1 hora de mão-de-obra de carpintaria. Um trem requer
1 horas de mão-de-obra de acabamento e 1 hora de mão-de-obra de
carpintaria. A cada semana, o Giapetto pode obter toda a
matéria-prima necessária, mas somente 100 horas de acabamento e 80
horas de carpintaria. A demanda para trens é ilimitada, mas no
máximo 40 soldados são comprados a cada semana. O Giapetto deseja
maximizar os lucros semanais (receita – custos).
Informações
Dois
tipos de brinquedos de madeira: soldados e trens.
O
soldado é vendido por $ 27, utiliza $ 10 de matéria-prima e
aumenta os custos de mão-de-obra e despesas de $ 14.
O
trem é vendido por $ 21, utiliza $ 9 de matéria-prima e aumenta os
custos de mão-de-obra e despesas em $ 10.
Um
soldado requer 2 horas de mão-de-obra e acabamento e 1 hora de
mão-de-obra de carpintaria.
Um
trem requer 1 hora de mão-de-obra de acabamento e 1 hora de
mão-de-obra de carpintaria.
Só
são permitidos 100 horas de acabamento e 80 horas de carpintaria
estão disponíveis por semana.
Por
semana tem uma demanda ilimitada de trens e soldados no máximo 40
serão vendidos.
Objetivo
Encontrar o número máximo de
soldados e trens para maximizar o lucro semanal.
Modelagem
Primeiramente devemos
estabelecer as variáveis de decisão. Na loja do Giapetto a função
objetivo é o lucro que é a quantidade de soldados e trens produzido
por semana.
Variáveis
de decisão
A função objetivo deste
problema é receita menos o custo para cada brinquedo, como a função
X1 e X2.
Como os soldados e os trens
requerem tempo de acabamento, os dois precisam ser levados em
consideração. Vamos supor que 10 soldados e 20 trens foram
contruidos. A quantidade de horas de acabamento necessárias seriam
de 10 vezes 2 horas (para soldados) mais 20 vezes 1 hora (para trens)
para um total de 40 horas de mão-de-obra de acabamento. A restrição
geral em termos das variáveis de decisão é:
A restrição de horas de
carpintaria é descoberta da mesma forma:
Restrição da demanda de
soldados que poder haver no máximo 40 soldados produzidos por
semana:
A demanda de trens é
ilimitada e por isso nehuma restrição pode ser escrita. Por tanto o
modelo está construido com as equações:
2x1
+ x2 ≤ 100 (restrição de acabamento);
max
z = 3x1 + 2x2 ( objetivo da função);
X1
≤ 40 (demanda de soldados);
X1
≥ 0, x2 ≥ 0 (restrições);
x1 + x2 ≤ 80 (restrição
de carpintaria).
5.1
UTILIZANDO O GLPK PARA SOLUCIONAR O MODELO
A
fórmula matemática para solucionar o problema de Giapetto nessecita
ser escrita com a linguagem MathProg do GNU. È necessário declarar:
A primeira etapa no MathPro é
declarar as variáveis de decisão. As linhas 8 e 9 declaram x¹ e
x². As variáveis de decisão começam com a palavra chave var. A
cada sentença no MathProg do GNU deve terminar com um ponto e
vírigula (;) Lembrando que x¹ são os números de soldados e x² o
número de trens.
Na
linha 12 é declarado a função de destino (objetivo). A função de
objetivo z é denominada representando 3x¹ + 2x². Observe que:
As linhas 15,16 e 17 são os
limitadores e são seguidos de s.t. que não é obrigatoriamente
necessário mas ajuda na capacidade de leitura.Os três limitadores
do código foram representados por : Acabamento, Carpintaria e
Demanda.
A imagem abaixo ilustra o
código para solucionar o Giapetto com MathProg.
Saída
do glpsol
O
relatório de solução estará em giapetto.sol com informações
sobre o tempo e a memória que o GLPK consumiu. O relatório mostra
que glpsol lê o modelo e em seguida chama a função de API do GLPK
para gerar a função de objetivo e, em seguida, chama outra função
de API para gerar os limitadores. Após o modelo ter sido gerado, o
glpsol explica brevemente como o problema foi tratado internamente
pelo GLPK. No final, há informações sobre a solução e os
recursos utilizados pelo GLPK para soluciona-lo.
A imagem abaixo ilustra o
relatório do glpsol.
Solução
para o problema do Giapetto.sol
A solução e dividida em
quatro partes:
Informações
sobre o problema e o valor ideal da função de objetivo.
Informações
precisas sobre o status da função de objetivo e sobre os
limitadores.
Informações
precisas sobre os valores ideais para as variáveis de decisão.
Para
esta solução podemos ver que ela é OPTIMAL e que o lucro semanal é
de no máximo $ 180.
O status da restrição de
acabamento é nu (coluna st). NU significa que existe uma variável
não-básica no limite superior para essa restrição.
A demanda de carpintaria e de
soldados são semelhantes. Para a restrição de carpintaria é um
limite superior. Portanto um atenuação de uma unidade nessa
restrição faz com que o valor marginal 1 e torna-se 181.
6.
CONCLUSÃO
A
programação Linear possui vários softwares para modelar, construir
e resolver problemas de Programação Linear, fazendo uso de
linguagem de modelagem que possui funções que auxiliam na resolução
dos problemas, com objetivo de fazer modelagem para chegar na solução
testando as variáveis e as restrições até chegar numa solução
ótima.
