Plano de Ensino

IDENTIFICAÇÃO

EMENTA

Princípios de pesquisa operacional. Principais métodos de otimização com vantagens e limitações. Otimização combinatória e programação linear. Métodos estocásticos para otimização de sistemas. Análise e construção de simulações de Monte Carlo.

JUSTIFICATIVA

O estudo de técnicas para implementar simulações e métodos de otimização é uma importante competência para engenheiros da computação. Esse curso se alinha com as fundamentações e teorias necessárias para isso.

OBJETIVO

PROGRAMA

Introdução e revisão

◦ Análise multivariável

◦ Álgebra matricial

◦ Probabilidade e estatística

Pesquisa operacional

• Modelagem de problemas e modelos de programação linear

• Programação linear

◦ O algoritmo simplex

◦ Algoritmos de ponto interior

◦ Dualidade

• Programação dinâmica

◦ Princípio de otimização de Bellman

◦ Problema do horizonte finito

◦ Problema do caminho de menor custo (ou parada ótima)

• Algoritmos gulosos

◦ Algoritmo de Kruskal para o problema de árvore de extensão mínima

• Separação e relaxamento

◦ Separação e avaliação (ramos e fronteira)

◦ Relaxamento de problemas combinatoriais

Fundamentos em Busca e Otimização

• Definições e questões básicas

• Métodos determinísticos vs estocásticos

• Teorema no free lunch para otimização

• Sumário dos principais métodos de otimização e suas limitações

Técnicas de busca direta

• Introdução à busca direta aleatótia

• Métodos de Monte Carlo

• Algoritmos simplex não lineares (Nelder-Mead)

Métodos da classe de mínimos quadrados

• Métodos recursivos para sistemas lineares

• Mínimos quadrados recursivo (RLS)

• Mínimo quadrático médio (LMS)

• Relação com Filtros de Kalman

Aproximação estocástica para sistemas lineares e não-lineares

• Algoritmos de lugar de raízes e aproximação estocástica baseada em gradiente (Robins-Monro)

• Métodos de aproximação estocástica indepentente de gradiente

◦ Diferenças finitas (FDSA)

◦ Perturbação simultânea (SPSA)

Métodos de busca inspirados por processos físicos e biológicos

• Recozimento simulado (simulated annealing) e métodos relacionados

• Computação Evolucionária e Algoritmos Genéticos

Otimização estocástica discreta

• Métodos estatísticos (e.g. ranking e seleção, comparações múltiplas)

• Métodos gerais de busca aleatória

• Método de aproximação estocástica por perturbação simultânea discreta (DSPSA)

Construção de modelos

• Questões particulares a modelos de simulação por Monte Carlo

• Compromisso entre enviesamento e variância

• Seleção de modelo mais próprio por validação cruzada

• Matriz de informação de Fisher como medida sumária

Otimização baseada em simulação

• Uso de simulações Monte Carlo para melhorar o desempenho de sistemas do mundo real

• Métodos baseados em gradiente (análise de perturbação infinitesimal e razão de verossimilhança) e não baseados em gradiente (FDSA, SPSA etc)

• Números aleatórios comuns

Método de Monte Carlo baseado em cadeias de Markov

• Métodos de Monte Carlo para cálculos difíceis

• Amostragens de Metropolis-Hastings e Gibbs

• Aplicações para integrações numéricas e estimações de estatísticas

Seleção de entradas e design experimental

• Design clássico vs design ótimo

• Critério prático para design ótimo (D-otimizado)

• Seleção de entradas em modelos lineares e não-lineares

METODOLOGIA

a) Atividades síncronas: 25 horas
Horários das atividades síncronas: A definir na primeira aula remota
Plataforma de T.I./softwares que poderão ser utilizados: MConf, Google Meet, MS Teams - a definir
b) Atividades assíncronas: 15 horas

Plataforma de T.I. /softwares que serão utilizados: Vídeo-aulas disponibilizados para download e em plataformas como MS Teams ou Moodle para visualização online e documentos para leitura. Uso da linguagem Python de programação.
Endereço web de localização dos arquivos: A definir na primeira aula remota
c) Demais atividades letivas: 5 horas;

O atendimento ao aluno será realizado de forma remota, seja durante as aulas na modalidade síncrona, ou através do grupo criado para esse fim no aplicativo Whatsapp ou no Telegram.

AVALIAÇÃO

- Quizzes (8 questionários online podendo ser múltipla escolha ou questões abertas): 50 pontos

- Dois Projetos: 25 pontos cada, 50 pontos total

BIBLIOGRAFIA

Básica

• Michel Bierlaire. Optimization: principles and algorithms. EPFL Press, 2015.
• ROSS, Sheldon M. Simulation. 4th ed. Amsterdam: Elsevier, c2006.
• SPALL, James C. Introduction to stochastic search and optimization: estimation, simulation, and control. Hoboken: J. Wiley, c2003.

Complementar

• CHONG, Edwin Kah Pin. An introduction to optimization. 2nd ed. New York: Wiley, c2001.
• ESFANDIARI, Ramin S. Modeling and analysis of dynamic systems. 2nd ed. Boca Raton: CRC Press, Taylor & Francis, c2014.
• HEYMAN, Daniel P. Stochastic models in operations research. Mineola: Dover Publication, 2004.
• KORTE, B. H. Combinatorial optimization: theory and algorithms. 4th ed. Berlin: Springer, c2010.
• SEILA, Andrew F. Applied simulation modeling. Belmont: Thomson Brooks/Cole, 2003.
• STEWART, William J. Probability, Markov chains, queues, and simulation: the mathematical basis of performance modeling. Princeton: Princeton University Press, c2009.
• VENKATARAMAN, P. Applied optimization with MATLAB® programming. New York: Wiley, c2002.

APROVAÇÃO

Aprovado em reunião do Colegiado realizada em: ____/____/______

Coordenação do Curso de Graduação: _________________________

---

Documento assinado eletronicamente por Igor Santos Peretta, Professor(a) do Magistério Superior, em 26/06/2021, às 13:44, conforme horário oficial de Brasília, com fundamento no art. 6º, § 1º, do Decreto nº 8.539, de 8 de outubro de 2015.

---

A autenticidade deste documento pode ser conferida no site https://www.sei.ufu.br/sei/controlador_externo.php?acao=documento_conferir&id_orgao_acesso_externo=0, informando o código verificador 2865108 e o código CRC 117C738F.

---