PESQUISA OPERACIONAL II

Prévia do material em texto

PESQUISA OPERACIONAL II
	
	PROBLEMAS DE CONEXÃO
	 
		
	
		1.
		A figura 1a a seguir apresenta um grafo cujo vértice D corresponde a um depósito, e os demais vértices correspondem a locais onde serão feitas entregas a partir desse depósito. Os valores sobre os arcos correspondem à distância entre esses pontos. Veja:
Uma rota deve ser definida partindo do depósito D, passando por todos os pontos de entrega e retornando ao depósito. Buscando minimizar a distância total a ser percorrida, utilizou-se uma heurística do problema do caixeiro-viajante, que compreende a formação de "subtour e tour", agregando um vértice a cada iteração. Em determinada iteração, chegou-se à subtour, apresentada na figura 1b, onde os vértices C2 e C3, além do depósito, já fazem parte da subtour.
Dando continuidade ao procedimento para busca da solução, deve-se, na próxima iteração, incluir na subtour o vértice:
	
	
	
	C4 entre os vértices C3 e C2
	
	
	C1 entre os vértices C2 e C3
	
	
	C4 entre os vértices D e C3
	
	
	C4 entre os vértices C2 e D
	
	
	C1 entre os vértices D e C2
	
Explicação:
A resposta correta é: C4 entre os vértices C3 e C2
	
	
	 
		
	
		2.
		Um viajante deve visitar clientes instalados em 6 cidades da Península Ibérica. Procura-se determinar qual o percurso mais econômico, tendo em atenção, exclusivamente, as distâncias entre as cidades. A tabela a seguir apresenta essas distâncias em quilômetros:
O viajante, neste momento, está em Faro. A melhor rota que deve ser seguida pelo viajante é:
	
	
	
	1582
	
	
	1435
	
	
	1586
	
	
	1798
	
	
	1799
	
Explicação:
	
	
	FLUXOS E REDES
	 
		
	
		3.
		Temos então o seguinte problema para solucionar. A SBF inicial será? 
	
	
	
	Guarulhos-São Paulo: 5, Guarulhos-Salvador:15, Campinas-Rio de Janeiro:10, Taubaté-Rio de Janeiro: 5, Taubaté-Salvador:10
	
	
	Guarulhos-São Paulo: 10, Guarulhos-Salvador:5, Campinas-Rio de Janeiro:10, Taubaté-Rio de Janeiro: 5, Taubaté-Salvador:5
	
	
	Guarulhos-São Paulo: 15, Guarulhos-Rio de Janeiro:5, Campinas-Salvador:25, Taubaté-Rio de Janeiro: 20
	
	
	Guarulhos-São Paulo: 15, Guarulhos-Rio de Janeiro:5, Campinas-Rio de Janeiro:10, Taubaté-Rio de Janeiro: 5, Taubaté-Salvador:25
	
	
	Guarulhos-São Paulo: 10, Guarulhos-Rio de Janeiro:5, Campinas-Salvador:25, Taubaté-Rio de Janeiro: 25
	
Explicação:
A resposta correta é: Guarulhos-São Paulo: 15, Guarulhos-Rio de Janeiro:5, Campinas-Rio de Janeiro:10, Taubaté-Rio de Janeiro: 5, Taubaté-Salvador:25
	
	
	 
		
	
		4.
		Construa o caminho Crítico do nó A para o nó E no seguinte grafo:
	
	
	
	A-B-E-F
	
	
	A-C-E-F
	
	
	A-B-D-F
	
	
	A-B-D-E-F
	
	
	A-C-D-F
	
Explicação:
A resposta correta é: A - C - E - F
	
	
	PROBLEMA DO CAIXEIRO VIAJANTE
	 
		
	
		5.
		Dado o grafo a seguir, utilizando o método do vértice adjacente mais próximo, a distância total a ser percorrida será?
 
	
	
	
	58
	
	
	64
	
	
	60
	
	
	45
	
	
	47
	
Explicação:
A resposta correta é: 60.
	
	
	 
		
	
		6.
		Considere o grafo a seguir apresentado em uma tabela de distâncias entre localidades:
