Campus - Mossoró Profª Adricia Fonseca Mendes

Algoritmo Simplex

Já vimos que a solução ótima de um PPL é um ponto extremo (solução básica viável).

Em grandes problemas o número de pontos extremos pode ser muito grande.

Como evitar o teste de todas as soluções viáveis básicas possíveis para garantir a otimização do sistema?

Notas de aula Professor: Rodrigo A. Scarpel

Início: Forma Padrão

Encontrar uma solução SBF* inicial

A solução é ótima?

Variável que entra

Variável que sai

Utilizar o método Gauss-Jordan e recalcular a solução básica

Fim Sim

Não

*Solução Básica Factível

Fim ø

Sujeito a:

Início: Forma Padrão

Encontrar uma solução SBF* inicial

A solução é ótima?

Variável que entra

Variável que sai

Utilizar o método Gauss-Jordan e recalcular a solução básica

Fim Sim

Não

*Solução Básica Factível

Fim ø

Max z = 3x1+ 2x2 (0)

x1 + x2 + x3= 6 (1)
5x1+ 2x2+ x4 = 20 (2)
x1, x2 , x3 , x4 ≥ 0(3)

Sujeito a: 6

Tableau Simplex

Na forma tabular, a função de maximização passa a ser escrita como:

Variável básica

Nº da equação

Valor Coeficientes

Variável básica

Nº da equação

Valor Coeficientes

•Neste problema, temos m = 2 restrições e n = 4 variáveis.

•Para termos uma solução básica viável, é preciso pelo menos n – m = 2 variáveis nulas e que todas as variáveis tenham valores nãonegativos.

Início: Forma Padrão

Encontrar uma solução SBF* inicial

A solução é ótima?

Variável que entra

Variável que sai

Utilizar o método Gauss-Jordan e recalcular a solução básica

Fim Sim

Não

*Solução Básica Factível

Fim ø

Teste de otimalidade:

Como os coeficientes de x1 e x2 são negativos na linha 0, a SBF atual não é ótima, pois um incremento positivo em x1 e x2 resultará em SBF adjacente melhor do que a SBF atual.

Início: Forma Padrão

Encontrar uma solução SBF* inicial

A solução é ótima?

Variável que entra

Variável que sai

Utilizar o método Gauss-Jordan e recalcular a solução básica

Fim Sim

Não

*Solução Básica Factível

Fim ø

Variável básica

Nº da equação

Valor Coeficientes

•Escolhe-se a variável não básica com maior coeficiente negativo

0. Portanto, a variável x1 é selecionada para entrar na base, e a coluna dessa variável é a coluna pivô.

Variável básica

Nº da equação

Coeficientes Valor

Entra

Início: Forma Padrão

Encontrar uma solução SBF* inicial

A solução é ótima?

Variável que entra

Variável que sai

Utilizar o método Gauss-Jordan e recalcular a solução básica

Fim Sim

Não

*Solução Básica Factível

Fim ø

Variável básica

Nº da equação

Coeficientes Valor

•De quanto podemos aumentar o valor de x1 ?

Podemos aumentar seu valor contanto que as outras variáveis permaneçam não-negativas.

•Escolhe-se a variável que limita mais o crescimento de x1, ou seja, a linha com menor quociente.

Variável básica

Nº da equação

Coeficientes Valor

Entra

Sai

Entra

Sai

Variável básica

Nº da equação

Coeficientes Valor

Pivô

Início: Forma Padrão

Encontrar uma solução SBF* inicial

A solução é ótima?

Variável que entra

Variável que sai

Utilizar o método Gauss-Jordan e recalcular a solução básica

Fim Sim

Não

*Solução Básica Factível

Fim ø

• Nova linha pivô

Variável básica

Nº da equação

Coeficientes Valor

Variável básica

Nº da equação

Coeficientes Valor

• Nova linha da equação 1

• Nova linha da equação 0

Variável básica

Nº da equação

Coeficientes Valor

• Nova forma tabular após o método de eliminação Gauss-Jordan (Iteração 1)

Variável básica

Nº da equação

Coeficientes Valor

Início: Forma Padrão

Encontrar uma solução SBF* inicial

A solução é ótima?

Variável que entra

Variável que sai

Utilizar o método Gauss-Jordan e recalcular a solução básica

Fim Sim

Não

*Solução Básica Factível

Fim ø

• A solução é ótima?

