programación dinamica

Conceptos y ejemplos básicos de
Programación Dinámica

Wilson Julián Rodríguez Rojas
julianrodriguez1212@hotmail.com

Trabajo de Grado para Optar por el Título de Matemático

Director: Pervys Rengifo Rengifo
Ingeniero Universidad Nacional de Colombia

Fundación Universitaria Konrad Lorenz
Facultad de Matemáticas
Bogotá D.C.
2005Introducción......................................................................................................................4
Programación dinámica...................................................................................................5
Ejemplos de funciones recursivas ....................................................................................6
Ejemplo1.1:...................................................................................................................6
Ejemplo 1.2:...................................................................................................................6

Ejemplos de Programación Dinámica.............................................................................7
Ejemplo 1.3 (El problema de la diligencia).....................................................................7
Teorema de optimalidad...............................................................................................12
Ejemplo 1.4: (Problema de la distribución de la inversión)...........................................13
Ejemplo 1.5: (Proble ma de la subdivisión óptima)........................................................17
Ejemplo 1.6: (Problema de ProgramaciónLineal)........................................................23
Ejemplo 1.7: (Problema de Programación Lineal Entera)............................................25
Ejemplo 1.8: (Problema de Programación no Lineal)...................................................27

Comparación entre los métodos basados en ecuaciones recursivas de
avance y los basados en ecuaciones recursivas deretroceso........................................31
Ejemplo 1.9:.................................................................................................................31

Conclusión ......................................................................................................................33Bibliografía.....................................................................................................................33

2

Resumen
Se presentan algunos resultados de la teoría matemática de Programación
Dinámica y se exponen ejemplos que muestran la gran versatilidad de la
técnica. También se muestra un esquema de demostración del Principio
de Optimalidad.

Abstract
Some results of the Mathematical theory of Dynamic Programming are
presented and some of the consequences ofthese results are exposed
through examples that demonstrate the great versatility this technique
owns; There is here also included a demonstration scheme of the
Optimal Principle.

3

Introducción

El presente trabajo comprende la exposición de la teoría y algunos
ejemplos de Programación Dinámica (P.D.). La P.D. está comprendida
dentro de un conjunto de técnicas matemáticas que a suvez forman parte
de un área más amplia, conocida como Investigación de Operaciones.
Esta última puede definirse como una ciencia interdisciplinaria que tiene
por objeto la búsqueda de estrategias que permitan obtener resultados
óptimos en el desarrollo de actividades por parte de sistemas hombremáquina (estos sistemas pueden estar formados exclusivamente por
hombres, por máquinas o por unacombinación de los dos). Como se verá
más adelante, los problemas propios de la P.D. son aquellos que pueden
ser divididos en subproblemas, los cuales, a su vez, tienen una estructura
igual al problema original (en este sentido podría decirse que tienen una
estructura “fractal”). Para este propósito, el método consiste en dividir el
problema en etapas, resolver la primera de estas, utilizar...