Base_PO_Simplex_1a

Prévia do material em texto

O Problema
Max z = 10x1 + 12x2 
Sujeito a: 
 x1 + x2 ≤ 100 
2x1 +3x2 ≤ 270 
 x1 ≥ 0, x2 ≥ 0
1 passo: preparar para o quadro
z = 10x1 + 12x2 z – 10x1 – 12x2 = 0
 x1 + x2 ≤ 100 x1 + x2 + xF1 = 100
 2x1 + 3x2 ≤ 270 2x1 + 3x2 + xF2 = 270
2 passo – montar o quadro
	
	z
	x1
	x2
	xF1
	xF2
	b
	z
	1
	-10
	-12
	0
	0
	0
	xF1
	0
	 1
	 1
	1
	0
	100
	xF2
	0
	 2
	 3
	0
	1
	270
3 passo: É ótimo? 
A mesma pergunta: 
· Existem coeficientes negativos na primeira linha nas variáveis xs e xFs?
 
	
	z
	x1
	x2
	xF1
	xF2
	b
	z
	1
	-10
	-12
	0
	0
	0
	xF1
	0
	 1
	 1
	1
	0
	100
	xF2
	0
	 2
	 3
	0
	1
	270
Resposta Sim solução não é ótima 
4 passo: Escolher quem entra. 
· Escolher o menor negativo na 1 linha(-12) x2
· Marcar a coluna do x2
	
	z
	x1
	x2
	xF1
	xF2
	b
	z
	1
	-10
	-12
	0
	0
	0
	xF1
	0
	 1
	 1
	1
	0
	100
	xF2
	0
	 2
	 3
	0
	1
	270
5 passo: Escolher quem sai 
· Dividir o valor do termo independente pelo coeficiente 
· Escolher o menor positivo
· A linha que tem o valor 90
	
	z
	x1
	 x2
	xF1
	xF2
	b
	
	z
	1
	-10
	-12
	0
	0
	0
	Não calcula
	xF1
	0
	 1
	 1
	1
	0
	100
	100/ 1 = 100
	xF2
	0
	 2
	 3
	0
	1
	270 
	270/ 3 = 90
 
6 passo: Escolher o pivô 
O pivô é o elemento da interação da coluna com a linha, portanto o pivô é o 3.
	
	z
	x1
	x2
	xF1
	xF2
	b
	z
	1
	-10
	-12
	0
	0
	0
	xF1
	0
	 1
	 1
	1
	0
	100
	xF2
	0
	 2
	 3
	0
	1
	270
7 passo: Fazer o pivotamento 
O que se quer:
	
	z
	x1
	x2
	xF1
	xF2
	b
	L1
	...
	...
	0
	...
	...
	...
	L2
	...
	...
	 0
	...
	...
	...
	L3
	...
	...
	 1
	...
	...
	...
Como fazer?
Transformar o pivô em um .
· No quadro o valor é 3.
· Portanto basta dividir a linha onde está o pivô por 3
	
	z
	x1
	x2
	xF1
	xF2
	b
	z
	1
	-10
	-12
	0
	0
	0
	xF1
	0
	 1
	 1
	1
	0
	100
	xF2
	0
	 2
	 3
	0
	1
	270
	
	z
	x1
	x2
	xF1
	xF2
	b
	
	L3
	0
	 2
	 3
	0
	1
	270
	
	L3/3 
	0
	2/3
	1
	0
	1/3
	90
	Linha com o pivô igual a 1
	
	z
	x1
	x2
	xF1
	xF2
	b
	z
	1
	-10
	-12
	0
	0
	0
	xF1
	0
	 1
	 1
	1
	0
	100
	xF2. 
	0
	2/3
	1
	0
	1/3
	90
Transformar os outros elementos da coluna do pivô e zero
· Multiplicar a linha do pivô pelo inverso do número que queremos zerar
· Somar com a linha que queremos zerar
	
	z
	x1
	x2
	xF1
	xF2
	b
	procedimento
	L1
	1
	-10
	-12
	0
	0
	0
	L1 = (L3 * 12) + L1 
	L2
	0
	 1
	 1
	1
	0
	100
	L2 = (L3 * -1) + L2 
	L3 . 
	0
	2/3
	1
	0
	1/3
	90
	 Nova L3 (pivô) 
Cálculo da linha 1
	
	z
	x1
	x2
	xF1
	xF2
	b
	
	L3
	0
	2/3
	1
	0
	1/3
	90
	
	L3 * 12 
	0
	8
	12
	0
	4
	1080
	
	L1
	1
	-10
	-12
	0
	0
	0
	
	+ 
	1
	-2
	0
	0
	4
	1080
	Nova L1
Cálculo da linha 2
	
	z
	x1
	x2
	xF1
	xF2
	b
	
	L3
	0
	2/3
	1
	0
	1/3
	90
	
	L3 * -1 
	0
	-2/3
	-1
	0 
	-1/3
	-90
	
	L2
	0
	 1
	 1
	1
	0
	100
	
	+ 
	0
	1/3
	0
	1
	-1/3
	10
	Nova L2
