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: Máx 2*(x12 + x22) - 2x1x2 - 46x1 - 66x2 - 695 ; s. a: x0 = 20 , x3 = 30

x1,x2

Los cálculos:

n=3

s f *3 x*3

20  s  30 (s - 30)2 - 6*30 - 5

= (s - 30)2 - 185 30

Observación: Es claro que f *3 tiene su valor máximo para s =20, ya que a medida que s crece de 20 a 30, f *3 va decreciendo de -85 hasta -185.

n = 2 f2 (s , x2) = f 2 = (x2 - s)2 - 6x2 - 5 + (x2 - 30)2 - 185

= x22 - 2x2s + s2 - 6x2 - 5 + x22 - 60x2 + 900 -185

= 2x22 - 2x2s - 66x2 + s2 + 710

 f 2 = 4x2 - 2s - 66 = 0  x2 = (s + 33)/2

x2

2 f 2 = 4 > 0  existe un mínimo local, ¡¡y no un máximo!!. No sirve x2 = (s + 33)/2

x2 2

Por lo que la decisión óptima está en los bordes de la región factible.

- Si x2 = 20, f 2 = 800 - 40s -1320 + s2 + 710 = s2 - 40s + 190

- Si x2 = 30, f 2 =1800-60s-1980+s2+710 = s2 - 60s + 530

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

10  s  30 s2 - 40s + 190

s2 - 60s + 530 con x*2 = 20

con x*2 = 30

n = 1 ; i) si x2=20 , f 1 = (20 - x1)2 - 6x1 - 5 + x12 - 40x1 + 190

= 400 - 40x1 + x12 - 6x1 - 5 + x12 - 40x1 + 190

= 2x12 - 86x1 + 585

 f 1 = 4x1 - 86 = 0  x1 = 86/4

x1

f 1 tiene mínimo en x1=86/4=21,5 (no interesa, porque buscamos

...