Origim

A Programação Linear (P.L.) surgiu com a necessidade de resolver problemas relacionados à

alocação eficiente de recursos em organizações complexas, que cresciam com a Revolução
Industrial. A Investigação Operacional (I.O.) foi criada para lidar com esses problemas, usando
métodos científicos para a gestão organizacional, com uma abordagem quantitativa e qualitativa
na tomada de decisões. A I.O. analisa sistemas interrelacionados e busca soluções que atendam a
organização como um todo.

A P.M. (Programação Matemática) é um dos ramos da I.O., e se divide em várias áreas,

incluindo a Programação Linear, que trata de problemas onde tanto as condições quanto o
objetivo podem ser descritos por relações lineares, como equações e inequações. A Programação
Linear é uma subclasse de problemas de Programação Matemática, onde as restrições e o
objetivo podem ser expressos de forma linear, sendo a P.L. fundamental para resolver questões
práticas em diversas áreas, como negócios, economia e indústria.
INTRODUÇÃO
A programação linear é um campo da programação matemática que surgiu com a finalidade de
otimizar funções lineares sujeitas a restrições lineares, com amplas aplicações práticas. Sua
origem remonta aos estudos de Fourier sobre sistemas lineares de inequações em 1826, mas
ganhou destaque em 1939 com Kantorovich, que formulou um algoritmo para sua solução,
aplicando-o em problemas de distribuição de carga e fluxos em redes. No entanto, seu trabalho
só foi amplamente reconhecido após 1950.
Na década de 1940, George Dantzig, ao desenvolver o Algoritmo Simplex, e George Stigler, ao
aplicar a programação linear na formulação de dietas, consolidaram a programação linear como
uma ferramenta poderosa. Dantzig também formulou o problema de transporte, que foi abordado
tanto por Hitchcock quanto por Koopmans. Em 1956, Alex Orden generalizou o modelo de
transporte, permitindo pontos de transbordo de carga, enquanto outros problemas como fluxos
máximos e fluxo de custo mínimo em rede foram formulados por Lester Ford e Delbert
Fulkerson.
Entre 1950 e 1965, houve um intenso desenvolvimento de algoritmos para problemas de
programação linear em rede, com destaque para as especializações do método Simplex e o
método Primal-Dual. Em 1975, Kantorovich e Koopmans receberam o Prêmio Nobel de
Economia pelas suas contribuições à alocação de recursos, enquanto Dantzig, apesar de sua
importância, não foi reconhecido com o prêmio.
Em resumo, a programação linear evoluiu com contribuições significativas de vários
pesquisadores e desempenha um papel central em várias áreas, como otimização de recursos,
planejamento e análise econômica.
Aplicação da programação linear
Uma vez que os problemas de P.L. determinam o planeamento óptimo de actividades, ou seja,
um plano óptimo que representa a melhor solução entre todas as soluções possíveis, as suas
principais áreas de aplicação são:
- Económica e especialmente Economia de Empresas, onde se situam as aplicações mais
férteis e os estímulos mais fortes para os desenvolvimentos teóricos da P.L.;
- Matemática, onde a P.L. tem impulsionado a obtenção de importantes resultados teóricos
e o aperfeiçoamento das técnicas de Análise Numérica;
 - Militar, onde as aplicações são numerosas mas normalmente pouco divulgadas por razões
de segurança.
Problemas de programação linear
A programação linear é usada pra optimizar um objectivo, sujeito a um conjunto de restrições.
Aqui podemos dividir os problemas de programação linear em três tipos:
1) Problemas de transporte
Os problemas de transporte em programação linear envolvem encontrar a forma mais
eficiente de transportar bens de vários fornecedores para vários consumidores,
minimizando custos e atendendo às restrições de oferta e demanda.
2) Problemas de composição
Os problemas de composição em programação linear envolvem a combinação de
diferentes componentes ou matérias-primas para formar produtos finais, de modo a
otimizar um determinado objetivo (como minimizar custos ou maximizar lucros).
3) Problemas de Formação e Produção
Os problemas de formação e produção em programação linear envolvem a alocação
eficiente de recursos para fabricar produtos, maximizando lucros ou minimizando custos,
enquanto se respeitam restrições de capacidade, demanda e insumos.
CONCEITOS FUNDAMENTAIS DA PROGRAMAÇÃO
LINEAR
Para uma melhor compreensão de um problema de programação linear enunciamos de seguida
alguns conceitos e expressões que vão ser usados ao longo do trabalho:
 Função objectivo (função económica ou função critério) – é uma função linear que
