Programacion Dinamica

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

11.1. Resumen del Trabajo . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

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

2

2. Programación Dinámica Discreta

3

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

3

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

3

2.1.2. Elproblema . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

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

4

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

6

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

7

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

82.2.2. Ecuación Funcional . . . . . . . . . . . . . . . . . . . . . . . .

9

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

9

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

10

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

12

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

13

2.4. El Problema de la Dimensión. . . . . . . . . . . . . . . . . . . . . . .

15

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

16

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

17

3. Aplicación al Cálculo de Variaciones

19

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

3.2. Resolución Numérica de Problemas Variacionales . . . . . . . . . . .

21

4. Programación Dinámica Estocástica

i

23

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

23

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

24

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

244.2.2. Valuación de una Opción . . . . . . . . . . . . . . . . . . . . .

26

ii

1.

1.1.

Introducción

Resumen del Trabajo

La Programación Dinámica es un método de optimización de extraordinaria versatilidad. 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 mismasideas pueden utilizarse en otro tipo de problemas de matemática aplicada, 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 deOptimalidad 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 paraaquellos 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 resolución de problemas aplicados con el auxilio de las...