| 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
|
|
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. A avaliação realizada ao longo do período de ensino-aprendizagem consistirá em duas provas escritas. O estudante poderá ainda realizar um exame final.
|
|
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
|