Algoritmica II

Raúl Antelo J.
2019
Cronograma

Miércoles 18/09/2019 Inicio de la materia

Miércoles 02/10/2019 Primer parcial 30%

Viernes 18/10/2019 Segundo parcial 30%

Viernes 01/11/2019 Examen final 40%

TÉCNICAS DE ANÁLISIS

Programación Dinámica
1. PROGRAMACIÓN DINÁMICA
Introducción y concepto
- La programación dinámica es una técnica matemática
que se utiliza para la solución de problemas matemáticos
seleccionados, en los cuales se toma un serie de
decisiones en forma secuencial.

- Proporciona un procedimiento sistemático para encontrar

la combinación de decisiones que maximice la
efectividad total, al descomponer el problema en etapas,
las que pueden ser completadas por una o más formas
(estados), y enlazando cada etapa a través de cálculos
recursivos.
 1. PROGRAMACIÓN DINÁMICA

“La PD es una técnica matemática de optimización restringida, que divide en

etapas la solución de los problemas y se utiliza para tomar una serie de
decisiones interrelacionadas, ligadas entre sí por medio de una función
recursiva. El objetivo es proporcionar un procedimiento sistemático que sirva
para determinar la mejor combinación de decisiones que pueda
maximizar y/o minimizar la efectividad global de todo el sistema”
1. PROGRAMACIÓN DINÁMICA
Definiciones
- Etapa: es la parte del problema que posee un conjunto
de alternativas mutuamente excluyentes, de las cuales se
seleccionará la mejor alternativa.
- Estado: es el que refleja la condición o estado de las
restricciones que enlazan las etapas. Representa la “liga”
entre etapas de tal manera que cuando cada etapa se
optimiza por separado la decisión resultante es
automáticamente factible para el problema completo.
1. PROGRAMACIÓN DINÁMICA
Solución de problemas
- La programación dinámica no cuenta con una
formulación matemática estándar, sino que se trata de
un enfoque de tipo general para la solución de
problemas, y las ecuaciones específicas que se usan se
deben desarrollar para que representen cada situación
individual.
- Comúnmente resuelve el problema por etapas, en donde
cada etapa interviene exactamente una variable de
optimización (u optimizadora)
1. PROGRAMACIÓN DINÁMICA

- Optimalidad: Si consideramos una trayectoria óptima

entre los puntos E0 y Et de la figura; en ciertas condiciones
toda porción o pedazo de esta trayectoria es en sí
óptima entre todas las trayectorias posibles. Esta
propiedad constituye el principio de optimalidad cuya
demostración es trivial. El principio de optimalidad ilustra
que los problemas de PD, solo pueden ser resueltos si se
los descompone en etapas o secuencias.
- La teoría unificadora fundamental de la programación
dinámica es el Principio de Optimalidad, que nos indica
básicamente como se puede resolver un problema
adecuadamente descompuesto en etapas utilizando
cálculos recursivos.
1. PROGRAMACIÓN DINÁMICA

- “Una política óptima tiene la propiedad de que,

independientemente de las decisiones tomadas para
llegar a un estado particular, en una etapa particular, las
decisiones restantes deben constituir una política óptima
para abandonar ese estado”,
- Para resolver problemas de PD se requiere un buen
conocimiento de la estructura general de los problemas
para reconocer cuando un problema se puede resolver
por medio de estos procedimientos y como esto se
puede llevar a cabo.
1. PROGRAMACIÓN DINÁMICA
Características de problemas de PD
- El problema se puede dividir en etapas que requieren una
política de decisión en cada una.
- Cada etapa tiene cierto número de estados asociados a
ella.
- El efecto de la política de decisión en cada etapa es
transformar el estado actual en un estado asociado con
la siguiente etapa.
- El procedimiento de solución esta diseñado para
encontrar una política óptima para el problema
completo.
1. PROGRAMACIÓN DINÁMICA
Características de problemas de PD
- Dado un estado actual, una política óptima para las
etapas restantes es independiente de la política
adoptada en las etapas anteriores (principio de
optimalidad).
- El procedimiento de solución se inicia al encontrar la
política optima para la ultima etapa.
- Se dispone de una relación recursiva que identifica la
política optima par la etapa n dada la política optima
para la etapa (n+1)
1. PROGRAMACIÓN DINÁMICA
Recursividad
Existen dos formas de plantear la fórmula de recursividad en
los problemas de programación dinámica:
- Recursividad de Retroceso: el problema se resuelva
partiendo de la última etapa hacia la primera.
- Recursividad de Avance: el problema se resuelve
partiendo de la primera etapa hacia la última.
1. PROGRAMACIÓN DINÁMICA
Problema de la Diligencias
Un caza fortunas de Missouri decide irse al oeste a unirse a
la fiebre del oro en California. Tiene que hacer el viaje en
diligencia a través de territorios sin ley donde existían serios
peligros de ser atacados en el camino. Aún cuando su
punto de partida y destino eran fijos, tenia muchas opciones
en cuanto a que estados debía elegir como puntos
intermedios. Se desea estimar la ruta mas segura , como el
costo de la póliza para cualquier jornada de la diligencia
esta basada en una evaluación de seguridad del recorrido,
la ruta mas segura debe ser aquella que tenga el costo
total mas barato.
¿Cuál es la ruta que minimiza el costo total de la póliza?
1. PROGRAMACIÓN DINÁMICA
Problema de la Diligencias

Solución 1: Seleccionar la ruda mas corta sin pensar en la

optimalidad en el futuro.
Solución 2: Encontrar la ruta óptima tanteando todas las
soluciones posibles (1 x 3 x 3 x 2 x 1 = 18 posibilidades)
Solución 3: Usar programación dinámica
1. PROGRAMACIÓN DINÁMICA
Problema de la Diligencias
1. PROGRAMACIÓN DINÁMICA
Variables importantes en la resolución

n = Etapa que se está resolviendo

xn = Variable de decisión, estado inmediato
s = Estado que se evalúa
c(s, xn) = Costo de ir del estado s al estado xn
fn(s, xn) = Costo óptimo total acumulado
1. PROGRAMACIÓN DINÁMICA
Problema de la ruta mas corta
La empresa de correo DHL, desea obtener una ruta para
recorrer la menor cantidad de kilómetros desde la ciudad 1
hasta la ciudad 12, pero se encuentra en la dificultad de
que hay muchos pueblos intermedios y se tienen
demasiadas rutas. Se le pide a ud. que diseñe la ruta mas
corta a fin de que en el viaje se recorra la menor cantidad
de kilómetros en el menor tiempo posible.
Utilice Programación Dinámica para encontrar su respuesta
teniendo en cuenta que la red de caminos y distancia se
presentan en el esquema adjunto:
1. PROGRAMACIÓN DINÁMICA
Problema de la ruta mas corta