Otimização Combinatória
Código
10809
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Matemática
Créditos
6.0
Professor responsável
Isabel Cristina Silva Correia, Ruy Araújo da Costa
Horas semanais
4
Total de horas
56
Língua de ensino
Português
Objectivos
A Optimização Combinatória (OC) é uma área da Matemática Aplicada que combina técnicas da Programação Linear, Teoria de Algoritmos e Cálculo Combinatório para resolver problemas de optimização em domínios discretos. Nesta disciplina começar-se-á por familiarizar os alunos com os problemas clássicos de OC mais referenciados na literatura dada a sua grande aplicabilidade em situações reais. Por se tratarem de problemas de difícil resolução estudar-se-ão técnicas para o cálculo de limites inferiores e superiores para o seu valor óptimo. A incorporação destes limites em algoritmos de tipo enumerativo poderá permitir a determinação do valor óptimo.
Pré-requisitos
Os alunos deverão ter sólidos conhecimenos de Optimização Linear e de Informática (na óptica do utilizador e programação).
Conteúdo
1 - Problemas clássicos de Optimização Combinatória: Caixeiro Viajante, Rotas de Veículos, Cobertura, Partição, Localização, Empacotamento, Sequenciamento e Saco/Mochila.
2 - Complexidade Computacional
3 - Heurísticas
4 - Dualidade Lagrangeana
5 - Algoritmos de Pesquisa em Árvore
6 - Algoritmos de Planos de Corte
Bibliografia
Garey, M. R. e Johnson, D. S. (1979). Computers and Intractability: a Guide to the Teory of NP-Completeness. W. H. Freeman and Company, San Francisco.
Garfinkel, S. R. E Nemhauser, G. L. (1972). Integer Programming. John Wiley & Sons, New York.
Martelo, S. e Toth, P. (1990). Knapsack Problems. Algorithms and Computer Implementations. John Wiley and Sons, Chichester.
Nemhauser, G. L. e Wolsey, L. A. (1999). Integer and Combinatorial Optimization. John Wiley & Sons, New York
Papadimitriou, C. H. e Steiglitz, K. (1982). Combinatorial Optimization: algorithms and complexity. Prentice-Hall, Englewood Cliffs.
Método de ensino
As aulas teórico-práticas decorrem em laboratório computacional.
Método de avaliação
Em Época Normal a avaliação é feita com 4 Testes. Em Época de Recurso é feita com um Exame de 3h.
Exige-se Frequência para que um aluno seja avaliado.