Os Métodos Quantitativos

A programação linear (LP) é um método para obter o melhor resultado (como lucro máximo ou custo mais baixo) em um modelo matemático cujos requisitos são representados por relacionamentos lineares. Seu objetivo é fornecer ferramentas para resolver problemas de otimização nos quais uma função objetivo linear está sujeita a restrições (igualdades/desigualdades) também lineares, encontrando o maior ou o menor valor possível dessa função. Se todas as variáveis do problema pertencerem ao conjunto dos números inteiros, temos uma subclasse chamada Programação Inteira.

A PL apresenta os seguintes elementos fundamentais: variáveis de decisão, cujos valores assumidos determinam o resultado da função objetivo; função objetivo, uma equação que representa a combinação linear entre as variáveis de decisão e os coeficientes unitários da função matemática (que costumam representar o custo ou lucro unitário); restrições, equações ou inequações lineares que associam as variáveis de decisão com os coeficientes unitários.

As restrições lineares definem um poliedro convexo. Sua função objetivo é uma função afim (linear) de valor real definida nesse poliedro. Um algoritmo de programação linear encontra um ponto no poliedro onde essa função tem o menor ou maior valor, caso esse ponto exista.

Existem duas situações nas quais uma solução ótima não pode ser encontrada: se as restrições se contradizem, pois nesse caso a região factível é vazia e não pode haver solução nenhuma - o PL é dito inviável; se o poliedro for ilimitado na direção da função objetivo, pois nesse caso soluções arbitrariamente grandes da função objetivo podem ser construídas e não existe solução ótima - o PL é dito ilimitado.

Fora estas duas condições, o ótimo é sempre alcançado. Entretanto, nem sempre ele é único: é possível ter um conjunto de soluções ótimas cobrindo uma aresta ou face do poliedro, ou até mesmo o poliedro inteiro (caso a função seja uniformemente igual a uma constante).

O algoritmo simplex constrói uma solução admissível nos vértices do poliedro, caminhando por eles, a partir de um vértice busca outro vizinho que melhore a função sucessivamente até não existir mais vértice vizinho que a melhore. Embora este algoritmo seja bastante eficiente e garanta encontrar um ótimo global (assumidas certas condições para se evitar ciclos), ele é fraco no pior caso: é possível construir um problema de programação linear prático para o qual o método simplex realiza uma quantidade exponencial de passos em relação ao tamanho do problema.

A programação linear pode ser aplicada a várias áreas. É amplamente utilizada em matemática e, em menor grau, em negócios, economia e alguns problemas de engenharia. As indústrias que usam modelos de programação linear incluem transporte, energia, telecomunicações e manufatura. Ela tem se mostrado útil na modelagem de diversos tipos de problemas em planejamento, roteamento, programação, atribuição e design.

O problema de resolver um sistema de desigualdades lineares remonta pelo menos até Fourier, que publicou um método para resolvê-las em 1827 e deu origem ao nome do método de eliminação de Fourier-Motzkin.

Em 1939, o economista soviético Leonid Kantorovich formulou uma programação linear para um problema equivalente ao problema de programação linear geral, e também propôs um método para resolvê-lo. Esse método foi desenvolvido, durante a Segunda Guerra Mundial, para planejar gastos e retornos, a fim de reduzir os custos do exército e aumentar as perdas impostas ao inimigo. Na mesma época, o economista holandês-americano T. C. Koopmans formulou programações lineares para problemas econômicos clássicos (Kantorovich e Koopmans dividiram o prêmio Nobel de economia 1975). Em 1941, Frank Lauren Hitchcock também formulou programações lineares para problemas de transporte e deu uma solução muito semelhante à do posterior método simplex.

Em 1946, Dantzig era consultor para a Força Aérea no Pentágono e desenvolveu uma formulação geral de programação linear a ser usada no planejamento de problemas militares. Ele recebeu dos seus colegas D. Hitchcock e M. Wood o desafio de mecanizar o processo de planejamento e no verão de 1947 propôs um algoritmo, o método simplex, que pela primeira vez abordou de forma eficiente o problema de programação linear na maioria dos casos, tornando possível a solução de problemas de otimização de vários tipos, como transporte, produção, alocação de recursos e problemas de escalonamento. O desenvolvimento dos computadores permitiu a aplicação do método simplex a problemas de grande porte (atualmente, a diversidade de variáveis e a quantidade de cálculos envolvidos torna o uso do computador indispensável na maior parte dos problemas de PL), ao mesmo tempo que revelou alguns dos problemas numéricos que podiam ocorrer em cálculos feitos por um computador.

O exemplo original de Dantzig foi encontrar a melhor distribuição de 70 pessoas para 70 empregos. A capacidade de computação necessária para testar todas as permutações para selecionar a melhor é vasta, dado que o número de configurações possíveis excede o número de partículas no universo observável. No entanto, leva apenas um momento para encontrar a solução ideal ao formular o problema como um programa linear e aplicar o algoritmo simplex. A teoria por trás da programação linear reduz o número de possíveis soluções que devem ser verificadas.