Programação linear

PROGRAMAÇÃO LINEAR

Programação Linear é uma ferramenta de planejamento que nos ajuda a selecionar que atividades (variáveis de decisão) empreender, dado que essas atividades (diversas alternativas) competem entre si pela utilização de recursos escassos (restrições) ou então precisam satisfazer certos requisitos mínimos. O objetivo será maximizar (minimizar) uma função das atividades, geralmente lucros (perdas). A preocupação de otimizar problemas matemáticos descritos por equações ou inequações lineares não é recente; pode-se dizer que remonta aos gregos. Euclides, no século III A.C, no seu livro III dos elementos, registrou um processo primitivo de se encontrar a maior e a menor distância entre um ponto e uma circunferência pertencentes a um plano. Depois de Euclides, uma série de matemáticos, físicos e economistas, como Newton, Lagrange, Quesnay, Leontieff, Kantorovich, Dantzig, buscavam construir suas técnicas de otimização. Foi George Dantzig, porém, que em 1947 criou para a Força Aérea Americana, na Universidade de Stanford, a mais eficaz e simples técnica de minimização e maximização de sistemas de inequações lineares. Seus resultados foram publicados em 1950, no livro Linear Programming and Extensions.

INEQUAÇÕES LINEARES

A equação linear produz uma partição de em 3 subconjuntos: (i) os pontos que satisfazem a equação dada; (ii) os pontos que satisfazem a inequação ; (iii) os pontos que satisfazem a inequação .
O primeiro conjunto, dos pontos que satisfazem a equação, é uma reta; os outros dois conjuntos são denominados semi-planos.
Em particular, a solução da inequação linear ax + by c ( ou ax + by c) é denominada um semi-plano. Geometricamente falando, um semi-plano consiste nos pontos que estão sobre a reta delimitadora ax + by = c e nos pontos que estão de um dos lados da reta.

EX: Para construirmos o gráfico da inequação 2x – 3y -6, primeiro representamos graficamente a reta 2x – 3y = -6. Depois tomamos um ponto