Método Simplex – passos elementares da resolução matricial
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)
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
x3
x4
x5
z
x1
1
0
1
150
x2
1
1
1.4
300
Coluna
pivot
x3
1
0
0
0
x4
0
1
0
0
x5
0
0
1
0
k
5000
2700
5400
0
x1
1
0
1
150
x2
0
1
0
0
x3
1
0
0
0
x4
-1
1
-1.4
-300
x5
0
0
1
0
k
2300
2700
1620
-810000
k/c(xj)
5000.0
2700.0
3857.1
Linha pivot
Iteração 1
x3
x2
x5
z
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.