Hvjvufyclonijo

[pic]

Pesquisa Operacional

Método Simplex

Por: Liana Mascarenhas Costa

2011.01060832

Salvador, 09 de abril de 2012 • O que é Método Simplex?

O Método Simplex é uma técnica utilizada para se determinar, numericamente, a solução ótima de um modelo de Programação Linear. Será desenvolvido inicialmente para Problemas de Programação Linear, na forma padrão, mas com as seguintes características para o sistema linear de equações:

i) Todas as variáveis são não-negativas: ii) Todos os bi’ são não-negativos; iii) Todas as equações iniciais do sistema são do tipo “ £ “. Assim, na forma padrão, só encontra-se variáveis de folga.

Se uma das características vistas não ocorrer, então, casos especiais do método devem ser considerados, como o Método Simplex de Duas Fases.

• O MÉTODO SIMPLEX

- Passo 1: Localize o número mais negativo da última linha do quadro simplex, excluída a última coluna, e chame a coluna em que este número aparece de coluna de trabalho. Se existir mais de um candidato a número mais negativo, escolha um.

- Passo 2: Forme quocientes da divisão de cada número positivo da coluna de trabalho pelo elemento da última coluna da linha correspondente (excluindo-se a última linha do quadro).Designe por pivô o elemento da coluna de trabalho que conduz ao menor quociente. Se mais de um elemento conduzir ao mesmo menor quociente, escolha um. Se nenhum elemento da coluna de trabalho for positivo, o problema não terá solução.

- Passo 3: Use operações elementares sobre as linhas a fim de converter o elemento pivô em 1 e, em seguida, reduzir a zero todos os outros elementos da coluna de trabalho.

- Passo 4: Substitua a variável x existente na linha pivô e primeira coluna pela variável x da primeira linha e coluna pivô. Esta nova primeira coluna é o novo conjunto de variáveis básicas.

- Passo 5: Repita os passos de 1 a 4 até a inexistência de números negativos na última linha, excluindo-se desta apreciação