Exercícios Resolvidos - Tópicos Especiais - PO Pesquisa Operacional

Prévia do material em texto

CENTRO UNIVERSITÁRIO DE BELO HORIZONTE (UNI-BH) 
GABRIEL FILIZZOLA 
 
 
 
 
 
 
TÓPICOS ESPECIAIS B 
Lista 01 
 
 
 
 
 
 
 
 
 
 
 
 
BELO HORIZONTE 
2018 
Lista 01 – Aulas 02 a 05 
Página 2 de 7 
1. O que é um modelo matemático? Como ele pode ser visto? 
Um modelo matemático é uma representação simplificada de uma situação real e deve 
demonstrar a essência do problema, representando as grandezas envolvidas por variáveis e as 
relações de interdependência existentes entre elas através de expressões matemáticas. 
Pode ser visto como uma caixa preta, representando as relações que descrevem a dependência 
das variáveis. 
 
2. Defina um comparativo de modelos, considerando suas características e exemplos. 
 
 
3. Apresente o diagrama da forma geral de modelos. 
 
 
TIPOS CARACTERÍSTICAS EXEMPLOS
Tangível
Compreensão fácil Modelo de aeronaves
Reprodução difícil Modelos de residências
Manipulação difícil Modelo de cidades
Escopo de uso: muito baixo
Intangível
Compreensão difícil Mapas de estradas
Reprodução fácil Velocímeto
Manipulação fácil Gráficos
Escopo de uso: baixo
Intangível
Compreensão mais difícil Modelos de simulação
Reprodução muito fácil Modelos algébricos
Manipulação muito fácil Modelos de planilhas
Escopo de uso: amplo
Físico
Simbólico
Analógico
Lista 01 – Aulas 02 a 05 
Página 3 de 7 
4. Descreva 3 definições de Sistema. 
Sistemas podem ser definidos como “um conjunto de objetos, como pessoas ou máquinas, por 
exemplo, que atuam e interagem com a intenção de alcançar um objetivo ou um propósito 
lógico” [Taylor, 1970]. 
“Um grupo de coisas inter-atuantes e interdependentes que formam um todo unificado. ” 
[Dicionário Webster’s] 
“Uma agregação ou montagem de coisas de tal forma combinada pela natureza ou pelo homem 
que forma um todo integral ou complexo.” [Enciclopédia Americana] 
 
5. Apresente e descreva 2 exemplos clássicos de problemas de otimização combinatória. 
Como exemplos clássicos de problemas de otimização combinatória podemos citar o problema 
do caixeiro viajante e problema da cobertura mínima por conjuntos. 
O Problema do Caixeiro Viajante (PCV) é um problema que tenta determinar a menor rota para 
percorrer uma série de cidades (visitando uma única vez cada uma delas), retornando à cidade 
de origem. 
Já o problema da cobertura mínima por conjuntos consiste em encontrar uma cobertura de 
arestas de tamanho mínimo. 
 
6. Apresente 3 Desafios Computacionais que a otimização combinatória apresenta. 
1. Resolver problemas de otimização combinatória pertencentes a classe NP-hard ou NP-
completo com pouco esforço computacional (tempo de execução). 
2. Encontrar soluções ótimas, ou mesmo aproximadas, para esses tipos de problemas é um 
desafio nem sempre fácil de ser vencido. 
3. Em muitos problemas práticos não há a necessidade de encontrar uma solução 
“teoricamente” ótima. 
 
7. O que é Heurística? Qual sua limitação? Os algoritmos heurísticos são capazes de encontrar 
a solução ótima do problema? Qual objetivo de uma heurística? 
Heurística é uma técnica que melhora a eficiência do processo de busca de soluções de um 
problema. 
Os algoritmos heurísticos não garantem encontrar a solução ótima de um problema, mas são 
capazes de retornar uma solução de qualidade em um tempo adequado para as necessidades da 
aplicação. 
O objetivo de uma heurística é tentar encontrar uma solução “boa” de maneira simples e rápida. 
 
