Programação Dinamica

Programação Dinâmica:
Modelos Determinísticos
Prof. Fernando Augusto Silva Marins
Departamento de Produção
Faculdade de Engenharia – Campus de Guaratinguetá
UNESP
www.feg.unesp.br/~fmarins [e-mail] 1

Introdução
Útil em processos de decisão sequencial / multiestágio / com muitas variáveis interdependentes.
Histórico:
Wald (1950) - decisão sequencial
Dvoretzky, Kiefer & Wolfowitz (1952) - estoques
Bellman (década de 50) - artigos, livros.
Idéia:
obter uma série de problemas com um único estágio e um número menor de variáveis.

2

Princípio da Otimalidade da
Programação Dinâmica
A aplicação da Programação Dinâmica-PD baseia-se fundamentalmente naquele que é conhecido como Princípio de
Otimalidade de Bellman:
“Uma política de decisões ótimas só pode ser formada por subpolíticas ótimas”:
A verificação da validade desse princípio é intuitiva: basta considerar uma subpolítica tomada de uma decisão ótima; se essa subpolítica não for ótima, existe outra subpolítica melhor, a qual, completa pelo restante da política considerada, poderá melhorar esta, o qual contraria a hipótese efetuada.
3

Introdução
Exemplos da PD:
Problema da viagem
Problema da produção (contínua)/ estocagem
Problema da sobrevivência
Problema da Viagem com Custos Terminais
Problema da produção (discreta)/ estocagem
4

Problema da Viagem
Viajante sai da cidade A com destino a cidade J.
Qual a trajetória de menor custo de transporte?

5

Problema da Viagem
Solução sobre o Grafo, partindo da Cidade Destino J e considerando o
Custo Remanescente Mínimo de cada Cidade até J .

Custo mínimo da viagem entre as cidades A e J= 20

6

Elementos importantes em modelos de PD: ilustração com o Problema da Viagem
Estágios
(instante de início/término de uma viagem - k= 0, 1, 2, 3, 4)
Estado
(cidade onde o viajante está num dado estágio - exemplo: no estágio 3 há os estados viáveis h, i)
Decisão
(para ir de uma cidade à outra - de outro