Introdução

"A programação linear é uma ferramenta para solucionar problemas de otimização. Em 1947, George Dantzig desenvolveu um método eficiente, o algoritmo simplex, para solucionar problemas de programação linear. Desde o desenvolvimento do algoritmo simplex, a programação linear tem sido utilizada para solucionar problemas de otimização em segmentos de mercado tão variados quanto o financeiro, de educação, florestal, de petróleo e de transporte por caminhão. Em uma pesquisa de opinião da Fortune em 500 empresas, 85% dos entrevistados disseram que utilizaram programação linear."

De Pesquisa de Operações: Aplicativos e Algoritmos, 4ª Edição, por Wayne L. Winston (Thomson, 2004); consulte Recursos a seguir, para obter um link.

Muitas ferramentas estão disponíveis para solucionar problemas de programação linear. As ferramentas proprietárias são bem conhecidas, mas muitos membros da comunidade de software livre podem não saber sobre a ferramenta GLPK gratuita.

O primeiro em uma série de três artigos que mostram recursos e uso do GLPK, esse artigo descreve brevemente o GLPK e, em seguida, demonstra e aplica a Linguagem MathProg do GNU no GLPK.

Se você estiver apenas começando com a teoria de pesquisa de operações e deseja aprender como modelar e solucionar problemas lineares, esse artigo é um bom guia.

O GNU Linear Programming Kit

O GNU Linear Programming Kit (GLPK) é uma biblioteca de rotinas que utilizam algoritmos de pesquisa de operações bem conhecidas para solucionar problemas. As rotinas implementam o algoritmo simplex, ponto interior primitivo-dual, de ramificação e de ligação, bem como muitos outros algoritmos. Verifique o manual do GLPK incluído com o download do GLPK para saber mais. (Para fazer download do GLPK, consulte a seção Recursos para obter um link à página do GLPK em gnu.org.)

GLPK não é um programa -- ele não pode ser executado e não possui nenhuma função main() . Como alternativa, os clientes alimentam os dados do problema nas rotinas de algoritmo através da API do GLPK e recebem de volta resultados. O GLPK tem um cliente padrão, o programa glpsol, que faz interface com essa API. Geralmente, um programa como glpsol é chamado de solucionador em vez de cliente, de forma que você verá essa nomenclatura daqui pra frente.

Voltar para parte superior

A Linguagem de Modelagem MathProg do GNU

A linguagem de modelagem MathProg do GNU é agradável e simples para declarar problemas lineares. Em geral, uma declaração de problema consiste em:

• Variáveis de decisão do problema.
• Uma função de objetivo (destino). Observe que objetivo é um substantivo, não um adjetivo. O nome é padrão na teoria de pesquisa de operações.
• Limitadores do problema.
• Parâmetros do problema (dados).

Vamos começar com um exemplo simples de duas variáveis: Woodcarving do Giapetto, Inc.

Voltar para parte superior

Giapetto's Woodcarving Inc..

Esse problema é de Pesquisa de Operações:

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 hora 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).

Para resumir as informações e premissas importantes sobre esse problema:

1. Existem dois tipos de brinquedos de madeira: soldados e trens.
2. Um soldado é vendido por $ 27, utiliza $ 10 de matéria-prima e aumenta os custos de mão-de-obra e despesas gerais variáveis em $ 14.
3. Um trem é vendido por $ 21, utiliza $ 9 de matéria-prima e aumenta os custos de mão-de-obra e despesas gerais variáveis em $ 10.
4. Um soldado requer 2 horas de mão-de-obra de 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. No máximo, 100 horas de acabamento e 80 horas de carpintaria estão disponíveis por semana.
7. A demanda semanal para trens é ilimitada, enquanto, no máximo, 40 soldados serão vendidos.

O objetivo é encontrar os números de soldados e trens que irão maximizar o lucro semanal.

Voltar para parte superior

Modelagem

