LCF5734 - Manejo Florestal Avançado (2018)

Introdução à Programação Matemática

A programação matemática compreende a utilização de modelos matemáticos para a solução de certos problemas de otimização muitos úteis para o gestor.  As expressões matemáticas utilizadas em um determinado modelo podem ser lineares ou não lineares, e envolver variáveis contínuas ou inteiras.  Os coeficientes utilizados nas expressões matemáticas podem ser perfeitamente conhecidos, dando uma conotação determinística ao modelo, ou sujeitos a uma certa variabilidade, tornando os modelos probabilísticos (ou estocásticos).  Neste texto, a nossa atenção estará voltada para os modelos determinísticos.

A palavra programação nos induz a pensar na necessidade de um programa computacional que utilize um conjunto de instruções que nos permita resolver os problemas.  É fato que a maioria dos problemas de programação matemática são resolvidos em computadores, mas isto não quer dizer que essa seja a única maneira de resolver esses problemas.  A solução computacional é necessária e conveniente quando os problemas envolvem um número muito grande de variáveis.  A princípio, todos os problemas de programação matemática poderiam ser resolvidos com o simples uso de um lápis e papel, não fosse o fato do número de computações necessárias aumentar muito conforme aumenta o número de variáveis envolvidas nos modelos.

Para problemas relativamente simples, é possível derivar uma solução analítica com recursos bastante simples de álgebra e cálculo.  Freqüentemente, entretanto, a solução ótima de um problema de programação linear é obtida por meio de métodos numéricos, que podem ser definidos como sofisticadas técnicas de tentativa e erro.  Os métodos numéricos mais poderosos são algorítmicos.  Um algoritmo é um conjunto de operações lógicas e matemáticas implementadas de acordo com uma seqüência pré definida.  Pode-se dizer, portanto, que um algoritmo é um programa que resolve um determinado tipo de problema matemático.  A partir de uma solução inicial, o algoritmo busca uma nova solução melhor que a anterior.  A seqüência de operações que conduz a uma nova solução é chamada iteração.  As iterações são interrompidas apenas quando um pré determinado critério de otimalidade seja satisfeito.

Para problemas adequadamente representados por um modelo de programação matemática e algoritmos corretamente desenhados, a "melhor” solução encontrada durante o processo iterativo resulta sempre na solução ótima do problema.  Para que um algoritmo resulte prático, são necessárias certas propriedades:  (1) cada solução sucessiva deve resultar melhor que a anterior;  (2) um número finito de soluções sucessivas deve se mostrar convergente para uma solução ótima;  (3) os requisitos computacionais em cada iteração devem ser pequenos o suficiente para que a solução do problema como um todo seja computacionalmente viável.

O principal truque em qualquer técnica de programação matemática é encontrar uma solução ótima sem ter que recorrer a uma busca exaustiva de todas as possíveis soluções.  Na prática, esse número é geralmente infinito, tornando a enumeração e análise impossíveis.  Os algoritmos de programação matemática são desenhados para reduzir a busca e ao mesmo tempo garantir a definição de uma solução ótima.  Não é nosso objetivo entrar nos aspectos teóricos do desenvolvimento desses algoritmos.  Usaremos somente argumentos intuitivos como base para explicar os princípios da programação matemática.

Por enquanto, é válido dizer que: (1) Existe um problema de gestão para ser resolvido, e esse problema incorpora todas as características que definem um problema de programação matemática.  (2) Um modelo de programação matemática pode ser desenvolvido para servir como abstração do sistema em estudo.  Esse modelo inclui meios de se avaliar as possíveis soluções em termos do critério de otimização (isto é, do objetivo) e considera as limitações de recursos existentes.  (3) A solução ótima para o problema de programação matemática pode ser obtida numericamente por meio de um algoritmo.

