Resolução do Exercício proposto pelo Método SIMPLEX

Prévia do material em texto

Método SIMPLEXMétodo SIMPLEXMétodo SIMPLEXMétodo SIMPLEX:::: Resolução do ExercícioResolução do ExercícioResolução do ExercícioResolução do Exercício (1)(1)(1)(1) 
MPO IMPO IMPO IMPO I (Profº Edson Urtado) 
Dados: 
Maximizar: Z = 3xZ = 3xZ = 3xZ = 3x1111 + 5x+ 5x+ 5x+ 5x2222 
Sujeito as restrições: xxxx1111 ≤ 4444 
 xxxx2222 ≤ 6666 
 3x3x3x3x1111 + 2x+ 2x+ 2x+ 2x2222 ≤ 18181818 
x1, x2 ≥ 0 
SOLUÇÃO: 
1) Inserir as variáveis de folga nas restrições: 
xxxx1111 +x3 = 4 
xxxx2222 +x4 = 6 
3xxxx1111 + 2xxxx2222 +x5 = 18 
 
2) Montagem do quadro de cálculos (tableu): 
Linha BASEBASEBASEBASE X1 X2 X3 X4 X5 VALORVALORVALORVALOR 
1 X3 1 0 1 0 0 4 
2 X4 0 1 0 1 0 6 
3 X5 3 2 0 0 1 18 
4 Z -3 -5 0 0 0 0 
 
3) Escolher a coluna com o maior valor: (-5). (Essa será a variável que entrará na BASE. 
Dividir os valores da coluna “VALOR” pelos respectivos valores da coluna X2: 
4/0 = N; 6/1 = 6; 18/2 = 9 
Então, o menor valor (6) determina que a linha X4 será a variável que sairá da BASE. 
Linha BASEBASEBASEBASE X1 X2 X3 X4 X5 VALORVALORVALORVALOR 
1 X3 1 0 1 0 0 4 
2 X4 0 1 0 1 0 6 
3 X5 3 2 0 0 1 18 
4 Z -3 -5 0 0 0 0 
 
4) Nova linha PivôNova linha PivôNova linha PivôNova linha Pivô (X2) (linha que entra na BASE): 
=Linha antiga / nº pivô (1): 
0/1 1/1 0/1 1/1 0/1 6/1 
= 
0000 1111 0000 1111 0000 6666 
Nova L2Nova L2Nova L2Nova L2 
5) Nova linha 1 (L1)Nova linha 1 (L1)Nova linha 1 (L1)Nova linha 1 (L1) 
Repetir nova linha pivô e multiplicar pelo inverso do valor do cruzamento da linha e a 
coluna pivô: 
0*(0) 1*(0) 0*(0) 1*(0) 0*(0) 6*(0) 
= 
0 0 0 0 0 0 
Somar com a linha L1 antiga: 
1111 0000 1111 0000 0000 4444 
Nova L1Nova L1Nova L1Nova L1 
 
6) Nova linha 3 (L3)Nova linha 3 (L3)Nova linha 3 (L3)Nova linha 3 (L3) 
Repetir nova linha pivô e multiplicar pelo inverso do valor do cruzamento da linha e a 
coluna pivô: 
0*(-2) 1*(-2) 0*(-2) 1*(-2) 0*(-2) 6*(-2) 
= 
0 -2 0 -2 0 -12 
Somar com a linha L3 antiga: 
0+3 -2+2 0+0 -2+0 1+0 -12+18 
3333 0000 0000 ----2222 1111 6666 
Nova LNova LNova LNova L3333 
 
7) Nova linha Nova linha Nova linha Nova linha 4 (L44 (L44 (L44 (L4)))) 
Repetir nova linha pivô e multiplicar pelo inverso do valor do cruzamento da linha e a 
coluna pivô: 
0*(5) 1*(5) 0*(5) 1*(5) 0*(5) 6*(5) 
= 
0 5 0 5 0 30 
Somar com a linha L4 antiga: 
0-3 5-5 0+0 5+0 0+0 30+0 
----3333 0000 0000 5555 0000 30303030 
Nova LNova LNova LNova L4444 
 
