Teoria da Optimização

Mestrado em Matemática
1º semestre - 2004/05


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: 14 de Fevereiro de 2005

  1. Todos os textos de apoio foram corrigidos. Foram acrescentados exercicios e as resoluções dos exercícios que sairam em exame.
  2. Teresa: a sua nota de exame é 15 em 20. Pode vir ver o exame quando quiser.
    Os textos de apoio foram actualizados. Diversas gralhas foram corrigidas e alguns exercícios foram acrescentados.
  3. A primeira versão do trabalho de síntese deve ser entregue até ao dia 26 de Novembro, sem falta.
  4. Código matlab para a resolução de problemas lineares através do método simplex preparado por Helder Jorge Rodrigues Inácio
    em 29/10/2004 disponível no ficheiro pl_matlab.tar.gz.
  5. O exame de época de recurso será dia 3 de Fevereiro.
  6. Teresa Grilo: Os apontamentos de que lhe falei estão aqui.
    As páginas que interessam são as 37-39 (representação minimal de um cone poliedral).
  7. No exercício 62 deve acrescentar-se 'não degenerada' a seguir a '(23)'.
  8. Já podem fazer os exercícios 16 e 17 do Texto de Apoio 2.
  9. Já disponho de enunciados para o artigo científico do qual devem fazer um relatório de síntese. Podem aparecer no meu gabinete quando quiserem.
  10. Os exercícios 16 e 17 do Texto de Apoio 1 usam conceitos que serão introduzidos mais tarde. Por isso, não é oportuna a sua resolução.
  11. Bem-vindo à página da disciplina.

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

Tipo de Texto Ficheiro Título
Folha Introdutória (.pdf) Informaçao sobre programa, bibliografia e avaliação
Texto de Apoio 1 (.pdf) Modelos de Optimização Linear, Não Linear e Inteira
Texto de Apoio 2 (.pdf) Optimização Linear
Texto de Apoio 3 (.pdf) Optimização Não Linear
Texto de Apoio 4 (.pdf) Optimização Inteira
Texto de Apoio 5 (.pdf) Problema de afectação

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

Setembro: 

DIA AULA SUMÁRIO TPC
20 1 Modelos de Optimização Linear, Não Linear e Inteira.
Motivação para o estudo dos tópicos da disciplina. 		TA1: 8
24 2 (Aula de substituição da aula do dia 21 de Setembro, 11.00-12.30 na sala 3.2)
Optimização Linear: Introdução à Dualidade; Teorema da Dualidade Fraca. 		TA2: 2, 12
27 3 Teorema da Solvabilidade de Sistemas de Inequações Lineares (Eliminação de Fourier).
Optimização Linear: Teorema da Dualidade Forte.		 TA2: 19, 25
28 4 Teorema Fundamental (da Programação Linear) e Teorema da Complementaridade de Folgas.
Optimização Linear: outras formas de Dualidade. 		TA2: 30, 33.

Outubro: 

DIA AULA SUMÁRIO TPC
4 Tolerância de ponto para o funcionalismo público
5   Feriado Nacional  
11 5 Conjuntos Convexos. Introdução ao estudo de poliedros (pontos extremos). TA2: 42, 46, 56.
TA2: 57(T), 58(H).
12 6 Optimização Linear: Método de Simplex. TA2: 48, 62
15 7 (Aula de substituição da aula do dia 3 de Janeiro, 11.00-12.30 na sala 3.3)
Optimização Linear: Fase 1 do Método de Simplex.		 TA2: 70, 74
18 8 Optimização Linear: Convergência finita do Método Simplex. TA2: 90
19 9 Optimização Não Linear: Funções convexas e sua caracterização diferencial. TA3: 5, 7
25 10 Optimização Não Linear: Existência de minimizante para um modelo de programação não linear; Condições suficientes de optimalidade para problemas convexos. TA3: 20, 23, 26, 31
26 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. TA3: 34, 36, 41, 48

Novembro: 

DIA AULA SUMÁRIO TPC
1 Feriado Nacional
2 12 Aula de Apoio à resolução de exercícios de Optimização Linear e Não Linear.  
5 13 (Aula de substituição da aula do dia 4 de Janeiro, 11.00-12.30 na sala 3.3)
Optimização Não Linear: Condições necessárias de optimalidade de primeira ordem; Caracterização algébrica do cone tangente; Teorema de Liusternik.		 TA3: 55(H), 56, 57(T)
8 14 Optimização Não Linear: Demonstração do Teorema de Karush-Kuhn-Tucker.
Optimização Inteira: Exemplos de alguns problemas-tipo. Revisão de alguns conceitos elementares de Teoria de Grafos.		 TA4: 2
9 15 Optimização Inteira: Formulações. TA4: 5
15 16 Complementos de Teoria de Poliedros: Teorema de Weyl-Minkowski. TA4: 44, 57
16 17 Complementos de Teoria de Poliedros: caracterização do espaço afim e da sua dimensão em termos do conjunto das igualdades de um poliedro. TA4: 51
22 18 Complementos de Teoria de Poliedros: Faces, pontos extremos e facetas. TA4: 65, 67, 68
23 19 Optimização Inteira: Forma Normal de Hermite de uma matriz e sistemas de equações lineares Diofantinas.  
26 20 (Aula de substituição da aula do dia 30 de Novembro, 11.00-12.30 na sala 3.3)
Optimização Inteira: Teorema de Dirichelet para aproximação Diofantina.
Optimização Inteira: Invólucro Convexo Inteiro.		 TA4: 27, 33, 74
29 21 Optimização Inteira: Integralidade Dual Total (TDI) e sua aplicação aos emparelhamentos de um grafo.

Dezembro: 

DIA AULA SUMÁRIO TPC
6 22 Optimização Inteira: Unimodularidade Total (TU) e sua aplicação à matriz de incidência vértice-aresta de um grafo, dirigido ou não. TA4: 112, 113, 125
7 23 Optimização Inteira: Teorema do Fluxo Máximo - Corte Mínimo. TA4: 136, 140
13 24 Optimização Inteira: Submodularidade.  
14 25 Optimização Inteira: Caracterização do poliedro das florestas e do poliedro das árvores geradoras de um grafo.  
17   Exame de época normal (1ª parte, às 14h30min na sala 2.5)  
20   Data limite para entrega da segunda parte do exame de época normal  

Fevereiro: 

DIA AULA SUMÁRIO TPC
3   Exame de época de recurso (1ª parte, na sala)  
7   Data limite para entrega da segunda parte do exame de época de recurso  

Ligações:

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