Prova de Pesquisa Operacional Avaliação 2 - 12 07 21

Prévia do material em texto

1. Resolva o modelo utilizando o método simplex
Max. z = 2x1 + 4x2 + 6x3
Acrescentando as variáveis de folga Na restrições:
X1+ x2+x3+xf1= 100
2x1 – x2 +5x3 +xf2= 50
3x1 + x3 + xf3= 200
X1, x2, x3, xf1, xf2. Xf3 ≥ 0
Escreva em forma de vetores
X1= 0, X2=0 E X3=0
X1+ x2+x3+xf1= 100 1*0 +1*0 +XF1=100 XF1= 100
2x1 – x2 +5x3 +xf2= 50 2*0 -1*0+5*0 + XF2= 50 XF2= 50
3x1 + x3 + xf3= 200 3*0 +1*0+ XF3=200 XF3= 200
	X1
	X2
	X3
	XF1
	XF2
	XF3
	B
	0
	0
	0
	1
	0
	0
	100
	0
	0
	0
	0
	1
	0
	50
	0
	0
	0
	0
	0
	1
	200
Descrição do método de maximização
1º passo 
Max z= 2x1 +4x2 +6x3 
X1= 0, X2=0, X3=0 e Z= 0; z= 2x1 +4x2 +6x3
X1=1
z= 2x1 +4*0 +6*0 2
X2= 1
z= 2*0 +4*1 +6*0 4
X3= 1
z= 2*0 +4*0 +6*1 6
Z – 2X1 – 4X2 -6X3= 0
2º passo – cálculo da nova solução
Z – 2X1 – 4X2 -6X3= 0 ou z= 2x1 +4x2 +6x3
A- variável que entra na base
Entrou a variável x3, pois cada unidade a mais em x3 aumentou z em 6 unidade
B- variável que sai
X1+ x2+x3+xf1= 100 100/1= 100
2x1 – x2 +5x3 +xf2= 50 50/5= 10 menor valor sai
3x1 + x3 + xf3= 200 200/1= 100
C- Elemento pivô- a coluna variável que entra e a linha da variável que sai identifica o elemento pivô. Coeficiente 5 do elemento x3 é o elemento pivô.
D- Calculo da nova solução:
Z – 2X1 – 4X2 -6X3
	Z
	X1
	X2
	X3
	Xf1
	Xf2
	Xf3
	B
	1
	-2
	-4
	-6
	0
	0
	0
	0
	0
	1
	1
	1
	1
	0
	0
	100
	0
	2
	-1
	5
	0
	1
	0
	50
	0
	3
	0
	1
	0
	0
	1
	200
 Linha pivô= 5 dividir por 5- Da linha pivô, nova linha pivô 
	Z
	X1
	X2
	X3
	Xf1
	Xf2
	Xf3
	B
	1
	-2
	-4
	-6
	0
	0
	0
	0
	0
	1
	1
	1
	1
	0
	0
	100
	0
	0,4
	-0,2
	1
	0
	0,2
	0
	10
	0
	3
	0
	1
	0
	0
	1
	200
Reescreva cada uma das linhas da seguinte maneira
	Z
	X1
	X2
	X3
	Xf1
	Xf2
	Xf3
	B
	1
	-2
	-4
	-6
	0
	0
	0
	0
	0
	0,4
	-0,2
	1
	0
	0,2
	0
	10
	Multp.6
	2,4
	-1,2
	6
	0
	1,2
	0
	60
	1
	0,4
	-5,2
	0
	0
	1,2
	0
	60
O coeficiente da variável que entra x3 na segunda linha 1
	
	Z
	X1
	X2
	X3
	XF1
	XF2
	XF3
	B
	NOVA LINHA PIVÔ
	0
	0,4
	-0,2
	1
	0
	0,2
	0
	10
	*1
	0
	-0,4
	0,2
	-1
	0
	-0,2
	0
	-10
	Soma da 2ª linha 
	0
	1
	1
	1
	1
	0
	0
	100
	Soma da nova 2ª linha
	0
	0,6
	1,2
	0
	1
	-0,2
	0
	90
