Optimização Discreta

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

Faculdade de Ciências e Tecnologia
Universidade de Coimbra

João Soares

Email:jsoares@mat.uc.pt

Gabinete 6.4 do Dep. Matemática

Tel. 239 791 154

Horário de Atendimento: 
Quartas das 11.30 às 13.00 (Gabinete 6.4@DM)

DIA

AULA

SUMÁRIO

18

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.

20

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. Comparação de formulações.

25

3

Teoria Poliedral: Conceitos de invólucro convexo, invólucro cónico e invólucro afim e sua caracterização algébrica; Teorema da Alternativa para sistemas de desigualdades lineares e sua demonstração através da eliminação de Fourrier-Motzkin.

27

4

Teoria Poliedral: Desigualdades válidas e polaridade. Independência afim e dimensão; Faces, pontos extremos e facetas; Representação minimal de um poliedro.

DIA

AULA

SUMÁRIO

3

5

Matrizes Totalmente Unimodulares: definição e propriedades. Exemplos e contra-exemplos no âmbito de problemas em grafos.

5

6

Aplicações da Unimodularidade Total: Teorema de Koenig-Egervary e Teorema do Casamento.

10

7

Aplicações da Unimodularidade Total: Teorema do Fluxo Máximo-Corte Mínimo e Teorema de Menger.

12

8

Aplicações da Unimodularidade Total: Caminho mais curto e questões relacionadas com a sua formulação algébrica.

17

9

Caracterizações alternativas da Unimodularidade Total.

19

10

Sistemas de equações lineares Diofantinas: existência e unicidade da Forma Normal de Hermite de uma matriz de racionais.

24

11

Resolução de sistemas de equações lineares Diofantinas.

26

12

O algoritmo de Euclides. Teorema de Dirichelet para Aproximação Diofantina.

31

13

Aproximação Diofantina: o método das fracções contínuas.

DIA

AULA

SUMÁRIO

2

14

Bases de Hilbert. O invólucro inteiro e sua caracterização nalguns casos mais simples.

7

-

Férias da Páscoa

9

-

Férias da Páscoa

14

15

Sistemas de desigualdades TDI. O poliedro dos emparelhamentos. Teorema de Cunningham-Marsh (enunciado apenas).

16

16

Teorema de Berge para a caracterização de um emparelhamento de máxima cardinalidade. Algoritmo dos caminhos alternados para grafos bipartidos. Discussão do algortimo de Edmonds para o caso geral.

21

17

O método Húngaro para o problema de Afectação.

23

18

Validade e propriedades do método Húngaro.

28

19

Funções submodulares. Exemplos e caracterizações alternativas.

30

20

O algoritmo Guloso para optimização submodular.

DIA

AULA

SUMÁRIO

5

21

Funções características submodulares. Caracterização poliédrica de árvores e florestas em grafos não orientados.

7

22

Resolução de exercícios práticos (número reduzido de alunos).

12

Professor falta

14

23

Matroides: definição e exemplos.

19

24

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. Problema da mochila 0-1 (do inglês, 0-1 knapsack): resolução via programação dinâmica, complexidade computacional.

21

25

Método de enumeração exaustiva (do inglês, Branch-and-Bound): motivação e aplicação a um exemplo.

26

26

Método de enumeração exaustiva: regras práticas para ramificação e selecção do subproblema seguinte.

28

27

Desigualdades válidas para Programação Inteira: Introdução; o algoritmo de Gomory e alguns exemplos de aplicação.

DIA

AULA

SUMÁRIO

2

28

Resoluções de exames de anos anteriores.