Pesquisa Operacional II - Tema 3

Prévia do material em texto

Tema 3 – Pesquisa Operacional II 
1-O grafo a seguir apresenta todas os possíveis caminhos que um cliclista pode percorrer em seu treinamento. Admitindo que sua residência fica no nó “1” e que deseja após o treinamento retornar ao mesmo nó, quantas possibilidades de rotas ele poderá percorrer?
a-5.040
b-40.320
c-720
d-4.580
2. Um distribuidor de produtos farmacêuticos deseja saber qual a menor distância que seu caminhão deverá percorrer para fazer entrega para seus clientes a partir de seu centro de distribuição, conforme o grafo a seguir. O veículo deverá visitar um cliente apenas uma vez (distâncias em quilômetros).
a-7.740
b-6.685
c-5.810
d-7.645
3. Digamos que temos um grafo com n nós. Em cada nó existe uma máquina para ser reparada, e existe apenas um mecânico. Dado o tempo requerido pelo mecânico para viajar entre nós, pretende-se encontrar um circuito que minimize o tempo total de espera para todas as máquinas, sabendo-se que começa no nó 1 e deve retornar ao mesmo nó.
a-20
b-21
c-22
d-24
4. Dada a tabela, a seguir, que representa a distância entre as localidades, utilizando o método do vértice adjacente mais próximo, partindo do nó “A”, qual a menor distância a ser percorrida?
a-474
b-418
c-368
d-456
5. Numa região, existem 5 cidades que designamos pelas letras A, B, C, D, E. As ligações existentes entre essas cidades e as respectivas distâncias estão representadas no grafo abaixo:
Suponha que você pretende visitar todas essas cidades partindo de “A” e voltar à cidade inicial, percorrendo a menor distância possível. Obtenha uma solução para a escolha do melhor trajeto. Ele será:
a-30
b-31
c-32
d-33
6. O grafo, a seguir, representa os locais nos quais uma máquina automática de solda deverá realizar a soldagem de transistores em uma placa de computador. Os tempos colocados são em segundos, representando o deslocamento da cabeça de solda. Qual o menor tempo para realizar o percurso total, sendo o ponto inicial o nó “A”?
A árvore de caminhos mínimos a partir do vértice D e passando por todos os demais é igual a:
a-12
b-14
c-15
d-17
1- Uma comissão de exames nacionais pretende calendarizar os testes, de modo que os alunos não tenham duas avaliações no mesmo dia. A tabela que se segue mostra os exames que os alunos A, B, C e D têm de realizar. Considerando que cada aluno não pode fazer mais do que um por dia, diga qual é o número mínimo de dias necessários para a realização dos exames e apresente a distribuição destes pelos variados dias.
a-2
b-3
c-4
d-5
2-. Cinco localidades, designadas pelas letras A, B, C, D, E, estão ligadas entre si por diversas estradas e as suas respectivas distâncias são:
[AB] 7 km, [AE] 17 km, [BC] 10 km, [BD] 21 km,
[CE] 8 km, [CD] 12 km, ED] 33 km, [EB] 11 km
Nesta região, será construída uma canalização para abastecimento de água, e pretendemos planejar a obra de modo a usar a menor quantidade possível de tubos. Admita que só pode construir tubulações de acordo com as ligações e as distâncias acima indicadas. Apresente a árvore abrangente mínima correspondente e o seu comprimento total. .
a-
b-
c-
d-
Modulo 2
1-O grafo a seguir apresenta os bairros de uma cidade onde uma empresa de telecomunicações deseja implantar uma rede de fibra óptica:
O objetivo é descobrir a menor quantidade de cabo em quilômetros que possa atender a todos os bairros, que é igual a:
a-216
b-146
c-249
d-102
2. Uma companhia de petróleo pretende expandir sua rede de tubulação de gás para os municípios do grande Rio a partir de sua central de:
Como a tubulação terá seu custo em função de seu comprimento, quantos quilômetros de tubos a empresa deverá comprar de modo a atender a todos os municípios a um custo mínimo?
a-82
b-102
c-72
d-98
3. Considere o grafo a seguir, em que os valores representam as distâncias entre as localidades.
Qual é a distância total para a ligação entre as localidades, de modo que seja mínima, partindo do nó “1” e retornando ao mesmo?
a-39
b-40
c-32
d-36
4. Um condomínio residencial em construção com 12 casas de alto padrão está analisando a instalação de uma rede de distribuição de água. O objetivo é montar uma rede, sabendo que a distância entre as casas é apresentada no grafo a seguir. Para o circuito ser fechado, deverá iniciar na casa “1” e retornar a casa “1”. Qual a proposta de ligação que gastará aproximadamente a menor quantidade de tubulação? Observação: Para calcular as ligações cruzadas, utilize a seguinte fórmula:
a-39
b-40
c-32
d-36
5. Suponhamos que o Marcelo consiga incrementar o seu negócio e tenha um leque de clientes espalhados por dez cidades. O custo das viagens entre as cidades está representado abaixo, em forma de uma tabela. Saindo de “A”, qual a menor distância que ele percorrerá para visitar seus clientes e retornar ao ponto de saída?
a-2.847
b-3.784
c-2.229
d-3.146
6. A prefeitura deseja instalar ciclovias conectando os bairros, mas não tem recursos para conectar todos entre si. O grafo a seguir apresenta as possíveis ligações e a distância em quilômetros. A ciclovia deve partir do Centro e retornar ao Centro de modo a obter-se um ciclo completo. A menor distância para esta ciclovia será de?
a-246
b-222
c-237
d-216
1- A tabela abaixo indica as distancias aproximadas, em milhas, entre sete locais de Marte, onde cientistas da NASA pensam haver maior probabilidade de encontrar vestígios de vida. É planejado uma viagem que colocará um robô em Marte, aterrissando em “A”. O robô deverá percorrer cada um dos locais, recolher amostras de solo e regressar a “A”, de onde um foguete trará as amostras para a Terra de forma a serem analisadas. Como encontrar um ciclo ótimo no grafo correspondente?
a-20.100
b-18.130
c-21.400
d-19.260
2. Fernanda terá uma manhã muito atarefada! Tem de ir: à Escola, depositar um cheque no Banco, comprar beterrabas na mercearia, visitar uma amiga no hospital, além de ir ao açougue comprar meio quilo de carne moída. Ela terá de sair de casa e regressar ao fim da manhã. Na seguinte planta, estão marcados a casa da Fernanda e os locais onde ela deve ir. Cada quarteirão tem aproximadamente 1 quilômetro de comprimento e não é possível atravessá-los diagonalmente. Para fazer o ciclo completo, ela percorrerá quantos quilômetros?
a-33
b-37
c-28
d-25
Módulo 3
1-Analise o grafo a seguir:
Qual é o menor caminho pelo método da inserção com menor encargo?
a-AB, BD, BD, DF, DE
b-AD, DF, FB, BE, EC
c-AB, AC, BD, DF, DE
d-AB, AC, BD, BF, FE
2-Sobre o grafo a seguir, que é a solução pelo método da inserção com menor encargo, assinale a opção em que é apresentada a descrição em vértices (V) e arestas (A).
a-V = {1, 2, 3, 4, 5, 6}
A = {(2, 4), (2, 3), (2, 5), (3, 6), (1, 5)}
b-V = {2, 4, 1, 3, 6, 5}
A = {(4, 2), (1, 3), (5, 2), (6, 3), (5, 3)}
c-V = {1, 2, 3, 4, 5, 6}
A = {(4, 5), (3, 4), (5, 6), (1, 2), (2, 3)}
d-V = {1, 2, 3, 4, 5, 6}
A = {(4, 2), (3, 1), (5, 1), (6, 2), (5, 3)}
3. Considere o seguinte grafo, no qual os valores representam as distâncias entre as localidades:
Para solucioná-lo pelo método da inserção com menor encargo, você escolheria quais nós?
a-X1, X7, X9
b-X1, X7, X4
c-X7, X4, X5
d-X6, X7, X2
4. Dado o grafo a seguir, e, admitindo que pelo método da inserção com menor encargo escolhamos os nós 1, 4 e 5 como primeiro passo, e que para o passo 2 seja escolhido o nó 2, a distância deste percurso será?
a-16
b-18
c-11
d-15
5. O grafo a seguir representa todas as possibilidades para instalação de antenas para celular em 16 locais.
Se iniciarmos o método da inserção com menor encargo pelos nós 1, 2, 3 no passo 1, para o passo seguinte podemos selecionar o nó:
a-5
b-6
c-7
d-8
6. O grafo a seguir apresenta os postos de saúde localizados em uma macrorregião:
O Governo Estadual tem seu 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 iniciar o método da inserção com menor encargo, você iniciaria pelos nós?
a-1, 2, 6
b-6, 8, 11
c-4, 9, 10
d-4, 8, 10
1-Neste módulo, vocêaprendeu a minimizar um caminho pelo método da inserção com menor encargo. No grafo a seguir, responda às perguntas propostas.
Observe as afirmações a seguir:
I. Não podemos resolver por este método porque nem todos os ciclos estão fechados.
II. O caminho 5, 9, 8 é um ciclo fechado.
III. O caminho 5, 9, 10 é um ciclo fechado.
IV. O caminho 1, 4, 3 é um ciclo fechado.
Estão incorretas as afirmativas:
a-Apenas I
b-I e II
c-III e IV
d-II e IV
2. Observe as afirmações a seguir:
I. O método da inserção com menor encargo é conhecido como uma aplicação de força bruta para encontrar o melhor resultado.
II. O método da inserção com menor encargo nunca possibilitará o caminho ótimo.
III. O grafo apresentado não permite que possamos sair de qualquer nó para achar uma solução pelo método da inserção com menor encargo.
IV. No método da inserção com menor encargo sempre obteremos uma solução, mesmo que não seja a ótima.
Estão corretas as afirmativas:
a-I e II
b-II e III
c-III e IV
d-II e IV
Módulo 4
1.Resolva pelo método de maior afastamento. O melhor caminho terá a seguinte distância:
a-99
b-106
c-93
d-87
2.Sobre o grafo a seguir, que é a solução pelo método da inserção com maior afastamento, o melhor caminho terá a seguinte distância:
a-47
b-69
c-63
d-49
3. Considere o seguinte grafo em que os valores representam as distâncias entre as localidades:
Para solucioná-lo pelo método da inserção com maior afastamento, você escolheria que nós?
a-25
b-20
c-24
d-28
4. Podemos afirmar sobre o método da inserção com maior afastamento:
I. Devemos procurar o par de locais com o ciclo de maior custo no início do processo.
II. Devemos procurar o par de locais com o ciclo de menor custo no início do processo.
III. Devemos verificar a distância de todos os nós do caminho para todos os nós que ainda não estão no caminho. Para cada nó fora do caminho, anotar a menor distância.
IV. Devemos verificar a distância de todos os nós do caminho para todos os nós que ainda não estão no caminho. Para cada nó fora do caminho, anotar a maior distância.
Estão corretas as afirmações:
a-I e III
b-II e IV
c-I e IV
d-II e III
5. Podemos afirmar sobre o método da inserção com maior afastamento:
I. Sempre encontramos a solução ótima.
II. É um método simples e é fácil encontrar a solução.
III. É um método simples, porém encontrar a solução pode se tornar complexa.
IV. O cálculo dos ciclos envolve a agregação de novos nós.
Estão corretas as afirmações:
a-I e III
b-III e IV
c-I e IV
d-II e IV
6. O grafo da figura representa uma rede rodoviária tendo associada a cada uma das arestas a distância (km) entre os vértices extremos. Uma viatura de uma empresa situada em "A" necessita entregar encomendas em B, C, D, E (clientes) e regressar à empresa. Se pretender passar uma e só uma vez em cada vértice e percorrer a menor distância total, qual será a distância percorrida?
a-53
b-47
c-38
d-35
1.No grafo a seguir, pelo método do maior afastamento, o nó inicial para a primeira iteração será?
a-4-7-4
b-3-5-3
c-7-9-7
d-2-9-6
2. No grafo orientado a seguir, pelo método do maior afastamento, a solução será?
a-34
b-25
c-32
d-29
Pública