Uma forma concisa de resumir as intenções por trás do uso de modelos de programação matemática é dizer que a programação matemática se preocupa com a alocação ótima de recursos escassos entre atividades alternativas.  É importante ressaltar também que geralmente existe uma diferença entre a solução para o problema de programação matemática e a implementação no campo dessa solução.  Tomadores de decisão raramente estão interessados nas soluções propriamente ditas, mas sim em informação na qual possam basear as suas decisões.  Uma análise de programação linear propicia parte dessa informação, pois igualmente importante são as outras considerações não quantitativas do problema original que não puderam ser incorporadas no modelo matemático.  É aconselhável, portanto, pensar que modelos de programação matemáticas nos dão inspiração (insight), e não números.  É verdade que os números representando uma solução ótima são de algum interesse, mas só até o ponto onde o modelo matemático consegue incorporar a realidade.  Qualquer modelo matemático representa somente uma visão limitada do sistema real, sendo este o alvo do nosso interesse, não o modelo.

Uma Introdução Gráfica à Programação Linear

A programação linear é o mais usado método de programação matemática, e o mais aplicado na gestão de recursos naturais e disciplinas correlatas.  Para estudá-lo vamos nos basear em um problema bastante simples de programação que pode ser apresentado da seguinte forma:

Este problema claramente trata da alocação ótima de recursos escassos (acres de terra e capital de investimento) entre atividade alternativas (gado ou floresta).  Poderíamos, portanto, redefinir o problema da seguinte forma:

Deseja-se definir o número de novilhos para engorda e de lotes de 1.000 árvores para plantio que maximize a receita anual obtida com essas atividades, sem exceder as limitações de área e capital de investimento disponíveis.

Variáveis de Decisão

No curto prazo, o número de acres na fazenda e o capital disponível são fixos.  As variáveis do problema - ou seja, aquilo que pode ser controlado (variado) no curto prazo - são número de novilhos e número de lotes de árvores.  Uma decisão deve ser tomada a respeito desses valores, por isso representam variáveis de decisão.  Uma convenção em problemas de programação linear é representar as variáveis de decisão através da notação x_j   j=1,2, ..., N, onde N representa o número total de variáveis de decisão no problema.  No nosso problema temos N=2,e poderíamos definir

As variáveis de decisão podem também ser chamadas atividades, e é geralmente útil imaginá-las dessa forma.  Assim sendo, x₁ poderia representar a atividade de produção de novilhos e x₂ a atividade de produção de árvores.  Os números eventualmente associados com cada uma dessas variáveis de decisão (após a solução do problema de programação linear) representam os níveis das atividades.  A lista completa desses níveis expressa a solução do problema de programação linear.

Função Objetivo

No exemplo afirmamos que nosso objetivo era maximizar a receita anual obtida com novilhos e árvores.  Nesse exemplo em particular faz sentido medir o objetivo em dólares, ou outra unidade monetária qualquer, pois estamos tratando de um objetivo econômico.  Isto não quer dizer que outras unidades representando outros objetivos não possam ser utilizadas também, desde que manifestem um valor quantitativo e consistente.  Tanto objetivos econômicos como não-econômicos podem ser acomodados em modelos de programação linear.  A decisão final sobre o tipo de unidade utilizada na função objetivo depende fortemente no tipo de problema sendo estudado e na imaginação ou necessidades do analista.

Ao expressar qualquer função objetivo em modelos de programação linear, devemos nos assegurar de que as unidades são consistentes.  No nosso problema, as duas variáveis de decisão envolvem unidades diferentes: número de novilhos e número de lotes de 1.000 árvores.  Se o objetivo é medido em dólares, devemos ser cuidadosos ao expressar a contribuição de cada uma dessas variáveis de decisão à função objetivo.  Para x₁, número de novilhos para engorda, isto é fácil: 9 moedas por novilho vezes x₁ novilhos = contribuição total.  Para x₂, número de lotes de 1000 árvores plantadas, entretanto, a tarefa fica um pouco mais complicada.  O problema declara como receita da atividade manejo de árvores um valor em moedas por hectare. O problema nos diz que são plantadas 500 árvores por hectare (ou, alternativamente, que cada lotede árvores ocupa 2 acres).  Isto implica em 20 moedas por lote de 1000 árvores.

