PHPSimplex

Otimizar os recursos com Programação Linear



História da Pesquisa Operacional

Ao longo da história é frequente se ver uma estreita colaboração entre cientistas e militares com o fim de encontrar a melhor decisão na batalha e tentar obter a vitória. É por isso que muitos especialistas na matéria consideram o início da Pesquisa Operacional no século III A.C, durante a Segunda Guerra Púnica, com a análise e proposta de solução de Arquimedes para defender a cidade de Siracusa, sitiada pelos romanos. Entre suas invenções se encontravam a catapulta e um sistema de espelhos para incendiar as naves inimigas concentrando os raios do sol.

Em 1503, Leonardo da Vinci participou como engenheiro na guerra contra Pisa, pois sabia técnicas de bombardeio, construir navios, veículos blindados, canhões, catapultas e outras máquinas de guerra.

Lâminas com invenções de Leonardo da Vinci

Outro antecedente do uso da Pesquisa Operacional foi produzido durante a Primeira Guerra Mundial na Inglaterra, com o estudo matemático de Frederick William Lanchester sobre o poder balístico das forças opositoras. Também desenvolveu, a partir de um sistema de equações diferenciais, a Lei Quadrada de Lanchester para Combate, com a qual era possível determinar o resultado uma batalha militar em função da força numérica relativa e a capacidade relativa de fogo dos combatentes.

Thomas Alva Edison também fez uso da Pesquisa Operacional, contribuindo na guerra anti-submarino, desenvolvendo técnicas para que os navios pudessem fugir e destruir submarinos inimigos, proporcionando-lhes uma proteção anti-torpedo.

Do ponto de vista matemático, nos séculos XVII e XVIII, Newton, Leibniz, Bernoulli, e Lagrange, trabalharam para obter máximos e mínimos condicionados de determinadas funções. O matemático francês Jean Baptiste Joseph Fourier, esboçou métodos da atual programação linear. E nos últimos anos do século XVIII, Gaspar Monge estabeleceu os precedentes do método gráfico com o desenvolvimento da Geometria Descritiva.

No final do século XIX, Frederick Winslow Taylor realizou um estudo que permitiu maximizar o desempenho dos mineiros, no qual foi determinado que a única variável realmente significativa era o peso combinado da pá e sua carga.. Desta forma se desenharam pás segundo os diferentes tipos de materiais que seriam usados.

John Von Neumann publicou sua obra "Teoria dos Jogos" em 1928, que forneceu os fundamentos matemáticos da Programação Linear. Posteriormente, em 1947, idealizou a semelhança entre os problemas de programação linear e a teoria das matrizes que ele havia desenvolvido.

Em 1939, o matemático russo Leonid Vitálievich Kantorovich e o holandês Tjalling Charles Koopmans, desenvolveram a teoria matemática chamada "Programação Linear", pela que foram agraciados com o Prêmio Nobel de Economia.

Em 1945, George Joseph Stigler levantou o problema da dieta, a raiz da preocupação do exército americano para garantir os requisitos nutricionais básicos para suas tropas tendo o menor custo possível. Se tratava de determinar a quantidade, entre 77 alimentos diferentes, que deveria ingerir diariamente um homem de estatura mediana de aproximadamente 70 kg, de modo que as necessidades mínimas de nutrientes fossem iguais às recomendadas pelo Conselho Nacional de Investigação norte americano. O problema foi resolvido manualmente mediante um método heurístico, no qual se examinaram 510 diferentes possibilidades de combinações de alimentos, e cuja solução diferia somente alguns centavos da solução dada anos mais tarde pelo método Simplex.

Durante os anos 1941 e 1942, Kantorovich e Koopmans estudaram de forma independente o problema do transporte pela primeira vez, conhecendo-se estes tipos de problemas como os chamados "Problemas de Kantorovich-Koopmans". Para sua solução usaram métodos geométricos que estão relacionados com a teoria de convexidade de Minkowski.

Alguns especialistas consideram que Charles Babbage foi o pai da Pesquisa Operacional, devido a suas investigações sobre os custos de transporte e triagem do correio feitas para o Uniform Penny Post da Inglaterra em 1840.

No entanto, ninguém considera que nasceu uma nova ciência chamada Pesquisa Operacional até à II Guerra Mundial, durante a batalha da Grã-Bretanha. A Luftwaffe, a Força Aérea alemã estava submetendo o país a um assédio forte, devido à limitada capacidade aérea britânica em consequência da política de desarmamento, embora com experiência em combate. O governo britânico, buscando alguma forma para defender seu país, convocou cientistas de diversas disciplinas para resolver o problema e obter o máximo benefício dos radares recém-inventados que dispunham. Graças ao seu trabalho determinando a localização ideal das antenas e da melhor distribuição de sinal conseguiram dobrar a eficácia do sistema de defesa aérea e evitar que a ilha caísse nas mãos da Alemanha nazista.

