Introdução à Pesquisa Operacional/Algoritmo Simplex

O algoritmo simplex desenvolvido por George Dantzig é uma técnica popular para dar soluções numéricas de problemas da programação linear. Um método sem relação, mas chamado de maneira similar é o método Nelder-Mead ou método simplex de baixo custo devido a Nelder e Mead (1965) e é um método numérico para otimização de problemas livres multidimensionais, pertencentes à classe mais geral de algoritmos de busca.

Em ambos os casos, o método usa o conceito de um simplex, que é um polítopo de N + 1 vértices em N dimensões: um segmento de reta sobre uma linha, um triângulo sobre um plano, um tetraedro em um espaço de três dimensões e assim sucessivamente.

Procedimentos

Estes procedimentos são válidos para problemas de maximização:

1. Introduzir as variáveis de folga, uma para cada desigualdade;
2. Montar um quadro para os cálculos, colocando os coeficientes de todas as variáveis com os respectivos sinais e, na última linha, incluir os coeficientes da função objetivo transformada;
3. Estabelecer uma solução básica inicial, usualmente atribuindo valor zero às variáveis originais e achando valores positivos para as variáveis de folga;
4. Como próxima variável a entrar na base, escolher a variável não básica que oferece, na última linha, a maior contribuição para o aumento da função objetivo (ou seja, tem o maior valor negativo). Se todas as variáveis que estão fora da base tiverem coeficientes nulos ou positivos nesta linha, a solução atual é ótima. Se alguma dessas variáveis tiver coeficiente nulo, isto significa que ela pode ser introduzida na base sem aumentar o valor da função objetivo. Isso quer dizer que temos uma solução ótima, com o mesmo valor da função objetivo.
5. Para escolher a variável que deve deixar a base, deve-se realizar o seguinte procedimento:
   1. Dividir os elementos da última coluna pelos correspondentes elementos positivos da coluna da variável que vai entrar na base. Caso não haja elemento nenhum positivo nesta coluna, o processo deve parar, já que a solução seria ilimitada.
   2. O menor quociente indica a equação cuja respectiva variável básica deverá ser anulada, tornando-se variável não básica.
6. Usando operações válidas com as linhas da matriz, transformar o quadro de cálculos de forma a encontrar a nova solução básica. A coluna da nova variável básica deverá se tornar um vetor identidade, onde o elemento 1 aparece na linha correspondente à variável que está sendo anulada.
7. Retornar ao passo 4 para iniciar outra iteração.