| dc.description | Um problema de programação linear (PL) é um problema de otimização cuja função a ser
Minimizada ou maximizada e 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 [3] em 1947, ´e 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 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,
´e um esquema que ordena os cálculos evitando operações desnecessárias, de forma a minimizar
o tempo da computação. | |
