Bellman

Nombre del estudiante: Janeth Jacqueline Hernández
Aguirre

Nombre del trabajo: Principio de optimalidad de Bellman

Fecha de entrega: 11 de octubre de 2015

Campus: Lomas Verdes

Carrera: Ingeniería Industrial

Semestre: Tercer semestre

Nombre del maestro: Mario Ernesto Jiménez Jiménez

1

ÍNDICE
Introducción……………………………………………………………………3
Principio de Bellman………………………………………………………….3
La ecuaciónde Bellman……………………………………………………..3
Ejemplo………………………………………………………………………...4
Conclusión…………………………………………………………………….7
Información adicional (aportaciones)……………………………………….8
Bibliografía…………………………………………………………………….8

2

Introducción
En este trabajo desarrollaremos el tema de Principio de optimalidad de Bellman,
que se refiere a principios básicos de la programación dinámica. La idea primaria de
laprogramación dinámica (PD) es descomponer el problema en subproblemas
(más manejables). Los cálculos se realizan entonces recursivamente donde la
solución óptima de un subproblema se utiliza como dato de entrada al siguiente
problema. La forma en que se realizan los cálculos recursivos depende de cómo se
descomponga el problema original.

Principio de optimalidad de Bellman
Principio aplicado enprogramación dinámica que consiste en que una secuencia
óptima de decisiones que resuelve un problema debe cumplir la propiedad de que
cualquier subsecuencia de decisiones, que tenga el mismo estado final, debe ser
también óptima respecto al subproblema correspondiente.
Entonces se dice que un problema de optimización satisface el principio de
optimalidad de Bellman si en una sucesión óptima si en unasucesión óptima de
decisiones o elecciones, cada subsolución es a su vez óptima. Es decir, si miramos
una subsolución de la solución óptima, debe ser solución del subproblema asociado
a esa subsolución.

La ecuación de Bellman
Esta ecuación es una relación recursiva fundamental que traduce matemáticamente
el principio básico de la programación dinámica llamado el principio de optimalidad
de Bellmanque se enuncia en lo siguiente:

3

“Una política optima tiene la propiedad de que, cualesquiera que sean el estado y
las decisiones iniciales tomadas (es decir, el control), las restantes decisiones
deben constituir una política óptima con independencia del estado resultante de la
primer decisión.”
En términos matemáticos el principio de optimalidad se puede expresar por medio
de lo que se leconoce como la relación de recurrencia fundamental de la
programación dinámica o Ecuación de Bellman así:

𝐽(𝑤𝑡 ) = max[𝑓(𝑥𝑡 , 𝑤𝑡 ) + 𝛽𝐽(𝑤𝑡+1 )]
𝑤𝑡

𝑠𝑎: 𝑤𝑡+1 = ⎾(𝑥𝑡 , 𝑤𝑡 )
Lo que coloquialmente dice que el valor máximo se puede obtener desde el estado

𝑤𝑡

es el valor máximo desde el estado siguiente más el valor máximo de f una vez

optimizada con respecto a variable de control para el periodo de tEjemplo (Problema de la ruta más corta)
Supongamos que queremos seleccionar la ruta por carretera más corta entre dos
ciudades. La red en la figura 1 proporciona las posibles rutas entre la ciudad de
inicio en el nodo 1 y la ciudad de destino en el nodo 7. Las rutas pasan por
ciudades intermedias designadas por los nodos 2 a 6.

Figura 1

4

Podemos resolver este problema enumerando todas lasrutas entre los nodos 1 y 7.
Sin embargo la enumeración exhaustiva es computacionalmente insoluble en redes
grandes.
Para resolver el problema por PD, primero lo descomponemos en etapas como se
indica mediante rayas verticales en la figura 2. A continuación realizamos por
separado los cálculos de cada etapa.
La idea general para determinar la ruta más corta es calcular las distancias
(acumulativas)más cortas a todos los nodos terminales de una etapa, y luego
utilizarlas como datos de entrada a la etapa inmediatamente subsiguiente.
Partiendo del nodo 1, la etapa 1 llega a tres nodos terminales (2, 3 y 4) y sus
cálculos son simples.

Etapa 1
Distancia más corta del nodo 1 al nodo 2= 7 millas (desde el nodo 1)
Distancia más corta del nodo 1 al nodo 3= 8 millas (desde el nodo 1)
Distancia más...