Grátis: O problema do caixeiro viajante (TSP) é um dos mais clássicos e estudados na área de otimização combinatória e teoria dos grafos. O TSP é um proble... – Questões Respondidas

Inglês

Outros

O problema do caixeiro viajante (TSP) é um dos mais clássicos e estudados na área de otimização combinatória e teoria dos grafos. O TSP é um problema NP-difícil, o que significa que, à medida que o número de cidades aumenta, a complexidade do problema cresce exponencialmente. Imagine que um caixeiro viajante precisa visitar cinco cidades diferentes em um dia. Ele deseja planejar a rota mais curta possível, começando e terminando na mesma cidade.
Qual das alternativas representa o problema descrito?
a. Otimização da velocidade do caixeiro viajante ao realizar entregas nas cidades.
b. Minimização do número de cidades visitadas pelo caixeiro viajante.
c. Minimização da distância percorrida pelo caixeiro viajante ao visitar cada cidade apenas uma vez.
d. Maximização da distância percorrida pelo caixeiro viajante ao visitar cada cidade duas vezes.
e. Determinação da melhor cidade para estabelecer um novo ponto de distribuição.

Desafios Para o Conhecimento

há 3 meses

Desafios Para o Conhecimento

há 3 meses

ATIVIDADE ONLINE 1 - AV12026_3_ Revisão da tentativa _ Graduação EAD

UNIFCV

Respostas

Ed

há 3 meses

O problema do caixeiro viajante (TSP) consiste em encontrar a rota mais curta possível que permita ao caixeiro visitar todas as cidades uma única vez e retornar à cidade de origem. Analisando as alternativas: a) Otimização da velocidade do caixeiro viajante ao realizar entregas nas cidades. — Incorreto, pois o foco não é a velocidade, mas a rota. b) Minimização do número de cidades visitadas pelo caixeiro viajante. — Incorreto, pois o caixeiro deve visitar todas as cidades. c) Minimização da distância percorrida pelo caixeiro viajante ao visitar cada cidade apenas uma vez. — Correto, é a definição do TSP. d) Maximização da distância percorrida pelo caixeiro viajante ao visitar cada cidade duas vezes. — Incorreto, o objetivo é minimizar a distância e visitar cada cidade uma vez. e) Determinação da melhor cidade para estabelecer um novo ponto de distribuição. — Incorreto, não é o problema do TSP. Resposta correta: c) Minimização da distância percorrida pelo caixeiro viajante ao visitar cada cidade apenas uma vez.

Essa resposta te ajudou?

0

0

Ainda não achou a resposta?

Integrado com os principais modelos de IA do mercado
Respostas em segundos
IA treinada para estudantes brasileiros.

Evolua sua forma de estudar

Cadastre-se ou realize login

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

ATIVIDADE ONLINE 1 - AV12026_3_ Revisão da tentativa _ Graduação EAD

UNIFCV

Mais perguntas desse material

O método de PO convencional é construir um modelo matemático que represente a base do problema. Ao explorar a natureza dos modelos em geral e dos modelos matemáticos em particular, observa-se que a medida de desempenho apropriada, que pode ser o lucro, por exemplo, pode ser representada por uma função matemática dessas variáveis de decisão.
Podemos admitir quanto aos modelos matemáticos que:
I) O modelo deve ser capaz de prever as causas relativos à escolha de opções alternativas com precisão suficiente de modo que favoreça uma decisão sensata.
II) Os modelos matemáticos apresentam muitas desvantagens se comparados a uma descrição verbal do problema.
III) O modelo matemático é base para o emprego de técnicas matemáticas e computacionais potentes para analisar questões dando previsibilidade de resultados.
a. I e II estão corretas
b. Somente a III está correta
c. Somente a II está correta
d. Somente a I está correta
e. II e III estão corretas

A principal ação na Pesquisa Operacional (PO) é de aplicar métodos matemáticos, mas não é a única frente. A análise matemática normalmente representa apenas uma parte do esforço total necessário.
Quanto as etapas de aplicação da PO, pode-se contemplar:
I. Definir o problema de interesse e coletar dados. Formular modelo matemático para representar o problema.
II. Desenvolver procedimento computacional a fim de derivar soluções para o problema com base no modelo. Testar o modelo e aperfeiçoá-lo.
III. Preparar para aplicação contínua do modelo conforme prescrito pela gerência e implementá-lo.
a. I e II estão corretas.
b. Todas estão corretas.
c. Somente II está correta.
d. I e III estão corretas.
e. Somente III está correta.