Lista 01 – Aulas 02 a 05 
Página 4 de 7 
8. Cite e descreva as 5 classificações da heurística que foram comentadas em sala. 
Métodos construtivos: processo iterativo que inicia com uma solução vazia e adiciona um novo 
elemento a cada iteração até a obtenção de uma solução. 
Métodos de decomposição: consistem em dividir o problema em subproblemas menores, de 
modo que a resolução de todos os subproblemas possa compor uma solução para o problema 
maior. 
Métodos de redução: identificam algumas características que presumidamente deverá possuir a 
solução ótima e simplifica o problema fixando-se o valor de tais variáveis. 
Manipulação do modelo: modificam o modelo de tal forma que ele fique mais fácil de resolver. 
Ex. relaxação linear, relaxação lagrangeana. 
Métodos de buscas: categoria a qual pertencem a maioria das meta-heurísticas: inicia em uma 
solução (podendo ser obtida a partir de outra heurística) e caminha sobre as soluções vizinhas. 
 
9. Apresente o algoritmo heurístico do vizinho mais próximo. 
 
 
 
10. Descreva, com suas palavras, o algoritmo do vizinho mais próximo. 
O algoritmo do vizinho mais próximo é utilizado para determinar uma solução para o problema 
do problema do caixeiro viajante. Ele gera rapidamente um caminho curto, mas geralmente não 
o ideal. 
 
11. Descreva: 
 
a) Espaço de soluções: conjunto de todas as soluções (viáveis) possíveis (satisfazendo as 
restrições do problema) 
b) Vizinhança: dada uma solução X, os elementos da vizinhança N(x) de X são aquelas soluções y 
que pode ser obtida aplicando uma perturbação elementar sobre X. 
c) Movimento: é uma transição de uma solução para outra solução vizinha. 
Lista 01 – Aulas 02 a 05 
Página 5 de 7 
d) Espaço de busca: conjunto das soluções obtidas por meio de uma vizinhança. 
e) Ótimo local: é uma solução tão boa ou melhor do que qualquer das soluções vizinhas. 
f) Ótimo global (solução ótima): é a melhor solução dentre todos os ótimos locais. 
 
12. Como os algoritmos de busca local são construídos? Cite e descreva os 3 elementos que 
devem ser definidos. 
Os algoritmos de busca são construídos como uma forma de exploração do espaço de busca. 
Partida: solução inicial obtida através de um método construtivo. 
Iteração: melhoria sucessiva da solução corrente através de uma busca na sua vizinhança. 
Parada: primeiro ótimo local encontrado, ou seja, não existe solução vizinha melhor. 
 
13. Qual a dependência dos algoritmos de busca local? Qual o papel da representação de uma 
solução? Quais as formas mais adotadas? 
São dependentes da forma adotada para representar as soluções. 
A representação de uma solução indica quais elementos estão presentes e quais não estão. 
As formas mais adotadas são: vetores de pertinência, combinações e permutações. 
 
14. Descreva e exemplifique “Vetores de pertinência”. 
Vetores onde o mapeamento de cada elemento da solução é feito para cada uma das posições 
(ou dimensões) do vetor. A presença de um determinado elemento na resposta é representada 
pelo 1 na posição correspondente. Sua ausência é representada pelo 0 (ou vice-versa). 
 
15. Descreva e exemplifique a representação baseada em “Combinações”. 
 
 
 
 
Lista 01 – Aulas 02 a 05 
Página 6 de 7 
16. Descreva a representação baseada em “Permutações”. 
Conjuntos contendo exatamente os elementos presentes na resposta (ou exatamente os 
elementos ausentes). 
 
 
17. O que são Metaheuristicas? Como são baseados seus modelos? Quais seus objetivos? 
São modelos gerais que servem como guia para construção de algoritmos heurísticos. 
São baseados na natureza (físicos, biológicos, evolutivos). 
Tem como objetivo superar as falhas da busca local, como por exemplo, o término prematuro em 
um ótimo local. 
 
18. Quais as propriedades desejadas em uma Metaheuristica? 
- Simplicidade 
- Coerência 
- Generalidade 
- Eficácia 
- Eficiência 
- Robustez 
 
19. Apresente o algoritmo genético (diagrama) . Cite e descreva seus termos principais. 
 
 
Lista 01 – Aulas 02 a 05 
Página 7 de 7 
20. Apresente o algoritmo Simulated Annealing e comente qual a sua essência.Simulated Annealing ou (recozimento simulado) é uma meta-heurística para otimização que consiste 
numa técnica de busca local probabilística, e se fundamenta numa analogia com a termodinâmica. 
Como vantagens do AS pode-se citar tanto sua capacidade de resolver problemas de diversos níveis 
de complexidade em várias áreas específicas, quanto sua relativa previsibilidade e simplicidade, uma 
vez que trabalha com poucos parâmetros e envolve operações matemáticas e computacionais 
simples.