O coeficiente da variável que entra na 4ª linha 1 
	
	Z
	X1
	X2
	X3
	XF1
	XF2
	XF3
	B
	NOVA LINHA PIVÔ
	0
	0,4
	-0,2
	1
	0
	0,2
	0
	10
	*1
	0
	-0,4
	0,2
	-1
	0
	-0,2
	0
	-10
	Soma da 4ª linha 
	0
	3
	0
	1
	0
	0
	1
	200
	Soma da nova 4ª linha
	0
	2,6
	0,2
	0
	0
	-0,2
	1
	190
Reescrevendo a nova tabela
	z
	X1
	X2
	X3
	Xf1
	Xf2
	Xf3
	B
	0
	0,4
	-0,2
	1
	0
	0,2
	0
	10
	1
	0,4
	-5,2
	0
	0
	1,2
	0
	60
	0
	0,6
	1,2
	0
	1
	-0,2
	0
	90
	0
	2,6
	0,2
	0
	0
	-0,2
	1
	190
Conclusão da nova solução
Variáveis não básica Valor de Z
Z= 60
Variáveis básica 
X3= 10
Xf1=90
Xf3=190
X1=0
X2=0
Xf2=0
Calculando a nova solução
	Z
	X1
	X2
	X3
	Xf1
	Xf2
	Xf3
	B
	0
	0,4
	-0,2
	1
	0
	0,2
	0
	10
	1
	0,4
	-5,2
	0
	0
	1,2
	0
	60
	0
	0,6
	1,2
	0
	1
	-0,2
	0
	90
	0
	2,6
	0,2
	0
	0
	-0,2
	1
	190
Variável que sai= 60/-5,2= -11,53
 90/1,2= 75 menor valor= variável dessa linha no caso é xf1
 190/0,2= 950
Elemento pivô= 1,2 
	Linha pivô 3ª linha
	0
	0,6
	1,2
	0
	1
	-0,2
	0
	90
	Dividir por 1,2
	0
	0,5
	1
	0
	0,83
	-0,16
	0
	75
Coeficiente que entra na primeira linha é -0,2
	
	Z
	X1
	X2
	X3
	XF1
	XF2
	XF3
	B
	NOVA LINHA PIVÔ
	0
	0,5
	1
	0
	0,83
	-0,16
	0
	75
	*0,2
	0
	0,1
	0,2
	0
	0,166
	0,032
	0
	15
	Soma da 1ª linha 
	0
	0,4
	-0,2
	1
	0
	0,2
	0
	10
	Soma da nova ª linha
	0
	0,5
	0
	1
	0,166
	0,232
	0
	25
Coefiente que entra na 2º linha -5,2
	
	Z
	X1
	X2
	X3
	XF1
	XF2
	XF3
	B
	NOVA LINHA PIVÔ
	0
	0,5
	1
	0
	0,83
	-0,16
	0
	75
	*5,2
	0
	2,6
	5,2
	0
	4,316
	-0,832
	0
	390
	Soma da 2ª linha 
	1
	0,4
	-5,2
	0
	0
	1,2
	0
	60
	Soma da nova 2 ª linha
	1
	3
	0
	0
	4,316
	0,368
	0
	450
 
Coeficiente que entra na 4 ª linha 0,2
	
	Z
	X1
	X2
	X3
	XF1
	XF2
	XF3
	B
	NOVA LINHA PIVÔ
	0
	0,5
	1
	0
	0,83
	-0,16
	0
	75
	*-0,2
	0
	-0,1
	-0,2
	0
	-0,166
	0,032
	0
	-15
	Soma da 4ª linha 
	0
	2,6
	0,2
	0
	0
	-0,2
	1
	190
	Soma da nova ª 4 linha
	0
	2,5
	0
	0
	-0,166
	-0,168
	1
	175
Reescrever a tabela com os valores obtidos:
	Z
	X1
	X2
	X3
	Xf1
	Xf2
	Xf3
	B
	0
	0,5
	0
	1
	0,166
	0,232
	0
	25
	1
	3
	0
	0
	4,316
	0,368
	0
	450
	0
	0,5
	1
	0
	0,83
	-0,16
	0
	75
	0
	2,5
	0
	0
	-0,166
	-0,168
	1
	175