Conseguimos obter valores numéricos para a contribuição à receita total proveniente de cada novilho ($9) e de cada lote de árvores ($20).  Desta forma, se multiplicarmos a contribuição de cada novilho pelo número de novilhos (x₁) e acrescentarmos essa quantia à contribuição de cada lote de árvores multiplicada pelo número de lotes teremos uma expressão matemática para o nosso objetivo.  Esta expressão é chamada  função objetivo e, por convenção, é geralmente associada com a letra Z.  Matematicamente a função objetivo do nosso problema poderia ser expressa da seguinte forma:

Digamos que x₁=600 e x ₂=300 resultasse em uma solução para o nosso problema.  O valor da função objetivo neste caso seria igual a  Z = 9(600) + 20(300) = 11.400.  Não sabemos se a engorda de 600 novilhos e o plantio de 300.000 árvores resulta na solução ótima para o nosso problema.  Para que em breve possamos avaliar essa possibilidade é útil, entretanto, que tenhamos uma representação gráfica da função objetivo. No espaço Euclidiano bidimensional, a função objetivo pode ser representada por uma linha reta cujos pontos extremos são calculados da seguinte forma  x₁  = Z/9  e x₂  = Z/20.  Procure na Figura 1 as diferentes combinação de x₁ e x₂ que resultam no mesmo valor de  Z = 11.400.

Figura 1: Gráfico com diferentes valores de Z

Restrições

Nosso problema é encontrar os valores de x₁ e x₂ para os quais o valor de Z é máximo.  Considere o gráfico da Figura 1 com diferentes valores arbitrários para a função objetivo. As linhas no gráfico podem ser vistas como curvas de nível.  Quanto mais a "nordeste" no gráfico maior é o valor de Z.  Isto significa que poderíamos aumentar o valor de Z indefinidamente, não fossem as limitações impostas à produção de novilhos e árvores.

No caso do nosso problema, essas limitações são da ordem de 1.200 acres e 142.500 moedas para investimento.  Assim sendo, qualquer combinação de x₁ e x₂ que resulte no uso dos recursos em  níveis superiores a esses limites representará soluções inviáveis.  Por exemplo, teríamos área e capital suficientes para engordar 200 novilhos e plantar 480.000 árvores?  Dos dados do problema sabemos que 200 novilhos ocupariam 200 acres (1acre/novilho x 200 novilhos) e exigiriam 15.000 moedas de investimento ($75/novilho x 200 novilhos), e que 480.000 árvores ocupariam 960 acres (2 acres/lote x 480 lotes) e 144.000 moedas de investimento ($300/lote x 480 lotes).  Necessitaríamos de uma área total de 1160 acres e de um capital total de 159.000 moedas.  Obviamente essa combinação excede a capacidade de investimento do fazendeiro, ainda que com folga na disponibilidade de área (40 acres).

Será que todas as combinações com Z=11.400 correspondem a soluções inviáveis?  Se considerarmos a combinação x₁ =600 e x₂ =300, veremos que essa solução resulta numa necessidade de área de 1200 acres e de um investimento de 135.000 moedas.  Essa solução utiliza toda a área e quase que integralmente o capital disponível (sobram 7500 moedas).  Trata-se, portanto, de uma solução viável com um valor de Z equivalente à solução anterior que era inviável.  Mais tarde veremos que existe uma solução viável ainda melhor do que esta.

Antes porém, seria interessante dispormos de um método gráfico mais conveniente para análise da viabilidade de diferentes soluções e escolha de soluções viáveis.  Esse método deve representar adequadamente as restrições impostas aos valores de x ₁ e x ₂.

O problema explicitamente informa que "a soma de x₁ mais 2x₂ deve ser inferior a 1200 acres".  Matematicamente, isto significa x₁ + 2x₂  £ 1200.  Os coeficientes das variáveis dessa inequação são chamados coeficientes tecnológicos. O número à direita do sinal de desigualdade é chamado de parâmetro do RHS ("right hand side"), ou simplesmente RHS.

Utilize o link abaixo para acessar um ambiente que permite estudar a representação gráfica do problema, usando a formulação matemática proposta nesta seção. Analise a região de viabilidade resultante e a solução do problema nesse ambiente gráfico.