| Código |
14794
|
| 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.
Período Lectivo (Ensino-Aprendizagem)
Para um aluno obter aprovação à unidade curricular de Optimização deverá frequentar pelo menos 50% das aulas e ter uma classificação (CEA) superior ou igual a 9,5 valores somando as classificações obtidas nos elementos seguintes:
1º trabalho prático, cotado em 5 valores.
2º trabalho prático, cotado em 5 valores.
Frequência final - 6 de Janeiro de 2022, cotado em 10 valores.
Exames
Neste caso, para um aluno obter aprovação à unidade curricular de Optimização deverá ter uma CEA superior ou igual a 6 valores e ter uma classificação no exame de 1ª chamada ou de recurso.
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
|