Utilizando o método da inserção com o maior afastamento, a distância a ser percorrida no primeiro passo do método será:
	
	
	
	5278
	
	
	9158
	
	
	3254
	
	
	5156
	
	
	1448
	
Explicação:
A resposta correta é: 9158.
	
	
	ANÁLISE MULTICRITÉRIO À DECISÃO
	 
		
	
		7.
		Considere o problema de decisão caracterizado pela matriz de resultados em que, para todos os atributos, exceto A1, os valores mais altos são os preferidos (os atributos A2, A3 e A4 são medidos em uma escala de 1 a 10). Considere concordância e discordância iguais a 50%.
Nesse caso, podemos afirmar que:
	
	
	
	A alternativa X2 é a mais importante.
	
	
	A alternativa X4 é a mais importante.
	
	
	A alternativa X3 é a mais importante.
	
	
	Todas alternativas têm mesmo grau de importância.
	
	
	As alternativas X2 e X3 têm o mesmo grau de importância.
	
Explicação:
A resposta correta é: A alternativa X4 é a mais importante.
	
	
	 
		
	
		8.
		Uma tecelagem de tecidos para decoração está estudando modernizar seus teares e, para isso, está analisando quatro fornecedores. O departamento de compras, em conjunto com setor operacional, levantou três critérios qualitativos para a análise, em uma escala de 1 a 10, em que 10 representa a melhor avaliação. Considerando que deverá haver, entre os critérios, uma concordância superior a 70% e uma discordância inferior a 40%, qual a tear você recomendaria?
 
	
	
	
	Tear 1
	
	
	Tear 3
	
	
	Tear 4
	
	
	Poderiam ser os teares 2 e 3, pois apresentam a mesma performance.
	
	
	Tear 2
	
Explicação:
A resposta correta é: Tear 1.
	
	
	PROGRAMAÇÃO MATEMÁTICA
	 
		
	
		9.
		A tabela, a seguir, apresenta o número de falhas/hora de determinado componente. Utilizando todos os pontos da amostra, qual o polinômio interpolador?
 
	
	
	
	P(x) = 48 - 24(x - 0) + 7,5(x - 0)(x - 1) - 2,17(x - 0)(x - 1)(x - 2) + 0,67(x - 0)(x - 1)(x - 2)(x - 3).
	
	
	P(x) = 32 - 24(x - 0) + 9,3(x - 0)(x - 1) ¿ 3,12(x - 0)(x - 1)(x - 2) + 4,67(x - 0)(x - 1)(x - 2)(x - 3).
	
	
	P(x) = -25 - 12(x - 0) - 9,3(x - 0)(x - 1) + 3,12(x - 0)(x - 1)(x - 2) + 4,67(x - 0)(x - 1)(x - 2)(x - 3).
	
	
	P(x) = 32 - 24(x - 0) + 9,3(x - 0)(x - 1).
	
	
	P(x) = 48 - 24(x - 0) + 7,5(x - 0)(x - 1) -2,17(x - 0)(x - 1)(x - 2)
	
Explicação:
A resposta correta é: P(x) = 48 - 24(x - 0) + 7,5(x - 0)(x - 1) - 2,17(x - 0)(x - 1)(x - 2) + 0,67(x - 0)(x - 1)(x - 2)(x - 3).
	
	
	 
		
	
		10.
		Utilizando o método de Branch and Bound, quais os valores de x1 e x2 que resolvem o modelo a seguir?
Maximizar Z = x1 + 3x2
s.a.
3x1 + 2x2 ≤≤ 180
x1 ≤≤ 40
x1 ≤≤ 60
x2 ≥≥ 10
x1 + x2 ≥≥ 20
x1 e x2 ∈∈ Z+
	
	
	
	x1 = 40 e x2 = 10
	
	
	x1 = 0 e x2 = 90
	
	
	x1 = 20 e x2 = 60
	
	
	x1 = 10 e x2 = 40
	
	
	x1 = 0 e x2 = 60
	
Explicação:
A resposta correta é: x1 = 0 e x2 = 90.