Programacion dinmica Estocastica

Programacion dinmica EstocasticaInvestigacin Operativa 2

IntroduccionLa programacin dinmica es una tcnica matemtica til para la toma de decisiones secuenciales interrelacionadas. Proporciona un procedimiento sistemtico para determinar la combinacin optima de decisiones, daremos a entender algunos conceptos de programacin dinmica. Esto se realizara mediante la definicin de conceptos principales que permitan su fcil comprensinEn este informe se explica cmo usar la programacin dinmica para resolver problemas en los que el costo del periodo actual o el estado del siguiente periodo son aleatorios. A estos problemas se les conoce como problemas de programacin dinmica Estocastica (PDE). En una PDE, por lo general el objetivo de quien toma la decisin es minimizar el costo esperado en que se incurre o maximizar la recompensa esperada obtenida en un determinado horizonte de tiempo.

Qu es la programacin dinmica?La programacin dinmica es una tcnica matemtica que a menudo resulta til a tomar una sucesin de decisiones interrelacionadas. Proporciona un procedimiento sistemtico para determinar la combinacin de decisiones que maximice la efectividad global.Contrastando con la programacin lineal, no existe un planteamiento matemtico estndar "del" problema de programacin dinmica. Ms bien, la programacin dinmica es un tipo general de enfoque para resolver problemas y las ecuaciones particulares usadas deben desarrollarse para que se ajusten a cada situacin individual. Por lo tanto, se requiere un cierto grado de ingenio y de visin de la estructura general de los problemas de programacin dinmica, a fin de reconocer cuando un problema se puede resolver mediante los procedimientos de esta programacin y cmo se hara. Probablemente se puedan desarrollar mejor estas aptitudes por medio de una exposicin de una amplia variedad de aplicaciones de la programacin dinmica y de un estudio de las caractersticas que son comunes a todas estas.Por fortuna, la programacin dinmica suministra una solucin con mucho menos esfuerzo que la enumeracin exhaustiva. (Los ahorros de clculo seran enormes para versiones ms grandes de un problema.) La programacin dinmica parte de una pequea porcin del problema y encuentra la solucin ptima para este problema ms pequeo.Entonces gradualmente agranda el problema, hallando la solucin ptima en curso a partir de la anterior, hasta que se resuelve por completo el problema original. En seguida se dan los detalles involucrados en la implementacin de esta filosofa general.Qu es un proceso Estocstico?Un proceso estocstico es aquel en el que se representan todos y cada uno de los pasos necesarios para realizar una actividad, adems de las formas o maneras en que cada uno de los pasos puede ser llevado a efecto y sus respectivas probabilidades, dicho de otra manera, cualquier proceso en el que se involucren probabilidades es un proceso estocstico.En el caso de la Programacion dinmica estocstica (o tambin llamada probabilstica) existe una distribucin de probabilidad del valor posible del siguiente estado. La programacin dinmica estocstica difiere de la programacin dinmica determinstica en que el estado de la etapa siguiente no queda completamente determinado por el estado y la decisin de la poltica en el estado actual. En lugar de ello existe una distribucin de probabilidad para lo que ser el estado siguiente. Sin embargo, esta distribucin de probabilidad todava esta completamente determinada por el estado y la decisin de la poltica del estado actual.

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 decisin. Si el rbol de decisin no es demasiado grande, proporciona una manera til de resumir las diversas posibilidades que pueden ocurrir

HistoriaLa programacin dinmica fue la creacin de un matematico estadounidense, llamado Richard Bellman, que describi la forma de resolver los problemas en los que se necesitaba encontrar la mejor decisin a tomar, una tras otra. En los cuarenta y tantos aos desde su su desarrollo el numero de usos y aplicaciones de programacin dinmica se ha incrementado enormemente. Por ejemplo, en 1982 Davis Kohler utiliza programacin dinmica para analizar la mejor manera de jugar el juego de dardos

EjemplosProgramacin Dinmica Probabilstica.

En la programacin dinmica probabilstica, el estado en la etapa siguiente no queda completamente determinado por el estado y la decisin de la subpoltica en el estado actual, sino que existe una distribucin de probabilidad para lo que sera el estado siguiente.

Grficamente tenemos:

donde:

1 N es el nmero de estados posibles de la etapa n + 1

2 p1, p2, ..., pN. Distribucin de probabilidad de lo que ser el estado, dados Sn y Xn en la etapa n.

3 ci : es la contribucin resultante de la funcin objetivo.

Por ejemplo, si el objetivo es minimizar la suma esperada de las contribuciones de las etapas individuales, la funcin objetivo quedara:

Donde esta minimizacin se toma sobre los valores factibles de Xn + 1

Ejemplo 1

Una compaa ha recibido un pedido para surtir un solo artculo muy especial y de una calidad tan rigurosa que es posible que el fabricante tenga que producir ms de un artculo para obtener uno aceptable. La probabilidad estimada para que sea aceptable es 1/3 y de que sea defectuoso sin posibilidad de reparacin 2/3. Por lo tanto la probabilidad de producir cero artculos aceptables en un lote de tamao L es (2/3)L.Los costos marginales de produccin son de $ 100 por artculo, incluso si es defectuoso (los artculos en exceso no tienen valor). El costo de preparacin es $ 200, cada vez que se monte el proceso de produccin de este artculo, el cual puede hacerlo como mximo 3 veces. Si no se ha obtenido un artculo aceptable al final de la tercera serie de produccin, el costo por ventas perdidas y de penalizacin ser de $ 1500. El objetivo es determinar la poltica referente al tamao del lote para las series de produccin de manera de minimizar el costo total esperado.Solucin:Etapas: Series de produccin (1, 2, 3).Variables de decisin: Xn: Son el tamao del lote produccin en la etapa n.