Também em 1942, a U-Bootswaffe alemã com sua frota de submarinos U-boat começou um bloqueio à Grã-Bretanha atacando os comboios de navios com carregamentos de suprimentos dos Estados Unidos impedindo que chegassem ao seu destino. O Grupo de Pesquisa de Operações de Guerra Anti-Submarino dos EUA (ASWORG, Anti-Submarine Warfare Operations Research Group em inglês) realizou representações matemáticas destes comboios, tendo em conta uma série de restrições e condições impostas pela realidade, como a máxima velocidade dos navios, a quantidade de suprimentos a ser transportado e o combustível necessário para chegar ao seu destino. Eles aplicaram os modelos também sobre os U-boats: a dimensão da sua frota, o alcance dos submarinos, os seus torpedos, etc. Com base nestas informações eles foram capazes de modelar a guerra naval, e determinar se era melhor uma estratégia baseada em comboios compostos por um grande grupo de navios de carga escoltados por muitos contratorpedeiros, ou pelo contrario grupos pequenos e mais difíceis de localizar para o inimigo, e até mesmo como causar mais danos ao submarino U-Boot. Quando a Marinha dos Estados Unidos de América implementaram essas estratégias reduziu significativamente o número de navios afundados, enquanto aumentou a destruição de submarinos alemães (aumentaram os afundamentos desde cerca de 30 por ano para aproximadamente 250 por ano em 1943 e 1944).

Comboio de provisões com destino a Grã-Bretanha

Depois de avaliar a extensão dessa nova disciplina, a Inglaterra criou outros grupos da mesma natureza para obter melhores resultados na batalha. Da mesma forma os Estados Unidos ao se unir à guerra em 1942, começou a aplicar técnicas de Pesquisa Operacional militarmente, e alguns anos mais tarde, em 1947, formou um grupo de trabalho dedicado a melhorar o processo de planejamento em larga escala: o projeto SCOOP (Scientific Computation Of Optimum Programs). Neste grupo estava trabalhando George Bernard Dantzig, que em 1947 desenvolveu o algoritmo do método Simplex.

Durante a Guerra Fria, a ex-União Soviética (URSS) excluída do Plano Marshall, queria controlar as comunicações terrestres, incluindo as rotas fluviais, em Berlim. Para evitar a rendição da cidade e sua submissão como parte da Zona Comunista Alemã, Inglaterra e Estados Unidos decidiram abastecer a cidade, tanto por comboios escoltados (que poderia levar a novos confrontos) ou por transporte aéreo, quebrando ou fugindo em qualquer caso o bloqueio de Berlim. Esta segunda opção foi escolhida, iniciando a Luftbrücke (transporte aéreo) em 25 de junho de 1948. Este foi outro problema no qual o grupo participou SCOOP: em dezembro daquele ano foi atingido o volume de 4500 toneladas por dia de abastecimento, e após os estudos de Pesquisa Operacional foi otimizado chegando a 8000 ou 9000 toneladas por dia em março 1949. Esse número era o mesmo que poderia ser transportado por terra. Assim os soviéticos decidiram levantar o bloqueio em 12 de maio de 1949.

Depois da Segunda Guerra Mundial, considerou-se adequado fazer a organização dos recursos de EUA (energia, armas, e todos os tipos de suprimentos) por meio de modelos de otimização, resolvidos pela Programação Linear.

Além da teoria da Pesquisa Operacional concomitantemente foram também desenvolvidas as técnicas de computação, o que permitiu uma redução significativa no tempo de resolução dos problemas.

O primeiro resultado destas técnicas foi obtido em 1952, utilizando um computador SEAC do National Bureau of Standards para obter a solução de um problema. O êxito no tempo de resolução foi tão animador que imediatamente foi usado para todos os tipos de problemas militares, como a gestão dos fundos monetários para a logística e armamento, determinar a altura ideal em que as aeronaves devem voar para localizar submarinos inimigos e calcular a profundidade a que as cargas seriam enviadas para alcançar os submarinos de uma forma que causassem os maiores danos. Tudo isso resultou em um aumento de até cinco vezes na eficiência da força aérea.

Durante as décadas de 50 e 60, aumentou o interesse e desenvolvimento da Pesquisa Operacional incluindo a sua aplicação no domínio do comércio e indústria. Um exemplo disso é o problema de calcular o melhor plano de transporte de areia de construção para as obras de construção da cidade de Moscou, onde havia 10 pontos de origem e 230 pontos de destino. Para resolver o problema foi utilizado um computador Strena em Junho de 1958, e após 10 dias de cálculos retornou uma solução que proporcionou uma redução do 11% dos gastos com referência aos custos originais planejados.

Anteriormente, estes problemas eram abordados numa disciplina chamada Análise de Negócios ou Empresas, mas não tinham métodos tão eficazes quanto os desenvolvidos durante a Segunda Guerra Mundial (por exemplo, o método Simplex). As aplicações não militares da Pesquisa Operacional se estendeu para todas as áreas, com problemas que vão desde alimentação, agricultura, distribuição de campos de agricultura, transporte de mercadorias, localização, distribuição de pessoal, problemas de rede, filas, grafos, etc.

Como exemplo, você pode observar os seguintes casos reais de utilização da Pesquisa Operacional e os benefícios relatados.

Copyright ©2006-2017 PHPSimplex. Todos os direitos reservados. Termos e condições.
Siga-nos no Twitter
X

PHPSimplex
Versão 0.81

Copyright ©2006-2017. Todos os direitos reservados.

Desenvolvido por:
Daniel Izquierdo Granja
Juan José Ruiz Ruiz

Tradução para o Inglês por:
Luciano Miguel Tobaria

Tradução para o Francês por:
Ester Rute Ruiz

Tradução para o Português por:
Rosane Bujes