Um problema de programação linear é um problema de otimização cuja função a ser minimizada ou maximizada é linear bem como o seu conjunto de restrições (relações de interdependência entre as variáveis). As técnicas de resolução de problemas de PL são amplamente utilizadas principalmente na Física, Engenharia e Economia. É possível mostrar que se o conjunto das soluções viáveis de um problema de PL, ou seja, o conjunto de soluções em que as variáveis assumem valores positivos e satisfazem todas as restrições, for não vazio e a função objetivo for limitada inferiormente neste conjunto, ele será um conjunto convexo e fechado. Esse conjunto possuirá um número finito de pontos extremos e a solução ótima do problema corresponderá a um ponto extremo deste conjunto. Desse modo, o método simplex, proposto por Georges Dantzig em 1947, é um procedimento matricial que percorre esses pontos extremos em busca da solução ótima. O algoritmo utiliza um critério de busca de forma que a solução seguinte seja sempre “melhor” do que a anterior. Como o conjunto possui um numero finito de pontos extremos isso nos garante que o algoritmo termina em algum ponto, que sera a solução ótima do problema. Existem “versões melhoradas” desse método que obtêm uma solução em menos tempo computacional. O método simplex revisado, por exemplo, é um esquema que ordena os cálculos evitando operações desnecessarias, de forma a minimizar ´ o tempo da computação.
Metodo Simplex
Simplex é um algoritmo criado por George Dantzig que viabiliza a solução de muitos problemas da programação linear. Bastante popular, encontra boa aceitação em áreas onde diversas necessidades e restrições influenciam em um valor que precisa ser aumentado ou diminuído ao máximo.
Metodo Dual
Uma dos conceitos mais importantes em programação linear é o de dualidade. Qualquer problema de PL tem associado um outro problema de PL, chamado o Dual. Neste contexto, o problema original denomina-se por Primal. Um dos principais papéis da teoria da dualidade é a interpretação e implementação da análise de sensibilidade, que é uma parte muito importante de um estudo de PL.