---

Área de concentração: 55134 - Ciências de Computação e Matemática Computacional

Criação: 07/12/2023

Nº de créditos: 12

Carga horária:

Teórica Por semana	Prática Por semana	Estudos Por semana	Duração	Total
3	0	9	15 Semanas	180 Horas

Docentes responsáveis:

Eduardo Fontoura Costa
Maristela Oliveira dos Santos

Objetivos:

Apresentar os conceitos de Programação Dinâmica e aplicações em diferentes tipos de problemas de
otimização, inlcuindo problemas determinísticos e estocásticos, de horizonte finito e infinito, assim
como a teoria que fundamenta esta metodologia de solução de problemas de otimização.

Justificativa:

Este curso complementa a formação dos pós-graduandos na área de otimização, oferecendo uma visão
de problemas de otimização que podem ser modelados como problemas envolvendo sistemas
dinâmicos determinísticos e estocásticos, também aprofundando o conhecimento do estudante em
problemas estocásticos.

Conteúdo:

1. Introdução a Programação Dinâmica (PD)
1.1.Exemplos de problemas que podem ser abordados por PD:
a) Mochila ; b) Caminho mínimo; c) braquistócrona; d) Estoque com demanda aleatória
2. Formalização de PD
2.1. Sistemas dinâmicos - representação por equação de estado.
2.2. Noção de função valor e Princípio de otimalidade.
2.3. Algoritmo básico da programação dinâmica.
2.4. Exemplos de aplicação em problemas determinísticos
3. Contexto estocástico.
3.1. Sistemas dinâmicos estocásticos
3.2. Casos com observação perfeita e imperfeita de estado.
3.3. Aplicação no problema de estoque com demanda aleatória.
3.4. Aplicação em cadeia de Markov controlada.
4. PD com horizonte infinito.
4.1. Problema com custo descontado.
4.2. Problema de custo médio.
4.3. Exemplos de aplicação.

Forma de avaliação:

Provas, exercícios e trabalhos dentro e fora da sala de aula

Observação:

Nenhuma.

Bibliografia:

Bibliografia fundamental
1. Kumar, P.R.; Varaya, P., Stochastic Systems, Prentice-Hall, 1986.
2. S. M. Ross, Introduction to Stochastic Dynamic Programming, Academic Press, 1995.
3. Roughgarden, T.. Algorithms Illuminated: Greedy algorithms and dynamic programming. Part 3,
isbn=9780999282946, Soundlikeyourself Publishing, 2019.

Bibiografia complementar
1. Arenales, M.; Morabito, R.; Armentano, V.; Yanasse, H. Pesquisa Operacional para Cursos de
Engenharia}, Elsevier Brasil, 2015