vamos optimizar, maximizando ou minimizando;
 Variáveis de decisão – são os valores de um número n de decisões a serem tomadas e
designam-se por x1, ..., xn e que estão interrelacionadas pela função objectivo;
 Variáveis de folga – são as variáveis que usamos para transformar as inequações em
equações; de salientar que cada variável de folga está associada a uma restrição;
 Restrições – são condições (representadas por equações ou inequações lineares) que se
impõem ao modelo dado; existem dois tipos de restrições:
 Restrições do problema – são restrições do tipo ≤ , = ou ≥ , que relacionam uma ou mais
variáveis do problema;
 Restrições de não negatividade – são desigualdades do tipo x1 ≥ 0, ..., xn ≥ 0, em que
x1, ..., xn são as variáveis de decisão;
 Forma padrão (standard) – quando as restrições de um problema de P.L. são
apresentadas na forma de equações;
 Forma canónica – quando as restrições de um problema de P.L. são apresentadas na
forma de inequações;
 Solução – é qualquer conjunto de valores para as variáveis x1, ..., xn que satisfaça as
restrições;
 Solução admissível (solução possível) – é qualquer especificação de valores para as
variáveis x1, ..., xn que satisfaça as restrições do problema e as condições de não
negatividade;
  Solução ilimitada (unbounded) – é aquela em que a função objectivo pode crescer (no
caso da maximização) ou decrescer (no caso da minimização), indefinidamente, tendo em
conta todas as restrições do problema;
 Solução óptima – é aquela que maximiza ou minimiza a função objectivo sobre toda a
região admissível;
 Região admissível – é o conjunto de todas as soluções admissíveis.
Modelagem com Programação Linear
Propriedades de modelo PL
Objectivo e as restrições são todos funções lineares. Linearidade implica que PL deve satisfazer
três propriedades básicas:
1) Proporcionalidade: essa propriedade requer que a contribuição de cada variável de
decisão, tanto na função objetivo quanto nas restrições, seja diretamente proporcional ao
valor da variável. Por exemplo, no modelo Reddy Mikks, as quantidades 5x1 e 4x2, dão
os lucros para a produção de x1e x2, toneladas de tinta para exteriores e interiores,
respectivamente, sendo que os lucros unitários por tonelada, 5 e 4, darão as constantes de
proporcionalidade. Por outro lado, se a Reddy Mikks conceder algum tipo de desconto
por quan-tidade quando as vendas ultrapassarem certas quantidades, o lucro não será
mais proporcional às quantidades de produção, x, ex, e a função lucro se torna não linear

2) Aditividade: essa propriedade requer que a contribuição total de todas as variáveis da

função objetivo e das restrições seja a soma direta das contribuições individuais de cada
variável. No modelo da Reddy Mikks, o lucro total é igual à soma dos dois componentes
individuais do lucro. Contudo, se os dois produtos competirem por participação de
mercado de modo tal que um aumento nas vendas de um deles provoque um efeito
adverso nas vendas do outro, então a propriedade de aditividade não é satisfeita e o
modelo deixa de ser linear.

3) Certeza: todos os coeficientes da função objetivo e das restri-ções do modelo de PL são

determinísticos, o que significa que são constantes conhecidas uma ocorrência rara na
vida real, na qual o mais provável é que os dados sejam representados por distribui-ções
de probabilidade. Em essência, os coeficientes em PL são apro-ximações do valor médio
das distribuições de probabilidade. Se os desvios-padrão dessas distribuições forem
suficientemente peque-nos, a aproximação será aceitável. Grandes desvios-padrão podem
ser levados em conta diretamente com a utilização de algoritmos estocásticos de PL ou
indiretamente pela aplicação de análise de sensibilidade à solução ótima.