Algortmo do método Simplex

Algoritmo do Método Simplex

O algoritmo prevê TRÊS possibilidades bem definidas de término dos cálculos:

1) o conjunto de soluções viáveis é vazio;

2) o problema não tem solução ótima finita e;

3) uma solução ótima finita para o problema existe e é encontrada no último passo.

Graficamente pode-se representá-lo pelo esquema abaixo:

ALGORITMO SIMPLEX

DEFINIÇÕES INICIAIS
1º PASSO
FAZER O QUADRO BÁSICO.
PREENCHER TODAS AS CÉLULAS COM OS DADOS INICIAIS DO PROBLEMA.
A PRIMEIRA LINHA É A DA FO. AS SUBSEQUENTES SÃO DAS RESTRIÇÕES, EXCETO A RESTRIÇÃO DA NÃO-NEGATIVIDADE DAS VARIÁVEIS DE DECISÃO QUE NÃO É COLOCADA.

2º PASSO
DEFINIÇÃO DA COLUNA PIVOT (CP).
EXAMINE A LINHA DOS COEFICIENTES DA FUNÇÃO OBJETIVA.
O COEFICIENTE DE MENOR VALOR RELATIVO ENTRE OS ELEMENTO DAS VARIÁVEIS DE DECISÃO DEFINE A COLUNA PIVOT.

3º PASSO
DEFINIÇÃO DA LINHA PIVOT (LP).
PARA TODAS AS LINHAS, RELATIVAS ÀS RESTRIÇÕES, FAZER: VALOR DO BI / COEF DA COLUNA PIVOT CORRESPONDENTE.
ESCOLHER A LINHA QUE RESULTOU NO MENOR VALOR POSSÍVEL DA DIVISÃO FEITA.
CONSTRUÇÃO DA NOVA TABELA.

4º PASSO
NOVA CP.
NA CP, EXCETO O PIVOT QUE SERÁ IGUAL A “1”, ZERAR A COLUNA.

5º PASSO
NOVA LP.
NOVO VALOR DA CELULA NA LINHA PIVOT = VALOR DA CELULA DA TABELA ANTERIOR / VALOR DO PIVOT DA TABELA ANTERIOR.

6º PASSO
REPITA ENQUANTO HOUVER “0”. EXAMINE A COLUNA PIVOT ANTERIOR, SE VALOR DA CÉLULA = 0 ENTÃO REPETIR A LINHA CORRESPONDENTE AO “0” DA COLUNA, SENÃO FAÇA NADA.

7º PASSO
REPITA ENQUANTO HOUVER “0”. EXAMINE A LINHA PIVOT ANTERIOR, SE VALOR DA CÉLULA = 0 ENTÃO REPETIR A COLUNA CORRESPONDENTE AO “0” DA COLUNA, SENÃO FAÇA NADA.

8º PASSO
SE CELULA VAZIA, ENTÃO FAÇA: NOVO VALOR DA CELULA = VALOR DA CELULA DA TABELA ANTERIOR – (VIZINHO LÓGICO DA COLUNA PIVOT * VIZINHO LÓGICO DA LINHA PIVOT) / VALOR DO PIVOT DA TABELA ANTERIOR, ENQUANTO HOUVER CELULAS VAZIAS.

9º PASSO
EXAMINE A LINHA CORRESPONDENTE À DA FUNÇÃO OBJETIVA.
SE AINDA HOUVER COEFICIENTE AFETADO COM