Programação Inteira

Imagem d@ Fernando Manuel Tavares Pereira [Ficheiro Local]
Fernando Manuel Tavares Pereira
Código:
16611
Ano:
2
Semestre:
S2
Créditos ECTS:
6
Carga Horária:
TP(60H)
Área Científica:
Matemática
Objectivos de Aprendizagem:
Pretende-se que os alunos complementem os conhecimentos adquiridos na unidade curricular de Programação Linear com o estudo de problemas de Programação Linear Inteira (PLI). Problemas desta natureza, em que as variáveis são inteiras e/ou binárias têm elevada aplicabilidade e ocorrem frequentemente na vida real. Além disso, uma vez que muitos desses problemas pertencem à classe NP-difícil, torna-se fundamental o estudo de boas formulações para os mesmos, bem como a obtenção eficiente de soluções de boa qualidade, que constituem os dois principais objectivos desta unidade curricular. Mais especificamente, são ainda objectivos:
1) Distinguir conceitos fundamentais de PLI;
2) Modelar problemas em PLI;
3) Diferenciar relaxações de um problema de PLI;
4) Distinguir matrizes (totalmente) unimodulares;
5) Comparar formulações;
6) Determinar desigualdades válidas;
7) Aplicar o método de partição e avaliação;
8) Diferenciar e aplicar heurísticas.
Conteúdos programáticos:
1. Introdução
1.1) Definições e conceitos fundamentais de Programação Linear Inteira (PLI)
1.2) Alguns casos especiais de PLI
1.3) Aplicações de PLI
1.4) Relaxações de um problema de PLI
2. Relaxação Linear
2.1) Definições e resultados preliminares
2.2) Unimodularidade
2.3) Convexificação de um problema de PLI
2.4) Reformulação de um problema de PLI
2.5) Desigualdades válidas e planos de corte
2.6) Dualidade linear
3. Método de Partição e Avaliação
3.1) Introdução
3.2) Partição
3.3) Avaliação
3.4) Questões estratégicas
3.5) Aplicações
4. Métodos Heurísticos
4.1) Introdução e conceitos fundamentais
4.2) Métodos construtivos
4.3) Métodos adaptativos
4.4) Métodos de melhoramento
4.5) Meta-heurísticas
Bibliografia principal:
- Wolsey, L. (1998). Integer Programming. Wiley.
- Beasley, J. (1996). Advances in Linear and Integer Programming. Oxford University Press.
- Lawler, E. (1976, 2011). Combinatorial Optimization: Networks and Matroids. Dover.
- Papadimitriou, C., Steiglitz, K. (1998). Combinatorial optimization: algorithms and complexity. Dover.
Língua:
Português