8) Construção da nova tabela: 
Linha BASEBASEBASEBASE X1 X2 X3 X4 X5 VALORVALORVALORVALOR 
1 X3 1111 0000 1111 0000 0000 4444 
2 X2 0000 1111 0000 1111 0000 6666 
3 X5 3333 0000 0000 ----2222 1111 6666 
4 Z ----3333 0000 0000 5555 0000 30303030 
 
A linha 4 (Z) tem um nº negativo, então ainda não temos a solução ótima. Refazer os 
passos de 3 à 8 novamente. 
 
9) Escolher a coluna com o maior valor: (-3). (Essa será a variável que entrará na BASE. 
Dividir os valores da coluna “VALOR” pelos respectivos valores da coluna X1: 
4/1 = 4; 6/0 = N; 6/3 = 2 
Então, o menor valor (2) determina que a linha X5 será a variável que sairá da BASE. 
Linha BASEBASEBASEBASE X1 X2 X3 X4 X5 VALORVALORVALORVALOR 
1 X3 1111 0000 1111 0000 0000 4444 
2 X2 0000 1111 0000 1111 0000 6666 
3 X5 3333 0000 0000 ----2222 1111 6666 
4 Z ----3333 0000 0000 5555 0000 30303030 
 
10) Nova linha PivôNova linha PivôNova linha PivôNova linha Pivô (X1) (linha que entra na BASE): 
=Linha antiga / nº pivô (3): 
3/3 0/3 0/3 -2/3 1/3 6/3 
 
= 
1111 0000 0000 ----2/32/32/32/3 1/31/31/31/3 2222 
Nova LNova LNova LNova L3333 
11) Nova linha Nova linha Nova linha Nova linha 1111 (L(L(L(L1111)))) 
Repetir nova linha pivô e multiplicar pelo inverso do valor do cruzamento da linha e a 
coluna pivô: 
1*(-1) 0*(-1) 0*(-1) -2/3*(-1) 1/3*(-1) 2*(-1) 
= 
-1 0 0 2/3 -1/3 -2 
Somar com a linha L1 antiga: 
-1+1 0+0 0+1 2/3+0 -1/3+0 -2+4 
0000 0000 1111 2/32/32/32/3 ----1111/3/3/3/3 2222 
Nova LNova LNova LNova L1111 
 
12) Nova linha Nova linha Nova linha Nova linha 2222 (L(L(L(L2222)))) 
Repetir nova linha pivô e multiplicar pelo inverso do valor do cruzamento da linha e a 
coluna pivô: 
1*(0) 0*(0) 0*(0) -2/3*(0) 1/3*(0) 2*(0) 
= 
0 0 0 0 0 0 
Somar com a linha L1 antiga: 
0000 1111 0000 1111 0000 6666 
Nova LNova LNova LNova L2222 
 
13) Nova linha Nova linha Nova linha Nova linha 4 (L44 (L44 (L44 (L4)))) 
Repetir nova linha pivô e multiplicar pelo inverso do valor do cruzamento da linha e a 
coluna pivô: 
1*(3) 0*(3) 0*(3) -2/3*(3) 1/3*(3) 2*(3) 
= 
3 0 0 -2 1 6 
Somar com a linha L4 antiga: 
3-3 0+0 0+0 -2+5 1+0 6+30 
0000 0000 0000 3333 1111 36363636 
Nova LNova LNova LNova L4444 
 
14) Construção da nova tabela: 
Linha BASEBASEBASEBASE X1 X2 X3 X4 X5 VALORVALORVALORVALOR 
1 X3 0000 0000 1111 2/32/32/32/3 ----1111/3/3/3/3 2222 
2 X2 0000 1111 0000 1111 0000 6666 
3 X1 1111 0000 0000 ----2/32/32/32/3 1/31/31/31/3 2222 
4 ZZZZ 0000 0000 0000 3333 1111 36363636 
A linha 4 (Z) tem valores zero, então temos uma solução ótimasolução ótimasolução ótimasolução ótima (maximização para Z=36 
e X1=2 e X2=6). 
X1=2, X2=6; Z = 36.X1=2, X2=6; Z = 36.X1=2, X2=6; Z = 36.X1=2, X2=6; Z = 36.