Tutorial De P4

1. INTRODUCCIÓN A LA PROGRAMACIÓN DINÁMICA
1. CONCEPTOS
1. ¿Qué es la Programación Dinámica (PD)?
• Es una técnica de optimización.
• Es el planeamiento de los cambios de las variables de estado a través del tiempo.
2. ¿Qué es un Estado?
Es una situación actual del problema que se está solucionando. Esta situación actual está representada por un vector de estado.
3. ¿Qué es un vector deestado?
Es un conjunto de variables de estado, cuyos valores especifican la condición actual del subproblema del sistema. La cantidad de variables de estado, dependerá de la complejidad del problema. Para nuestro curso el máximo será 5 variables.
Las variables de estado cambian de valor cuando se toma una decisión.
4. ¿Qué es una variable de estado?
Es la representación de todo elemento oentidad del sistema que requiere ser evaluado en el modelo dinámico; su valor es necesario saberlo para poder tomar una decisión.
5. ¿Qué es una decisión?
Es una oportunidad para cambiar el valor de algunas variables de estado. En un estado determinado, podemos tomar un conjunto de decisiones.
i. Ejemplos de estados y decisión:
ii. Estado: Estamos en el bulto 2, con 10 toneladas disponibles.Decisión: Llevar el bulto 2 o no llevarlo.
iii. Estado: Me encuentro en el nodo 3.
Decisión: Ir al nodo 5 o ir al nodo 6.
iv. Estado: Estoy en el día 3, con un inventario de 100 unidades del artículo A.
Decisión: Cuantas unidades del artículo A debemos producir.
2. HISTORIA DEL PD
• Richard Bellman y sus colegas de la corporación RAND, son los creadores de estatécnica.
• Su trabajo fue publicado en 1957.
• La tecnología de esos tiempos, no permitió que esta técnica alcance éxitos.
• Hoy, gracias al avance tecnológico, software y hardware, la PD está permitiendo resolver problemas grandes y complejos.
3. PRINCIPIO DE OPTIMALIDAD
”La mejor ruta desde cualquier estado Z al estado Final o cualquier otro estado, depende solo del estado Z, estado en que está,y no depende de la ruta para llegar al estado Z”
En grandes problemas donde se pueda aplicar el principio de optimalidad, podemos aplicar PD.

4. APLICACIÓN DE LA PD
Para un problema dado, podemos aplicar PD, si:
• Cumple con el principio de optimalidad.
• El problema lo podemos dividir en sub problemas, resolviendo cada uno de los sub problemas, resolvemos el problema principal.
• Podemosaplicar el concepto de ecuación recursiva: f(s) = max o min{ a(s,d) + f(sn)}.
• Los valores óptimos de los estados finales, estados de contorno, son valores triviales.
2. TERMINOLOGÍA
1. Estado
Es el vector de estado, formado por una variable o por un conjunto de variables. El símbolo que lo representa es: S = { s1, s2, … , sn}.
Ejemplos:
• S = { S1}, S1 es el año donde será reemplazado elequipo.
• S = { s1, s2}, s1 es el mes y s2 es la disponibilidad de dinero.
• S = {s1, s2, s3}, s1 es la semana, s2 es la disponibilidad de dinero y s3 es la disponibilidad de espacio.
• S = {s1, s2, s3, s4}, s1 es el artículo, s2 es la disponibilidad de dinero, s3 es la disponibilidad de espacio y s4 es la decisión tomada en el artículo anterior.
2. Decisión
Es una oportunidad para que lasvariables de estado cambien su valor; por lo tanto, cambiemos de estado. Si nos encontramos en un estado actual (S) y queremos generar un estado siguiente (Sn), debemos tomar una decisión en el estado actual.
El símbolo que lo representa es: D = {d1, d2, …, dk}.
Para un problema determinado, se puede dar:
• Que todos los estados tengan el mismo conjunto de decisión.
• Que cada estado tenga suconjunto de decisión.
Ejemplos:
• D = { 0, 1}, d=0, no podemos llevar el artículo; d=1, podemos llevar el artículo.
• D = { 0, 1, …, 8}, d indica la cantidad de millones que podemos invertir en un proyecto, con un incremento de un millón.
• D(2) = { 0, 1, …, 8}, d indica la cantidad de millones que podemos invertir en un proyecto, con un incremento de dos millones.
• D(inc(s1)) = { 0, 1, …,...