Pesquisa operacional e programação linear, uma breve introução

A Programação Linear é uma técnica de planejamento que se originou no final da década de quarenta e, com o surgimento do computador na década de cinquenta, encontrou o seu aliado natural, tendo então um desenvolvimento acelerado e sendo também muito difundida.

Costuma-se dizer, também, que a PL é um tópico da ciência Pesquisa Operacional, a qual contém outros tópicos tais como Teoria das Filas, Simulação, Teoria dos Jogos, Programação Dinâmica, PERT/CPM, etc.

Estudos estatísticos têm mostrado que a PL é hoje uma das técnicas mais utilizadas da Pesquisa Operacional. É comum vermos aplicações de PL fazerem parte de rotinas diárias de planejamento das mais variadas empresas, tanto nas que possuem uma sofisticada equipe de planejamento como nas que simplesmente adquiriram um software para alguma função de planejamento.

Podemos conceituar a Programação Linear como a seguir:

  •  A Programação linear ée uma técnica de otimização;
  • A Programação linear é uma ferramenta utilizada para encontrar o lucro máximo ou o custo mínimo em situações nas quais temos diversas opções de escolha sujeitas a algum tipo de restrição ou regulamentação.

 É importante também desde já, esclarecer que a palavra programação tem aqui o significado de planejamento. Fazemos isto para evitar a confusão com o termo programação de computadores, termo atualmente bastante utilizado na Ciência da Computação. Portanto a Programação linear é uma técnica de planejamento baseada em matemática e eeconomia. certamente a Programação linear utiliza computadores para resolver seus problemas, mas é importante entender que a palvra programação tem significados diferentes nas 2 ciências.

Aplicações da Programação Linear

Na prática a Programação linear tem sido aplicada em áreas tão diversas como mostram os cenários seguintes:

  • alimentação: que alimentos as pessoas (ou os animais) devem utilizar de modo que o custo seja mínimo e que possuam os nutrientes nas quantidades adequadas, e que também atendam a outros requisitos tais como variedade entre as refeições, aspecto, gosto, etc?
  • rotas de transporte: qual deve ser o roteiro de veículos de carga de modo que entreguem toda a carga no menor tempo e no menor custo total?
  • manufatura: qual deve ser a composição de produtos a serem fabricados por uma empresa de modo que se atinja o lucro máximo, sendo respeitadas as limitações ou exigências do mercado consumidor e a capacidade de produção da fábrica?
  • siderurgia: quais minérios devem ser carregados no alto-forno de modo a se produzir, ao menor custo, um determinado aço dentro de determinadas especificações de elementos químicos?
  • petróleo: qual deve ser a mistura de petróleo a ser enviada para uma torre de craqueamento para produzir seus derivados (gasolina, óleo, etc) a um custo mínimo? Os petróleos são de diversas procedências e possuem composições diferentes.
  • agricultura: que alimentos devem ser plantados de modo que o lucro seja máximo e sejam respeitadas as características do solo, do mercado comprador e dos equipamentos disponíveis?
  • carterira de investimento: quais ações devem compor uma carteira de investimentos de modo que o lucro seja máximo e sejam respeitadas as previsões de lucratividade e as restrições governamentais?
  • mineração: em que sequência deve-se lavrar blocos de minérios abixo do solo, dado sua composição, posicionamento e custo de extração?
  • localização industrial: onde devem ser localizadas as fábricas e os depósitos de um novo empreendimento industrial de modo que os custos de entrega do produto aos varejistas sejam minimizados ?

Vantagens do uso da Programação Linear

Vimos na própria definição da Programação linear que seu objetivo é encontrar lucro máximo ou custo mínimo. Mas qual é a magnitude deste benefício dentro das empresas?

 É conveniente apresentar a informação, obtida em pesquisas efetuadas em empresas que têm utilizado esta ferramenta, de que a redução de custos se enquadra facilmente na faixa entre 1% e 5%, existindo casos em que chega até a 15%.

Analisemos então duas indústrias que utilizam intensamente técnicas de PL: siderúrgica e petrolífera. É comum encontrar empresas destas áreas com faturamento anual de US$ 1 bilhão e com um custo de produção da ordem de US$ 300 milhões anuais (exclusive mão-de-obra). Imaginando que, nestas empresas, a PL produza uma redução de custos da ordem de 3%, vemos que isto significa uma economia de 0,03 x 300 = US$ 9 milhões por ano.

