Programacion dinamica.
Enviado por wilfre50 • 1 de Febrero de 2016 • Apuntes • 3.394 Palabras (14 Páginas) • 325 Visitas
1
UNIVERSIDAD DE LIMA
FACULTAD DE INGENIERIA DE SISTEMAS
DEPARTAMENTO ACADEMICO DE INGENIERIA DE SISTEMAS
ASIGNATURA : INVESTIGACION OPERATIVA II
SECCION : 901, 902
PROFESORA : ANGELICA KAMIYAMA M.
PER. ACADEMICO: 2001-1
Programación Dinámica
El término proceso de decisiones secuenciales describe una actividad que involucra una
secuencia de decisiones para cumplir un determinado fin. Programación Dinámica es la
colección de herramientas matemáticas para el análisis de procesos de decisiones
secuenciales determinando los valores óptimos de dichas decisiones.
Aplicaciones :
Determinación de políticas de inventarios
Operación de reservorios
Selección de inversiones
Determinación de políticas de expansión de capacidad
Problema de caminos más cortos
I. Problema prototipo de Programación Dinámica:
Problema de caminos más cortos
Ejemplo: En la siguiente red hallar un camino más corto del nodo 1 al nodo 9
12 5
2 7
4 7
1 6 15
3
1 4 7
10
3 8 9
2 3
7 15
3 4
6
2
Sean
t i J = longitud del arco ( i, j )
f i = la mínima distancia de i a 9 (longitud de un camino más corto de i a 9)
Entonces,
t i J + f J = longitud total del camino de i a 9 que se inicia en el arco ( i, j ) y
luego toma el camino más corto de j a 9
f i < t i J + f J i ¹ 9
Por lo tanto,
f i = min í t i J + f J ý i ¹ 9, puesto que un camino más corto de i a 9
j pasa por algún arco ( i, j )
Entonces, como f 9 = 0
f 8 = 10 + f 9 = 10
f 7 = 3 + f 9 = 3
f 6 = min { 7 + f 8 , 15 + f 9 } = min { 7 + 10 , 15 + 0 } = 15
… … ..
f 1 = min { 1 + f 2 , 2 + f 3 } = min { 1 + 20 , 2 + 17 } = 19
Por lo tanto, la longitud de un camino más corto de 1 a 9 es 19.
II. Propiedades Recurrentes
El problema de caminos más cortos y una gran variedad de otros procesos de decisiones
secuenciales comparten varias propiedades :
1. El problema original está sumergido en un conjunto de problemas de optimización.
2. La solución óptima del problema de optimización está caracterizada por una ecuación
recursiva.
3. La solución óptima puede ser calculada evaluando la ecuación recursiva en los
estados en una secuencia predeterminada.
4. Se cumple el principio de optimalidad :
4.1 “ Sea P un camino óptimo de i a j. Cualquier subcamino de ip a iq contenido en
P es un camino óptimo de ip a iq “.
4.2 “ La mejor ruta desde cualquier nodo z al nodo final depende solo del nodo z y no
de la ruta usada para llegar a z ”.
3
4.3 “ Una ruta óptima tiene la propiedad de que cualquiera sea el nodo inicial y arco
inicial, los arcos restantes deben constituir una ruta óptima con respecto al primer
nodo alcanzado después del nodo inicial “.
III. Estructuración de la técnica
1. Estado
Un estado es un resumen de la historia del proceso que es suficientemente detallada
para poder tomar una decisión. Los estados son entonces los puntos donde se toman las
decisiones.
Las variables de estado son los elementos de un (vector de) estado.
Notación :
S = vector de estado
= ( s1, s2, … ., sn)
si = variable de estado i
E = conjunto de todos los estados
2. Decisión
D(S) = conjunto de decisiones para el estado S
{ d1, d2, … ., dn }
3. Función de transición
Es la función T que define el nuevo estado al tomar la decisión d en el estado actual S,
Sn = T( d, S )
Sn = nuevo estado
4. Generación de estados
Dado un estado inicial la aplicación repetida de la función de transición generará el
conjunto de todos los estados del problema siempre y cuando se tomen en cuenta las
restricciones del problema.
5. Función de valor óptimo
4
A cada estado se le asocia un subproblema del mismo tipo que el problema original pero
de menor tamaño. La función de valor óptimo es la regla que asigna al estado S el valor
óptimo de la función objetivo del subproblema asociado a él. Dicha función es denotada
como f (S).
6. Función de política óptima
Es la regla que asigna la mejor primera decisión a cada subproblema. Se denota por P
(S) .
7. Función de retorno
Sea ad ( S ) = valor (costo o utilidad) asociado a la decisión d tomada en el estado S
Entonces
R( S, d ) = valor de la ruta desd S al estado final dada la decisión d y la ruta
óptima desde Sn.
= ad( S ) + f (Sn)
8. Ecuación recursiva
f ( S ) = min { R(S,d) }
dÎD(S)
9. Condición de contorno
Valor o valores de la función de valor optimo f que son obvios o que no requieren cálculo.
Tabla de generación de estados
5
Estado actual Decisión Nuevo estado
S d Sn
-------------------------------------------------------------------------
1 2 2
3 3
-------------------------------------------------------------------------
2 5 5
9 9
------------------------------------------------------------------------
3 4 4
6 6
-------------------------------------------------------------------------
4 5 5
6 6
7 7
8 8
-------------------------------------------------------------------------
5 7 7
-------------------------------------------------------------------------
6 8 8
9 9
-------------------------------------------------------------------------
7 9 9
-------------------------------------------------------------------------
8 9 9
Procedimiento tabular de solución
S d Sn ad(S) f(Sn) R(S,d) f(S) P(S)
6
9 0 ___
8 9 9 10 0 10 10 9_
7 9 9 3 0 3 3 9_
6 8 8 7 10 17 15 9
9 9 15 0 15 __
5 7 7 7 3 10 10 7_
4 5 5 4 10 14 14 5
7 7 15 3 18
8 8 7 10 17
6 6 3 15 18 __
3 4 4 3 14 17 17 4
6 6 4 15 19 __
2 5 5 12 10 22 20 4
4 4 6 14 20 __
1 2 2 1 20 21 19 3
3 3 2 17 19 __
7
El problema de la alforja
Se tienen N objetos de peso Pi y valor Vi. Se desea escoger los objetos a llevar en una
...