.

ET589 - Optimização

Versão do curso: 2007.2
Duração: [17/9/2007]-[24/1/2008]

Assuntos Ministrados

Aula Assunto
1 - 17/9 Apresentação do Curso e Metodologia
2 - 20/9 Conceitos de Programação Matemática; Tipos de Programação [C07, Cap.1]; Desenvolvimento de Modelos [PP87, p.46-49]; Exercícios [S96,p.18]
3 - 24/9 Exemplo de Modelagem: Problema da Dieta com Comentários Históricos [PP87, p.50-54; I02, p.103-105]; Método Gráfico de Solução [PP87, p.58; C07, Cap.3]; Comentários Iniciais sobre Formatação Padrão de um Problema de PL [PP87, p.65-67]
4 - 28/9 Transformação para a Forma Padrão [PP87, p.65-70; C07, Cap.4]; Convexidade [PP87, p.38-42; C07, Cap.2]; Teoremas Fundamentais de Programação Linear [PP87, p.70-76; C07, Cap.5]
5 - 1/10 Simplex: Método Algébrico [PP87, p.77-82], [C07]
6 - 4/10 Simplex: Solução via Quadros (Tableaux) [PP87, p.82-87], [C07, Cap.7]
7 - 8/10 Estudo de uma implementação em MATLAB para Simplex via Quadros [C07, Apen.C]
8 - 11/10 Simplex: Implementação Matricial [C07, Cap.8]
9 - 18/10 Estudo de uma implementação em MATLAB para Simplex (Matricial) [C07, Apen.D]
10 - 25/10 Dualidade: Primal e Dual; Propriedades; Exercícios [PP87, p.146-157]
11 - 29/10 Teorema da Dualidade Fraca, Teorema da Dualidade Forte [PP87, p.157-162]
12 - 1/11 Teorema da Folga Complementar [PP87, p.163-171]
13 - 5/11 Método Dual-Simplex [P87, p.171-177]
14 - 8/11 Leitura
15 - 12/11 1o. Exercício Escolar (Versa sobre Aulas 2-14)
16 - 19/11 Correcção do 1o. EE
17 - 22/11 Expansão em Série de Taylor [Vide qualquer livro de Cálculo]
18 - 26/11 Otimização Irrestrita de Funções de uma Variável: Estudo das Derivadas [C07, Cap.13]; Otimização de Funções Unimodais [C07, Cap.13]; Busca Sequencial: Busca trisseccional [C07, Cap.13]
19 - 29/11 Busca Áurea [C07, Cap.13], [MF, url]; Busca de Fibonacci [C07, Cap.13], [MF, url]
20 - 5/12 Méthodos de Ponto Fixo; Méthodo de Newton-Raphson para Optimização; Aproximação Quadrática [C07, Cap.13]
21 - 6/12 Condições de Convergência para o Méthodo de Newton-Raphson; Estudo de uma Implementação Computacional no N-R; Método da Secante para Optimização [C07, Cap.13]
22 - 10/12 Otimização Irrestrita de Funções de Várias Variáveis; Gradiente; Pontos Críticos; Classificação dos Pontos Críticos; Matriz Hessiana [C07, Cap.14]
23 - 13/12 Definidade; Caso Bidimensional [C07, Cap.14]
24 - 15/12 Aplicação: Méthodo dos Mínimos Quadrados [C07, Cap.14]
25 - 20/12 Método do Gradiente [MF]
26 - 3/1 Método dos Multiplicadores de Lagrange: Demonstração, Interpretação; Uso do Hessiano para Classificação dos Pontos Críticos Obtidos
27 - 10/1 Generalização do Método dos Multiplicadores de Lagrange: Condições de Karush-Kuhn-Tucker
28 - 16/1 2o. Exercício Escolar (Versa sobre Aulas 17-27)
29 - 17/1 Correcção do 2o. EE
30 - 21/1 2a. Chamada (Versa sobre Aulas 2-27)
31 - 24/1 Exame Final (Versa sobre Aulas 2-27)

Tarefa de Casa