Variáveis não básica Valor de Z
Z= 450
Variáveis básica 
X2= 75
X3= 25
Xf3=175
X1=0
Xf1=0
Xf2=0
A Tabela Simplex ao lado fornece a seguinte solução ótima
2. Resolva pelo Simplex, usando o método do M grande para obter a solução básica inicial.
Max z = 2x1 + 3x2
 
Resolução: max z= 2x1+ 3x2
 X1+ x2 +xf1 + a1= 10
 2x1 + x2 + xf2 =16
Função objetiva auxiliar, pode escrever M como:
Minimizar M= a1 
A1= 10 –x1 –x2 +xf1
M= - x1 - x 2 + u1 + 10 (*-1)
Maximizar –M - x1 - x 2 + XF1= -10
	Z
	X1
	X2
	XF1
	XF2
	A1
	B
	0
	1
	1
	-1
	0
	1
	10
	0
	2
	1
	0
	1
	0
	16
	1
	-2
	-3
	0
	0
	0
	0
	0
	-1
	-1
	1
	0
	0
	-10
Resolução:Variáveis não básica 
X1=0
X2=0
Valor de Z
Z=0
Variáveis básicas 
XF2= 16
XF1= -10
A1= 10
Calcula da nova solução
Variável que entra x1= ( coeficiente 1)
Variável que sai= 10/1= 10
 16/2= 8 sai a variável é a segunda linha
 -10/-1= 10
 
Linha pivô= 2ª linha 
Elemento pivô= 2
Nova linha pivô dividi por 2
	
	Z
	X1
	X2
	Xf1
	Xf2
	A1
	b
	Linha pivô
	0
	2
	1
	0
	1
	0
	16
	Nova linha pivô
	0
	1
	0,5
	0
	0,5
	0
	8
Calcular a nova primeira linha (coeficiente da variável que entra 1)
	nova linha pivô
	0
	1
	0,5
	0
	0,5
	0
	8
	*-1
	0
	-1
	-0,5
	0
	-0,5
	0
	-8
	+ 1ª linha
	0
	1
	1
	-1
	0
	1
	10
	Soma da nova 1ª linha
	0
	0
	0,5
	-1
	-0,5
	1
	2
Calculo da nova terceira linha (coeficiente da variável -2)
	nova linha pivô
	0
	1
	0,5
	0
	0,5
	0
	8
	*2
	0
	2
	1
	0
	1
	0
	16
	+ 3ª linha
	1
	-2
	-3
	0
	0
	0
	0
	Soma da nova 3ª linha
	1
	0
	-2
	0
	1
	0
	16
 
Calculo da nova quarta linha ( coeficiente da variável que entra -1)
	nova linha pivô
	0
	1
	0,5
	0
	0,5
	0
	8
	*1
	0
	1
	0,5
	0
	0,5
	0
	8
	+ 4ª linha
	0
	-1
	-1
	1
	0
	0
	-10
	Soma da nova 4ª linha
	0
	0
	-0,5
	1
	0,5
	0
	-2
Novo quadro
	Z
	X1
	X2
	XF1
	XF2
	A1
	B
	0
	0
	0,5
	-1
	-0,5
	1
	2
	0
	1
	0,5
	0
	0,5
	0
	8
	1
	0
	-2
	0
	1
	0
	16
	0
	0
	-0,5
	1
	0,5
	0
	-2
Resolução:Variáveis não básica 
X2=0
Xf2=0
Valor de Z
Z=16
Variáveis básicas 
X1= 8
Xf1= -2
A1= 2
Calculo da nova solução =
Variável que entra x2 
Variável que saí= 2/0,5 4
 8/0,5 16
 -2/-0,5 4
Nova linha pivô 1ª linha 
Elemento pivô= 0,5
Nova linha pivô dividi por 0,5
	
	Z
	X1
	X2
	Xf1
	Xf2
	A1
	b
	Linha pivô
	0
	0
	0,5
	-1
	-0,5
	1
	2
	Nova linha pivô
	0
	0
	1
	-2
	-1
	2
	4
