ProgDinCont

Universidad de Chile
Facultad de Ciencias Forestales
Depto: Manejo de Recursos Forestales

Curso: "Investigación de Operaciones - II"

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, yhasta 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 sonlos 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 estosapuntes, 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 denivel 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 deempleo 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:

Apuntes para el curso:

P: Mín 

i=3

" Investigación de Operaciones - II " ----

(xi - xi-1 ) ;

Pág.: 2 / 20

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:
s

F*3

X*3

30  s  60

(50 - s)2

50

N=3N=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
2f2
x22
Análisis:



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

 existe mínimo para f2 en la variable x2 , en términos de la variable s.

= 4 > 0

Con 20  s  50  35  x*2  50 , por lo que todos los valores posibles de sproducen 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
20  s  50

Resumen para n=2

N=1 ;

f *2
(s - 50)2
2

x*2
s - 50
2

f1(s,x1) = (s-x1)2 + f *2 = (10 - x1)2 + (x1 - 50)2 / 2
f1
x1

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

2f1 = 3 > 0
x12

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

 existe mínimo para f1

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
Prof. Juan Barrios ------

(Que es el Optimo).

Tema: Programación Dinámica en variable continua ---

Pág.: 2 / 20

Apuntes para el curso:

" Investigación de Operaciones - II " ----

Resumenpara n=1

Pág.: 3 / 20

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....