Teoria

 Teoria da Programação Linear

Geometricamente, as restrições lineares definem um poliedro convexo, que é chamado de conjunto dos pontos viáveis. Uma vez que a função objetivo é também linear, todo ótimo local é automaticamente um ótimo global. 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 x₁ + 3 x₂ sujeito a x₁ ≥ 0, x₂ ≥ 0, x₁ + x₂ ≥ 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.