El Valor De La Vida

UNIDAD I:

PROGRAMACIÓN DINÁMICA

1.1CARACTERÍSTICAS DE LOS PROBLEMAS DE PROGRAMACIÓN DINÁMICA: ETAPAS, ESTADOS, FÓRMULARECURSIVA, PROGRAMACIÓN EN AVANCE Y EN RETROCESO

La programación dinámica es una técnica matemática que se utiliza parala solución de problemas matemáticos seleccionados, en los cuales se tomauna serie de decisiones en forma secuencial.Proporciona un procedimiento sistemático para encontrar la combinaciónde decisiones que maximice la efectividad total, al descomponer el problema enetapas, las que pueden ser completadas por una o más formas (estados), yenlazando cada etapa a través de cálculos recursivos.La programación dinámica es un enfoque general para la solución deproblemas en los que es necesario tomar decisiones en etapas sucesivas. Lasdecisiones tomadas en una etapa condicionan la evolución futura del sistema,afectando a las situaciones en las que el sistema se encontrará en el futuro(denominadas estados), y a las decisiones que se plantearán en el futuro.La programación dinámica parte de una pequeña porción del problema yllega a la solución óptima para esa pequeña parte del problema, entoncesgradualmente se agranda el problema hallando la solución óptima en curso apartir de la anterior. Este proceso se repite hasta obtener la solución óptimadel problema original.El problema de la diligencia es un prototipo literal de los problemas deprogramación dinámica. Por tanto una manera de reconocer una situación quese puede formular como un problema de programación dinámica es poder identificar una estructura análoga a la del problema de la diligencia.

Características básicas.

1.- El problema se puede dividir en etapas que requieren una política dedecisión en cada una de ellas.2.- Cada etapa tiene cierto número de estados asociados con su inicio. Losestados son las distintas condiciones posibles en las que se puede encontrar elsistema en cada etapa del problema.3.- El efecto de la política de decisión en cada etapa es transformar el estadoactual en un estado asociado con el inicio de la siguiente etapa.4.- El procedimiento de solución está diseñado para encontrar una políticaóptima para el problema completo.

5.- Dado el estado actual, una política óptima para las etapas restantes esindependiente de la política adoptada en etapas anteriores. Este es el principiode optimalidad para programación dinámica.6.- El procedimiento de solución se inicia al encontrar la política óptima para laúltima etapa.7.- Se dispone de una relación recursiva que identifica la política óptima para laetapa n, dada la política óptima para la etapa n+1. La forma precisa de relaciónrecursiva difiere de un problema a otro de programación dinámica, perousaremos una notación análoga a la siguiente:N = número de etapas.n = etiqueta para la etapa actual ( n = 1,2,...,N)sn = estado actual para la etapa nxn = variable de decisión para la etapa nxn* = valor óptimo de xn (dado sn)fn(sn,xn) = contribución a la función objetivo de las etapas n, n+1,...,N, si elsistema se encuentra en el estado sn en la etapa n, la decisión inmediata es xny en adelante se toman decisiones óptimas. fn*(sn) = fn(sn,xn*) La relaciónrecursiva siempre tendrá la forma: fn*(sn) = mín fn(sn,xn) ó fn*(sn) = maxfn(sn,xn)8.- Cuando se usa esta relación recursiva, el procedimiento de solucióncomienza al final y se mueve hacia atrás etapa por etapa, hasta que encuentrala política óptima desde la etapa inicial

Procedimiento de solución.

1. Se construye una relación recursiva que identifica la política óptima paracada estado en la etapa

n,

dada la solución óptima para cada estado en laetapa

n

+

l.

2. Se encuentra la decisión óptima en la última etapa de acuerdo a la políticade decisión establecida. Comúnmente la solución de esta última etapa estrivial, es decir, sin ningún método establecido, tomando en cuenta solamentela "contribución" de la última etapa.3. La idea básica detrás de la relación recursiva es trabajar "hacia atrás",preguntándose en cada etapa: ¿qué efecto total tendría en el problema si tomouna decisión particular en esta etapa y actúo óptimamente en todas las etapassiguientes?

Si se resolviera el problema "hacia adelante", es decir, de la primeraetapa hacia la sería necesario realizar una enumeración exhaustiva de todaslas alternativas, que resolviéndolo "hacia atrás" reducimos el número dealternativas a analizar, simplificando la solución del problema. Cuando se llegaa la etapa inicial se encuentra la solución óptima.

1.2EJEMPLOS DE MODELOS DE PROGRAMACIÓN DINÁMICA

El problema de la diligencia.

Un cazafortunas desea ir de Missouri a California en una diligencia, yquiere viajar de la forma más segura posible. Tiene los puntos de salida ydestino conocidos, pero tiene múltiples opciones para viajar a través delterritorio. Se entera de la posibilidad de adquirir seguro de vida como pasajerode la diligencia.El costo de la póliza estándar (cij ) se muestra en la tabla siguiente.

El problema de las monedas.

Para el problema de las monedas

...