Em matemática, problemas de Programação Linear (PL) são problemas de otimização nos quais a função objetivo e as restrições são todas lineares.

Programação Linear é uma importante área da otimização por várias razões. Muitos problemas práticos em pesquisa operacional podem ser expressos como problemas de programação linear. Certos casos especiais de programação linear, tais como problemas de network flow e problemas de multicommodity flow são considerados importantes o suficiente para que se tenha gerado muita pesquisa em algoritmos especializados para suas soluções. Vários algoritmos para outros tipos de problemas de otimização funcionam resolvendo problemas de PL como sub-problemas. Historicamente, ideias da programação linear inspiraram muitos dos conceitos centrais de teoria da otimização, tais como dualidade, decomposição, e a importância da convexidade e suas generalizações.

Aqui está um exemplo de problema de programação linear. Suponha que um fazendeiro tem um pedaço de terra de digamos, A km2, para ser semeado com trigo ou cevada ou uma combinação de ambas. O fazendeiro tem uma quantidade limitada de fertilizante F permitido e de inseticida P permitido que podem ser usados, cada um deles sendo necessários em quantidades diferentes por unidade de área para o trigo (F1, P1) e para a cevada (F2, P2). Seja S1 o preço de venda do trigo, e S2 o da cevada. Se chamarmos a área plantada com trigo e cevada de x1 e x2 respectivamente, então o número ideal de km2 de plantação com trigo vs. cevada pode ser expresso como um problema de programação linear:

maximize S1x1 + S2x2 (maximize o lucro - esta é a "função objetivo")

sujeito a x_1 + x_2 \le A (limite da área total)

F_1 x_1 + F_2 x_2 \le F (limite do fertilizante)

P_1 x_1 + P_2 x_2 \le P (limite do insecticida)

x_1 \ge 0,\, x_2 \ge 0 (não se pode semear uma área negativa)

Geometricamente, as restrições lineares definem um poliedro convexo, que é chamado de conjunto dos pontos viáveis. Uma vez que a função objectivo é também linear, todo óptimo local é automaticamente um ótimo global. A função objetivo ser linear também implica que uma solução ótima pode apenas ocorrer em um ponto da fronteira do conjunto de pontos viáveis.

Existem duas situações nas quais uma solução ótima não pode ser encontrada. Primeiro, se as restrições se contradizem (por exemplo, x ≥ 2 e x ≤ 1) logo, a região factível é vazia e não pode haver solução ótima, já que não pode haver solução nenhuma. Neste caso, o PL é dito inviável.

Alternativamente, o poliedro pode ser ilimitado na direção da função objetivo (por exemplo: maximizar x1 + 3 x2 sujeito a x1 ≥ 0, x2 ≥ 0, x1 + x2 ≥ 10), neste caso não existe solução ótima uma vez que soluções arbitrariamente grandes da função objetivo podem ser construídas, e o problema é dito ilimitado.

Fora estas duas condições patológicas (que são frequentemente eliminadas por limitações dos recursos inerentes ao problema que está sendo modelado, como acima), o óptimo é sempre alcançado num vértice do poliedro. Entretanto, o ótimo nem sempre é único: é possível ter um conjunto de soluções ótimas cobrindo uma aresta ou face do poliedro, ou até mesmo o poliedro todo (Esta última situação pode ocorrer se a função objetivo for uniformemente igual a zero).

Extraido de Wikipedia-pt