Calculo da nova 2ª linha coeficiente 0,5
	nova linha pivô
	0
	0
	1
	-2
	-1
	2
	4
	*-0,5
	0
	0
	-0,5
	1
	0,5
	-1
	-2
	+ 2ª linha
	0
	1
	0,5
	0
	0,5
	0
	8
	Soma da nova 2ª linha
	0
	1
	0
	1
	1
	-1
	6
Calculo da nova 3ª linha coeficiente -2
	nova linha pivô
	0
	0
	1
	-2
	-1
	2
	4
	*2
	0
	0
	2
	-4
	-2
	4
	8
	+ 3ª linha
	1
	0
	-2
	0
	1
	0
	16
	Soma da nova 3ª linha
	1
	0
	0
	-4
	-1
	4
	24
Calculo da nova 4ª linha coeficiente -0,5
	nova linha pivô
	0
	0
	1
	-2
	-1
	2
	4
	*0,5
	0
	0
	0,5
	-1
	-0,5
	1
	2
	+ 4ª linha
	0
	0
	-0,5
	1
	0,5
	0
	-2
	Soma da nova 4ª linha
	0
	0
	0
	0
	0
	1
	0
 
	Z
	X1
	X2
	XF1
	XF2
	A1
	B
	0
	0
	1
	-2
	-1
	2
	4
	0
	1
	0
	1
	1
	-1
	6
	1
	0
	0
	-4
	-1
	4
	24
	0
	0
	0
	0
	0
	1
	0
Como a 1=0, podemos abandonar a função-objetivo auxiliar M e as variáveis artificiais.
Então excluímos a coluna a1.
Nova tabela 
	Z
	X1
	X2
	Xf1
	Xf2
	b
	0
	0
	1
	-2
	-1
	4
	0
	1
	0
	1
	1
	6
	1
	0
	0
	-4
	-1
	24
solução:Variáveis não básica 
Xf1=0
Xf2=0
Variáveis básicas 
X1= 6
X2= 4
Valor de Z
Z=24
Calculo da nova solução =
Variável que entra xf1 
Variável que saí= 4/-2= -2
 6/1= 6
Calculo da solução ótima 
Nova linha pivô 2ª linha 
Elemento pivô= 1Nova linha pivô dividi por 1
	
	Z
	X1
	X2
	Xf1
	Xf2
	b
	Linha pivô
	0
	1
	0
	1
	1
	6
	Nova linha pivô
	0
	1
	0
	1
	1
	6
Calcular a nova 1ª linha coeficiente que entra -2
	nova linha pivô
	0
	1
	0
	1
	1
	6
	*2
	0
	2
	0
	2
	2
	12
	+ 1ª linha
	0
	0
	1
	-2
	-1
	4
	Soma da nova 1ª linha
	0
	2
	1
	0
	1
	16
Calcular a nova 3ª linha coeficiente que entra -4
	nova linha pivô
	0
	1
	0
	1
	1
	6
	*4
	0
	4
	0
	4
	4
	24
	+ 1ª linha
	1
	0
	0
	-4
	-1
	24
	Soma da nova 1ª linha
	1
	4
	0
	0
	3
	48
Variáveis não básicas
X1=0
Xf2=0
Nova tabela Variáveis básicas 
X2=16
Xf1=6
Valor de z
Z= 48
	Z
	X1
	X2
	Xf1
	Xf2
	b
	 0
	2
	1
	0
	1
	16
	0
	1
	0
	1
	1
	6
	1
	4
	0
	0
	3
	48
 Uma vez que não existe variáveis não-básicas com coeficiente negativo a solução não poderá mais ser melhorada, portanto, está solução é ótima
3. Resolva pelo Simplex, usando o método da função objetivo auxiliar para obter a solução básica inicial.
Min z = 3x1 + 2x2
4. Três armazéns abastecem cinco pontos de venda. O quadro abaixo mostra os custos de distribuição, a capacidade dos armazéns e as necessidades nos pontos de venda. A companhia responsável pelos armazéns não quer abastecer o ponto de venda P4 a partir do armazém A1, nem o ponto de venda P3 a partir do armazém A3.
 
a.Calcule uma solução inicial pelo método de Vogel.
	
	
D1
	
