Optimização Discreta

Licenciatura Matemática, Ramo Científico;
Especialização em Matemática Aplicada
2º semestre - 2002/03


Faculdade de Ciências e Tecnologia
Universidade de Coimbra

Docente:

João Soares Email:jsoares@mat.uc.pt
Gabinete 6.4 do Dep. Matemática Tel. 239 791 154
Horário de Atendimento: 
Segundas das 14.30 às 15.30 (Gabinete 6.4@DM)		  

Sumários das aulas teóricas

Fevereiro: 

DIA AULA SUMÁRIO
24 1 Informações sobre a disciplina. Formulação de problemas de programação inteira: problema da Afectação, problema da Mochila 0-1, problema da Cobertura, problema do Caixeiro Viajante Não Simétrico.
27 2 Formulação de problemas de programação inteira mista: restrições disjunctivas, problema da Localização de Armazéns sem restrições de capacidade, custos fixos. Formulação ideal. Comparar formulações. Revisão de conceitos de Programação Linear. Formulação da união de dois polítopos.

Março: 

DIA AULA SUMÁRIO
3 3 Obtenção de limites primais: algoritmos guloso para o problema da mochila e de pesquisa local para o problema da localização de armazens. Obtenção de limites duais: relaxação linear, relaxação combinatória.
7 4 Obtenção de limites duais para o valor óptimo de um problema inteiro: dualidade lagrangeana e dualidade.
10 5 Matrizes Totalmente Unimodulares: definição e propriedades. Aplicações da Unimodularidade Total a problemas definidos em grafos orientados: fluxo de custo mínimo e fluxo máximo entre dois vértices.
14 6 Condição necessária e suficiente para que a matriz de incidência de um grafo não dirigido seja TU.
Algoritmo guloso para o problema da árvore geradora de peso máximo num grafo não orientado.
17 7 Algoritmo guloso para optimização submodular.
21 8 Introdução ao estudo de matroides.
Caracterização algébrica (ou poliédrica) de árvores e florestas de grafos não orientados.
24 9 Conjunto de restrições Totalmente Dual Integral (TDI): definição e propriedades.
28 10 Emparelhamentos de máxima cardinalidade.
Algoritmo para determinar o emparelhamento de máxima cardinalidade num grafo bipartido não orientado. 
31 11 Redução do problema de determinar o emparelhamento de peso méximo a um problema de afectação.
O método Húngaro para o emparelhamento de peso máximo.

Abril: 

DIA AULA SUMÁRIO
4 12 Redução do problema do Carteiro Chinês num grafo não orientado ao problema de determinar o emparelhamento perfeito de menor peso num grafo completo (exercício 4 do capítulo 4 do livro adoptado).
7 13 Sistemas de Equações Lineares Diofantinas: existência e unicidade da Forma Normal de Hermite de uma matriz racional.
11 14 Sistemas de Equações Lineares Diofantinas: algoritmo prático de resolução.
14   Férias da Páscoa
18   Férias da Páscoa
21   Tolerância de ponto
25   Feriado
28 15 Conceitos e aplicações de Combinatória Poliedral: independência afim, invólucro afim, dimensão.

Maio: 

DIA AULA SUMÁRIO
2   Professor falta
5   Tolerância de ponto
9 16 Conceitos e aplicações de Combinatória Poliedral: faces e facetas.
12 17 Problema de loteamento (do inglês, lot-sizing) sem restrições de capacidade: definição do problema, resolução via programação dinâmica, complexidade computacional.
16 18 Problema da mochila 0-1 (do inglês, 0-1 knapsack): resolução via programação dinâmica, complexidade computacional.
19 19 Método de enumeração exaustiva (do inglês, Branch-and-Bound): motivação e aplicação a um exemplo.
23 20 Método de enumeração exaustiva: regras práticas para ramificação e selecção do subproblema seguinte.
26 21 Desigualdades válidas para Programação Inteira: Introdução; o algoritmo de Gomory e alguns exemplos de aplicação.
30 22 Desigualdades válidas para Programação Inteira Mista: as desigualdades válidas da classe Mixed Integer Rounding.
Algoritmo de Gomory para Programação Inteira Mista.

Junho: 

DIA AULA SUMÁRIO
2 23 Apresentação dos trabalhos preparados pelos alunos
6 24 Apresentação dos trabalhos preparados pelos alunos

última actualização em 6 de Junho de 2003 (todos os sumários com datas posteriores são apenas perspectivados)