PDF de programación - Programación Dinámica

Programación Dinámica

Manuel Maurette e Ignacio Ojea

Junio de 2006

Agradecimientos:

Nuestro reconocimiento a la Dra. Susana Puddu, por su compromiso con la labor

docente y con los alumnos y, especialmente, al Dr. Fabio Vicentini por su tesón en la

difusión de la matemática aplicada y la generosidad con que brinda sus

conocimientos a los estudiantes.

Índice

1. Introducción

1.1. Resumen del Trabajo . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2. Historia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2. Programación Dinámica Discreta

2.1. El Problema del Camino de Mínimo Costo . . . . . . . . . . . . . . .

2.1.1. Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.2. El problema . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.3. El planteo con Programación Dinámica . . . . . . . . . . . . .

2.1.4. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2. El método general . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.1. Principio de optimalidad . . . . . . . . . . . . . . . . . . . . .

2.2.2. Ecuación Funcional . . . . . . . . . . . . . . . . . . . . . . . .

2.3. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.1. Asignación de un Recurso . . . . . . . . . . . . . . . . . . . .

2.3.2. Multiplicación de Matrices . . . . . . . . . . . . . . . . . . . .

2.3.3. El Problema de la Carga . . . . . . . . . . . . . . . . . . . . .

2.4. El Problema de la Dimensión.

. . . . . . . . . . . . . . . . . . . . . .

2.5. Multiplicadores de Lagrange . . . . . . . . . . . . . . . . . . . . . . .

2.5.1. Los Multiplicadores de Lagrange en Programación Dinámica .

3. Aplicación al Cálculo de Variaciones

3.1. El Planteo Formal con Programación Dinámica . . . . . . . . . . . .

3.2. Resolución Numérica de Problemas Variacionales

. . . . . . . . . . .

4. Programación Dinámica Estocástica

i

1

1

2

3

3

3

3

4

6

7

8

9

9

10

12

13

15

16

17

19

20

21

23

4.1. Procesos de Decisión Markoviana . . . . . . . . . . . . . . . . . . . .

4.2. Ejemplos de Retorno Incierto . . . . . . . . . . . . . . . . . . . . . .

4.2.1. Distribución de un Producto . . . . . . . . . . . . . . . . . . .

4.2.2. Valuación de una Opción . . . . . . . . . . . . . . . . . . . . .

23

24

24

26

ii

1.

Introducción

1.1. Resumen del Trabajo

La Programación Dinámica es un método de optimización de extraordinaria ver-
satilidad. Si bien fue desarrollada especialmente para la resolución de problemas en
Procesos de Decisión en Múltiples Pasos, diferentes investigaciones han mostrado que
las mismas ideas pueden utilizarse en otro tipo de problemas de matemática aplica-
da, e incluso pueden ser útiles en el planteo de algunas cuestiones teóricas. Habiendo
surgido en los inicios de la época de las computadoras, la Programación Dinámica
fue, además, concebida con un ojo puesto en esta potente herramienta. La Ecuación
Funcional que se obtiene, para cada problema, a través del uso del Principio de Op-
timalidad de Bellman permite, con mayor o menor esfuerzo dependiendo del caso,
establecer una recurrencia que es, en sí misma, un algoritmo que resuelve el problema
en cuestión.

El objetivo de esta monografía es brindar un panorama relativamente amplio de
las aplicaciones de la Programación Dinámica, de manera que resulte accesible para
cualquier estudiante de Licenciatura, incluso para aquellos que no estén familiarizados
con las áreas especícas de dichas aplicaciones. Persiguiendo este n, procuramos, en
la medida en que el espacio lo permitió, exponer todos los pasos de cada razonamiento
y los elementos teóricos básicos para su comprensión.

Atendiendo a la utilidad principal de la Programación Dinámica, esto es: la res-
olución de problemas aplicados con el auxilio de las computadoras; nuestro trabajo
se centra en la exposición y resolución de algunos ejemplos clásicos, a través de los
cuales intentamos mostrar las ideas que pone en juego la técnica de la Programación
Dinámica, su versatilidad y, también, sus limitaciones.

Teniendo en cuenta que temas como, por ejemplo, el Cálculo de Variaciones o los
Procesos Estocásticos, difícilmente sean abordados en las materias regulares de una
carrera de Licenciatura, preferimos dar prioridad a los problemas discretos y deter-
minísticos, que requieren menos conocimientos teóricos previos para su comprensión,
y dejar las aplicaciones de la Programación Dinámica en estas áreas para el nal.
Dadas las limitaciones de extensión, debimos, a nuestro pesar, reducir los últimos
temas abordados a su mínima expresión.

1

1.2. Historia

Durante la Segunda Guerra Mundial la investigación matemática se extendió hacia
zonas que hasta entonces le habían sido ajenas. Si bien la participación de la ciencia,
y de la matemática en particular, en los enfrentamientos bélicos, puede remontarse
a la organización, por parte de Arquímedes, de las defensas de Siracusa, lo cierto es
que, hasta la Segunda Guerra, no habían existido políticas consecuentes de aplicación
especíca de la matemática a problemas de importancia en esta materia.

