MÉTODO SIMPLEX – SOLUÇÃO INICIAL ARTIFICIAL Problemas de

MÉTODO SIMPLEX – SOLUÇÃO INICIAL ARTIFICIAL 



Problemas de PL nos quais todas as restrições são (≤) com lados direitos não negativos oferecem uma solução básica inicial viável conveniente, na qual todas as variáveis são de folga. Isso não acontece com os modelos que envolvem restrições (=) ou (≥). 

Chamados de problemas de PL “mal comportados”

MÉTODO SIMPLEX – SOLUÇÃO INICIAL ARTIFICIAL 

O procedimento para iniciar a resolução de problemas de PL “mal comportados”, com restrições (=) ou (≥), é usar variáveis artificiais que desempenham o papel de folgas na primeira iteração e, então, descartá-las legitimamente em iterações posteriores.



Para isso, existem dois métodos principais: Método M-Grande – mais antigo, porém não utilizado em situações práticas;  Método das Duas Fases 

MÉTODO SIMPLEX – MÉTODO DAS DUAS FASES 

Fase I 

Expresse o problema na forma de equações e adicione as variáveis artificiais necessárias às restrições para garantir uma solução básica inicial.



Em seguida, ache uma solução básica com as equações resultantes que, independentemente de o problema de PL ser de Maximização ou Minimização, sempre minimizará a soma das variáveis artificiais. Se o valor mínimo da soma for positivo, o problema de PL não tem solução viável, o que encerra o processo (OBS.: uma variável artificial positiva significa que uma restrição original não foi satisfeita.  Caso contrário, passe para a FASE II. 

MÉTODO SIMPLEX – MÉTODO DAS DUAS FASES 

Fase II 

Use a solução viável da Fase I como uma solução básica viável inicial para o problema original.

MÉTODO SIMPLEX – MÉTODO DAS DUAS FASES 

Dado o problema de PL Minimizar z = 4x1 + x2

Sujeito a 3x1 + x2 = 3 4x1 + 3x2 ≥ 6 x1 + 2x2 ≤ 4 x1, x2 ≥ 0

MÉTODO SIMPLEX – MÉTODO DAS DUAS FASES 

Dado o problema de PL Minimizar z = 4x1 + x2

Sujeito a 3x1 + x2 = 3 4x1 + 3x2 ≥ 6 x1 + 2x2 ≤ 4 x1, x2 ≥ 0

MÉTODO SIMPLEX – MÉTODO DAS DUAS FASES 

Transformando em equações: Minimizar z = 4x1 + x2 (z – 4x1 – x2 = 0)

Sujeito a 3x1 + x2 = 3 4x1 + 3x2 – s1 = 6 x1 + 2x2 + s2 = 4 x1, x2, s1, s2 ≥ 0

MÉTODO SIMPLEX – MÉTODO DAS DUAS FASES 

FASE I – Adicionando as variáveis artificiais R1 e R2 Minimizar z = R1 + R2 (z – R1 – R2 = 0)

Sujeito a 3x1 + x2 + R1 = 3 4x1 + 3x2 – s1 + R2 = 6 x1 + 2x2 + s2 = 4 x1, x2, s1, s2, R1, R2 ≥ 0

MÉTODO SIMPLEX – MÉTODO DAS DUAS FASES 

FASE I – A tabela inicial é

Base

x1

x2

s1

s2

R1

R2

Solução

z

0

0

0

0

-1

-1

0

R1

3

1

0

0

1

0

3

R2

4

3

-1

0

0

1

6

x4

1

2

0

1

0

0

4



Próximo passo: A tabela está inconsistente, em função da inclusão de R1 e R2  Substituir os valores de R1 e R2 na linha z usando o cálculo: 

Nova Linha z = Velha Linha z + (1 * Linha R1 + 1 * Linha R2)

MÉTODO SIMPLEX – MÉTODO DAS DUAS FASES 

FASE I – A tabela inicial é Nova Linha z = Velha Linha z + (1 * Linha R1 + 1 * Linha R2) Nova Linha z = (0 0 0 0 -1 -1 0) + ((3 1 0 0 1 0 3) + (4 3 -1 0 0 1 6)) Nova Linha z = (0 0 0 0 -1 -1 0) + (7 4 -1 0 1 1 9) Nova Linha z = (7 4 -1 0 0 0 9)

MÉTODO SIMPLEX – MÉTODO DAS DUAS FASES 

FASE I – A tabela inicial é

Base

x1

x2

s1

s2

R1

R2

Solução

z

7

4

-1

0

0

0

9

R1

3

1

0

0

1

0

3

R2

4

3

-1

0

0

1

6

x4

1

2

0

1

0

0

4



Próximo passo: 

Resolver normalmente a FASE I do problema, a fim de encontrar uma nova solução em que R1 e R2 não façam parte da solução.

MÉTODO SIMPLEX – MÉTODO DAS DUAS FASES 

FASE I – A tabela ótima da Fase I é

Base

x1

x2

s1

s2

R1

R2

Solução

z

0

0

0

0

-1

-1

0

x1

1

0

1/5

0

3/5

-1/5

3/5

x2

0

1

-3/5

0

-4/5

3/5

6/5

x4

0

0

1

1

1

-1

1



Próximo passo: Com z = 0, a Fase I produz a solução básica viável x1 = 3/5, x2 = 6/5 e x4 = 1.  As variáveis artificiais concluíram sua missão e suas colunas podem ser eliminadas.  Passamos para a Fase II. 

MÉTODO SIMPLEX – MÉTODO DAS DUAS FASES 

FASE II – Solução final 

O problema “original” é reescrito como

Minimizar z = 4x1 + x2 (z – 4x1 – x2 = 0) Sujeito a x1 + 1/5s1 = 3/5 x2 – 3/5s1 = 6/5 s1 + s2 = 1 x1, x2, s1, s2 ≥ 0

MÉTODO SIMPLEX – MÉTODO DAS DUAS FASES 

FASE II – A tabela da Fase II representa uma solução básica viável inicial



Base

x1

x2

s1

s2

Solução

z

-4

-1

0

0

0

x1

1

0

1/5

0

3/5

x2

0

1

-3/5

0

6/5

x4

0

0

1

1

1

Próximo passo: 

Como as variáveis básicas x1 e x2 têm coeficientes não zero na linha z, elas devem ser substituídas com o seguinte cálculo: Nova Linha z = Velha Linha z + (4 * Linha x1 + 1 * Linha x2)

MÉTODO SIMPLEX – MÉTODO DAS DUAS FASES 

FASE II – A Nova Linha z é Nova Linha z = Velha Linha z + (4 * Linha x1 + 1 * Linha x2) Nova Linha z = (-4 -1 0 0 0) + ( 4 * (1 0 1/5 0 3/5) + 1 * (0 1 -3/5 0 6/5)) Nova Linha z = (-4 -1 0 0 0) + ( (4 0 4/5 0 12/5) + (0 1 -3/5 0 6/5)) Nova Linha z = (-4 -1 0 0 0) + (4 1 1/5 0 18/5) Nova Linha z = (0 0 1/5 0 18/5)

MÉTODO SIMPLEX – MÉTODO DAS DUAS FASES 

FASE II – A nova tabela inicial é



Base

x1

x2

s1

s2

Solução

z

0

0

1/5

0

18/5

x1

1

0

1/5

0

3/5

x2

0

1

-3/5

0

6/5

x4

0

0

1

1

1

Próximo passo: Resolver normalmente pelo método Simplex  s1 entra na solução básica e s2 sai, sendo necessário apenas concluir essa iteração para encontrar a solução ótima. 

MÉTODO SIMPLEX – MÉTODO DAS DUAS FASES 

Exercícios 

Agora sim....



Resolva o problema da Casa das Rações pelo Método Simplex;



Desenvolva todos os cálculos necessários, passo a passo;



Compare a sua solução com a realizada no software TORA;



Encaminhe a solução para o e-mail do professor.

MÉTODO SIMPLEX – MÉTODO DAS DUAS FASES 

Comentários finais: 

A remoção das variáveis artificiais e suas colunas no final da Fase I só pode ocorrer quando todas elas forem não básicas.



Se uma ou mais variáveis artificiais forem básicas no final da Fase I, então é preciso executar as etapas a seguir para removê-las antes do início da Fase II.

MÉTODO SIMPLEX – MÉTODO DAS DUAS FASES 

Comentários finais: 

Etapa 1 Selecione uma variável artificial com coeficiente igual a zero para sair da solução básica e designe sua linha como a linha pivô.  A variável que entra pode ser qualquer variável não básica (não artificial) que tenha um coeficiente não zero (positivo ou negativo) na linha pivô.  Execute a iteração simplex associada. 



Etapa 2 Remova da tabela a coluna da variável artificial (que acabou de sair).  Se todas as variáveis artificiais com coeficiente igual a zero tiverem sido removidas da solução básica, passe para a Fase II.  Caso contrário, volte para a Etapa I. 

REFERÊNCIAS BIBLIOGRÁFICAS 

TAHA, H. A. Pesquisa Operacional. 8. ed. São Paulo: Pearson, 2008.