Unidad I

Programacin dinmica (DP)

Programacin dinmica

La tcnica de Programacin dinmica fue inventada
como un mtodo general de optimizacin de
procesos de decisin por etapas.

La tcnica de programacin dinmica es adecuada
para resolver problemas cuya solucin puede
caracterizarse recursivamente (como con la tcnica
divide y vencers) y en la que los subproblemas que
aparecen en la recursin se solapan de algn modo,
lo que significara una repeticin de clculos
inaceptable si se programara la solucin recursiva de
manera directa.

La aplicacin de la tcnica de programacin
dinmica evita la repeticin de clculos mediante la
memorizacin de la solucin de cada subproblema
en una tabla, de manera que no haya que calcularlo
mas de una vez.
Fases para la aplicacin de la tcnica

La aplicacin de la tcnica de programacin
dinmica tiene dos fases fundamentales:

1 Definir recursivamente la solucin del problema.

2 Definir la estructura de datos para memorizar las
soluciones de los subproblemas y escribir el
algoritmo que va calculando los valores de esa
estructura de datos siguiendo la caracterizacin de
la solucin definida en la fase 1, pero sin repetir el
calculo de soluciones de subproblemas.
CONCEPTUALIZACIN DE PROGRAMACIN DINMICA

1. En contraste con la programacin lineal, no se cuenta con
una formulacin matemtica estndar para el problema de
Programacin dinmica.

2. Se trata de un enfoque de tipo general para la solucin de
problemas y las ecuaciones especficas que se usan se
deben desarrollar para que representen cada situacin
individual.

3. Se necesita un cierto grado de creatividad y un buen
conocimiento de la estructura general de los problemas de
Programacin Dinmica para reconocer cundo y cmo se
puede resolver un problema por medio de estos
procedimientos.
TIPOS DE PROGRAMACIN DINMICA

1. Programacin dinmica determinstica.

El estado en la siguiente etapa est completamente
determinado por el estado y la poltica de decisin de la etapa
actual.

2. Programacin dinmica probabilstica.

El estado en la siguiente etapa no est completamente
determinado por el estado y la poltica de decisin de la etapa
actual, existiendo en su lugar una distribucin de probabilidad
para determinar cul ser el siguiente estado.
CARACTERSTICAS DE PROGRAMACIN
DINMICA

1. Etapas:

El problema se puede dividir en etapas que
requieren una poltica de decisin en cada una de
ellas.

2. Estados asociados:
Cada etapa tiene cierto nmero de estados
asociados con su inicio.
3. Poltica de decisin:

El efecto de la poltica de decisin en cada etapa es
transformar el estado actual en un estado asociado
con el inicio de la siguiente etapa.

4. Diseo de solucin:

El procedimiento de solucin est diseado para
encontrar una poltica ptima para el problema
completo, es decir, una receta para la poltica de
decisin ptima en cada etapa para cada uno de los
estados posibles.
5. Principio de optimalidad:

a. Dado el estado actual, una poltica ptima para
las etapas restantes es independiente de la
poltica adoptada en etapas anteriores.

b. La decisin inmediata ptima depende slo del
estado actual y no de cmo se lleg ah.

6. Inicio de solucin:

El procedimiento de solucin se inicia al encontrar
una poltica ptima para la ltima etapa.

7. Relacin recursiva:

Se dispone de una relacin recursiva que identifica la
poltica ptima para la etapa n, dada la poltica
ptima para la etapa n + 1.

8. Retroceso:

Cuando se use esta relacin recursiva, el
procedimiento de solucin comienza al final y se
mueve hacia atrs etapa por etapa encontrando
cada vez la poltica ptima para esa etapa hasta
que se encuentra la poltica ptima desde la etapa
inicial.
Ejemplo: problema de la ruta ms corta

Supongamos que se trata de seleccionar la ruta ms
corta entre dos ciudades. La red de la figura
siguiente muestra las rutas posibles entre el inicio del
nodo1 y el destino en el nodo 7.
Las rutas pasan por ciudades intermedias,
representadas por los nodos 2 a 6.

Este problema se puede resolver enumerando en
forma detallada todas las rutas entre los nodos 1 y 7
(hay 5).
Para resolver el problema con programacin
dinmica primero se descompone en etapas,
delimitadas por las lneas verticales interrumpidas
de la figura. A continuacin se hacen los clculos
para cada etapa por separado.

El concepto general es calcular las distancias
(acumuladas) mas cortas a todos los nodos
terminales de una etapa, para usarlas a
continuacin como datos de la etapa inmediata
posterior. La etapa 1 tiene 3 nodos finales, 2,3 y 4,
y sus clculos son sencillos.
Resumen de los resultados de la etapa 1.

