GLPK

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:

• Função objetiva;
• Restrições;
• Informações de variáveis;
• Limites;
• Variáveis.

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:

• Função-objetivo.
• Restrições.
• Informações de variáveis.
• Limites.
• Variáveis inteiras genéricas.
• Variáveis binárias.

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

1. Dois tipos de brinquedos de madeira: soldados e trens.
2. O soldado é vendido por $ 27, utiliza $ 10 de matéria-prima e aumenta os custos de mão-de-obra e despesas de $ 14.
3. O trem é vendido por $ 21, utiliza $ 9 de matéria-prima e aumenta os custos de mão-de-obra e despesas em $ 10.
4. Um soldado requer 2 horas de mão-de-obra e acabamento e 1 hora de mão-de-obra de carpintaria.
5. Um trem requer 1 hora de mão-de-obra de acabamento e 1 hora de mão-de-obra de carpintaria.
6. Só são permitidos 100 horas de acabamento e 80 horas de carpintaria estão disponíveis por semana.
7. 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

• X1: Número de soldados produzidos por semana.
• X2: Número de trens produzidos por semana.

A função objetivo deste problema é receita menos o custo para cada brinquedo, como a função X1 e X2.

• Z = (27 – 10 - 14)x1 + (21 – 9 - 10)x2 = 3x1 + 2x2

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

• 2x1 + x2 ≤ 100

A restrição de horas de carpintaria é descoberta da mesma forma:

• X1 + x2 ≤ 80

Restrição da demanda de soldados que poder haver no máximo 40 soldados produzidos por semana:

• X1 ≤ 40

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:

• As variáveis de decisão
• A função objetivo
• Os limitadores
• O conjunto de dados do problema

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:

• O caractere (:) é usado para separar o nome da função de objetivo e sua definição.
• O caractere (*) representa a multiplicação

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.