Flashcard FC241294
O que enuncia o princípio da otimalidade em programação dinâmica sobre a política ótima e o estado atual?
Programação Linear
CESGRANRIO · 2012
O que enuncia o princípio da otimalidade em programação dinâmica sobre a política ótima e o estado atual?
Mostrar resposta e comentário
Resposta
A política ótima para os estágios restantes depende apenas do estado atual, não das decisões anteriores.Explicação:
Em programação dinâmica, dado o estado presente s_t, as decisões ótimas futuras podem ser determinadas recursivamente sem referência às decisões passadas — é o fundamento da equação de Bellman.
Por exemplo, em controle de estoque com demanda aleatória, o valor ótimo a partir do estoque x no tempo t satisfaz:
\(V_t(x)=\min_{q\ge 0}\left\{ c\,q + \mathbb{E}\big[h\max(0,x+q-D_t)\big] + \mathbb{E}\big[V_{t+1}(x+q-D_t)\big]\right\}\),
onde q é a quantidade encomendada, c é o custo de pedido, h o custo de armazenagem e \(D_t\) a demanda. A escolha ótima de q depende apenas de x, ilustrando o princípio da otimalidade.
Exemplo: suponha \(c=1\), \(h=0.5\), horizonte final e demanda determinística \(D_t=2\), estoque \(x=3\). Escolher \(q=0\) tem custo imediato \(1\cdot0+0.5\max(0,3+0-2)=0.5\) e próximo estado 1; a decisão usa só o estoque atual \(x=3\), não o histórico.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/236110
Conteúdo do catálogo FC Concursos · Atualizado em