Código |
13935
|
Ano |
3
|
Semestre |
S1
|
Créditos ECTS |
6
|
Carga Horária |
TP(60H)
|
Área Científica |
Matemática
|
Objectivos de Aprendizagem |
1) Distinguir conceitos elementares da Teoria de Grafos; 2) Modelar problemas em Programação Linear Inteira; 3) Balizar valores óptimos desconhecidos; 4) Diferenciar problemas de Optimização em Redes; 5) Modelar problemas em Redes; 6) Aplicar e distinguir algoritmos de Optimização em Redes; 7) Diferenciar problemas de Optimização Combinatória; 8) Aplicar e diferenciar heurísticas para problemas de Optimização Combinatória.
|
Conteúdos programáticos |
I. Introdução a) Grafos e Redes: conceitos elementares b) Formulações em Programação Linear Inteira c) Relaxação Linear vs Heurísticas
II. Optimização em Redes a) Problema do Caminho Mais Curto Definição e formulação Princípio de optimalidade Algoritmos de rótulos temporários e de rótulos definitivos Aplicações b) Problema de Fluxo Máximo Definição e formulação Princípio de optimalidade Teorema de Fluxo Máximo/Corte de Capacidade Mínima Algoritmo de Ford-Fulkerson Casos particulares Aplicações c) Problema de Fluxo de Custo Mínimo Definição e formulação Algoritmo Simplex Casos particulares Aplicações III. Optimização Combinatória a) Problema de Saco-Mochila Definição e formulação Variantes e heurísticas Aplicações b) Problema do Caixeiro Viajante e Problema do Carteiro-Chinês i. Definições e formulações ii. Heurísticas iii. Aplicações c) Problemas de Cobertura-Empacotamento, Problema de Partição e Problema de Localização i. Definições e formulações ii. Heurísticas iii. Aplicações
|
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 do professor, acompanhada de exemplos, e com o diálogo com os alunos, a quem são fornecidas notas escritas pelo professor. A parte prática das aulas assenta na resolução de exercícios, tanto de forma acompanhada como autónoma. A avaliação realizada ao longo do período de ensino-aprendizagem consistirá em duas provas escritas. O estudante poderá ainda realizar um exame final.
|
Bibliografia principal |
- Ahuja, R., Magnanti, T., Orlin, J. (1993). Network Flows: Theory, Algorithms, and Applications. Pearson. - Bazaraa, M., Jarvis, J., Sherali, H. (2010). Linear Programming and Network Flows. Wiley. - Lawler, E. (1976, 2011). Combinatorial Optimization: Networks and Matroids. Dover. - Papadimitriou, C., Steiglitz, K. (1998). Combinatorial optimization: algorithms and complexity. Dover. - Wolsey, L. (1998). Integer Programming. Wiley.
|
Língua |
Português
|