Programação Linear Aplicada · Capítulo 2
Objetivos de aprendizagem
2.1 / fundamentos
Problemas de alocação de recursos tratam da melhor forma de distribuir recursos limitados entre alternativas de uso ou atividades, buscando otimizar um objetivo. Em geral, é necessário decidir quanto executar de cada atividade, produto ou destino, respeitando as disponibilidades existentes. Os recursos podem representar matéria-prima, mão de obra, tempo, orçamento, capacidade produtiva ou outros elementos escassos. A característica central é que as decisões consomem recursos, as relações entre as quantidades são lineares e existe um objetivo claramente definido, como maximizar o benefício ou minimizar o custo.
Esse tipo de problema aparece em diferentes contextos: produção e mistura de produtos, distribuição e transporte, alocação de pessoas e equipes, orçamento, capacidade de atendimento e utilização de instalações. Em todos esses casos, a Programação Linear procura identificar a melhor combinação possível entre as alternativas, respeitando as limitações do sistema.
Ideia central
Um problema de alocação de recursos procura determinar quanto fazer de cada alternativa para obter o melhor resultado possível com os recursos disponíveis.
Uma fábrica produz mesas e cadeiras. Cada mesa requer quatro unidades de madeira e duas horas de trabalho, enquanto cada cadeira requer duas unidades de madeira e três horas de trabalho. A fábrica dispõe, por semana, de quarenta unidades de madeira e trinta horas de trabalho. A venda de cada mesa proporciona lucro de R$ 50,00 e a venda de cada cadeira proporciona lucro de R$ 40,00. O problema consiste em determinar quantas mesas e quantas cadeiras devem ser produzidas semanalmente para maximizar o lucro, respeitando a disponibilidade de madeira e de horas de trabalho.
2.2 / modelagem
As variáveis de decisão representam as quantidades que precisam ser determinadas pelo modelo. Elas traduzem, de forma mensurável, aquilo sobre o que o decisor pode agir. No exemplo da fábrica, a decisão é escolher as quantidades semanais de cada produto.
Depois de definidas as variáveis, o problema precisa ser expresso por relações matemáticas. Em Programação Linear, essas relações são organizadas principalmente em uma função objetivo, que representa aquilo que se deseja otimizar, e em restrições, que expressam as limitações impostas pelos recursos ou pelas regras do problema.
x₁: mesas
x₂: cadeiras
Representa o lucro total e deve ser maximizada.
Representam os limites de madeira e de horas de trabalho.
A função objetivo traduz matematicamente o critério utilizado para comparar as alternativas. Dependendo do problema, pode-se desejar maximizar lucro, produção, nível de serviço ou utilização de recursos; em outros casos, pode-se desejar minimizar custos, distâncias ou tempos. No exemplo, cada mesa contribui com R$ 50,00 para o lucro e cada cadeira com R$ 40,00. Assim, o lucro total é dado pela soma dessas contribuições.
As restrições delimitam as combinações possíveis das variáveis de decisão. Elas representam recursos disponíveis, capacidades, exigências técnicas, limites contratuais ou outras condições que não podem ser violadas.
Para a madeira, cada mesa consome quatro unidades e cada cadeira duas. Como existem quarenta unidades disponíveis:
Para o trabalho, cada mesa utiliza duas horas e cada cadeira três. Como existem trinta horas disponíveis:
As variáveis representam quantidades produzidas. Nesse contexto, não faria sentido admitir uma produção negativa de mesas ou de cadeiras. Por isso, o modelo inclui as condições de não negatividade, que restringem as variáveis ao conjunto dos valores iguais ou superiores a zero.
Reunindo as relações construídas, o problema da fábrica é representado pelo seguinte modelo:
Esse modelo contém os elementos essenciais da decisão: o que deve ser determinado, o que se deseja otimizar e quais condições limitam as escolhas possíveis.
2.3 / planilha
Uma planilha eletrônica é uma ferramenta especialmente útil para popular o modelo com os dados do problema e tornar visíveis as relações entre parâmetros, variáveis de decisão, função objetivo e restrições. No exemplo, os coeficientes de lucro, consumo de madeira e consumo de horas podem ser organizados por produto; as quantidades produzidas ocupam as células reservadas às variáveis; e fórmulas calculam automaticamente o lucro total e o consumo de cada recurso.
Além de facilitar a organização, a planilha permite alterar rapidamente as quantidades de produção e observar como essas mudanças afetam o lucro, o consumo dos recursos e as folgas. Dessa forma, antes mesmo de utilizar um algoritmo de otimização, o aluno pode compreender a lógica do modelo e testar diferentes cenários.
O Solver é o recurso do Excel destinado à solução de problemas de otimização. Em vez de testar manualmente diferentes valores para as variáveis, o Solver busca valores que otimizem a célula correspondente à função objetivo, respeitando as restrições definidas no modelo. Neste momento, o mais importante é compreender sua função: ele automatiza a procura pela melhor combinação das variáveis. A configuração e o uso do Solver serão retomados posteriormente.
2.4 / interpretação geométrica
Como o Exemplo 1 possui apenas duas variáveis de decisão, x₁ e x₂, é possível representar geometricamente o modelo em um plano cartesiano. Essa representação é especialmente útil porque permite visualizar o significado das restrições, da região viável, da função objetivo e da solução ótima.
Uma restrição linear com duas variáveis define uma região do plano. Para desenhá-la, começa-se pela reta associada, substituindo a desigualdade por uma igualdade. Em seguida, podem ser determinados dois pontos da reta fazendo uma das variáveis igual a zero.
Para a restrição de madeira:
Para a restrição de horas de trabalho:
Cada desigualdade seleciona um dos lados da reta, isto é, um semiplano. A região viável do problema é formada pelas combinações de x₁ e x₂ que satisfazem simultaneamente todas as restrições, inclusive a não negatividade. Graficamente, ela corresponde à interseção dos semiplanos e assume a forma de um polígono.
No Exemplo 1, a região viável tem como vértices principais os pontos (0,0), (0,10), (7,5;5) e (10,0). O ponto (7,5;5) é a interseção das duas retas de restrição.
A função objetivo também pode ser representada por retas. Ao fixar um valor para Z, a expressão 50x₁ + 40x₂ = Z define uma reta. Diferentes valores de Z produzem retas paralelas, pois os coeficientes de x₁ e x₂ permanecem os mesmos. À medida que a reta é deslocada na direção de valores maiores de Z, o lucro cresce.
Para um problema de maximização, a reta da função objetivo é deslocada paralelamente no sentido de crescimento de Z até atingir o último ponto da região viável. No Exemplo 1, esse ponto ocorre na interseção das duas restrições:
Substituindo esses valores na função objetivo:
Portanto, a solução gráfica indica uma produção de 7,5 mesas e 5 cadeiras, com lucro máximo de R$ 575,00, considerando o modelo tal como formulado.
2.5 / aplicações
Um quiosque produz sucos de laranja e de abacaxi. Cada suco de laranja requer três laranjas e dois minutos de preparo, enquanto cada suco de abacaxi requer duas fatias de abacaxi e três minutos de preparo. O quiosque dispõe, por dia, de 30 laranjas/fatias equivalentes e de 30 minutos para preparo. A venda de cada suco de laranja gera lucro de R$ 8,00 e a de cada suco de abacaxi gera lucro de R$ 6,00. O problema consiste em determinar quantos sucos de cada tipo devem ser produzidos por dia para maximizar o lucro, respeitando a disponibilidade de frutas e o tempo de preparo.
Uma refinaria produz três tipos de gasolina: verde, azul e comum. Para a produção dessas gasolinas são utilizados três componentes: gasolina pura, octana e aditivo. A refinaria dispõe semanalmente de 9.600.000 litros de gasolina pura, 4.800.000 litros de octana e 2.200.000 litros de aditivo.
Cada litro de gasolina verde requer 0,22 litro de gasolina pura, 0,50 litro de octana e 0,28 litro de aditivo. Cada litro de gasolina azul requer 0,52 litro de gasolina pura, 0,34 litro de octana e 0,14 litro de aditivo. Já cada litro de gasolina comum requer 0,74 litro de gasolina pura, 0,20 litro de octana e 0,06 litro de aditivo.
Com base na demanda de mercado, a refinaria estabeleceu ainda duas condições para seu programa de produção: a quantidade produzida de gasolina comum deve ser, no mínimo, 16 vezes a quantidade de gasolina verde, enquanto a produção de gasolina azul não pode ultrapassar 600.000 litros por semana.
A margem de contribuição para o lucro obtida pela refinaria é de $ 0,30 por litro de gasolina verde, $ 0,25 por litro de gasolina azul e $ 0,20 por litro de gasolina comum.
Determine o programa semanal de produção da refinaria, isto é, as quantidades de gasolina verde, azul e comum que devem ser produzidas, de modo a maximizar a margem total de contribuição para o lucro, respeitando a disponibilidade dos componentes e as condições estabelecidas para a produção.
Uma indústria de cimento fabrica dois produtos: o cimento Portland 320 (CP320) e o cimento alto-forno 250 (AF250). A fabricação desses produtos utiliza quatro componentes: clínquer, escória de alto-forno, gesso e aditivo.
Para produzir uma tonelada de CP320, são necessários 85% de clínquer, 7% de escória de alto-forno, 3% de gesso e 5% de aditivo. Para produzir uma tonelada de AF250, são necessários 50% de clínquer, 45% de escória de alto-forno, 3% de gesso e 2% de aditivo.
A capacidade anual de produção de clínquer é limitada a 1.100.000 toneladas, em razão da capacidade do forno. A capacidade do moinho também limita a produção conjunta de CP320 e AF250 a 1.100.000 toneladas por ano.
Além de utilizar o clínquer na fabricação dos dois tipos de cimento, a empresa pode vendê-lo para outros fabricantes, sendo essa venda limitada a 200.000 toneladas por ano. A escória de alto-forno é adquirida de usinas siderúrgicas e sua compra está limitada a 180.000 toneladas por ano. As compras de gesso e de aditivo estão limitadas, cada uma, a 50.000 toneladas por ano.
A empresa obtém uma contribuição marginal de $ 41,00 por tonelada de CP320, $ 37,80 por tonelada de AF250 e $ 34,40 por tonelada de clínquer vendido. Para a produção dos cimentos, devem ainda ser considerados os custos dos componentes adquiridos: $ 22,10 por tonelada de escória de alto-forno, $ 34,20 por tonelada de gesso e $ 1,90 por tonelada de aditivo. As contribuições marginais informadas foram calculadas a partir da receita líquida menos os custos fixos e os custos variáveis, excetuando-se os custos da escória, do gesso e do aditivo, que, portanto, devem ser considerados separadamente na determinação do resultado.
Determine o programa anual de produção, estabelecendo as quantidades de CP320 e AF250 a serem fabricadas e de clínquer a ser vendido, de modo a maximizar o lucro total da empresa, respeitando as capacidades produtivas, as disponibilidades dos componentes e as demais limitações estabelecidas.
Esses exemplos mostram que a mesma estrutura de raciocínio — variáveis, função objetivo, restrições e não negatividade — pode ser empregada em contextos muito diferentes. O que muda é a interpretação dos coeficientes e das relações do modelo.
2.6 / fechamento
A construção de um modelo de Programação Linear começa com a compreensão do problema real. A partir dessa compreensão, identificam-se as decisões que precisam ser tomadas, traduzidas pelas variáveis; define-se o objetivo a otimizar; estabelecem-se as restrições; e, por fim, obtém-se uma representação matemática capaz de ser analisada por métodos gráficos ou computacionais.
Síntese do capítulo
A Programação Linear transforma uma decisão real em um modelo composto por variáveis de decisão, função objetivo, restrições e condições de não negatividade. Em problemas com duas variáveis, a representação gráfica permite visualizar a região viável e localizar a solução ótima; em problemas maiores, ferramentas computacionais assumem esse papel.