O Método Simplex

Método Simplex

O método Simplex é um método sequencial de otimização e pode ser empregado, assim como o método uni variado, tanto para maximizar como minimizar uma resposta. Pode ser definido ainda como um método de resolução da programação linear que fornece soluções otimizadas para problemas complexos que têm muitas variáveis e restrições.

Problema:

Maximizar	Z = f(x,y) = 3x + 2y
Sujeita às restrições:	2x + y ≤ 18
	2x + 3y ≤ 42
	3x + y ≤ 24
	x ≥ 0 , y ≥ 0

 Realizar uma mudança de variáveis e normalizar o sinal dos termos independentes.

Realiza-se uma mudança na nomenclatura das variáveis. Estabelecendo a seguinte correspondência:

Normalizar as restrições.

As inequações são transformadas em equação adicionando variáveis de folga, de excesso e artificiais, conforme a tabela a seguir:

Neste caso, deve-se introduzir uma variável de folga (X3, X4 e X5) em cada uma das restrições do tipo ≤, para convertê-las em igualdades, resultando o sistema de equações lineares:

Escrever a tabela inicial do método Simplex.

A tabela inicial do método Simplex é composta por todos os coeficientes das variáveis de decisão do problema original e as de folga, excesso e artificiais adicionadas no passo 2, e as restrições. A coluna Cb contém os coeficientes das variáveis que estão na base.

A primeira linha é formada pelos coeficientes da função objetivo, enquanto que a última linha contém o valor da função objetivo e os custos reduzidos Zj - Cj.

A última linha é calculada da seguinte forma: Zj = Σ(Cbi·Pj) para i = 1..m, onde se j = 0, P0 = bi e C0 = 0, e caso contrário Pj = aij. Embora seja a primeira tabela do método Simplex e que todos os Cb sejam nulos, pode-se simplificar o cálculo, e assim termos Zj = -Cj.

Critério de parada.

Se o objetivo é maximizar, quando na última linha (linha indicadora) não exista nenhum valor negativo entre os custos reduzidos (colunas P1 em diante) a condição de parada é alcançada.

Neste caso, o algoritmo chega ao final, porque já não existe possibilidade de melhoria. O valor de Z (coluna P0) é a solução ótima do problema.

Outra possibilidade é que na coluna da variável de entrada à base, todos os valores são negativos ou nulos. Isto indica que o problema não se encontra delimitado e sua solução sempre poderá ser melhorada. Neste caso, não será necessário continuar realizando iterações indefinidas e pode-se finalizar o algoritmo.

Caso contrário, as seguintes etapas são executadas de forma iterativa.

Escolha da variável de entrada e saída da base.

Em primeiro lugar, determina-se a variável que entra na base. Para isto é escolhida a coluna em que o valor da linha Z seja o menor entre todos os negativos. Neste caso seria a variável X1 (P1) de coeficiente -3.

Se houver dois ou mais coeficientes iguais que satisfazem a condição anterior (caso de empate), então se optará pela variável que seja básica.

A coluna da variável que entra na base chama-se coluna pivô (na cor verde).

Depois de obter-se a variável que entra na base, determina-se qual será a variável que sairá da mesma. A decisão é baseada em um cálculo simples: dividir cada termo independente (coluna P0) entre o elemento correspondente da coluna pivô, desde que ambos elementos sejam estritamente positivos (maior que zero). É escolhida a linha cujo resultado é mínimo.

Se houver algum elemento menor ou igual a zero não se realiza tal cálculo. Caso todos os elementos da coluna pivô tenham esta condição, o critério de parada seria satisfeito e o problema teria uma solução não delimitada

Neste exemplo: 18/2 [=9] , 42/2 [=21] y 24/3 [=8]

O termo da coluna pivô que na divisão anterior deu lugar ao menor quociente positivo, indica a linha de variável de folga que sai da base. Neste caso, resulta ser X5 (P5), de coeficiente 3. Esta linha chama-se linha pivô (na cor verde).