Para modelar um problema linear, as variáveis de decisão são estabelecidas primeiro, já que irão mudar com cada iteração do algoritmo simplex e determinar o valor da função de objetivo e, consequentemente, a solução ideal. Na loja do Giapetto, a função de objetivo é o lucro, que é uma função da quantidade de soldados e trens produzidos a cada semana. Portanto, as duas variáveis de decisão nesse problema são:

• x1: Número de soldados produzidos cada semana
• x2: Número de trens produzidos cada semana

Assim que as variáveis de decisão são conhecidas, a função de objetivo desse problema é simplesmente a receita menos os custos para cada brinquedo, como uma função x1 e x2.

Observe que o lucro depende linearmente de x1 e x2 -- esse é um problema linear.

Pode parecer, à primeira vista, que o lucro pode ser maximizado simplesmente aumentando x1 e x2. Bem, se a vida fosse tão fácil, poderíamos começar a fabricar trens e soldados e mudar para o Caribe! Infelizmente, existem restrições que limitam as variáveis de decisão que podem ser selecionadas (ou então o modelo provavelmente está errado).

Lembre-se das premissas feitas para esse problema. As primeiras três determinavam as variáveis de decisão e a função de objetivo. A quarta e a sexta premissas dizem que a conclusão dos soldados requer tempo para carpintaria e acabamento. A limitação aqui é que o Giapetto não possui infinitas horas de carpintaria e de acabamento. Essa é uma restrição! Vamos analisá-la para esclarecer.

Um soldado requer 2 horas de mão-de-obra de acabamento e o Giapetto tem, no máximo, 100 horas de mão-de-obra de acabamento por semana; portanto, não pode produzir mais de 50 soldados por semana. Semelhantemente, a restrição de horas de carpintaria torna impossível produzir mais de 80 soldados por semana. Observe aqui que a primeira restrição é mais restrita que a segunda. A primeira restrição é efetivamente um subconjunto da segunda; dessa forma, a segunda restrição é redundante.

O parágrafo anterior mostra como modelar problemas de otimização, mas é uma análise incompleta porque todas as variáveis necessárias não foram consideradas. Ele não é a solução completa do problema do Giapetto. Portanto, como o problema deve ser abordado?

Comece analisando os fatores limitantes primeiro, para encontrar as restrições. Primeiro, o que limita as horas de acabamento? Como os soldados e os trens requerem tempo de acabamento, ambos precisam ser levados em consideração. Suponha que 10 soldados e 20 trens foram construídos. A quantidade de horas de acabamento necessárias para isso seriam 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 é:

Existem muitos pares (x1,x2) que satisfazem essa desigualdade; portanto, isso não determina a melhor combinação para a loja do Giapetto.

Agora que a restrição para as horas de acabamento está pronta, a restrição de horas de carpintaria é descoberta da mesma forma como:

Ótimo! Existe apenas mais uma restrição para esse problema. Lembra-se da demanda semanal para soldados? De acordo com a descrição do problema, pode haver, no máximo, 40 soldados produzidos a cada semana:

A demanda para trens é ilimitada; portanto, nenhuma restrição pode ser escrita para isso. O modelo está concluído e consiste nas equações:

Observe a última restrição. Ela assegura que os valores das variáveis de decisão sejam sempre positivos. O problema não determina isso explicitamente, mas isso ainda é importante (e óbvio).

Agora, o GLPK pode resolver o modelo (visto que o GLPK é bom para solucionar problemas de otimização linear).

Voltar para parte superior

Um Pouco de Teoria

Vamos verificar o espaço de solução do problema. Com duas variáveis de decisão, ele possui duas dimensões.

As soluções (x1,x2) fora do primeiro quadrante (onde todos os valores são positivos) já foram descartadas. Observe, no entanto, que esse espaço de solução ainda é infinito (essa seria uma situação na qual eu me mudaria para o Caribe!)

Conforme os limitadores foram escritos, esse espaço de solução ilimitado ganhou limites. Com a desigualdade 6, acima, o resultado é mais interessante.

O espaço de solução contém todas as soluções possíveis (x1,x2) no primeiro quadrante que satisfazem a restrição de horas de acabamento.

