| 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 avaliação ao longo do período de ensino-aprendizagem consistirá em duas frequências (F1 ,F2) presenciais. Cada frequência será cotada para 10 valores.
A nota cumulativa das provas (N1) é a soma das duas frequências: N1= F1+F2
Se a nota cumulativa for superior a 9,5 (N1 >= 9,5) o aluno terá de fazer uma prova oral (PO) .
A nota final do período de ensino-aprendizagem (N) será a média aritmética da nota cumulativa das provas e da prova oral N=(N1+PO)/2
A nota mínima para admissão ao exame é de 4 valores.
Em exame, todos os alunos com nota superior ou igual a 9.5 serão convocados para uma prova oral cotada a 20 valores. A nota final será a média aritmética da classificação do exame escrito e da prova oral.
Os estudantes com estatuto especial têm regras próprias definidas pelo regulamento académico.
|
|
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
|