Pesquisa Operacional II

Prévia do material em texto

Pesquisa Operacional II modulo 1
1. O abastecimento de água de uma localidade do município do Rio de Janeiro é feito diretamente por meio de uma estação de abastecimento. Devido a trabalhos de manutenção, o abastecimento terá de ser realizado indiretamente por meio de outras localidades e poderá ser representado pela seguinte rede:
O nó 1 representa a estação de abastecimento e o nó 8 indica a localidade que se pretende abastecer. Os nós 2 a 7 correspondem às localidades a partir das quais pode ser feito o abastecimento. O valor associado a cada arco (i,j) indica a quantidade, em m3 por segundo, de água que pode ir diretamente de i para j.
Com o objetivo de analisar possíveis descontinuidades no abastecimento da localidade 8, os serviços municipalizados pretendem determinar a quantidade máxima de água que pode chegar indiretamente a essa localidade, que é:
71.
106.
113.
100.
2. A Motocicletas S.A. possui três fábricas, que estão localizadas em Cuiabá, Santo André e Florianópolis. A produção deve ser entregue em Recife, Salvador e Fortaleza. Que quantidade de vértices e arestas o grafo terá?
3 vértices e 3 arestas.
6 vértices e 6 arestas.
6 vértices e 18 arestas.
6 vértices e 9 arestas.
3. Observe os dados a seguir:
G = (V(G), E(G), 
G)
Onde:
V(G) = {v1, v2, v3, v4, v5}
E(G) = {e1, e2, e3, e4, e5, e6, e7, e8}
G (e1) = (v1, v2)
G (e2) = (v2, v3)
G (e3) = (v3, v5)
G (e4) = (v3, v4)
G (e5) = (v2, v4)
G (e6) = (v4, v5)
G (e7) = (v2, v5)
G (e8) = (v1, v5)
O grafo terá:
5 vértices e 8 arestas.
5 vértices e 40 arestas.
8 vértices e 5 arestas.
40 vértices e 8 arestas.
4. Em uma rede social, sabemos que:
• Antônio é amigo de Camila, Beto, Carlos e Dalva.
• Camila é amiga de Bruna e Diogo.
• Bruna é amiga de Camila, Ana e Diogo.
• Diogo é amigo de Ana, Bruna e Dalva.
• Carlos é amigo de Antônio e Diogo.
• Dalva é amiga de Antônio, Beto e Carlos.
• Beto é amigo de Antônio e Dalva.
• Ana é amiga de Diogo e Bruna.
Com base nestas informações, podemos afirmar que existem quantos relacionamentos interpessoais?
8.
12.
6.
10.
5. A área de comunicação do Governo Federal deseja imprimir 4.000.000 de mapas da região Nordeste do Brasil, em substituição ao modelo atual, como mostra a figura a seguir:
Mapa da região Nordeste do Brasil
Mapa da região Nordeste do Brasil
Em função dos gastos com a pandemia de Covid-19, deseja-se utilizar o menor número possível de cores. Como regra, uma ou mais cores podem ser repetidas, porém estados que tenham divisa entre si deverão ter cores diferentes. Com quantas cores será a nova solução?
3.
4.
5.
6.
6. Analise o grafo a seguir:
A árvore de caminhos mínimos a partir do vértice D, que passa por todos os demais, é igual a:
16.
17.
18.
19.
1. Analise o grafo a seguir:
O menor caminho entre os vértices a e m é igual a (os dados estão em quilômetros):
142.
156.
159.
189.
2. Analise o grafo a seguir. As medidas estão em quilômetros.
Considerando que não será obrigatória a passagem por todos os nós, qual é a distância mínima a ser percorrida partindo do nó 0 (zero) ao nó 5 (cinco)?
72.
74.
67.
61.
1. O grafo a seguir apresenta os bairros de uma cidade, onde uma empresa de telecomunicações deseja implantar uma rede de fibra ótica:
O objetivo é descobrir a menor quantidade de cabo em quilômetros que possa atender a todos os bairros, que é igual a:
216.
146.
181.
102.
2. Uma companhia de fornecimento de gás liquefeito de petróleo pretende expandir sua rede para os municípios da grande Florianópolis a partir de sua central:
Como a tubulação terá seu custo em função de seu comprimento, quantos quilômetros de tubos a empresa deverá comprar para atender todos os municípios a um custo mínimo?
82.
68.
72.
40.
Comentário
A alternativa correta é "C".
Pelos algoritmos estudados, temos:
3. Considere o grafo a seguir, no qual os valores representam as distâncias entre as localidades:
Qual é a distância total para que a ligação entre as localidades envolva a mínima distância possível?
39.
37.
32.
36.
4. Um condomínio residencial com 12 casas de alto padrão está analisando a instalação de uma Estação de Tratamento de Água (ETA), a fim de poder desativar as fossas sanitárias de cada unidade habitacional. Sabendo que a distância entre as casas é apresentada no grafo a seguir, o objetivo é montar uma rede de esgoto:
A ETA será instalada no final do condomínio. A distância até as três primeiras casas é de 100 metros. A melhor rede que representará a menor utilização de tubulações é a seguinte:
resposta correta
5. O grafo a seguir representa todas as possibilidades para que 16 transistores sejam soldados em uma placa de circuito impresso por uma soldadora robotizada.
Os valores representam o tempo em segundos de deslocamento da cabeça de solda. Qual é o menor tempo de deslocamento para que a tarefa seja concluída?
32.
38.
42.
30.
6. A prefeitura deseja instalar ciclovias conectando os bairros, mas não tem recursos para ligar todos entre si. O grafo a seguir apresenta as possíveis ligações e a distância em quilômetros:
Partindo do ponto CE (centro do município), qual é a melhor árvore geradora mínima?
resposta correta
1. Veja um exemplo de otimização de distribuição de sinal em redes.
Um sinal é gerado em um ponto da rede, transita codificado até pontos de decodificação e é distribuído aos usuários. O serviço de decodificação tem custos diferentes em cada ponto em virtude de características de demanda e operação nesses pontos. Distintas configurações de distribuição têm seu custo calculado pelo custo do caminho percorrido mais o custo do serviço de decodificação.
Um provedor de internet está reestruturando sua rede e recebeu a sugestão de montar a estrutura especificada a seguir:
Como quer otimizar a instalação com menor cumprimento de fibra ótica, tendo como premissa que todos os computadores precisam estar conectados, exceto o servidor e os computadores das pontas, quantos equipamentos deverá ter a rede? Os números representam a distância sugerida entre os equipamentos pelo fornecedor.
7.
6.
2.
5.
Comentário
Parabéns! A alternativa "A" está correta.
Vamos analisar o grafo, estudar o problema apresentado e identificar como foram montados todos os caminhos com as menores arestas para encontrar a melhor solução. Pelo algoritmo de Prim, temos:
2. O grafo a seguir apresenta várias localidades ligadas por estradas vicinais de terra em uma macrorregião.
O governo estadual estuda asfaltar os acessos, mas não tem recursos para todos. A Secretaria de Infraestrutura deseja que todos as localidades tenham acesso por asfalto, com o menor gasto com quilômetros contratados da empreiteira. O contrato deverá ser feito para o asfaltamento de quantos quilômetros?
33.
35.
31.
29.
Comentário
Parabéns! A alternativa "C" está correta.
Vamos analisar o grafo, estudar o problema apresentado e identificar como foram montados todos os caminhos com as menores arestas para encontrar a melhor solução. Pelo algoritmo de Kruskal, temos:
1. Analise o grafo a seguir:
Qual é o menor caminho?
AB, BD, DF, DE, CE.
AB, AC, BF, BD, FE.
AB, AC, BD, DF, DE.
AB, AC, BD, BF, FE.
Comentário
A alternativa correta é "C".
Pelo método do Dijkstra, temos:
2. Uma companhia de fornecimento de gás liquefeito de petróleo pretende expandir sua rede para os municípios da grande Florianópolis a partir de sua central:
Como a tubulação terá seu custo em função do comprimento, quantos quilômetros de tubos a empresa deverá comprar, utilizando o algoritmo de Dijkstra, para atender todos os municípios a um custo mínimo?
82.
68.
72.
40.
3. Considere o seguinte grafo, no qual os valores representam as distâncias entra as localidades:
18.
28.
19.
14.
4. Um condomínio residencial com 12 casas de alto padrão está analisando a instalação de uma Estação de Tratamento de Água (ETA), a fim de poder desativar as fossas sanitárias de cada unidade habitacional. O objetivo é montar uma rede de esgoto, sabendo que a distância entre as casas é apresentada no grafo a seguir:
A ETA será instalada no final do condomínio. A distância até as três primeiras casas é de 100 metros.A rede que representará a menor utilização de tubulações é a seguinte:
15.
24.
19.
16.
Comentário
A alternativa correta é "D".
Pelo método de Dijkstra, temos:
5. O grafo a seguir representa todas as possibilidades para que 16 transistores sejam soldados em uma placa de circuito impresso por uma soldadora robotizada:
Os valores representam o tempo de deslocamento em segundos da cabeça de solda. Assista ao vídeo para descobrir qual é o menor tempo de deslocamento para que a tarefa seja concluída.
32.
38.
42.
30.
6. O grafo a seguir apresenta os postos de saúde localizados em uma macrorregião:
O governo estadual possui um centro de distribuição de medicamentos (local 3) e deseja determinar a menor quilometragem que seus veículos percorrerão para entregar medicamentos aos postos de saúde. Para chegar ao posto 11, qual é a distância a ser percorrida?
6.
7.
8.
9.
Comentário
A alternativa "C" está correta.
Assista ao vídeo para descobrir.
Problema do caminho mínimo.
1. Observe as afirmações a seguir:
I. O método de Dijkstra apresenta o caminho da força bruta.
II. Os métodos de Dijkstra e de Kruskal têm como solução árvores geradoras diferentes.
III. Os métodos de Dijkstra e de Prim têm como solução árvores geradoras iguais.
IV. No método de Kruskal, a distância percorrida até o nó 8 foi igual a 12.
Estão corretas as afirmativas:
I e II.
II e III.
III e IV.
II e IV.
Comentário
Parabéns! A alternativa "B" está correta.
Vamos entender como formar, a partir de um ponto de saída, a árvore geradora mínima. Veja como foram montadas, passo a passo, as alternativas para a solução:
Método de Prim
Método de Kruskal
Método de Dijkstra
2. Observe as afirmações a seguir:
I. O método de Dijkstra é conhecido como uma aplicação de força bruta para encontrar o melhor resultado.
II. Se partimos, por exemplo, do nó “6”, o algoritmo de Dijkstra mostrará uma árvore diferente da árvore do nó “1”.
III. O método de Dijkstra tem como solução uma árvore geradora.
IV. Para a determinação do caminho mínimo, o método Dijkstra é o mais eficiente.
Estão corretas as afirmativas:
I e II.
II e III.
III e IV.
II e IV.
Comentário
Parabéns! A alternativa "B" está correta.
Vamos entender como formar, a partir de um ponto de saída, a árvore geradora mínima. Veja como foram montadas, passo a passo, as alternativas para a solução:
Método de Prim
Método de Kruskal
Método de Dijkstra
image7.jpeg
image8.jpeg
image9.jpeg
image10.jpeg
image11.jpeg
image12.jpeg
image1.jpeg
image2.jpeg
image3.jpeg
image4.jpeg
image5.jpeg
image6.jpeg