Após a desigualdade 7, o conjunto de resultados é reduzido.

Observe que o espaço de solução é menor. Isso significa que ainda menos soluções (x1,x2) estão nele. Após a desigualdade 8, o resultado é ainda menor.

O espaço de solução fica menor ainda. O espaço de solução que satisfaz todos os limitadores é chamado de região factível. A Figura 4 mostra a região factível para a loja do Giapetto. Qualquer par (x1,x2) que caia nessa região é uma possível solução para o problema.

A questão agora é: qual deles maximiza o lucro do Giapetto?

Voltar para parte superior

Utilizando o GLPK para Solucionar o Modelo

O GLPK é uma excelente ferramenta para solucionar a questão. A fórmula matemática do problema do Giapetto precisa ser escrita com a linguagem MathProg do GNU. Os itens-chave a declarar são:

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

O seguinte código mostra como solucionar o problema do Giapetto com MathProg. Os números de linhas nesse código não são parte do próprio código. Eles foram incluídos apenas para fazer referências ao código.

 1  #
 2  # Problema do Giapetto
 3  #
 4  # Isso encontra a solução ideal para maximizar o lucro do Giapetto
 5  #
 6
 7  /* Variáveis de decisão */
 8  var x1 >=0;  /* soldado */
 9  var x2 >=0;  /* trem */
10
11  /* Função de objetivo */
12  maximize z: 3*x1 + 2*x2;
13
14  /* Limitadores */
15  s.t. Acabamento : 2*x1 + x2 <= 100;
16  s.t. Carpintaria : x1 + x2 <= 80;
17  s.t. Demanda    : x1 <= 40;
18
19  fim;

As linhas 1 até 5 são comentários. # em qualquer lugar em uma linha começa um comentário até o final da linha. Comentários de estilo C também podem ser utilizados, conforme mostrado na linha 7. Eles até funcionam no meio de uma declaração.

A primeira etapa do MathProg é declarar as variáveis de decisão. As linhas 8 e 9 declaram x1 e x2. Uma declaração da variável de decisão começa com a palavra-chave var. Para simplificar limitadores de sinais (verifique a desigualdade 9), o MathProg permite uma restrição >= 0 na declaração da variável de decisão, conforme visto nas linhas 8 e 9. Cada sentença no MathProg do GNU deve terminar com um ponto e vírgula (;). Lembre-se de que x1 representa números de soldados e x2 representa números de trens . Essas variáveis poderiam ter sido chamadas de soldados e trens, mas isso confundiria os matemáticos no público.

A linha 12 declara a função de destino (objetivo). Problemas lineares podem ser maximizados ou minimizados. Lembre-se de que o modelo matemático do Giapetto é um problema de maximização; portanto, a palavra-chave maximizar é apropriada ao invés da palavra-chave oposta, minimizar. A função de objetivo é denominada z a equivale a 3x1 + 2x2. Observe que:

• O caractere dois pontos (:) separa o nome da função de objetivo e sua definição.
• O caractere asterisco (*) indica multiplicação e, de forma semelhante, os caracteres mais (+), menos (-) e barra (/) indicam adição, subtração e divisão como seria de esperar.

As linhas 15, 16 e 17 definem os limitadores. Embora s.t. não seja necessário no início da linha para declarar uma restrição, ele melhora a capacidade de leitura do código.

Os três limitadores do Giapetto foram rotulados de Acabamento, Carpintaria e Demanda. Cada um deles é declarado como no modelo matemático. Os símbolos <= e >= expressam as desigualdades. Não se esqueça do ; no final de cada declaração.

Cada arquivo do MathProg do GNU deve terminar com end;como visto na linha 19.

Agora, o glpsol pode utilizar esse arquivo como entrada. Mas, espere um minuto; onde está a seção de dados desse problema? Bem, esse problema é tão simples que os dados do problema são incluídos diretamente na função de objetivo e nas declarações de limitadores como os coeficientes das variáveis de decisão nas declarações. Por exemplo, na função de objetivo, os coeficientes 3 e 1 são parte do conjunto de dados do problema. Quando eu reescrever esse problema utilizando um conjunto de dados, se tornará claro como ele funciona; por enquanto, não se preocupe com isso.

