Programacion dinamica

Programación Dinámica en Variable Continua
Y Programación Dinámica Probabilística.

Introducción.

-Estos apuntes son continuación de los de PD en variable discreta que se estudian en el curso Investigación de Operaciones-I, y hasta ahora las variables de estado s han sido variables discretas. Aquí se estudia 2 temas: i)la PD en variable continua, y ii)la PD Probabilística.

-Recordemosque la PD es una técnica matemática que proporciona un procedimiento sistemático para determinar la combinación de decisiones que maximiza la efectividad total.

- Las características esenciales de los problemas que se abordan en PD son los ya enunciados en los apuntes anteriores. Hay estados s que ahoran toman valores en el conjunto de los números reales, normalmente en todo IR o en un intervalode éste. Esto hace que la cantidad de estados s es infinita, y la técnica de cálculo para llegar a la solución, ya vista, no es aplicable.

- A continuación se plantean y resuelven ejemplos de problemas del tipo que interesa en estos apuntes, y que son: PD en variable continua, y PD probabilística.

Ejemplo 1. (Variable continua)

Enunciado: Una empresa tiene 10 trabajadores con jornadacompleta y al cabo de 3 temporadas quiere tener 50, con las restricciones siguientes.

La temperada próxima siguiente debe tener de 20 a 50 trabajadores y la subsiguiente debe tener de 30 a 60 trabajadores. El costo para la empresa por el cambio de nivel de empleo de una temporada a otra es del cuadrado de la diferencia de niveles de empleo que se tenga, costos por contratación, capacitación yadecuación de la empresa al nuevo nivel de empleo. Si se bajara el nivel, el costo es por indemnizaciones, y costo social para la empresa.

Se puede tener fracción de jornada porque se entenderá que corresponde a jornada parcial.

Se desea saber qué nivel de empleo al final de la etapa 1 y etapa 2 hacen mínimo el costo total, y cuál es ese costo mínimo total.

||[pic] | |
| | | |
|Gráficamente: | | |

P:Mín (i=3(xi - xi-1 ) ; sujeto a: x0 = 10 , x3 = 50
i=1

P: Min ( (x1-10)2 + ( x2 - x1)2 + ( 50 - x2 )2 ( ; s. a: x1=10 , x3=5

Los Cálculos:

|N=3 |s |F*3 |X*3 |
| |30 ( s ( 60 |(50 - s)2 |50 |N=2 ; F.O. f2(s,x2) = (s - x2)2 + f *3 = (s - x2)2 + (50 - x2)2

= s2 - 2 x2s + x22 + 2500 - 100x2 + x22

= 2x22 - 2x2s - 100x2 + s2 + 2500

(f2 = 4x2 - 2s - 100 = 0
(x2

2( 2x2 - s - 50 ) = 0 ( x2 = ( s + 50 ) / 2 = x*2

(2f2 = 4 > 0 ( existe mínimo para f2 en la variable x2 , en términos de lavariable s.
(x22

Análisis: Con 20 ( s ( 50 ( 35 ( x*2 ( 50 , por lo que todos los valores posibles de s producen decisiones x2 que son factibles.

f *2( s ) = f2(s,x*2) = f 2(s , (s+50)/2 ) = (s - (s + 50 ) / 2 ) 2 = 1/4 [(s-50)2 + (50-s)2] = (s - 50)2 / 2

| |s |f *2 |x*2 |
|Resumen para n=2| | | |
| |20 ( s ( 50 |(s - 50)2 |s - 50 |
| | |2 |2 |

N=1 ; f1(s,x1) = (s-x1)2 + f *2 = (10 - x1)2 + (x1 - 50)2 / 2

(f1 = 2(10 - x1)*(-1)...