A utilização de algoritmos para solução de problemas que envolvem centenas ou milhares de variáveis pode ser incrivelmente eficiente. Na prática, os algoritmos normalmente são executados por pacotes de softwares comerciais.
Qual das alternativas apresenta softwares que podem ser utilizados para formular problemas de PO?
a. Courseware de PO e Lindo.
b. Lindo e Solver do Excel.
c. Solver do Excel e Windows.
d. Windows e Linux.
e. Oracle e Courseware de PO.

Uma das aplicações mais comuns de modelos de otimização é encontrar quantos produtos produzir de cada tipo, de modo a maximizar o lucro ou minimizar o custo. Para isso, se faz necessário conhecer as variáveis de decisão, o objetivo e as restrições do problema. Considere a seguinte situação: Uma fábrica de bancos e balanços deseja maximizar seus lucros decidindo quantas unidades dos diferentes tipos de produtos (bancos e balanços) deve produzir. Eles têm limitações de capacidade de produção e demanda variável para cada tipo de produto, o que torna fundamental determinar a quantidade ideal de cada produto a ser fabricada para otimizar seus recursos e atender à demanda do mercado.
Nesse problema, quais seriam as variáveis de decisão?
a. Preço de venda de bancos e balanços.
b. Custo de bancos e balanços.
c. Quantidade de matéria-prima a ser gasta em bancos e balanços produzidos.
d. Quantidade de bancos e balanços a serem produzidos.
e. Quantidade de mão de obra direta a ser gasta em bancos e balanços produzidos.

O método de PO pode ser tomado como base em diversos modelos. Podemos admitir a utilização de:
I) Modelo de Simulação; Heurística; Otimização Clássica.
II) Modelo de Estoque; Programação Dinâmica; Modelo de Cooperação.
III) Modelo de Sequenciamento; Modelo de Alocação; Modelo de Filas.
A. Somente a I está correto.
B. Somente a II está correto.
C. Somente a III está correto.
D. II e III estão corretos.
E. I e III estão corretos.

Em uma situação em que serviços são prestados a clientes, como em uma esmaltaria, princípios e técnicas de PO podem ser aplicados para modelar e analisar o processo de atendimento. Esse tipo de análise é útil para prever tempos de espera, otimizar o uso dos recursos e melhorar a satisfação dos clientes. Considere o seguinte caso: Se, em uma esmaltaria, temos duas cadeiras de atendimento que estão ocupadas. Cada atendimento leva 25 minutos, e a taxa de chegada de clientes é de um cliente a cada 15 minutos. Qual modelo melhor representará esse problema? A. Modelo de competição. B. Programação de rotas. C. Modelo de filas. D. Modelo de sequenciamento. E. Modelo de alocação.

Na PO, o objetivo é encontrar a solução ótima para problemas complexos, utilizando técnicas matemáticas e analíticas avançadas.
O que significa uma solução ótima em problemas de PO?
a. É a solução que rapidamente resolve o problema.
b. É a solução que não requer ajustes ou modificações futuras.
c. É a solução que melhor atinge o objetivo principal do problema.
d. É a solução que agrada a todos os stakeholders envolvidos.
e. É a solução que utiliza todas as técnicas disponíveis.

Quanto a definição do problema e a coleta de dados, na PO existem alguns pontos de devem ser seguidos.
Podemos admitir que:
I) Se deve estudar o sistema relevante e desenvolver um enunciado bem definido do problema a ser considerado.
II) Deve-se determinar objetivos apropriados, mas, quanto as restrições não são necessárias serem levantadas, sendo mais relevante saber do que pode ser feito em relação a área alvo a ser estudada e interrelação com demais áreas da organização.
III) Verificar caminhos alternativos, limites de tempo para tomada de decisão. A questão é importante pois se torna difícil obter resposta correta de uma questão mal elaborada ou incorreta.
a. Nenhuma.
b. Somente a II.
c. II e III.
d. I e II.
e. Somente a I.