Resultado
Não é ótimo
	
	z
	x1
	x2
	xF1
	xF2
	b
	z
	1
	-2
	0
	0
	4
	1080
	xF1
	0
	1/3
	0
	1
	-1/3
	10
	x2 
	0
	2/3
	1
	0
	1/3
	90
Coeficiente diferente de zero o valor da variável igual a zero
 -2x1 x1 = 0
 4xF2 xF2 = 0
Coeficiente igual de zero o valor está na linha onde o valor igual a um
x2 = 90
xF1 = 10
Valor de z
z = 1080
Repedir os passos
	
	z
	x1
	x2
	xF1
	xF2
	b
	
	z
	1
	-2
	0
	0
	4
	1080
	Não calcular 
	xF1
	0
	1/3
	0
	1
	-1/3
	10
	10/(1/3) = 30
	x2 
	0
	2/3
	1
	0
	1/3
	90
	90/(2/3) = 60
Passos
· Escolher x1 		 menor negativo (-2)
· Escolher xF1		 menor positivo (30)
· Encontrar (1/3)	 interseção linha com a coluna
· Transformar o pivô em 1 dividir 1/3
	
	z
	x1
	x2
	xF1
	xF2
	b
	
	L1
	1
	-2
	0
	0
	4
	1080
	
	L2
	0
	1/3
	0
	1
	-1/3
	10
	L2 = L2 / (1/3) L2 * 3
	L3 
	0
	2/3
	1
	0
	1/3
	90
	
	
	z
	x1
	x2
	xF1
	xF2
	b
	
	L1
	1
	-2
	0
	0
	4
	1080
	L1 = L2 * 2 + L1 
	L2
	0
	1
	0
	3
	-1
	30
	Pivô 
	L3 
	0
	2/3
	1
	0
	1/3
	90
	L3 = L2 * -2/3 + L3 
· Transformar os outros coeficientes em zero
	
	z
	x1
	x2
	xF1
	xF2
	b
	z
	1
	0
	0
	6
	2
	1140
	x1
	0
	1
	0
	3
	-1
	30
	x2 
	0
	0
	1
	-2
	1
	70
Coeficiente diferente de zero o valor da variável igual a zero
6xF1 xF1 = 0
2xF2 xF2 = 0
Coeficiente igual de zero o valor está na linha onde o valor igual a um
x1 = 30
x2 = 70
Valor de z
z = 1140
Verificação
xF1 = 0
xF2 = 0
x1 = 30
x2 = 70
z = 1140
z = 10x1 + 12x2 	
 x1 + x2 + xF1 = 100
2x1 + 3x2 + xF2 = 270
z = 10*30 + 12*70 = 1140
 x1 + x2 + xF1 30 + 70 + 0 = 100
2x1 + 3x2 + Xf2 2*30 + 3*70 + 0 = 270
	
	
	z
	x1
	x2
	xF1
	xF2
	b
	
	L1
	z
	1
	-10
	-12
	0
	0
	0
	L1 = L3 * 12 + L1 
	L2
	xF1
	0
	 1
	 1
	1
	0
	100
	L2 = L3 * -1 + L2
	L3
	xF2
	0
	2/3
	 1
	0
	1/3
	90
	= 
L3			 0	2/3	1		0	1/3	90
L3 * 12	 0	8		12		0	4		1080		
L1 +			1	-10	-12	0	0		0
				1	-2		0		0	4		1080
	
	
	z
	x1
	x2
	xF1
	xF2
	b
	
	L1
	z
	1
	-2
	0
	0
	4
	1080
	Não faço
	L2
	xF1
	0
	1/3
	0
	1
	-1/3
	10
	10/(1/3) = 30 
	L3
	X2
	0
	2/3
	1
	0
	1/3
	90
	90/(2/3)= 135
L2 = L2 * 3
	
	
	z
	x1
	x2
	xF1
	xF2
	b
	
	L1
	z
	1
	-2
	0
	0
	4
	1080
	L1 = L2 * 2 + L1
	L2
	xF1
	0
	1
	0
	3
	-1
	30
	=
	L3
	X2
	0
	2/3
	1
	0
	1/3
	90
	L3 = L2 *(-2/3) + L3
	
	
	z
	x1
	x2
	xF1
	xF2
	b
	L1
	z
	1
	0
	0
	6
	2
	1140
	L2
	X1
	0
	1
	0
	3
	-1
	30
	L3
	X2
	0
	0
	1
	-2
	1
	70
6xF1 xF1 = 0
2xF2 xF2 = 0
xF1 =0 	xF2 = 0
x1 = 30 
x2 = 70
z = 1140
z = 10x1 + 12x2 	 z – 10x1 – 12x2 = 0
x1 + x2 ≤ 100 	 x1 + x2 + xF1 = 100
2x1 +3x2 ≤ 270 	 2x1 + 3x2 + Xf2 = 270
z = 10*30 + 12*70 = 1140
x1 + x2 + xF1 30 + 70 + 0 = 100
2x1 + 3x2 + Xf2 2*30 + 3*70 + 0 = 270