| Código |
15620
|
| Ano |
1
|
| Semestre |
S2
|
| Créditos ECTS |
8
|
| Carga Horária |
TP(60H)
|
| Área Científica |
Matemática
|
|
Objectivos de Aprendizagem |
Pretende-se que os alunos caracterizem, modelem e resolvam problemas clássicos de Otimização e, ainda, que adaptem os métodos abordados para esses problemas na resolução exata e/ou aproximada de novos problemas.
No final da Unidade Curricular de Investigação Operacional o estudante deve ser capaz de:
1) Distinguir conceitos elementares da Teoria de Grafos e Complexidade Computacional;
2) Modelar problemas em Programação Linear Inteira;
3) Balizar valores ótimos desconhecidos;
4) Diferenciar problemas clássicos de Otimização em Redes;
5) Modelar problemas em Redes;
6) Aplicar e distinguir algoritmos de Otimização em Redes;
7) Diferenciar problemas clássicos de Otimização Combinatória;
8) Aplicar e diferenciar heurísticas para problemas de Otimização Combinatória.
|
|
Conteúdos programáticos |
I. Introdução
a) Conceitos Elementares sobre Grafos
- Conceitos fundamentais
- Representações de grafos
b) Conceitos Elementares sobre Complexidade Computacional
- Problemas e instâncias de um problema
- Dimensão de uma instância
- Algoritmos e sua eficiência
c) Formulações em Programação Linear Inteira
- Programas lineares inteiros, binários e mistos
- A explosão combinatorial
- Formulações alternativas, boas e ideais
d) Otimalidade, Relaxações e Limites
- Relaxações linear, combinatória e lagrangiana
- Dualidade
- Heurísticas
II. Otimização em Redes
Definição, formulação, aplicações e algoritmos exatos do/para o:
a) Problema do Caminho Mais Curto
b) Problema de Fluxo Máximo
c) Problema de Fluxo de Custo Mínimo
III. Otimização Combinatória
Definição, formulação, aplicações e heurísticas do(s)/para o(s):
a) Problema de Saco-Mochila
b) Problema do Caixeiro Viajante e Problema do Carteiro-Chinês
c) Problemas de Cobertura-Empacotamento, Problema de Partição e Problema de Localização
|
|
Metodologias de Ensino e Critérios de Avaliação |
A metodologia de ensino baseia-se em aulas teórico-práticas. A parte teórica decorre com exposição dos conteúdos, frequentemente motivados por exemplos/aplicações. Serão fornecidas notas escritas aos alunos. A parte prática das aulas assenta na resolução de exercícios, tanto de forma acompanhada, com justificações detalhadas, como autónoma.
A avaliação realizada ao longo do período de ensino-aprendizagem consistirá na realização e apresentação de um trabalho que cobrirá os tópicos principais do programa.
|
|
Bibliografia principal |
- Wolsey, L. (1998). Integer Programming. Wiley.
- de Carvalho, Valério. Optimização Combinatória. Universidade do Minho.
- de Carvalho, Valério. Programação Inteira. Universidade do Minho.
- Ahuja, R., Magnanti, T., Orlin, J. (1993). Network Flows: Theory, Algorithms, and Applications. Pearson.
- Lawler, E. (1976, 2011). Combinatorial Optimization: Networks and Matroids. Dover.
- Papadimitriou, C., Steiglitz, K. (1998). Combinatorial optimization: algorithms and complexity. Dover.
- Bazaraa, M., Jarvis, J., Sherali, H. (2010). Linear Programming and Network Flows. Wiley.
|
| Língua |
Português
|