Método Simplex para Programação Linear

Prévia do material em texto

1. Formular o problema de programação linear sob a forma normal/standardizada 
(passar inequações a equações através da utilização de variáveis de folga). 
2. Identificar uma solução básica admissível inicial (uma boa ideia é verificar se o 
ponto de máxima folga é uma solução admissível). Uma solução básica contém um 
número de variáveis idêntico ao número de restrições do problema. 
3. Passar todos os coeficientes e constantes do problema para um quadro simplex. Se 
o problema for de maximização, os coeficientes da função objectivo devem ser 
passados para o quadro simplex com o mesmo sinal. Se o problema for de 
minimização, os coeficientes da f.o. devem mudar de sinal quando entram no 
quadro simplex. 
4. Verificar se esta solução é óptima, ie, verificar se não há nenhum coeficiente 
positivo na linha da função objectivo. 
a. Caso isto se verifique, a solução óptima está encontrada. Não há 
nenhuma solução alternativa que melhore o valor da função objectivo. 
b. Caso isto não se verifique, escolher a coluna com o coeficiente mais 
positivo na linha da função objectivo como coluna pivot. A variável 
associada a essa coluna deve entrar na solução básica, já que é a que 
garante o maior crescimento no valor da função objectivo. 
5. A variável a sair da solução básica é aquela associada à restrição que primeiro 
limita o crescimento da nova variável básica. A forma de determinar essa variável é 
escolhendo a linha com o menor valor não-negativo do coeficiente reduzido = 
ki/(coeficiente em xj). A linha associada a essa variável é a linha pivot. (ki é o termo 
independente em cada equação i; xj é a nova variável a entrar na base, ie, a variável 
associada à coluna pivot j) 
Método Simplex – passos elementares da resolução matricial 
6. O elemento pivot é aquele coeficiente que se encontra na intersecção da coluna 
pivot com a linha pivot (cij). 
7. Terminada a iteração anterior, é necessário calcular um novo quadro simplex. Este 
cálculo baseia-se na operação sobre linhas de Gauss-Jordan e pode resumir-se da 
seguinte forma: 
a. Nova linha pivot = (Velha linha pivot)/(elemento pivot) 
b. Todas as outras linhas: 
Nova linha = (Velha linha) – (Coeficiente da coluna pivot associado à 
velha linha)*(Nova linha pivot) 
Iteração 0 
 x1 x2 x3 x4 x5 k k/c(xj) 
x3 1 1 1 0 0 5000 5000.0 
x4 0 1 0 1 0 2700 2700.0 Linha pivot 
x5 1 1.4 0 0 1 5400 3857.1 
z 150 300 0 0 0 0 
 
 
Coluna 
pivot 
 
Iteração 1 
 x1 x2 x3 x4 x5 k 
x3 1 0 1 -1 0 2300 
x2 0 1 0 1 0 2700 
x5 1 0 0 -1.4 1 1620 
z 150 0 0 -300 0 -810000 
 
c. O valor no canto inferior direito representa o simétrico da f.o.. 
8. Encontrada a solução óptima (ver ponto 4), o valor óptimo de cada variável básica 
corresponde ao valor da última coluna na linha respectiva a essa variável.