--- title: "Programação Dinâmica" source: "https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Din%C3%A2mica" wiki: "systems-analysis.info/int" article: "Programação_Dinâmica" language: "pt" categories: - "Category:Operations research" - "Category:Portuguese" revision_id: 5884 wiki_created_at: 2026-09-06T23:55:24Z wiki_modified_at: 2026-09-06T23:55:24Z downloaded_at: 2026-09-07T23:10:52Z --- # Programação Dinâmica **Programação dinâmica** (**PD**; em inglês: *dynamic programming, DP*) é um método para resolver problemas complexos de otimização, baseado na decomposição do problema original em uma sequência de subproblemas mais simples^{[\[1\]](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Din%C3%A2mica#cite_note-bigenc-dp-1)[\[2\]](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Din%C3%A2mica#cite_note-ru-wiki-dp-2)}. O método é aplicado a processos de tomada de decisão multiestágio, onde a solução ótima para o problema inteiro pode ser construída a partir das soluções ótimas de seus subproblemas. O termo foi introduzido pelo matemático americano Richard Bellman na década de 1950^{[\[3\]](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Din%C3%A2mica#cite_note-rechetnikov-dp-3)}. Nesse contexto, a palavra "programação" é usada no sentido de "planejamento" ou "elaboração de um plano de ação ótimo", e não na escrita de código de computador^{[\[4\]](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Din%C3%A2mica#cite_note-en-wiki-dp-4)}. ## Propriedades e Teoremas Fundamentais A aplicabilidade da programação dinâmica a um problema é determinada pela presença de duas propriedades fundamentais. ### Princípio da Otimalidade de Bellman O conceito central do método é o **princípio da otimalidade de Bellman** (em inglês: *Bellman's principle of optimality*). Ele afirma que: quaisquer que sejam o estado inicial e a decisão inicial, as decisões subsequentes devem constituir uma estratégia ótima em relação ao estado resultante da primeira decisão^{[\[3\]](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Din%C3%A2mica#cite_note-rechetnikov-dp-3)}. Em outras palavras, qualquer parte de uma trajetória ótima é, por si só, ótima. Essa propriedade permite decompor o problema geral em uma sequência de subproblemas mais simples e resolvê-los recursivamente. ### Subproblemas sobrepostos Um problema possui a propriedade de **subproblemas sobrepostos** (em inglês: *overlapping subproblems*) se, ao resolvê-lo recursivamente, os mesmos subproblemas surgem repetidamente. A PD evita cálculos repetidos, armazenando as soluções de subproblemas já encontrados (essa técnica é chamada de memoização ou tabulação), o que aumenta significativamente a eficiência em comparação com uma busca recursiva ingênua. ## Equação de Bellman Do princípio da otimalidade deriva a principal relação de recorrência do método — a **equação de Bellman**^{[\[1\]](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Din%C3%A2mica#cite_note-bigenc-dp-1)}. Ela relaciona o "valor" (ganho ou custo ótimo) do estado atual com os valores dos estados subsequentes. Em sua forma geral, para um processo determinístico multiestágio com uma função objetivo aditiva, ela tem a seguinte aparência: $$ V_{k - 1}(x) = \max\limits_{y \in U(x)}\{\varphi_{k}(x,y) + V_{k}(f_{k}(x,y))\} $$ onde: - $k$ — número da etapa (de $m$ a 1); - $x$ — estado do sistema na etapa $k - 1$; - $y$ — decisão de controle tomada na etapa $k$; - $\varphi_{k}(x,y)$ — ganho (ou custo) na k-ésima etapa; - $f_{k}(x,y)$ — função que define o novo estado do sistema; - $V_{k}(s)$ — valor ótimo da função objetivo para o subproblema que começa na etapa $k$ no estado $s$. A equação é resolvida sequencialmente, geralmente "de trás para frente", movendo-se da última etapa para a primeira. ## Exemplos de Aplicação - **Problema do caminho mais curto em um grafo**: Este problema possui a propriedade de subestrutura ótima, pois qualquer segmento de um caminho mais curto é, por si só, um caminho mais curto. Os algoritmos de Bellman-Ford e Floyd-Warshall são exemplos clássicos da aplicação da PD para resolver este problema^{[\[5\]](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Din%C3%A2mica#cite_note-mit-amp-5)}. - **Problema da mochila**: O problema de encher otimamente uma mochila de capacidade limitada com itens de diferentes valores e pesos. A PD permite resolver este problema considerando os itens sequencialmente e calculando, a cada etapa, o valor máximo para todos os valores possíveis de capacidade restante. - **Problema de alocação de recursos**: A alocação de um recurso limitado (por exemplo, investimentos) entre vários projetos para maximizar o efeito geral. ## Limitações A principal limitação do método é a **maldição da dimensionalidade** (em inglês: *curse of dimensionality*) — um termo introduzido por Bellman para descrever o crescimento exponencial do número de estados e, consequentemente, da complexidade computacional, com o aumento do número de variáveis que descrevem o estado do sistema^{[\[6\]](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Din%C3%A2mica#cite_note-ru-wiki-curse-6)[\[7\]](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Din%C3%A2mica#cite_note-utexas-ormm-7)}. Isso limita a aplicação prática da PD exata para problemas de dimensão muito grande. ## Conceitos Relacionados - [Pesquisa Operacional](https://systems-analysis.info/int/Pesquisa_Operacional "Pesquisa Operacional") - Teoria do controle ótimo - Processo de decisão de Markov (generalização estocástica) - Equação de Hamilton-Jacobi-Bellman (análogo para tempo contínuo) ## Notas 1. ↑ ^{[1.0](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Din%C3%A2mica#cite_ref-bigenc-dp_1-0)} ^{[1.1](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Din%C3%A2mica#cite_ref-bigenc-dp_1-1)} "Programação Dinâmica". *Grande Enciclopédia Russa*. [1] 2. [↑](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Din%C3%A2mica#cite_ref-ru-wiki-dp_2-0) "Programação dinâmica". *Wikipédia*. [2] 3. ↑ ^{[3.0](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Din%C3%A2mica#cite_ref-rechetnikov-dp_3-0)} ^{[3.1](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Din%C3%A2mica#cite_ref-rechetnikov-dp_3-1)} Reshetnikov A. N., Kochenkov A. V., Pirov D. M., Ryabokon D. A. (2011). *Programação Dinâmica. Exemplos de Aplicação*. Manual de Estudo, Universidade de Lobachevsky (FCMC). [3] 4. [↑](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Din%C3%A2mica#cite_ref-en-wiki-dp_4-0) "Dynamic programming". *Wikipedia*. [4] 5. [↑](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Din%C3%A2mica#cite_ref-mit-amp_5-0) Bradley S. P., Hax A. C., Magnanti T. L. (1977). *Applied Mathematical Programming*. Addison-Wesley. [5] 6. [↑](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Din%C3%A2mica#cite_ref-ru-wiki-curse_6-0) "Maldição da dimensionalidade". *Wikipédia*. [6] 7. [↑](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Din%C3%A2mica#cite_ref-utexas-ormm_7-0) Jensen P. A. (2004). *Dynamic Programming – Models*. Operations Research Models and Methods, Univ. of Texas. [7]