Para atingir esta economia, diversas empresas têm aceitado investir uma pequena fração deste valor na contratação de profissionais qualificados e em computadores poderosos. No caso de empresas petrolíferas, nas quais as economias são bastante significativas, as equipes que trabalham nesta área são em número expressivo (é comum encontrar empresas com mais de 20 pessoas na área) e altamente especializadas (o título de Mestre é comum e se encontram também Ph.D.s). Finalmente, é importante lembrar que, mesmo na época em que os computadores eram caríssimos (main-frames nas décadas de sessenta a oitenta), tais considerações eram válidas.

Além das vantagens citadas e que são as de maior visibilidade, podemos ainda citar como vantagens do uso da Programação linear:

  • Permite identificar as melhores opções em estudos de Qualidade Total;
  • Permite a identificação de gargalos em linhas de produção;
  • Fornece diretrizes para expansão;
  • Possibilita avaliar o potencial de aplicabilidade de uma pesquisa.

 Aspectos históricos da Programação linear

Durante a segunda guerra mundial foi levantado um problema, nos EUA, que desafiou os estudiosos de ciências exatas. Este problema ficou conhecido pelo nome de “Problema da Dieta” e se resumia em descobrir qual a alimentação mais económica, levando-se em conta que o organismo humano necessita de uma quantidade mínima diária de certos nutrientes (tais como proteínas, vitaminas, etc), que devem ser obtidos de alimentos que possuem preços diferentes e composição de nutrientes diferentes.

O desafio foi publicado no conhecido jornal The New York Times e ganhou repercussão nacional. A melhor solução ao problema foi apresentada por George Stigler, em 1945, na qual, partindo de 77 alimentos e levando em consideração a composição de 9 nutrientes em cada um, ele chegou à conclusão de que a dieta ideal implicaria um custo anual de US$59.88 e seria composta de farinha de trigo, repolho e fígado de porco.

A solução apresentada era inusitada, pois Stigler não levou em consideração nenhum aspecto de diversidade, gosto, aspecto, etc: apenas considerou aspectos económicos. O valor do custo de sua composição ficava muito abaixo das outras propostas mas, certamente, ninguém iria manter aquela única alimentação por qualquer período. Assim, o concurso foi alvo de muitas chacotas, mas em pouco tempo se constatou que aquela técnica poderia ser utilizada sem rejeição em áreas semelhantes, tais como alimentação de animais ou carga de um alto-forno de uma siderurgia. Imediatamente se iniciaram tais estudos, mas a técnica utilizada por Stigler (tentativas) se mostrou sujeita a erros, extremamente tediosa e cansativa, além de nem sempre encontrar a solução ótima.

Esta abordagem de planejamento somente se consolidou com George Dantzig, em 1947, que desenvolveu o Método Simplex, capaz de resolver qualquer problema de Programação linear. Dantzig desenvolveu esta técnica quando trabalhava na Rand Corporation no projeto SCOOP (Scientific Computation of Optimum Programs) para a Força Aérea Americana, desenvolvendo técnicas de otimização para problemas militares.

O algoritmo Simplex implica uma quantidade muito grande de cálculos e, nos primeiros anos de uso, ele se apoiou exclusivamente na resolução manual. Com o surgimento do computador, em 1951, a Programação linear encontrou seu aliado natural e foi se expandindo de uma maneira extraordinária. Na década de sessenta a Programação linear tinha a mesma divulgação e fascínio também obtidos por outras técnicas, tal como a Gestão pela Qualidade Total obteve nas décadas de oitenta e noventa.

Do ponto de vista histórico, é importante saber que o assunto foi inicialmente analisado em 1936 por Wassily Leontieff, que criou um modelo constituído por um conjunto de equações lineares, considerado como o primeiro passo para o estabelecimento das técnicas de Programação Linear. O matemático russo L.V. Kantorovick, em 1939, publicou um trabalho sobre planejamento da produção, o qual apresentava, dentre diversas abordagens, o uso de equações lineares. Este trabalho somente veio a ser conhecido no Ocidente em 1960. É importante ainda citar que, em 1940, Frank L. Hitchcock apresentou uma abordagem ao problema de transportes. 

Deixe um comentário

O seu endereço de e-mail não será publicado.