Programación dinámica_ACPD

Qué es

Frederick & Hilier

Decisiones interrelacionada, método sistemático. para determinar la combinacion óptima

Taha

Los cálculos se realizan recursivamente para encontrar el únto óptimo

Signos convencionales

Círculo: Denominado NODO, indica el origen o destino

Flecha, indica la relacion entre los circulos

Características:

El nodo actual es un estado de asociación con inicio de la siguiente etapa

Se prente lograr el punto óptimo

Cada etapa tiene Nodos

Relacion repercutiva

Se subdiide por etapas

Importancia

Puede Maximizar recursos y reducir costos; encuentr la optimalidad

Debemos identificar las etapas, variables de estados y variables de decisión.

Evita calcular 2 veces la misma información,manteniendo una tabla de resultados conocidos

Tecnica wue ayuda a identificar un problema en subprocesos

¿CUANDO APLICAR?

Subestrucura óptima

Superposición de problema

Principio de optimalidad de programación dinámica o de Bellman

Permite dividir el problema global y resolver la última etapa de decisión

Dado un estado: La política no depende

Una vez conocida la solución

Relación recursiva
Se aplica de acuerdo a criterio del desarrollador; se aplica con dinamismo el método Hacia atrás.

Hacia atrás o de retroceso

Hacia adelante o de avace.

El análisis inicia del último nodo hacia el promero

Se resuelve desde la primera etapa hasta el nodo final.

Arbol de axpansión mínima

Teoría de Grafos

Tipos

No simple

Ponderado

Dirigido

Completo

No dirigido

Se similitud

Persigue unir los nodos, buscando la longitud más corta en las ramas de conexión.

NO TIENE CICLOS, TIENE GRÁFICOS ABIERTOS.

Algoritmo de Prim

Incrementa continuamente el tamaño

Algoritmo de Kriscal

Pasar todos los puntos sin cerrar la gráfica

Modelos

Modelo de la Mochila/equio de vuelo / contenedor: maximizar recursoso o utilidades.

Tamano de la fuerza de trabajo

Reemplazo de equipo

De inversión

De inventario

Tipos de programación dinámica

deterministica

MEnciona que el estado diguiente esta determinado por el estado siguiente.