Variantes metodo simplex
1562 palavras
7 páginas
Método Simplex - VariantesV 1.1, V.Lobo, EN / ISEGI, 2008
Variantes sobre o método Simplex:
Método do grande M
Revisões
Simplex básico
Solução óptima multipla
Em simplex: valores 0 na função custo
Solução degenerada
Em simplex: empates na variável a sair, variáveis base nulas
Solução ilimitada
Em simplex: não há variáveis para sair
1
Método Simplex - Variantes
V 1.1, V.Lobo, EN / ISEGI, 2008
Variantes do simplex
Casos em que são necessários
Restrições são do tipo “=“ ou “≥”
Não há solução inicial admissível
Método do “Grande M”
Ideia base:
Vamos acrescentar uma VARIÁVEL ARTIFICIAL nas equações (similar à “folga”), mas vamos forçar essa variável artificial a anular-se no fim.
Exemplo do Wyndor Glass Co.
Se impusermos que a oficina 3 tem que ser usada em pleno, a 3ª restrição fica
Sistema revisto:
Função objectivo
Z =3x1+5x2
Restrições x1≤ 4
2x2 ≤ 12
3x1+2x2 =18
10
x2 (janelas)
3x1+2x2 = 18
5
2
1
0 1 2
5
10 x1 (portas)
2
Método Simplex - Variantes
V 1.1, V.Lobo, EN / ISEGI, 2008
Formulação para simplex
Vamos introduzir uma forte penalização para um valor positivo deste factor
Sistema aumentado
Z- 3x1 - 5x2 x1 +s1
2x2
+s2
3x1+ 2x2
+s3
=0
=4
= 12
= 18
Como funciona ?
No final TEM que ser 0 !
Sistema aumentado
M- Um número arbitrariamente grande
Z- 3x1 - 5x2
+Ma3 =0 x1 +s1
=4
2x2
+s2
= 12
3x1+ 2x2
+a3 = 18
Podemos substituir M por um número (neste caso, 10000), ou manipulá-lo algebricamente
1º Passo do método “big M”
Ao introduzir as penalizações, deixamos de ter a forma canónica da matriz (a “diagonal” de variáveis base)
Usar eliminação de Gauss !
Passar para forma canónica
V
x1
x2
s1
s2
a3
Z
-3
-5
0
0
M
0
s1
1
0
1
0
0
4
s2
0
2
0
1
0
12
a3
3
2
0
0
1
18
V
x1
x2
s 1 s 2 a3
Z
-(3M+3)
-(2M+5)
0
0