Questão FC624264
Um grupo de técnicos deve ser enviado ao Oriente Médio para participar de um evento. A proximidade da data do evento impede que seus participantes viajem no mesmo voo. Dessa forma,
Outros Tópicos de Estatística
CESGRANRIO · 2012
Um grupo de técnicos deve ser enviado ao Oriente Médio para participar de um evento. A proximidade da data do evento impede que seus participantes viajem no mesmo voo. Dessa forma, foram identificadas todas as opções de rede de conexões de transporte aéreo, considerando a disponibilidade de lugares nos voos e o tempo de viagem. Para chegar à melhor solução, tendo como objetivo fazer com que todos cheguem ao local do evento, mesmo que em rotas diferentes, porém com o menor tempo total de viagem para o grupo, deve-se utilizar um algoritmo de
- árvore mínima
- Min Max-Min Sum
- fluxo máximo
- fluxo a custo mínimo
- caminho mínimo
Mostrar resposta e comentário
Gabarito
D
Comentário do professor
O enunciado descreve um problema clássico de redes em que cada voo corresponde a uma aresta com capacidade (lugares disponíveis) e um custo (tempo de viagem). O objetivo é enviar um determinado número de técnicos até o destino de forma que todos cheguem, possivelmente por rotas diferentes, minimizando o tempo total do grupo. Isso caracteriza o problema de fluxo a custo mínimo.
Formalmente, busca‑se minimizar \(\sum_e c_e x_e\) sujeito às equações de conservação de fluxo em cada nó e às restrições \(0 \le x_e \le u_e\), garantindo que o fluxo total enviado iguale o número de técnicos. As variáveis \(x_e\) representam quantos passageiros seguem por cada trecho.
Algoritmos como o de caminhos sucessivos de menor custo, cancelamento de ciclos ou o network simplex resolvem esse modelo de forma eficiente, produzindo a alocação de assentos e rotas que minimiza o tempo agregado do grupo.
Conteúdo do catálogo FC Concursos · Atualizado em