Método Simplex

Método simplex passo a passo

O que é o método Simplex?

O método Simplex é um algoritmo que permite resolver problemas de Programação Linear.

A ideia básica do método Simplex consiste em resolver repetidas vezes um sistema de equações lineares para obter uma sucessão de SB (soluções básicas), cada uma "melhor" do que a anterior, até se chegar a uma SB ótima.

Em teoria de otimização matemática, o algoritmo simplex é 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 é método simplex de que consiste em um método numérico para otimização de problemas livres multidimensionais, pertencentes à classe mais geral de algoritmos de busca. O método usa o conceito de um simplex, que é um polígono de N + 1 vértices em N dimensões: um segmento de linha sobre uma linha, um triângulo sobre um plano, um tetraedro em um espaço de três dimensões e assim sucessivamente. 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:

6) Dividir os elementos da última coluna pelos correspondentes elementos positivos da coluna da variável que vai entrar na base. Caso nãohaja elemento nenhum positivo nesta coluna, o processo deve parar, já que a solução seria ilimitada.

7) O menor quociente indica a equação cuja respectiva variável básica deverá ser anulada, tornando-se variável não básica.

8) 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.

Retornar ao passo 4 para iniciar outra iteração.