Análise de Sensibilidade - Aula 6

Pesquisa Operacional para
Computação
O Método Simplex

Simplex
• Ao invés de enumerar todas as soluções básicas (pontos extremos) do problema de
PL, o método simplex investiga somente
“algumas dessas soluções selecionadas”.

[e-mail]

Pesquisa Operacional - DCOMP - UFSJ

2

Natureza interativa do método
• Geralmente, o método simplex começa na origem (ponto A), onde x1 = x2 = 0. Nesse ponto, a função objetivo z = 0.
• A pergunta lógica é se o aumento em x1 e/ ou x2 pode melhorar (aumentar) o valor de
z.
• Respondemos essa pergunta investigando a função objetivo: Max z = 2 x1 + 3 x2 [e-mail] Pesquisa Operacional - DCOMP - UFSJ

3

Natureza interativa do método
• A função mostra que o aumento em x1 ou x2 (ou em ambas) acima de seus valores atuais (zero) melhorará o valor de z.
• O método simplex exige o aumento de uma variável por vez.
• Escolher aumentar a variável que tiver a melhor taxa de melhoria em z.

[e-mail]

Pesquisa Operacional - DCOMP - UFSJ

4

Natureza interativa do método
• Assim, aumentamos o valor de x2 até atingir o ponto extremo B (parar antes de
B não é ótimo, porque um candidato deve ser um ponto extremo).
• No ponto B, o método simplex aumentará o valor de x1 para alcançar o ponto melhorado C, que é a solução ótima.
• Assim, o caminho do método simplex é definido como A à B à C. [e-mail] Pesquisa Operacional - DCOMP - UFSJ

5

Natureza interativa do método

[e-mail]

Pesquisa Operacional - DCOMP - UFSJ

6

Natureza interativa do método
• Cada ponto extremo pesquisado é associado a uma iteração do método. O método percorre bordas e não pode atravessar a região de soluções pulando de A para C diretamente.

[e-mail]

Pesquisa Operacional - DCOMP - UFSJ

7

Natureza interativa do método
• No caminho A à B à C
• A à B: variável não básica x2 torna-se básica (entra na base) e