En realidad, este fenómeno comenzó en los años previos al estallido de la guer-
ra. Alemania, Inglaterra, Estados Unidos y la U.R.S.S. formaron equipos de investi-
gación, cuyos trabajos fueron la base de muchos de los inventos que aparecieron en
funcionamiento durante la guerra (el radar, por ejemplo) y que abrieron las nuevas
ramas de la matemática que se desarrollarían enormemente después de 1945.

La primera gran disciplina que surgió a partir del abordaje matemático de los
problemas especícos de la guerra fue, seguramente, la Investigación Operativa1. El
término Operations Research fue utilizado por primera vez en Inglaterra, en 1941.
Las investigaciones realizadas en los centros de Investigación Operativa de la Royal
Air Force y otros organismos militares británicos permitieron, entre otras cosas, in-
crementar la ecacia de la los patrullajes aéreos en busca de submarinos alemanes, y
consecuentemente, la cantidad de submarinos dañados o hundidos.

Rápidamente se hizo evidente que las mismas técnicas utilizadas en el ámbito mil-
itar podían servir en otras áreas de aplicación. En los años posteriores a la Guerra se
abrieron nuevos temas de investigación y se plantearon nuevos problemas, que fueron
abordados desde una perspectiva matemática. Entre estos nuevos temas se encontra-
ba la teoría de los Procesos de Decision en Múltiples Pasos, que Richard Bellman
(1920 - 1984) abordó alrededor de 1952, y para los cuales fue pensada originalmente
la Programación Dinámica.

Después de desarrollar el método en el área especíca de los problemas de decisión
discretos, Bellman y sus colaboradores se dedicaron a la ardua tarea de formular
diferentes problemas en los términos de la Programación Dinámica. Como resultado de
esta labor, encontraron que las ideas centrales del método, en particular, el Principio
de Optimalidad, podían ser aplicadas satisfactoriamente en muchos de los problemas
abordados. Descubrieron también las limitaciones de esta técnica y hallaron modos
de sobreponerse a ellas, para algunos problemas puntuales.

La Programación Dinámica es, hoy en día, un recurso imprescindible de Matemáti-

ca Aplicada y, también, una importante herramienta teórica.

1En rigor, una traducción más exacta sería Investigación en Operaciones.

2

2. Programación Dinámica Discreta

2.1. El Problema del Camino de Mínimo Costo

2.1.1. Grafos

Llamamos grafo a un par de conjuntos V y E, de los cuales el primero contiene
los vértices o nodos, mientras que el segundo es el conjunto de las ramas o arcos y
está formado por pares de elementos de V que consideramos conectados entre sí. La
notación usual para un grafo es G = (V, E).

Nos interesa particularmente considerar el caso en que los elementos (u, v) ∈ E son
pares ordenados. Cuando esto sucede, el grafo se dice dirigido y las ramas se notan:
u → v. A modo de ejemplo, La Fig. 1 representa un grafo en donde V = {1, 2, 3, 4} y
E = {(1, 2); (4, 2); (3, 1)}.

Figura 1: Ejemplo de Grafo

En un grafo dirigido un camino del vértice u al vértice v es una sucesión de ramas

u → u1, u1 → u2, ..., uk−1 → v que conectan u con v.

Por último, un grafo se dice acíclico si no forma ciclos, es decir, si no existe ningún

camino que comience y termine en el mismo vértice.

2.1.2. El problema

Sea G = (V, E) un grafo dirigido y acíclico, donde cada arco u → v tiene asociado
un costo cuv ∈ R, y donde el costo de un camino se computa sumando los costos de
las ramas que lo componen.

El hecho de que sea acíclico implica que todo camino naliza en un vértice del que
no sale ninguna echa, al que llamamos terminal. Dado un vértice cualquiera, u ∈ V ,
el problema consiste en hallar un camino de costo mínimo que parta de u y nalice
en un vértice terminal. Un camino con estas características se llama camino óptimo
que parte de u.

Esta formulación matemática sirve de modelo para diversos problemas. El ejemplo
más sencillo es el de una red de carreteras que conectan una localidad de origen con
otra de destino, pasando por varias localidades intermedias. En este caso, el costo de

3

un tramo de ruta podría ser su longitud. Es a partir de este ejemplo que el problema
suele presentarse con el nombre de problema del camino más corto.

Debe tenerse en cuenta que tanto V como E pueden tener una enorme cantidad
de elementos, por lo que la búsqueda de un camino de costo mínimo representa un
auténtico problema. Por otra parte y como veremos luego en un ejemplo, una política
codiciosa a corto plazo, que tome en cada nodo la rama que resulte menos costosa,
no conduce, generalmente, a la construcción de un camino de costo mínimo.

Antes de encarar la resolución del problema, observemos que, puesto que existen
nitos caminos, debe existir al menos uno de costo mínimo. Es decir: nuestro problema
tiene solución.

2.1.3. El planteo con Program