Estados:Sn : puede suceder que, Sn =0 si el articulo aceptable se logro en la etapa anterior. o Sn =1 que significa que en la etapa anterior no se logr el articulo aceptable.

f*n (Sn) = Mn fn(Sn,Xn) Xn = 0, 1, ..., L (tamao del lote, costo marginal)

Donde:f*n (0) = 0 y S = 0 , cuando se ha obtenido en la etapa anterior un artculo aceptable, por lo tanto f*n (0) = 0, en esta etapa no es necesario que se incurra en gastos adicionales. (Prob. de 0 art. acept. ( prob de 1 art. Acept.)

f*n (Sn,Xn) = K + Xn + (2/3)Xn fn + 1 (1) + ( 1- (2/3)Xn) fn + 1 (0)donde:( 1- (2/3)Xn) fn + 1 (0) = 0 costo marginalluegof*n (1,Xn) = K + Xn + (2/3)Xn f*n + 1 (1).Considerando $ 100 como unidad monetaria y definiendo

0 Si Xn = 0 K = 2 Si Xn 0 (costo de preparacin)

(ETAPA ANTERIOR NO SE LOGRO ART. ACEPTABLE)

f*4 (1) = 15 , que es el costo de no obtener un artculo aceptable y perder la venta.f*4 (0) SI SE LOGRO ART.ACEPT.Luego, para n = 3 tendramos:

f3(1, X3) = K + X3 + (2/3)X3 15

S3 /X3012345f*3(1)X*3

00

1151310 2/39 4/98 26/278 79/818 26/274

Para n = 2:F2(1, X2) = K + X2 + (2/3)X2 8 26/27

S2 /X201234f*2(1)X*2

00

18 26/278 79/817 239/2437 478/7297 1685/2187 7 478/7293

Para n = 1f1(1, X1) = K + X1 + (2/3)X1 7 478/729

S1 /X101234f*1(1)X*1

17.6558.17.47.277.517.273

Luego la solucin del problema es la siguiente:

En la primera serie de produccin deben fabricarse 3 artculos, si se obtiene un articulo aceptable, X2 = X3 = 0. Si son defectuosos en la segunda se debe fabricar 3 artculos, si se obtiene un articulo aceptable X3 = 0. Si son defectuosos en la tercera serie de produccin deben fabricarse 4 artculos, todo con un costo esperado de $ 727.-

Ejemplo 2.-

Un joven estadstico cree que ha desarrollado un sistema para ganar en un juego de las vegas. Sus colegas no creen que esto sea posible, de modo que hacen una gran apuesta con l de que, empezando con dos fichas no podr tener 5 o ms fichas despus de 4 jugadas.Cada jugada comprende la apuesta de cualquier N deseado de fichas, se gana o se pierde lo apostado, l estadstico cree que su sistema le dar una probabilidad de 2/3 de ganar cada jugada.Suponiendo que l estadstico est en lo correcto, se debe determinar cuntas fichas apostar en cada una de las cuatro jugadas.El objetivo es maximizar la probabilidad de ganar la apuesta.Solucin: Etapas: jugadas ( 1, 2, 3 y 4 )Variable de decisin Xn : N de fichas que deben apostarse en la etapa nEstados: Sn : N de fichas disponibles para apostar en esa etapa.f*n (S ) = mx fn ( Sn, Xn )Xn = 0, 1, ..., 5fn( Sn, Xn ) = 1/3 f*n + 1 ( Sn - Xn ) + 2/3 f*n + 1 ( Sn + Xn )f*4(S) = 0 , Si S < 5 Pierde la apuesta;f*4(S) =1 , Si S 5 Gana la apuesta.La relacin recursiva es:

f* n( Sn) =Max 1/3 f*n + 1 ( Sn - Xn ) + 2/3 f*n + 1 ( Sn + Xn )

Xn = 0, 1, 2, ..., 5

Para n = 4 se tiene:

S4f*4 (S4 ) X*4

000

100

200

32/32

42/31

5 10

Para n = 3 (3 ra apuesta)

Fichas que Apuesta!!!tienef3( S3, X3)=1/3 f*4 (S3 - X3) + 2/3 f*4 (S3+X3)

S3 /X301234f*3 ( S3 )X*3

0000

10000

204/94/94/91,2

32/34/92/32/32/30,2,3,

42/38/92/32/32/38/91

5110

Para n = 2

f2( S2, X2)=1/3 f*3 (S2 - X2) + 2/3 f*3 (S2+X2)

S2 /X201234f*2 ( S2 )X*2

0000

108/278/271

24/94/916/2716/272

32/320/272/32/320/271

48/98/922/272/32/38/90,1

Para n = 1f1( S1, X1)=1/3 f*2 (S1 - X1) + 2/3 f*2 (S1+X1)

S1 /X1012f*1(1)X*1

216/2716/2716/2716/270,1,2

Para x1=0

S1 s2 s3s4(5)(5)(4) G (gana AP) G( gana AP)G x3=1(2)(2) P (x4=2) (3) P(pierde AP)X1=0 x2=2(0)(1) P (pierde AP)Las polticas ptimas seran:

4 X*1 = 0 X*2 = 25 Si perde X*2 = 2 pierde apuesta6 Si gana X*2 = 2 queda con 4....... X*3 = 1 7 Si gana X*3 = 1 gana la apuesta 8 Si pierde X*3 = 1 queda con 3.... X*4 = 2 9 Si gana X*4 = 2 gana apuesta. 10 Si pierde X*4 = 2 `pierde la apuesta.

para x1 = 2..

Este esquema se repite para las otras dos posibilidades.