|
| Lição nº 1 21/02/2005 |
||
| Apresentação, Bibliografia e Avaliação. Motivação para os problemas que serão estudados na disciplina. |
||
 |
||
| Lição nº 2 22/02/2005 |
||
| Capítulo 1: Introdução à programação optimização discreta. ====== Formulação de alguns problemas de optimização discreta |
||
|
||
| Lição nº 3 28/02/2005 |
||
| Capítulo 1: Introdução à programação optimização discreta. ====== Equivalência entre o problema do emparelhamento de peso mínimo e o problema do emparelhamento perfeito de peso mínimo. |
||
|
||
| Lição nº 4 07/03/2005 |
||
| Capítulo 2: Emparelhamentos óptimos ====== 2.1 - Emparelhamentos e caminhos alternantes |
||
|
||
| Lição nº 5 08/03/2005 |
||
| Capítulo 2: Emparelhamentos óptimos ====== 2.2 - Algoritmo para determinar emparelhamentos máximos em grafos bipartidos. Exemplificação do algoritmo. |
||
|
||
| Lição nº 6 14/03/2005 |
||
| Capítulo 2: Emparelhamentos óptimos ====== 2.3 - Algoritmo para determinar emparelhamentos máximos em grafos não bipartidos (algoritmo de Edmonds). |
||
|
||
| Lição nº 7 15/03/2005 |
||
| Capítulo 2: Emparelhamentos óptimos ====== 2.3 - Algoritmo de Edmonds (cont.). |
||
|
||
| Lição nº 8 29/03/2005 |
||
| Capítulo 2: Emparelhamentos óptimos ====== 2.4 - Algoritmo para determinar emparelhamentos de peso mínimo em grafos bipartidos (problema da afectação) - Método Húngaro. |
||
|
||
| Lição nº 9 04/04/2005 |
||
| Capítulo 3: Teoría Poliedral ======= Introdução. Conceitos básicos. |
||
|
||
| Lição nº 10 05/04/2005 |
||
| Capítulo 3: Teoría Poliedral (cont.) ======= Involucro convexo, cónico, afim. Exemplos. Teoremas sobre a solubilidade de sistemas Ax = b e Ax <= b. |
||
|
||
| Lição nº 11 11/04/2005 |
||
| Capítulo 3: Teoría Poliedral (cont.) ======= Método de eliminação de Fourier-Motzkin (cont) Resolução de exercícios |
||
|
||
| Lição nº 12 12/04/2005 |
||
| Capítulo 3: Teoría Poliedral (cont.) ======= Demonstração de alguns resultados teóricos (P = conv(V) + coco(D) => P é um poliedro) Definição de finitamente gerado. |
||
|
||
| Lição nº 13 18/04/2005 |
||
| Capítulo 3: Teoría Poliedral (cont.) ======= Desigualdades válidas. Construção do polar(P). Exemplos. Dimensão de poliedros. |
||
|
||
| Lição nº 14 19/04/2005 |
||
| Capítulo 3: Teoría Poliedral (cont.) ======= Independência afim. Demonstração de alguns resultados sobre dimensão de poliedros. |
||
|
||
| Lição nº 15 20/04/2005 |
||
| (Substituição da aula de 21/Março/2005) Capítulo 4: Heurísticas ======= Introdução ao estudo da ordem de complexidade de problemas combinatórios. Classes de problemas polinomiais, NP e NP-completos. Alguns exemplos. |
||
|
||
| Lição nº 16 20/04/2005 |
||
| (Substituição da aula de 22/Março/2005) Capítulo 4: Heurísticas ======= Breve descrição sobre as heurísticas de construção. Alguns exemplos para o problema da mochila e do caminho Hamiltoneano mais curto simétrico (heurística de Christofides, entre outras). Avaliação das heurísticas: tempo de execução, qualidade da solução. |
||
|
||
| Lição nº 17 26/04/2005 |
||
| Capítulo 5: Involucro convexo inteiro ======= Introdução. Alguns conceitos básicos. Demonstração de alguns resultados teóricos. |
||
|
||
| Lição nº 18 02/05/2005 |
||
| Capítulo 5: Involucro convexo inteiro ======= Sistemas de desiguldades totalmente duais inteiras (TDI). Capítulo 6: Método dos planos cortantes ======== Introdução. |
||
|
||
| Lição nº 19 03/05/2005 |
||
| Capítulo 6: Método dos planos cortantes ======== Demonstração de alguns resultados teóricos. Cortes gerais de Gomory Exemplos |
||
|
||
| Lição nº 20 16/05/2005 |
||
| Capítulo 6: Método dos planos cortantes - Revisão ======== Cortes gerais de Gomory (algoritmo fraccionário) Exemplos |
||
|
||
| Lição nº 21 17/05/2005 |
||
| Capítulo 6: Método dos planos cortantes - Revisão ======== Cortes gerais de Gomory (algoritmo inteiro). Plano cortante de Danzing Resolução de exercícios |
||
|
||
| Lição nº 22 23/05/2005 |
||
| Capítulo 7: Método de Branch-and-Bound ======== Descrição da ideia base. Resolução de exercícios. Método de Branch-and-Cut |
||
|
||
| Lição nº 23 24/05/2005 |
||
| Capítulo 8: Relaxação Lagrangeana ======== Descrição do método. Interpretação geométrica. Exemplos. |
||
|
||
| Lição nº 24 30/05/2005 |
||
| Capítulo 8: Relaxação Lagrangeana ======== Aplicação ao problema do trajecto mais curto com restrição. Método da geração de colunas. |
||
|
||
| Lição nº 25 31/05/2005 |
||
| Capítulo 8: Relaxação Lagrangeana ======== Método do subgradiente. Demonstração de alguns resultados teóricos. |
||
|
||
O Professor,
José Luis Esteves dos Santos