Teoria da Optimização

Mestrado em Matemática
1º semestre - 2003/04


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
   

Novidades:

Última actualização: 28 de Janeiro de 2004

  1. Exame de época normal disponível hoje (.pdf). Deve entregar resolução até dia 13 de Fevereiro.
  2. Diversos textos de apoio foram corrigidos. No entanto as correções não têm qualquer influência no exame.
  3. Trabalho 7, entregar dia 5 de Dezembro:  ex 15, 31, 38, 41 (do Texto de Apoio 7A).
  4. Lembrete: Deve entregar uma primeira versão do trabalho de síntese até dia 21 de Novembro.
  5. Trabalho 6, entregar dia 24 de Novembro:  ex 13,  9, 16 (do Texto de Apoio 5), ex 13, 17, 18  (do Texto de Apoio 6).
  6. Trabalho 5, entregar dia 11 de Novembro:  ex 2, 3, 6  (do Texto de Apoio 4).
  7. Trabalho 4, entregar dia 4 de Novembro:  ex 5 pg 17, ex 1 pg 20, ex 3 pg 24, ex 9(b) pg 25, ex 4 pg 30  (do Texto de Apoio 3).
  8. Trabalho 3, entregar dia 28 de Outubro:  ex 4 pg 9, ex 6 pg 9, ex 1 pg 14, ex 2 pg 14  (do Texto de Apoio 3).
  9. Trabalho 2, entregar dia 21 de Outubro:  ex 1 pg 19, ex 2 pg 20, ex 1(a) pg 26, ex 6(b) pg 26  (do Texto de Apoio 2).
  10. Trabalho 1, entregar dia 7 de Outubro: ex 2 pg 8, ex 1 pg 11, ex 6 pg 14, ex 5 pg 17, ex 6 pg 17, ex 6 pg 20 (do Texto de Apoio 2).
  11. Descrição do trabalho de síntese aqui.
  12. Exame de Julho de 2003 aqui.
  13. Bem-vindo à página da disciplina.

Textos (distribuídos nas aulas ou disponíveis nesta página):

Tipo de Texto Ficheiro Título Disponível
Folha Introdutória (.pdf) Informaçao sobre programa, bibliografia e avaliação Aula 1
Texto de Apoio 1 (.pdf) Modelos de Optimização Linear, Não Linear e Inteira Aula 2
Texto de Apoio 2 (.pdf) Optimização Linear Aula 2
Texto de Apoio 3 (.pdf) Optimização Não Linear Aula 8
Texto de Apoio 4 (.pdf) Optimização Inteira: Introdução Aula 13
Texto de Apoio 5 (.pdf) Optimização Inteira: Problemas Diofantinos Aula 14
Texto de Apoio 6 (.pdf) Optimização Inteira: Teoria de Poliedros Aula 17
Texto de Apoio 7 (.pdf) Optimização Inteira: Invólucro Convexo Inteiro Aula 17
Texto de Apoio 8 (.pdf) Optimização Inteira: Matrizes Totalmente Unimodulares Aula 17
Texto de Apoio 9 (.pdf) Optimização Inteira: Afectação e Carteiro Chinês Aula 29
Texto de Apoio 10 (.pdf) Optimização Inteira: Submodularidade Aula 26
Texto de Apoio 11 (.pdf) Optimização Inteira: Procedimento de Chvátal-Gomory Aula 28

Sumários (Aulas às 2ª, 10.00-11.30 na sala 5.3, e às 3ª, 14.30-16.00 na sala 5.3):
(todos os sumários com datas posteriores à última actualização desta página são apenas perspectivados)

Setembro: 

DIA AULA SUMÁRIO
15 1 Modelos de Optimização Linear, Não Linear e Inteira. Motivação para os tópicos da disciplina.
16 2 Optimização Linear: Introdução à Dualidade; Teorema da Dualidade Fraca.
22 3 Optimização Linear: Teorema da Solvabilidade de Sistemas de Inequações Lineares; Teorema Fundamental da Programação Linear; Teorema da Complementaridade de Folgas.
23 4 Optimização Linear: Outras formas de Dualidade; Conjuntos Convexos.
29 5 Optimização Linear: Pontos extremos de poliedros e consequências.
30 6 Optimização Linear: Método de Simplex.

Outubro: 

DIA AULA SUMÁRIO
6 7 Optimização Linear: Fase 1 do Método de Simplex; Convergência finita do Método Simplex.
9 8 (aula das 14.30 às 16.00 em substituição da aula do dia 7)
Aula de Apoio à resolução de exercícios de Optimização Linear.
14 8 Optimização Não Linear: Funções convexas e sua caracterização diferencial.
17 10 (aula das 10.00 às 11.30 em substituição da aula do dia 13)
Optimização Não Linear: Condições suficientes de optimalidade para problemas convexos.
20 11 Optimização Não Linear: Condições necessárias de optimalidade para problemas convexos; Teorema de Karush-Kuhn-Tucker; Necessidade de condições de regularidade.
21 12 Optimização Não Linear: Condições necessárias de optimalidade de primeira ordem; Caracterização algébrica do cone tangente; Demonstração do Teorema de Karush-Kuhn-Tucker.
27 13 Optimização Inteira: Exemplos de problemas; Invólucro convexo inteiro.

Novembro: 

DIA AULA SUMÁRIO
3 15 Optimização Inteira: Forma Normal de Hermite.
4 16 (aula das 11.30 às 13.00 em substituição da aula do dia 28)
Aula de Apoio à resolução de exercícios de Optimização Não Linear.
4 16 Optimização Inteira: Sistemas de equações lineares Diofantinas.
10 17 Optimização Inteira: Algoritmo de Euclides e Aproximação Diofantina (Teorema de Dirichelet).
11 18 Optimização Inteira: Complementos de Teoria de Poliedros.
17 19 Resolução de exercícios de Optimização Não Linear.
18 20 Optimização Inteira: Unimodularidade Total.
24 21 Optimização Inteira: Aplicações da Unimodularidade Total à Teoria de Grafos.
25 22 Optimização Inteira: Teorema do Fluxo Máximo - Corte Mínimo.

Dezembro: 

DIA AULA SUMÁRIO
2 23 Optimização Inteira: Caminho Mais Curto.
9 24 (aula suplementar das 11.30 às 13.00 em substituição da aula do dia 1)
Optimização Inteira: Invóluvro Convexo Inteiro.
9 25 Optimização Inteira: Inteirabilidade Dual Total.
15 26 Optimização Inteira: Submodularidade.
16 27 (aula inicia-se às 14 horas)
Optimização Inteira: Matroides.

Janeiro: 

DIA AULA SUMÁRIO
5 28 Optimização Inteira: Procedimento de Chvátal-Gomory.
6 29 (aula inicia-se às 14 horas)
Optimização Inteira: Emparelhamentos e Afectação.
12 30 Optimização Inteira: Obter o emparelhamento de máxima cardinalidade em garfos bipartidos
13 31 (aula inicia-se às 14 horas)
Optimização Inteira: Carteiro Chinês.
15 32 (aula suplementar das 11.30 às 13.00 em substituição da aula do dia 8)
Optimização Inteira: Resolução de exercícios.

Ligações:

  1. Short Math Guide for AMS LaTex here
  2. The Not So Short Introduction to LaTex2e  here.