Método simplex para programação linear

Abstract

Um problema de programação linear (PL) é 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˜ao 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 [3] 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 número finito de pontos extremos isso nos garante que o algoritmo termina em algum ponto, que ser´a 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 desnecessárias, de forma a minimizar o tempo da computação.