Otimização

Imagem d@ Fernando Manuel Tavares Pereira [Ficheiro Local]
Fernando Manuel Tavares Pereira
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
Esta informação promove os seguintes Objetivos de Desenvolvimento Sustentável da ONU:
Garantir o acesso à educação inclusiva, de qualidade e equitativa, e promover oportunidades de aprendizagem ao longo da vida para todos