Ejercicios De Programacion Dinamica

Programación Dinámica en Variable Continua

Y Programación Dinámica Probabilística.

Prof. J. Barrios M. -- Enero del 2002.

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.

-Recordemos que 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 intervalo de é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 jornada completa 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 y adecuació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.

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 la variable 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

Resumen para n=2 s f *2 x*2

20  s  50 (s - 50)2

2 s - 50

2

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

f1 = 2(10 - x1)*(-1) + 2/2*(x1-50) = 2(x1-10) + x1-50 = 3x1 - 70

x1

= 3x1 - 70 = 0  x*1 = 70/3 = 23.3333 ; y x*1 es factible.

2f1 = 3 > 0  existe mínimo para f1

x12

f *1 = f1( 10 , 70/3 ) = (10 - 70/3 )2 + 1/2 (70/3 - 50)2 = (- 40/3)2 + 1/2 (- 80/3)2

= (40/3)2 * [1 + 1/2 * 22]

= (402 / 9 ) * 3 = 1600/3 = 533,3333 (Que es el Optimo).

Resumen para n=1 s f*1 x*1

10 1600/3 70/3

Respuesta: Optimo = 533,33

Solución óptima: x*1 = 70/3 , x*2 = (s+50)/2 = (70/3 + 50)/2 = 220/6 = 110/3 = 36.6 , x*3 = 50

Es decir: x*1 = 23,33 , x*2 = 36,66 ; x*3 = 50

Verificación:

Valor de la ruta óptima = ( 70/3 - 10)2 + (110/3 - 70/3)2 + (50 - 110/3 ) 2

= 402/9 + 402/9 + 402/9

= ( 3*402 ) / 9 = 1600/3 = 533.333 = óptimo

Ejemplo 2. (Variable continua)

Enunciado: Se quiere pasar de un estado inicial 20 a un estado final 30 en 3 etapas en que el valor de la función objetivo al pasar de un estado s a la etapa siguiente con una decisión xi esta dado por el cuadrado de la diferencia menos 6 veces la decisión menos 5. Los estados factibles de la etapa 2 son [10,30] , y de [20,30] para la etapa 3 ¿Cuál es el recorrido que hace máxima la f.o.?

Gráficamente:

P: Máx. i=3  (xi - xi-1) 2 - 6 xi - 5 ; sujeto a: x0 = 20 , x3 = 30

i=1

Es decir:

P: Máx (x1 - 20)2 - 6x1 - 5 + (x2 - x1)2 - 6x2 - 5 + (30 - x2)2 - 6*30 - 5 )  ; s. a: x0 = 20 , x3 = 30

x1,x2

Es decir:

P:

...