Questões da Prova CESGRANRIO - 2010 - Petrobras - Analista de Pesquisa Operacional Júnior

Em Teoria dos Jogos, uma das clássicas hipóteses é de que os jogadores tomem decisões

Existem algoritmos de busca local estocástica em que a função passo está implementada em dois estágios. No primeiro estágio, uma solução vizinha s’ da solução candidata corrente s é selecionada uniformemente e depois é aceita, ou não, de acordo com a função de probabilidade: p(T,s,s’) = 1, se f(s’)  ≤ f(s); ou p(T,s,s’) = exp( (f(s)-f(s’))/T ), caso contrário, onde T é um parâmetro denominado temperatura e f é a função avaliação. Quanto ao emprego desse critério, conhecido como condição de Metropolis, tem-se que

Sejam S o conjunto de busca, N a relação de vizinhança e g a função avaliação. De um pseudoalgoritmo de busca local estocástica retiram-se os seguintes comandos:

determine N(s) = {s’ ∈ S | (s, s’) ∈ N};

determine I*(s) = {s’  ∈ N(s) | g(s’) = g*}, onde g* = min{g(s’) | s’ ∈ N(s)}; s’:= escolha aleatória segundo uma distribuição uniforme em I*(s) não vazio.

Uma alternativa para aumentar a rapidez dos algoritmos de busca local estocástica é selecionar o próximo passo de maneira mais eficiente. Neste contexto, o mecanismo de seleção do passo de busca do algoritmo, cujos comandos foram destacados acima, usa a estratégia de seleção

O procedimento troca de r arestas (r-exchange) é uma das heurísticas de maior sucesso em obter uma solução aproximadamente ótima para o problema do caixeiro-viajante com n vértices. Em relação a esse procedimento, considere as afirmativas a seguir.

I - A partir de um ciclo Hamiltoniano H, o procedimento retira r arestas de H, produzindo r caminhos desconexos e os reconecta usando arestas diferentes daquelas retiradas, produzindo uma nova rota H’.

II - De um ciclo Hamiltoniano H é produzido um novo ciclo H’, o qual difere de H em exatamente r arestas, as demais (n-r) arestas coincidem.

III - Caso o custo de H’, produzido a partir da troca de r arestas de um ciclo Hamiltoniano H, seja maior que o custo de H, então H é substituído por H’, senão um novo conjunto de r arestas de H é selecionado para troca.

IV - O processo de troca de r arestas é repetido até que nenhuma melhora adicional seja alcançada.

V - O procedimento r-exchange termina em um ótimo global, chamado de r-ótimo ou r-opt.

São corretas APENAS as afirmativas

Para comprar um carro novo, foram identificados 4 modelos das indústrias A, B, C e D. A decisão será tomada d acordo com preço e consumo de combustível. É evidente que a preferência é por um carro mais barato que consuma menos combustível. Nesse caso, tem-se um problema com 4 alternativas e 2 critérios. As características dos 4 modelos são apresentadas através dos pares de coordenadas A=(36,8), B=(35,7), C=(34,8) e D=(35,9), onde a primeira coordenada refere-se ao preço (dado emR$ 1.000,00) e a segunda refere-se ao consumo decombustível (dado em litro por quilômetro). Em relação ao conjunto viável, conclui-se que