MAJOTA: PESQUISA OPERACIONAL

MÉTODO SIMPLEX

Ø O método simplex é um algoritmo criado para se obter a solução algebricamente.

Ø Um algoritmo é um processo onde um procedimento sistemático é repetido (iterado) seguidamente até que o resultado desejado seja obtido.

Ø Cada percurso do procedimento sistemático é chamado de iteração.

Ø Conseqüentemente, um algoritmo substitui um problema difícil por uma série de outros fáceis.

Ø Além das iterações, os algoritmos também incluem um procedimento de dar início e um critério para determinar quando parar.

Ø Seqüência finita de passos que se seguidas levam ao objetivo procurado.

Ø É necessário conhecer o método para se interpretar melhor os resultados.

Ø Utiliza-se o exemplo que foi resolvido graficamente para se acompanhar os passos.

Ø Se o conjunto de possibilidades fosse formado por igualdades seria mais fácil resolver o sistema que o forma.

Ø Pode-se acrescentar uma variável não negativas (para ficarem na forma padrão) a cada restrição do modelo padrão de tal forma que as desigualdades sejam sempre atingidas.

Ø Estas variáveis são chamadas de variáveis de folga.

Ø As variáveis devem ser controladas, ou seja, são escolhidas pelo decisor de tal forma a atingir a igualdade nas restrições.

Ø As variáveis de folga aumentam os graus de liberdade do sistema (infinitas soluções).

Ø O poder que se tem sobre as variáveis deve ser usado para atingir o objetivo procurado.

Procedimento do Método Simplex (problemas de maximização)

1º passo – Introduzir as variáveis de folga; uma para cada desigualdade.

2º passo – Montar um quadro para os cálculos, colocando os coeficientes de todas as variáveis com seus respectivos sinais e, na última linha, incluir os coeficientes da função objetivo transformada.

3º passo – 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º passo – Como próxima variável a entrar na base, escolher a variável não-básica que fornece, 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 estão fora da base tiverem coeficientes nulos ou positivos nessa 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 outra solução ótima, com o mesmo valor da função objetivo.

5º passo – Para escolher a variável que deve deixar a base, deve-se realizar o seguinte procedimento:

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 algum positivo nessa coluna, o processo deve parar, já que a solução seria ilimitada.

b 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º passo – Empregando operações válidas com as linhas da matriz, transformar o quadro de cálculos de modo a encontrar a nova solução básica. A coluna da nova variável básica deverá se tornar um vetor identidade, no qual o elemento 1 aparece na linha correspondente à variável que está sendo anulada.

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

EXEMPLOS