Não, pois o coeficiente de x2 na equação 0 é negativo.

Qualquer incremento positivo em x2 resultará em um incremento positivo no valor da função objetivo.

Variável básica

Nº da equação

Coeficientes Valor

Início: Forma Padrão

Encontrar uma solução SBF* inicial

A solução é ótima?

Variável que entra

Variável que sai

Utilizar o método Gauss-Jordan e recalcular a solução básica

Fim Sim

Não

*Solução Básica Factível

Fim ø

Entra

Sai

Variável básica

Nº da equação

Coeficientes Valor

Entra

Sai Pivô

Variável básica

Nº da equação

Coeficientes Valor

Início: Forma Padrão

Encontrar uma solução SBF* inicial

A solução é ótima?

Variável que entra

Variável que sai

Utilizar o método Gauss-Jordan e recalcular a solução básica

Fim Sim

Não

*Solução Básica Factível

Fim ø

• Nova linha pivô

Variável básica

Nº da equação

Coeficientes Valor

• Nova linha da equação 2

Variável básica

Nº da equação

Coeficientes Valor

• Nova linha da equação 0

Variável básica

Nº da equação

Coeficientes Valor

• Nova forma tabular após o método de eliminação Gauss-Jordan (Iteração 2)

Variável básica

Nº da equação

Coeficientes Valor

Início: Forma Padrão

Encontrar uma solução SBF* inicial

A solução é ótima?

Variável que entra

Variável que sai

Utilizar o método Gauss-Jordan e recalcular a solução básica

Fim Sim

Não

*Solução Básica Factível

Fim ø

• A solução é ótima?

Sim, pois os coeficientes das variáveis não básicas x3 e x4 na equação 0 são positivos.

Variável básica

Nº da equação

Coeficientes Valor

Início: Forma Padrão

Encontrar uma solução SBF* inicial

A solução é ótima?

Variável que entra

Variável que sai

Utilizar o método Gauss-Jordan e recalcular a solução básica

Fim Sim

Não

*Solução Básica Factível

Fim ø

PROBLEMA DE MIX DE PRODUÇÃO Notas de aula Professor: Rodrigo A. Scarpel

37 Notas de aula Professor: Rodrigo A. Scarpel

38 Notas de aula Professor: Rodrigo A. Scarpel

39 Notas de aula Professor: Rodrigo A. Scarpel

40 Notas de aula Professor: Rodrigo A. Scarpel

Sujeito a:

Início: Forma Padrão

Encontrar uma solução SBF* inicial

A solução é ótima?

Variável que entra

Variável que sai

Utilizar o método Gauss-Jordan e recalcular a solução básica

Fim Sim

Não

*Solução Básica Factível

Fim ø

Max z = 4x1- 2x2 (0)

2x1 + x2 + x3= 10 (1)
x1 - x2+ x4 = 8 (2)
x1, x2 , x3 , x4 ≥ 0(3)

Sujeito a: 43

Tableau Simplex

Na forma tabular, a função de minimização passa a ser escrita como:

Variável básica

Nº da equação

Coeficientes Valor

•Neste problema, temos m = 2 restrições e n = 4 variáveis.

•Para termos uma solução básica viável, é preciso pelo menos n – m = 2 variáveis nulas e que todas as variáveis tenham valores nãonegativos.

Variável básica

Nº da equação

Coeficientes Valor

Início: Forma Padrão

Encontrar uma solução SBF* inicial

A solução é ótima?

Variável que entra

Variável que sai

Utilizar o método Gauss-Jordan e recalcular a solução básica

Fim Sim

Não

*Solução Básica Factível

Fim ø

Teste de otimalidade:

Para um problema de minimização, a solução é ótima se todos os coeficientes das variáveis não básicas na equação 0 são não positivos (≤ 0). Portanto, a solução

coeficiente da variáveis não básica x2 na equação 0 é positivo.

Entra na base a variável com o maior coeficiente positivo.

Início: Forma Padrão

Encontrar uma solução SBF* inicial

A solução é ótima?

Variável que entra

Variável que sai

Utilizar o método Gauss-Jordan e recalcular a solução básica

Fim Sim

Não

*Solução Básica Factível

Fim ø

Entra

Sai

Variável básica

Nº da equação

Coeficientes Valor

Entra

Sai

Variável básica

Nº da equação

Coeficientes Valor

Pivô

Comentários