Aula Tarefa
3 - 24/9 Resolva [PP87, p.61-64].
4 - 28/9 Estude [PP87, p.40-41]; Ler [C07]; Estude a Notação para as Dimensões dos vetores e Matrizes.
5 - 1/10 Resolva problemas de PL pelo método algébrico.
6 - 4/10 Resolva todos os exercícios propostos em [K96, p.329-330].
7 - 8/10 Implemente em R o algoritmo Simplex via quadros; Leia este tutorial do MATLAB.
8 - 11/10 Estude em detalhes [C07, Cap.8], inclusive o Exemplo Numérico; Consulte a referência: "Introduction to Algorithms (Cormen, Leiserson, and Rivest) 2001".
9 - 18/10 Implemente em R o algoritmo Simplex (matricial); Simulação computational: Para diversos valores de n e m, gere aleatoriamente 20 problemas de programação linear, resolva-os usando o Simplex e calcule o número médio de iterações necessárias. Faça um gráfico em três dimensões.
10 - 25/10 Leia [PP87, cap.6]; Resolva exercícios relacionados com a aula em [PP87, p.182-185].
11 - 29/10 Em [PP87, p.159], lê-se "Analogamente, pode-se demonstrar que y_i* (i=1,2,...m) é uma solução ótima do dual". Demonstre essa assertiva.
12 - 1/11 Estude o Corolário (e sua demonstração!) dado em [PP87, p.167]. Examine em detalhe o exemplo em [PP87, p.168-171]. Resolva o máximo de exercícios em [PP87, p.182-185] e [K96, p.335-337].
15 - 12/11 Resolva em extremo detalhe o 1o. Exercício Escolar.
17 - 22/11 Estude o conceito de expansão em série de Taylor; Estude sobre o erro de truncamento; Use seu livro de Cálculo favorito para resolver exercícios sobre estes assuntos. Usando o programa Winplot, no modo 2-Dim (pressione F2), use o menu 'Equa >> Explicit' para realizar o gráfico de alguma função. Depois vá no menu 'One >> Slider'. Use a barra de rolagem da janela slider. Faça a aproximação em série de Taylor para várias ordens (degree), usando o botão 'Taylor approx'.
18 - 26/11 Implemente em R o algoritmo da Busca Trissectional [C07, Cap.13].
19 - 29/11 Leia [C07, Cap.13]; Implemente em R o algoritmo da Busca Áurea e da Busca de Fibonacci [C07, Cap.13]; Consulte as seguintes sítios sobre os números de Fibonacci: (i) Mathworld e (ii) Wikipedia.
21 - 6/12 Resolva a lista de exercícios proposta sobre métodos de ponto fixo e o método de Newton-Raphson; Resolva/estude os exercícios resolvidos sobre (i) a Busca Áurea, (ii) a Busca de Fibonacci e (iii) o Método de Newton-Raphson na referência [MF] (Acesse os nexos anteriores).
25 - 20/12 Leia sobre o Método do Gradiente em [MF]; Resolva a seguinte lista sobre o Método do Gradiente.

Referências

  1. [PP87] Puccini, A. L.; Pizolato, N. D., "Programação Linear", Livros Técnicos e Científicos Editora S.A., 1987. [Disponível nas Bibliotecas do CTG e do CCSA.]
  2. [K96] Kolman, B., "Introdução à Álgebra Linear com Aplicações", Prentice-Hall do Brasil, 1996. [Texto elementar e introdutório, porém muito bem escrito e preciso; leitura recomendada.]
  3. [MF] Mathews, John H.; Fink, Kurtis D., Modules for Numerical Methods & Numerical Analysis, sítio da interrede em California State Univ. Fullerton. [Versão impressa em capa-dura disponível em Amazon.com, p.ex.]
  4. [I02] Intriligator, M. D., "Mathematical Optimization and Economic Theory", SIAM, 2002. [Livro clássico. Deve ser consultado pelos seriamente interessados.]
  5. [BV04] Boyd, S.; Vandenberghe, L., "Convex Optimization", Cambridge University Press, 2004. [Livro inteiro em formato PDF disponível gratuita e legalmente na interrede no seguinte sítio: "Convex Optimization – Boyd and Vandenberghe".]
  6. [C07] Cintra, R. J., "Notas de Aula de Optimização", UFPE, 2006-2008. [Notas de Aula em processo de escrita.]
  7. [S96] da Silva, E. M.; da Silva, E. M.; Gonçalves, V.; Murolo, A. C., "Pesquisa Operacional: Programação Linear, Simulação", Editora Atlas, 1996. [Este livro deve ser utilizado apenas pelos seus exercícios.]
  8. [MS] Material Suplementar.

Política do Curso

A prova de 2a. chamada é destinada apenas àqueles que não compareceram a um dos dois exercícios escolares.

Não serão realizados listas, provas extras, testes ou qualquer outro meio destinado a "melhorar" a nota. O conceito final no curso será obtido exclusivamente dos resultados apresentados nos Exercícios Escolares, na 2a. Chamada e no Exame Final.

Saciômetro (Contador de Sacis)

"A luta contra o erro tipográfico tem algo homérico. Durante a revisão os erros se escondem. Fazem-se positivamente invisíveis. Mas, assim que o livro sai, tornam-se visibilíssimos. Verdadeiros sacis a nos botar a língua em todas as páginas. Trata-se de um mistério que a ciência ainda não conseguiu decifrar..." -- Monteiro Lobato

As notas de aula estão sendo escritas "on the fly". A quantidade de erros (os sacis) presentes é significativa. Abaixo segue-se a contabilidade dos erros encontrados pelos alunos matriculados neste curso.

Diego Roberto : 1+2
Nathalia: 1

Vide a seguinte página.