impermeab

Universidade Federal de Itajubá
Instituto de Engenharia de Produção e Gestão

Pesquisa Operacional
Simplex
Prof. Dr. José Arnaldo Barra Montevechi

Programação Linear (PL)
Solução algébrica - método simplex Agora será apresentado mais um procedimento geral para resolução de problemas de PL, denominado “Método
Simplex” e que foi desenvolvido em 1947 por
George B. Dantzig.

Método Simplex
O método simplex é um método interativo
(algoritmo) utilizado para achar, algebricamente, a solução ótima de um problema de PL.

Procedimentos do Método
Simplex
Sabe-se que a solução ótima do modelo é uma solução básica do sistema, ou seja, um ponto extremo do polígono gerado pelas restrições. Para ser iniciado é necessário conhecer uma solução compatível básica (solução inicial) do sistema, isto é um dos pontos do polígono gerado. Procedimentos do Método
Simplex
O método simplex verifica se a presente solução é ótima. Se for o processo esta encerrado. Se não for ótima, é porque um dos pontos adjacentes fornece um valor maior que o inicial.
Neste caso, o método simplex faz então a mudança do ponto por um outro que mais aumente o valor da função objetivo.

Procedimentos do Método
Simplex
Agora tudo que foi feito para o primeiro ponto é feito para o novo ponto.
O processo finaliza quando se obtém um ponto extremo onde todos os outros pontos extremos, forneçam valores menores para a função objetivo.

Procedimentos do Método
Simplex
Como fazer, algebricamente, a mudança de um ponto extremo para outro?
Achar portanto a próxima solução básica exige a escolha de uma variável básica para deixar a base atual, tornando-se não básica, e a escolha de uma variável não básica para entrar na base em sua substituição.

Procedimentos do Método
Simplex
Supondo o seguinte problema para maximização: Max Z = 5X1 + 2X2
Sujeito a:
X1 ≤ 3
X2 ≤ 4
X1 + 2X2 ≤ 9
X1, X2 ≥ 0

Procedimentos do Método
Simplex
X2

Z
ZC=21
ZB=15