É boa prática utilizar a extensão .mod para arquivos de entrada do MathProg e redirecionar a solução para um arquivo com a extensão .sol. Esse não é um requisito -- você pode utilizar qualquer nome do arquivo e extensão que desejar. O arquivo do MathProg do Giapetto para esse exemplo será giapetto.mod e a saída estará em giapetto.sol. Agora, execute glpsol em seu console favorito:

glpsol -m giapetto.mod -o giapetto.sol

Essa linha de comando utiliza duas opções de glpsol:

• A opção -m informa o glpsol que a entrada está gravada no MathProg do GNU.
• A opção -o informa o glpsol para enviar sua saída para giapetto.sol.

O relatório de solução estará em giapetto.sol, mas algumas informações sobre a tempo e a memória que o GLPK consumiu são mostradas na saída padrão do sistema:

ceron@curly ~ $ glpsol -m giapetto.mod -o giapetto.sol
Lendo a seção de modelo a partir do giapetto.real.mod...
19 linhas foram lidas
Gerando z...
Gerando Acabamento...
Gerando Carpintaria...
Gerando Demanda...
O modelo foi gerado com êxito
lpx_simplex: LP original possui 4 linhas, 2 colunas, 7 não-zeros
lpx_simplex: LP pré-resolvida possui 2 linhas, 2 colunas, 4 não-zeros
lpx_adv_basis: tamanho da parte triangular = 2
*     0:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (0)
*     2:   objval =   1.400000000e+02   infeas =   0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
Tempo utilizado:   0,0 segs
Memória utilizada: 0,1 M (151326 bytes)
lpx_print_sol: gravando solução do problema de LP em `giapetto.sol'...

O relatório mostra que glpsol lê o modelo, chama uma 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 solucioná-lo e a solução é tida como ideal.

Ótimo. Mas quais são os valores ideais reais para as variáveis de decisão? Eles estão no arquivo giapetto.sol :

Problema:    giapetto
Linhas:       4
Colunas:      2
Não-zeros:    7
Status:     OPTIMAL
Objetivo:   z = 180 (MAXimum)

   No. Nome Linha   St  Atividade   Limite Inferior Limite Superior  Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 z            B            180
     2 Acabamento   NU           100                         100             1
     3 Carpintaria  NU            80                          80             1
     4 Demanda      B             20                          40

   No. Nome Coluna  St   Atividade  Limite Inferior Limite Superior  Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x1           B             20             0
     2 x2           B             60             0

Condições de Otimização Karush-Kuhn-Tucker

KKT.PE: max.abs.err. = 0.00e+00 na linha 0
        max.rel.err. = 0.00e+00 na linha 0
        Alta qualidade

KKT.PB: max.abs.err. = 0.00e+00 na linha 0
        max.rel.err. = 0.00e+00 na linha 0
        Alta qualidade

KKT.DE: max.abs.err. = 0.00e+00 na coluna 0
        max.rel.err. = 0.00e+00 na coluna 0
        Alta qualidade

KKT.DB: max.abs.err. = 0.00e+00 na linha 0
        max.rel.err. = 0.00e+00 na linha 0
        Alta qualidade

Fim da saída

A solução é dividida em quatro seções:

• 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
• Informações sobre as condições de otimização, se houver

Para esse problema específico, nós vemos que a solução é OPTIMAL e que o lucro semanal máximo do Giapetto é de $ 180.

O status de restrição de Acabamento é NU (a coluna St ). NU significa que existe uma variável não-básica no limite superior para essa restrição. Se você conhece alguma teoria de pesquisa de operação, construa o quadro simplex e o desmarque. Se não conhece, aqui está uma explicação prática breve.

Sempre que uma restrição atingir seu limite superior ou inferior, ela é chamada de restrição limitada. Uma restrição limitada impede que a função de objetivo atinja um valor melhor. Pense nela como um botão giratório de volume, por exemplo, que não pode ser girado nem um pouco mais. Quando isso ocorre, o glpsol mostra o status das restrição como NU ou NL (para limite superior e inferior, respectivamente) e ele também mostra o valor do marginal, também conhecido como o preço sombra. O marginal é o valor pelo qual a função de objetivo melhoraria se a restrição fosse atenuada em uma unidade (se o botão giratório de volume pudesse girar um pouco mais). Observe que o aperfeiçoamento depende se o objetivo é para minimizar ou para maximizar a função de destino. Por exemplo, no problema do Giapetto, que busca a maximização, o valor marginal 1 significa que a função de objetivo aumentaria em 1 se nós pudéssemos ter mais uma hora de mão-de-obra de acabamento (sabemos que ele é mais uma hora e não uma a menos, porque a restrição de horas de acabamento é um limite superior).

Os limitadores de demanda de carpintaria e de soldados são semelhantes. Para a restrição de carpintaria, observe que também é um limite superior. Portanto, uma atenuação de uma unidade nessa restrição (um incremento de uma hora) faria o valor ideal da função de objetivo tornar-se melhor pelo valor marginal 1 e tornar-se 181.

A demanda de soldados, entretanto, não é limitada; assim, seu estado é B e uma atenuação nela não alteraria o valor ideal da função de objetivo.

Tente atenuar o valor de cada restrição limitada um de cada vez, resolver o problema modificado e veja o que acontece para o valor ideal da função de objetivo. Verifique também que alterar o valor de limitadores ilimitados não fará nenhuma diferença na solução, conforme esperado.

Finalmente, o relatório do glpsol mostra os valores para as variáveis de decisão: x1 = 20 e x2 = 60. Isso informa ao Giapetto que deveria produzir 20 soldados e 60 trens para maximizar seu lucro semanal.

O problema do Giapetto era muito pequeno. Você pode estar se perguntando, em um problema com muito mais variáveis de decisão e limitadores, teria que declarar cada variável e cada restrição separadamente? E se você quisesse ajustar o dado do problema, como o preço de vendas de um soldado? Você terá que fazer alterações em todos os pontos em que esse valor aparece? A próxima seção discute isso.

Voltar para parte superior

Utilizando Modelo e Seções de Dados no Problema do Giapetto

Modelos do MathProg normalmente possuem uma seção de modelo e uma seção de dados, às vezes em dois arquivos diferentes. Dessa forma, o glpsol pode resolver um modelo com conjuntos de dados diferentes facilmente, para verificar qual seria a solução com esses novos dados. A lista a seguir indica o problema do Giapetto de uma forma bem mais elegante:

 1      #
 2      # Problema do Giapetto
 3      #
 4      # Isso encontra a solução ideal para maximizar o lucro do Giapetto
 5      #
 6
 7      /* Conjunto de brinquedos */
 8      set TOY;
 9
10      /* Parâmetros */
11      param Finishing_hours {i in TOY};
12      param Carpentry_hours {i in TOY};
13      param Demand_toys     {i in TOY};
14      param Profit_toys     {i in TOY};
15
16      /* Variáveis de decisão */
17      var x {i in TOY} >=0;
18
19      /* Função de objetivo */
20      maximize z: sum{i in TOY} Profit_toys[i]*x[i];
21
22      /* Limitadores */
23      s.t. Fin_hours : sum{i in TOY} Finishing_hours[i]*x[i] <= 100;
24      s.t. Carp_hours : sum{i in TOY} Carpentry_hours[i]*x[i] <= 80;
25      s.t. Dem {i in TOY} : x[i] <= Demand_toys[i];
26
27
28      data;
29      /* seção de dados */
30
31      set TOY := soldier train;
32
33      param Finishing_hours:=
34      soldier         2
35      train           1;
36
37      param Carpentry_hours:=
38      soldier         1
39      train           1;
40
41      param Demand_toys:=
42      soldier        40
43      train    6.02E+23;
44
45      param Profit_toys:=
46      soldier         3
47      train           2;
48
49      end;

Em vez de dois arquivos separados, o problema é indicado em um arquivo único com uma seção de modelagem (linhas 1 até 27) e uma seção de dados (linhas 28 até 49).

A linha 8 define um SET. Um SET é um universo de elementos. Por exemplo, se eu declarar matematicamente xi, para todos os i em {1;2;3;4}, estou dizendo que x é uma matriz que vai de 1 a 4 e, portanto, nós temos x1, x2, x3, x4. Nesse caso, {1;2;3;4} é o conjunto. Assim, no problema do Giapetto, existe um conjunto chamado TOY. Onde estão os valores reais desse conjunto? Na seção de dados do arquivo. Verifique a linha 31. Ela define o conjunto TOY para conter soldados e trens. Uau, o conjunto não é um intervalo numérico. Como pode ser? O GLPK trata disso de uma forma interessante. Você verá como utilizar isso em alguns instantes. Por hora, acostume-se com a sintaxe para declarações SET na seção de dados:

set label := value1 value2 ... valueN ;

As linhas 11, 12 e 13 definem os parâmetros do problema. Existem três: Finishing_hours, Carpentry_hours e Demand_toys. Esses parâmetros compõem a matriz de dados do problema e são utilizados para calcular os limitadores, como você verá posteriormente.

Tome o parâmetro Finishing_hours como um exemplo. Ele está definido no conjunto TOY ; portanto, cada tipo de brinquedo no conjunto TOY terá um valor para Finishing_hours. Lembre-se de que cada soldado requer 2 horas de trabalho de acabamento e de que cada trem requer 1 hora de trabalho de acabamento. Verifique as linhas 33, 34 e 35 agora. Lá está a definição das horas de acabamento para cada tipo de brinquedo. Basicamente, essas linhas declaram que Finishing_hours[soldier]=2 e que Finishing_hours[train]=1. Finishing_hours é, portanto, uma matriz com 1 linha e 2 colunas.

Horas e parâmetros de demanda de carpintaria são declarados de forma semelhante. Observe que a demanda para trens é ilimitada; portanto, um valor muito grande é o limite superior na linha 43. O valor parece familiar para você?

A linha 17 declara uma variável, x, para cada i em TOY (resultando em x[soldier] e x[train]) e os limita a serem maiores ou iguais a zero. Uma vez que você possui conjuntos, é bem fácil declarar variáveis, não é?

A linha 20 declara a função de objetivo (destino) como a maximização de z, que é o lucro total para cada tipo de brinquedo (existem dois: trens e soldados). Com soldados, por exemplo, o lucro é o número de soldados vezes o lucro por soldado.

Os limitadores nas linhas 23, 24 e 25 são declarados de uma forma semelhante. Tome a restrição de horas de acabamento como um exemplo: ela é o total das horas de acabamento por tipo de brinquedo vezes o número daquele tipo de brinquedo produzido, para os dois tipos de brinquedo (trens e soldados) e ele deve ser menor ou igual a 100. De forma semelhante, as horas totais de carpintaria devem ser menores ou iguais a 80.

A restrição de demanda é um pouco diferente das duas anteriores, porque é definida para cada tipo de brinquedo, não como o total para todos os tipos de brinquedo. Portanto, precisamos de dois deles, um para trens e um para soldados, como você pode ver na linha 25. Observe que a variável de índice ( {i em TOY} ) vem antes do :. Isso instrui o GLPK para criar uma restrição para cada tipo de brinquedo em TOY e a equação que irá governar cada restrição será o que vem após o :. Nesse caso, o GLPK criará

Dem[soldier] : x[soldier] <= Demand[soldier]

Dem[train] : x[train] <= Demand[train]

Solucionar esse novo modelo deve produzir os mesmos resultados:

Problema:    giapetto2
Linhas:       5
Colunas:      2
Não-zeros:    8
Status:     OPTIMAL
Objetivo:   z = 180 (MAXimum)

   No. Nome Linha   St  Atividade   Limite Inferior Limite Superior  Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 z            B            180
     2 Fin_hours    NU           100                         100             1
     3 Carp_hours   NU            80                          80             1
     4 Dem[soldier] B             20                          40
     5 Dem[train]   B             60                    6.02e+23

   No. Nome Coluna  St   Atividade  Limite Inferior Limite Superior  Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x[soldier]   B             20             0
     2 x[train]     B             60             0

Condições de Otimização Karush-Kuhn-Tucker

KKT.PE: max.abs.err. = 0.00e+00 na linha 0
        max.rel.err. = 0.00e+00 na linha 0
        Alta qualidade

KKT.PB: max.abs.err. = 0.00e+00 na linha 0
        max.rel.err. = 0.00e+00 na linha 0
        Alta qualidade

KKT.DE: max.abs.err. = 0.00e+00 na coluna 0
        max.rel.err. = 0.00e+00 na coluna 0
        Alta qualidade

KKT.DB: max.abs.err. = 0.00e+00 na linha 0
        max.rel.err. = 0.00e+00 na linha 0
        Alta qualidade

Fim da saída

Observe como os limitadores e as variáveis de decisão são agora nomeadas após o conjunto TOY , que parece limpo e organizado. Muito bem. Você maximizou o lucro do Giapetto!

Voltar para parte superior

Conclusão

Você viu como formular um problema linear simples, de duas variáveis. Em seguida, você viu como utilizar um programa MathProg simples para solucioná-lo utilizando conjuntos, parâmetros, limitadores, variáveis de decisão e uma função de objetivo (destino). O programa utilizou adição em conjuntos e uma seção de dados de parâmetros. Finalmente, você aprendeu como interpretar os resultados de um problema de maximização.

A próxima parcela nessa série de três artigos mostrará como tirar o máximo de uma má alimentação.

Voltar para parte superior

Download

Informações sobre métodos de download

Recursos

Aprender

• Os problemas nesse artigo são adotados com permissão de Pesquisa de Operações: Aplicativos e Algoritmos, 4ª Edição, por Wayne L. Winston (Thomson, 2004).
  
  
• A documentação on-line para GLPK fornece informações adicionais sobre o GLPK, como obter o software e como associar-se à comunidade do GLPK.
  
  
• Verifique a entrada da Wikipédia para GLPK.
  
  
• Inscreva-se na lista de endereçamento de ajuda do GLPK ou na lista de endereçamento de relatórios de erro.
  
  
• Na zona Linux do developerWorks, encontre mais recursos para desenvolvedores Linux.
  
  
• Fique atualizado com eventos técnicos e Webcasts do developerWorks.
  
  

Obter produtos e tecnologias

• Com o Software de período experimental IBM, disponível para download diretamente do developerWorks, construa seu próximo projeto de desenvolvimento em Linux.
  
  

Discutir

• Verifique blogs do developerWorks e envolva-se com a comunidade do developerWorks.
  
  

Sobre o autor

Rodrigo Ceron Ferreira de Castro é um Engenheiro Administrativo de Software no Centro de Tecnologia IBM Linux. Ele se formou na Universidade Estadual de Campinas (UNICAMP) em 2004. Recebeu o prêmio do Instituto de Engenharia do Estado e o Certificado de Honra ao Mérito do Conselho de Engenharia ao se formar. Fez palestras em conferências de software livre no Brasil e em outros países.

Classificar este artigo

Comentários

Voltar para parte superior

Índice

• Introdução
• O GNU Linear Programming Kit
• A Linguagem de Modelagem MathProg do GNU
• Giapetto's Woodcarving Inc..
• Modelagem
• Um Pouco de Teoria
• Utilizando o GLPK para Solucionar o Modelo
• Utilizando Modelo e Seções de Dados no Problema do Giapetto
• Conclusão
• Download
• Recursos
• Sobre o autor
• Comentários

Conheça a IBM da sua cidade

A IBM está mais perto do que você imagina!

---

Saiba mais