D2
	
D3
	
D4
	
D5
	
D6
	
Oferta
	
	
	
 16
	
	
12
	
	
12
	
	
12
	
	
16
	
	
	
	
	
	
	
	
	
	
F1
	
	 X
	
	 X
	
	36
	
	 X
	
	 X
	0
	134
	
170
	
14-12=2
	
14-12=2
	
14-12=2
	
14-12=2
	
16-0=16
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	 12
	
	
	
	 14
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	 
	4
	 42
	
	
	8
	1
	8
	
	0
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	F2
	
	 X
	
	
	
	 X
	
	8
	
	X
	
	X
	60
	8-4=4
	8-4=4
	8-4=4
	0
	0
	
	
	
	
	
	
	
	14
	
	10
	
	
	
	
	
	
	
	
	
	
F3
	8
	15
	6
	27
	4
	
X
	
	
X
	
	42
	0
	 6
	
90
	
8-6=2
	
 8-6=2
	
10-6=4
	
10-6=4
	
10-0=10
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
Dem
	
15
	
69
	
36
	
18
	
42
	
140
	Σ=3 20
	
12-8=4	6-4=2	14-12=2	14-8=6	10-8=2	0
	12-8=4
	6-4=2
	14-12=2
	0
	10-8=2
	0
	0
	6-4=2
	14-12=2
	0
	10-8=2
	0
	0
	14-6=8
	0
	0
	16-10=6
	0
	0
	 0 
	0
	0
	16-10=6
	0
CUSTO=B31*C31+D29*E29+D31*E31+F27*G27+H29*I29+J31*K31=1446
VB=X13=36; X16=134; X22=42; X24=18; X31=15; X32=27; X35=42; X36=6 
VNB=X11=0; X12=0; X14=0; X15=0; X21=0; X23=0; X25=0; X26=0; X33=0;X34=0
b.Calcule a solução ótima a partir da solução inicial de a.
	
	
D1
	
D2
	
D3
	
D4
	
D5
	
D6
	Oferta
	
F1
	
16
	
X
	
14
	
X
	
12
	
36
	
12
	
X
	
16
	
X
	
0
	
134
	
170
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
F2
	
12
	
X
	
4
	
42
	
14
	
X
	
8
	
18
	
8
	
X
	
0
	
X
	
60
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
F3
	
8
	
15
	
6
	
27
	
4
	
X
	
14
	
X
	
10
	
42
	
0
	
6
	
90
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	Dem.
	
15
	
69
	
36
	
18
	
42
	
140
	Σ=3 20
	X1 1
	X11-X16-36-X31-X11
	C=B47-L47+L51-B51=8
	X1 2
	X12-X16-X36-X32-X12
	C=D47-L47+L51-D51=8
	X1 5
	X15-X16-X36-X35-X15
	C=J47-L47+L51-J51=6
	X2 1
	X21-X22-X32-X31-X21
	C=B49-D49+D51-B51=6
	X2 3
	X23-X13-X16-X36-X32-X22- X23
	C=F49-F47+L47-L51+D51- D49=4
	X2 5
	X25-X35-X32-X22-X25
	C=J49-J51+D51-D49
	X2 6
	X26-X36-X32-X22-X26
	C=L49-L51+D51-D49=2
	X3 4
	X34-X32-X22-X24-X34
	C=H51-D51+D49-H49=4
C=B51*C51+D49*E49+D51*E51+F47*G47+H49*I49+J51*K51=1446
 X13=36; X16=134; X22=42; X24=18; X31=15; X32=27; 
 X35=42; X36=6
 X11=0; X12=0; X14=0; X15=0; X21=0; X23=0; X25=0; 
X26=0; X33=0; X34=0
5. No quadro de transporte a seguir, a quarta linha mostra as necessidades nos destinos e a quarta coluna as disponibilidades nas origens. Os outros dados representam custos unitários de transporte das origens para os respectivos destinos.
	10
	15
	20
	40
	12
	25
	18
	100
	16
	14
	24
	10
	50
	40
	60
	 
 
Determinar o plano de transporte que minimiza o custo total das transferências. Use o método do canto noroeste para a solução inicial.