L'equació de Bellman, també coneguda com la equació de programació dinàmica, nomenada en honor del seu descobridor, Richard Bellman, és una condició necessària per a la optimalidad associada en el método de l'optimisació matemàtica coneguda com programació dinàmica. S'escriu el valor d'un problema de decisió en un determinat punt en el temps en térmens de la recompensa que donen algunes opcions inicials i el valor del problema de decisió restant que resulta d'eixes opcions inicials. Açò trenca un problema d'optimisació dinàmica en subproblemas més simples, tal com el Principi de optimalidad de Bellman establix.

L'equació de Bellman es va aplicar primer a l'ingenieria en la teoria de control i atres temes de matemàtica aplicada i, posteriorment, es va convertir en una ferramenta important en la teoria econòmica.

Casi qualsevol problema que pot ser resolt usant la teoria de control òptim també es pot resoldre per mig de l'anàlisis de l'equació de Bellman apropiada. No obstant, el terme "equació de Bellman" per lo general es referix a l'equació de programació dinàmica associada a temps discret problemes d'optimisació. En els problemes d'optimisació en temps continu, l'equació anàloga és una equació diferencial parcial que generalment es diu l'equació d'Hamilton-Jacobi-Bellman.

Conceptes analítics en programació dinàmica

Per a entendre l'equació de Bellman, varis conceptes subjacents deuen ser entesos. En primer lloc, qualsevol problema d'optimisació deu tindre un objectiu - reduir al mínim el temps de viage, reduint al mínim cost, maximizar els beneficis, maximisació de l'utilitat, etcétera. La funció matemàtica que descriu este objectiu es denomina funció objectiu.

La programació dinàmica descompon un problema de planificació de múltiples periodos en passos més simples per a diferents moments. Per lo tant, es requerix fer el seguiment de cóm la situació de decisió està evolucionant en el temps. L'informació sobre la situació actual que es necessita per a prendre una decisió correcta es diu el estat (Vore Bellman, 1957, cap. III.2).[1][2] Per eixemple, per a decidir quànt consumir i gastar en cada punt en el temps, la gent tindria que saber (entre atres coses) la seua riquea inicial. Per lo tant, la riquea seria una de les seues variables d'estat, pero provablement hi hauria unes atres.

Les variables seleccionades en qualsevol punt donat en el temps es diuen variables de control. Per eixemple, donada la seua riquea actual, la gent podria decidir quànt consumir ara. L'elecció de les variables de control ara pot ser equivalent a l'elecció de la següent estat; més en general, el següent estat es veu afectada per atres factors, ademés de la regulació de corrent. Per eixemple, en el cas més senzill, la riquea de hui (l'estat) i el consum (el control) poden determinar en exactitut la riquea de matí (el nou estat), encara que per lo general atres factors poden afectar la riquea de matí també.

L'enfocament de programació dinàmica descriu el pla òptim per mig de la busca d'una regla que diu lo que els controls deuen ser, tenint en conte qualsevol possible valor de l'estat. Per eixemple, si el consum (c) solament depén de la riquea (W), llavors es buscaria una regla c(W) que dona el consum en funció de la riquea. Tal regla general, la determinació dels controls com una funció dels estats, es diu una funció de política (Vore Bellman, 1957, cap. III.2).[1]


Per últim, per definició, la regla de decisió òptima és la que conseguix el millor valor possible de l'objectiu. Per eixemple, si algú elegix el consum, la riquea donada, en la finalitat de maximizar la felicitat (suponent que la felicitat H pot ser representat per una funció matemàtica, tal com una utilitat de funció), a continuació, cada nivell de la riquea s'associa en algun nivell més alt possible de la felicitat, H(W). El millor valor possible de l'objectiu, escrita com una funció de l'estat, es diu la funció de valor.

Richard Bellman va mostrar que una dinàmica d'optimisació d'un problema en temps discret es pot afirmar en un recursivo forma, pas a pas, anotant la relació entre la funció de valor en un periodo i el valor de la funció en el pròxim periodo. La relació entre estes dos funcions de valor es diu l'equació de Bellman.

Derivació de l'equació de Bellman

Un problema de decisió dinàmic

Siga xt l'estat en el moment t. Per a una decisió que comença en el moment 0, prenem com donat l'estat inicial x0. En qualsevol moment, el conjunt de possibles accions depén de l'estat actual; podem escriure açò com at∈Γ(xt), a on l'acció at representa una o més variables de control. També suponem que l'estat canvia de x a un nou estat T(x,a) quan l'acció a es pren, i que el pagament actual de prendre l'acció a en l'estat x és F(x,a). Per últim, assumim l'impaciència, representat per un factor de desconte 0<β<1 .

Baix estos supòsits, un problema de decisió d'horisó infinit pren la següent forma:

V(x0)=max{at}t=0∞∑t=0∞βtF(xt,at),

subjecte a les llimitacions:

at∈Γ(xt),xt+1=T(xt,at),∀t=0,1,2,…

Note's que s'ha definit la notació V(x0) per a representar el valor òptim que es pot obtindre per mig de la maximisació de la funció objectiu en subjecció a les llimitacions assumides. Esta funció és la funció de valor. És una funció de la variable d'estat inicial x0, ya que la millor relació obtenible depén de la situació inicial.

Principi de Bellman de optimalidad

El método de programació dinàmica trenca este problema de decisió en subproblemas més menuts. El principi de optimalidad de Bellman explica cóm fer-ho:

Principi de optimalidad: Una política òptima té la propietat de que qualsevol que siga l'estat inicial i la decisió inicial, les decisions restants deuen constituir una política òptima en relació en l'estat resultant de la primera decisió. (Vore Bellman, 1957, Cap. III.3.)[1][2][3]

En ciències de la computació, es diu que un problema que pot ser descompost d'esta forma té subestructura òptima. En el context de la dinàmica de la teoria de jocs, este principi és anàlec al concepte d'equilibri perfecte en subjuegos, a pesar de lo que constituïx una política òptima en este cas, està condicionat als opositors del decisor elegir polítiques igualment òptimes des dels seus punts de vista.

Com sugerix el principi de optimalidad, considerarem la primera decisió per separat, deixant de costat totes les decisions futures (anem a escomençar de nou de volta en 1 en el nou estat x1). La recollida de les futures decisions entre paréntesis a la dreta, el problema anterior és equivalent a:


subjecte a les restriccions:

a0∈Γ(x0),x1=T(x0,a0).

Ací estem elegint a0, sabent que la nostra elecció farà que el temps d'1 estat siga x1=T(x0,a0). Eixe nou estat serà llavors afectar el problema de decisió de volta en 1. Tot el problema de decisió futura apareix dins dels corchetes de la dreta.

Referències

  1. ↑ 1,0 1,1 1,2 Bellman, R.E. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ. Republished 2003: Dover, ISBN 0-486-42809-5.
  2. ↑ 2,0 2,1 S. Dreyfus (2002), 'Richard Bellman on the birth of dynamic programming' Operations Research 50 (1), pp. 48–51.
  3. ↑ Bellman, R(August 1952).«On the Theory of Dynamic Programming».Proc Natl Acad Sci O S A.38(8): 716–9.doi:10.1073/pnas.38.8.716.


Referències