Investigacion de operaciones



Índice

Programación Dinámica Probabilística
Teoría y Ejemplo………………….……… Pg. 2-6

Programación Dinámica Determinista
Teoría y Ejemplo…………………..……… Pg. 7-11
















Programación Dinámica Probabilística

La programación dinámica probabilística difiere de la programación dinámica determinística en que el estado de la etapa siguiente no quedacompletamente determinado por el estado y la decisión de la política en el estado actual. En lugar de ello existe una distribución de probabilidad para lo que será el estado siguiente. Sin embargo, esta distribución de probabilidad todavía esta completamente determinada por el estado y la decisión de la política del estado actual. En la siguiente figura se describe diagramáticamente la estructurabásica que resulta para la programación dinámica probabilística, en donde N denota el número de estados posibles en la etapa n+1.













Cuando se desarrolla de esta forma para incluir todos los estados y decisiones posibles en todas las etapas, a veces recibe el nombre de árbol de decisión. Si el árbol de decisión no es demasiado grande, proporciona una manera útil de resumir lasdiversas posibilidades que pueden ocurrir.

Ejemplo

PROBLEMA DE LA DILIGENCIA.

Este problema trata sobre un cazafortunas de Missouri que decide ir al oeste a unirse a la fiebre del oro en California a mediados del siglo XIX.
Tiene que hacer el viaje en diligencia a través de territorios sin ley cuando existían serios peligros de ser atacado. Aún cuando su punto de partida y su destinoeran fijos, tenía muchas opciones en cuanto a qué estados debía elegir como puntos intermedios. En el diagrama siguiente se ilustran las posibles rutas en donde la dirección del viaje es siempre de izquierda a derecha.























Se requieren 4 etapas para viajar desde su punto de partida en el estado A a su destino en el estado J.
Preocupado por la seguridadde su viaje se le ocurrió una manera bastante ingeniosa para determinar la ruta más segura. Se le ofrecían pólizas de seguros de vida a los viajeros de manera que para determinar la ruta más segura habría que elegir la que tuviera el menor costo total de la póliza.
Los costos de las pólizas vienen dados en el diagrama. El problema es determinar la ruta que minimiza el costo total de la póliza.Observemos primero que el procedimiento de elegir la ruta más barata en cada etapa sucesiva no conduce a una decisión óptima global. Al seguir esta estrategia se obtiene la ruta A,B,F,I,J con un costo de 13, pero un pequeño sacrificio en una etapa permite mayores ahorros en la etapa siguiente, así por ejemplo, A,D, F es más barato que A,B,F.
La programación dinámica empieza con una pequeñaporción del problema original y encuentra la solución óptima para este problema pequeño. En el problema de la diligencia se comienza con el problema sencillo en el que el agente casa ha llegado al final de su viaje y sólo tiene una etapa más por recorrer. En cada una de las iteraciones siguientes, el problema se agranda aumentando de uno en uno el número de etapas que le quedan por recorrer paracompletar el viaje.

Formulación:
Sean
xn = variables que representan el destino inmediato de la etapa n.
fn(s,xn) = costo total = costo inmediato (etapa n) + mínimo costo futuro (etapas n+1 en adelante) = csxn+ fn+1*(s,xn*)
fn*(s) = mín fn(s,xn) = fn(s,xn*)
Como el destino final (estado J) se alcanza al terminar la etapa 4, f5*(J) = 0.
El objetivo es encontrar f1*(A) y la rutacorrespondiente.
La programación dinámica la encuentra al hallar sucesivamente f4*(s), f3*(s), f2*(s) para cada uno de los estados posibles s y usar después f2*(s) para encontrar f1*(A).
Procedimiento de solución:

n = 4
s
f4*(s)
x4*
H
3
J
I
4
J

n = 3
s
H
I
f3*(s)
x3*
E
4
8
4
H
F
9
7
7
I
G
6
7
6
H

n = 2
s
E
F
G
f2*(s)
x2*
B
11
11
12
11
E ó F
C
7
9...