Distancia mas corta al nodo 2= 7 millas (desde el nodo 1)
Distancia mas corta al nodo 3 = 8 millas (desde el nodo 1)
Distancia mas corta al nodo 4 = 5 millas (desde el nodo 1)
A continuacin, la etapa 2 tiene 2 nodos extremos,
el 5 y el 6. si se considera primero el nodo 5, se ve
en la figura que hay tres rutas posibles para llegar a
el, que son (2,5), (3,5) y (4,5).

Esta informacin, junto con las distancias mas
cortas a los nodos 2, 3 y 4 determina la distancia
(acumulada) mas corta al nodo 5, como sigue:
De igual manera para el nodo 6 se tiene
Resumen de resultados de la etapa 2:

Distancia ms corta al nodo 5 = 12 millas (desde el
nodo 4)
Distancia ms corta al nodo 6= 17 millas ( desde el
nodo 3)

El ultima paso es examinar la etapa 3. El nodo del
destino 7 se puede alcanzar ya sea desde el nodo 5
o desde el nodo 6. Usando el resumen de los
resultados de la etapa2, y las distancias de los nodos
5 y 6 al nodo 7, se obtiene.
Resumen de resultado de la etapa 3

Distancia ms corta al nodo 7= 21 millas (desde el
nodo 5).

Estos clculos indican que la distancia mas corta entre
los nodos 1 y 7 es 21 millas. Las ciudades que definen
la ruta optima se determinan como sigue.

Segn el resumen de la etapa 3, el nodo 7 esta
enlazado con el nodo 5. a continuacin segn el
resumen de la etapa 2 el nodo 4 esta vinculado al nodo
5. por ultimo, segn el resumen de la etapa 1, el nodo 4
esta enlazado con el nodo 1. as, la ruta ms corta se
define como: 1---- 4-----5 ----- 7.

Donde F4(X4)= 0 para X4 =7.

El orden asociado de clculos es f3 ---- f2-----f1

Etapa 3.

Como el nodo 7 (X4=7) est conectado con los nodos 5 y 6
(X3=5 y 6) con exactamente una ruta a cada uno, no hay
alternativas para elegir, y los resultados de la etapa 3 se
pueden resumir como sigue:

X3 d(x3,x4)/x4=7 solucin optima/ f3(x3) x4
5 9 9 7
6 6 6 7
Etapa 2. la ruta (2,6) esta bloqueada, porque no existe. Dada
f3(x3) desde la etapa 3, se pueden comparar las alternativas
factibles como se ven en el siguiente cuadro:

X2
2 12+9=21 --------------- 21 5
3 8+9=17 9+6=15 15 6
4 7+9=16 13+6=19 16 5
La solucin optima de la etapa 2 se lee como sigue:
si usted si usted est en las ciudades 2 o 4, La ruta
ms corta pasa por la ciudad 5, y si est en la
ciudad 3, la ruta ms corta pasa por la ciudad 6.

Etapa1.

Desde el nodo 1 se tiene tres rutas alternativas:
(1,2), (1,3), (1,4). Se usa f2(x2) desde la etapa 2
para calcular el siguiente cuadro
La solucin optima en la etapa 1 indica que la ciudad
1 esta enlazada con la ciudad 4. a continuacin, la
solucin optima en la etapa 2 enlaza la ciudad 4 con
la ciudad 5. por ultimo, la solucin optima en la
etapa 3 conecta la ciudad 5 con la ciudad 7. As la
ruta completa es 1 --- 4 ---5 ---- 7.
Ejemplos caractersticos de DP de sistemas de
energa elctrica

1. Planificacin de la expansin de la generacin

2. Programacin semanal de grupos trmicos

3. Coordinacin hidrotrmica
Planificacin de la expansin de la generacin
Minimizar los costes totales (fijos y variables) de expansin del
equipo generador para un alcance de varios aos.

Decisiones: Potencia a instalar de cada tipo de generacin en
cada ao del alcance del modelo.

Restricciones de expansin:
Potencia instalada inicial conocida.
Mxima (mnima) potencia instalable, inversin mxima
(mnima), nmero mximo
(mnimo) de generadores instalables en cada ao.
Restricciones de operacin:
Balance generacin demanda en cada ao.
Estados: Nmero total de generadores instalados al comienzo
de cada ao.
Respuesta al problema planteado:

El Ingeniero Forestal tiene un costo mnimo de $24
para ir desde su oficina al lugar de cosecha, y ese
mnimo lo puede lograr yendo desde su oficina al
lugar 3 luego al lugar 8 luego al lugar 9 y de ah al
lugar 13, que es donde est la cosecha.
Programacin Dinmica Probabilstica.

En la programacin dinmica probabilstica, el
estado en la etapa siguiente no queda
completamente determinado por el estado y la
decisin de la subpoltica en el estado actual, sino
que existe una distribucin de probabilidad para lo
que sera el estado siguiente.
Grficamente tenemos: