Teoria do método Simplex

O método Simplex é um processo iterativo que permite melhorar a solução da função objetivo em cada etapa. O processo finaliza quando não é possível continuar melhorando este valor, ou seja, quando se obtenha a solução ótima (o maior ou menor valor possível, segundo o caso, para que todas as restrições sejam satisfeitas).

Com base no valor da função objetivo, em um ponto qualquer, o procedimento consiste em procurar outro ponto que melhore o valor anterior. Como se pode ver no método Gráfico, tais pontos são os vértices do polígono (ou poliedro ou polícoro, se o número de variáveis é maior do que 2) e que faz parte da região determinada pelas restrições a que está sujeito o problema (chamada de região viável). A pesquisa é realizada por meio de deslocamentos pelas arestas do polígono, a partir do vértice atual até um adjacente que melhore o valor da função objetivo. Sempre que exista região viável, e como seu número de vértices e de arestas é finito, será possível encontrar a solução.

O método Simplex baseia-se na seguinte propriedade: se a função objetivo Z não toma seu valor máximo no vértice A, quer dizer que existe uma aresta que parte de A e ao longo da qual o valor de Z aumenta.

Será necessário considerar que o método Simplex trabalha apenas com restrições do problema cujas desigualdades sejam do tipo "≤" (menor ou igual) e seus coeficientes independentes sejam maiores ou iguais a 0. Portanto, é preciso padronizar as restrições para atender aos requisitos antes de iniciar o algoritmo Simplex. Caso apareçam, depois deste processo, restrições do tipo "≥" (maior ou igual) ou "=" (igualdade), ou não seja possível alterá-las, será necessário utilizar outros métodos de resolução, sendo o mais comum, o método das Duas Fases.