Introdução à Pesquisa Operacional (4ª parte)

Introdução à Pesquisa Operacional (4ª parte)

(Parte 1 de 2)

MÉTODO SIMPLEXMÉTODO SIMPLEX Módulo4Módulo 4

Prof. Ms. Antonio dos Santos

Método Simplex :

Seja o Problema de PL:Seja o Problema de PL:

Método Simplex :

Passo 1: Colocar o problema na forma padrão

Método Simplex

Passo 2: Montar o tableau Simplex

Z 600 X1 800 X2 X1 X2 X3 X4 X5 X6 B

Z = 600 X1 + 800 X2 Z –600 X1 –800 X2 = 0

Método Simplex

Passo 3: Escolher a variável que deve entrar na base

Pb l d i i ã X1 X2 X3 X4 X5 X6 B

Para um problema de maximização deve ser a variável com coeficiente negativo de maior valor absoluto. No exemplo é“ 800 ”

No exemplo é –800 Portanto “X2” deve entrar na base

Método Simplex

Passo 4: Escolher a variável que deve sair da base e determinar o “Pivô”

ÁDeterminar o “pivô” que deve ser

X1 X2 X3 X4 X5 X6 B o menor resultado da relação

“Bi / aij ”

Linha X3100/1 <= 100
Linha X4240/2 <= 120
Linha X560/0 = Infactível
Linha X680/1 <= 80

Portanto X6deve sair da base por ser a condição mais restritiva Piô1Pivô = 1

Método Simplex

Passo 5: Multiplicar ou dividir a linha do pivô por um número de forma que o valor do pivô fique = a 1

X1 X2 X3 X4 X5 X6 B portanto a linha fica como está.

Método Simplex

Passo 6: Colocar a linha do pivô no novo tableau.

X1 X2 X3 X4 X5 X6 B

X4 X5

Método Simplex

Passo 7: No novo tableau calcular as demais linhas de forma que os valores da coluna X2 fique = 0.

X1 X2 X3 X4 X5 X6 B

ƒPara tanto verifique o valor de

X2 na linha em análise.

Multiplique a linha do pivô pelo negativo do valor encontrado.

X4 Some a nova linha do pivô aos valores da linha em análise e coloque oresultado no novo X5 coloque o resultado no novo quadro.

Método Simplex

X1 X2 X3 X4 X5 X6 BX1 X2 X3 X4 X5 X6 B

Método Simplex

Passo 8: Escolher a nova variável que deve entrar na base

Pb l d i i ã X1 X2 X3 X4 X5 X6 BX1 X2 X3 X4 X5 X6 B Para um problema de maximização deve ser a variável com coeficiente negativo de maior valor absoluto.

Método Simplex

Passo 9: Escolher a nova variável que deve sair da base e determinar o “Pivô” Determinar o “pivô” que deve ser o menor resultado da relação

“Bi / aij ”

X1 X2 X3 X4 X5 X6 B

Linha X320/1 <= 20
Linha X480/3 <= 26,67
Linha X560/1 <= 60

Portanto X3deve sair da base por ser a condição mais restritiva Pi ô 1

Método Simplex

Passo 10: Multiplicar ou dividir a linha do pivô por um número de forma que o valor do pivô fique = a 1

X1 X2 X3 X4 X5 X6 B

Neste caso o valor do pivô já é 1

Método Simplex

Passo 1: Colocar a linha do pivô no novo tableau.

(Parte 1 de 2)

Comentários