Menu Conteúdo Rodapé
  1. Início
  2. Cursos
  3. Matemática e Aplicações
  4. Otimização

Otimização

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
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
Data da última atualização: 2020-06-16
As cookies utilizadas neste sítio web não recolhem informação pessoal que permitam a sua identificação. Ao continuar está a aceitar a política de cookies.