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.