Programacion-dinamica--algoritmo-ejemplos-e-implementacion

Vista previa del material en texto

UNIVERSIDAD NACIONAL AUTÓNOMA 
 DE MÉXICO 
 
 FACULTAD DE CIENCIAS 
 
 
PROGRAMACIÓN DINÁMICA: ALGORITMO, 
EJEMPLOS E IMPLEMENTACIÓN 
 
 
 
 
 
 
 
 
 
 
T E S I S 
 
 
 QUE PARA OBTENER EL TÍTULO DE: 
 ACTUARÍA 
 P R E S E N T A : 
 
EUNICE CARPIO MACEDO 
 
 
 
 
 
 
 
 
 
 
DIRECTOR DE TESIS: 
MTRA. MARÍA DEL CARMEN HERNÁNDEZ 
AYUSO 
2017 
 
 
Veronica
Texto escrito a máquina
CIUDAD UNIVERSITARIA, CD.MX.
 
UNAM – Dirección General de Bibliotecas 
Tesis Digitales 
Restricciones de uso 
 
DERECHOS RESERVADOS © 
PROHIBIDA SU REPRODUCCIÓN TOTAL O PARCIAL 
 
Todo el material contenido en esta tesis esta protegido por la Ley Federal 
del Derecho de Autor (LFDA) de los Estados Unidos Mexicanos (México). 
El uso de imágenes, fragmentos de videos, y demás material que sea 
objeto de protección de los derechos de autor, será exclusivamente para 
fines educativos e informativos y deberá citar la fuente donde la obtuvo 
mencionando el autor o autores. Cualquier uso distinto como el lucro, 
reproducción, edición o modificación, será perseguido y sancionado por el 
respectivo titular de los Derechos de Autor. 
 
 
 
ii 
1. Datos del alumno. 
Carpio 
Macedo 
Eunice 
044 55 6319 7474 
Universidad Nacional Autónoma de México 
Facultad de Ciencias 
Actuaría 
306147696 
 
2. Datos del tutor 
M. en I.O. 
María del Carmen 
Hernández 
Ayuso 
 
3. Datos del sinodal 1 
Dra. 
Claudia Orquídea 
López 
Soto 
 
4. Datos del sinodal 2 
M. en I. 
Adrián 
Girard 
Islas 
 
5. Datos del sinodal 3 
Mat. 
Laura 
Pastrana 
Ramírez 
 
4. Datos del sinodal 4 
Act. 
David Chaffrey 
Moreno 
Fernández 
 
5. Datos del trabajo escrito 
Programación Dinámica: algoritmo, ejemplos e implementación 
No. de páginas: 146 
2017 
 
i 
Introducción 
La programación dinámica es una técnica que permite determinar eficientemente las decisiones que 
optimizan el comportamiento de un sistema que evoluciona a lo largo de una serie de etapas. Ejemplos de 
sistemas o procesos en múltiples etapas pueden ser encontrados en diversas actividades de la vida 
cotidiana: determinar la ruta a seguir para llegar más rápido a un destino, programar la política óptima 
para la compra de productos e inventario de almacenes, tomar la decisión de participar o no en un 
programa de inversión, etcétera. 
El inicio y desarrollo de la programación dinámica se debe a Richard Bellman alrededor de la 
década de los cincuenta; su trabajo aportó una herramienta eficiente para dar respuesta a una amplia clase 
de problemas. En años más recientes, diferentes especialistas se han dedicado a ahondar en esta teoría de 
programación dinámica enriqueciendo el trabajo realizado por el matemático estadounidense. En términos 
generales esta técnica divide un problema en una secuencia de subproblemas y resuelve cada uno de ellos 
de manera recursiva, por lo que encontrar la solución del problema original se traduce en resolver 
subproblemas más sencillos y combinar las soluciones encontradas para la construcción de la solución del 
problema original, esta técnica es similar a “divide y vencerás”. Lo anterior es conocido como el 
algoritmo de programación dinámica. 
El objetivo de esta tesis es estudiar y analizar el algoritmo de programación dinámica con la 
finalidad de resolver problemas clásicos de programación dinámica, además de crear una herramienta 
computacional diseñada para la resolución de los mismos con ejemplos expuestos en el presente trabajo. 
Cabe señalar que esta herramienta puede servir de apoyo para los estudiantes y profesores del área de 
investigación de operaciones para el aprendizaje del algoritmo y el análisis de los problemas. 
El capítulo 1 aborda el punto medular de la tesis: el algoritmo de programación dinámica. En esta 
parte se presenta la definición de la programación dinámica, así como las características principales de los 
problemas que son resueltos con esta técnica. Posteriormente, se introducen los elementos básicos de un 
problema de programación dinámica tales como: etapas, estados, variables de decisión, costos y función 
de recurrencia. 
A lo largo de los siguientes capítulos se muestran diferentes tipos de problemas clasificados en 
dos grupos: determinísticos y probabilísticos. En cada uno de los apartados se describen de manera 
ii 
general las características de los problemas y se resuelven ejemplos que ayudarán a entender la lógica que 
sigue el algoritmo de programación dinámica. 
Primero, en el capítulo 2 se analizan y resuelven diferentes problemas determinísticos, es decir, 
aquellos en los que el azar no está involucrado en la evolución del sistema. Uno de los temas centrales de 
este capítulo es la formulación y solución de un problema de ruta más corta, esto debido a que los 
problemas de programación dinámica de estados finitos pueden ser vistos como un problema de este tipo. 
Por otro lado, en el capítulo 3 se describen las características de problemas probabilísticos en donde el 
comportamiento o la evolución del sistema no es completamente predecible. 
De acuerdo con el objetivo de la tesis y con base en lo analizado en los primeros capítulos, se 
implementaron una serie de rutinas que permiten resolver diferentes problemas utilizando el algoritmo de 
programación dinámica; a este conjunto de rutinas se le denominó “Prográmica”. Los algoritmos fueron 
construidos en Microsoft Excel utilizando el lenguaje de programación Visual Basic, el cual es sencillo y 
de fácil acceso para la mayoría de los usuarios. En el capítulo 4 se presenta la estructura de cada uno de 
los programas implementados, definiendo las variables y funciones utilizadas. 
El último capítulo es un manual cuyo propósito es facilitar la operación de la interfaz creada, de 
manera que el usuario pueda resolver correctamente los problemas con “Prográmica”. Además, se 
muestra como ejemplo la solución de los problemas mencionados en capítulos anteriores. 
Finalmente, en los anexos se muestran las líneas de código utilizadas en la construcción de las 
rutinas, así como ejemplos resueltos con “Prográmica”. 
iii 
Índice 
Introducción ................................................................................................................................................... i 
Índice ........................................................................................................................................................... iii 
Capítulo 1. Programación dinámica ......................................................................................................... 1 
1.1. Antecedentes ................................................................................................................................. 1 
1.2. Introducción .................................................................................................................................. 3 
1.3. Definición ..................................................................................................................................... 3 
1.3.1. Características ....................................................................................................................... 4 
1.4. Primer problema ............................................................................................................................ 4 
1.5. El problema de programación dinámica ....................................................................................... 6 
1.5.1. Ecuación de transformación de estados ................................................................................ 6 
1.5.2. Función de costo ................................................................................................................... 7 
1.5.3. Políticas de selección ............................................................................................................8 
1.6. El problema básico ........................................................................................................................ 9 
1.6.1. Planteamiento formal .......................................................................................................... 11 
1.7. Algoritmo de programación dinámica ........................................................................................ 12 
1.7.1. Principio de optimalidad ..................................................................................................... 12 
1.7.2. Algoritmo de programación dinámica ................................................................................ 13 
1.7.3. Función de recursión ........................................................................................................... 14 
1.7.4. Solución del primer problema ............................................................................................. 15 
1.7.5. Función de recursión multiplicativa .................................................................................... 19 
Capítulo 2. Sistemas determinísticos ..................................................................................................... 23 
2.1. Ruta más corta ............................................................................................................................. 24 
2.1.1. El problema del distribuidor ............................................................................................... 25 
2.1.2. Algoritmo de programación dinámica para rutas más cortas. ............................................. 29 
2.1.3. Representación gráfica del problema determinístico .......................................................... 30 
2.2. Problema de asignación de recursos ........................................................................................... 32 
2.2.1. Distribución de equipos médicos a distintas regiones ......................................................... 33 
2.2.2. Distribución de equipos médicos a distintas regiones como problema de rutas más cortas 36 
2.3. Problema de la mochila ............................................................................................................... 41 
2.3.1. Primer ejemplo del problema de la mochila ....................................................................... 42 
2.3.2. Segundo ejemplo del problema de la mochila. ................................................................... 45 
Veronica
Texto escrito a máquina
iv 
2.3.3. El problema de la mochila como un problema de rutas más cortas .................................... 48 
2.4. Problema de inventario ............................................................................................................... 50 
2.4.2. Estrategia de producción de lotes de revistas ...................................................................... 52 
2.4.3. Estrategia de producción de lotes de revistas como problema de rutas más cortas ............ 55 
2.5. Problema de reemplazo de maquinaria ....................................................................................... 58 
2.5.1. Política de reemplazo de una camioneta ............................................................................. 58 
2.5.2. Política de reemplazo de una camioneta como problema de rutas más cortas .................... 63 
Capítulo 3. Sistemas probabilísticos ...................................................................................................... 69 
3.1. Costos de la etapa actual inciertos, estado de la próxima etapa conocido .................................. 70 
3.1.1. Ejemplo: Plan de inversión en programas de educación ..................................................... 70 
3.2. Maximizar la probabilidad de ocurrencia de eventos favorables ................................................ 74 
3.2.1. Ejemplo: Probabilidad de ganar .......................................................................................... 74 
3.3. Problema de control de inventario .............................................................................................. 78 
Capítulo 4. Prográmica .......................................................................................................................... 85 
4.1. Objetivo....................................................................................................................................... 85 
4.2. Plataforma utilizada .................................................................................................................... 85 
4.3. Lenguaje de programación Visual Basic..................................................................................... 85 
4.4. Estructura general de los programas ........................................................................................... 90 
4.5. Programa para el problema de rutas más cortas .......................................................................... 90 
4.6. Programa para el problema de la mochila ................................................................................... 94 
4.7. Programa para el problema de inventario ................................................................................. 100 
Capítulo 5. Manual de usuario: Prográmica ........................................................................................ 107 
5.1. Requisitos .................................................................................................................................. 107 
5.2. Inicio ......................................................................................................................................... 107 
5.3. Menú Principal .......................................................................................................................... 108 
5.4. Interfaz para rutas más cortas .................................................................................................... 109 
5.5. Interfaz para el problema de la mochila .................................................................................... 111 
5.6. Interfaz para el problema de inventario .................................................................................... 113 
5.7. Guardar un ejercicio .................................................................................................................. 114 
5.8. Salir de Prográmica ................................................................................................................... 115 
Conclusiones ............................................................................................................................................. 117 
Bibliografía ............................................................................................................................................... 119 
Anexo 1. Código VBA de Excel para el algoritmo de rutas más cortas ............................................... 121 
v 
Anexo 2. Ejemplos de problemas de ruta más corta resueltos con Prográmica ................................... 125 
Anexo 3. Código VBA de Excel para el algoritmo del problema de la mochila. ................................. 129 
Anexo 4. Ejemplos de problemas de la mochila con Prográmica......................................................... 134 
Anexo 6. Código VBA de Excel para el algoritmo del problema de inventario................................... 140 
Anexo 7. Ejemplos de problemas de inventario resueltos con Prográmica .......................................... 146 
 
Tablas 
Tabla 1.1 Créditos otorgados por cantidad de materias en cada área de estudio .......................................... 5 
Tabla 1.2 Función de costo del problema: créditos otorgados .................................................................... 16 
Tabla 1.3 Probabilidad de fracaso de los equipos al incorporar a los expertos ...........................................20 
Tabla 2.1 Datos de rendimiento para el problema de asignación de equipos médicos ............................... 33 
Tabla 2.2 Variables para el problema de inventario ................................................................................... 53 
Tabla 2.3 Costo de operación y reventa ...................................................................................................... 58 
Tabla 4.1 Tipos de variables ....................................................................................................................... 86 
Tabla 4.2 Funciones utilizadas para construir los programas en VB .......................................................... 88 
Tabla 4.3 Variables para el programa de rutas más cortas .......................................................................... 90 
Tabla 4.4 Variables para el programa del problema de la mochila ............................................................. 94 
Tabla 4.5 Variables para el programa de inventario ................................................................................. 100 
Tabla 5.1 Requisitos del sistema para Office 2013 ................................................................................... 107 
 
Ilustraciones 
Ilustración 1.1 Representación gráfica del planteamiento del problema. ..................................................... 8 
Ilustración 2.1 Problema de programación dinámica determinística .......................................................... 24 
Ilustración 2.2 Rutas posibles para el distribuidor. ..................................................................................... 26 
Ilustración 2.3 Descomposición en etapas del problema de la ruta más corta ............................................ 28 
Ilustración 2.4 Representación gráfica de un problema determinístico. ..................................................... 31 
Ilustración 2.5 Representación gráfica: Asignación de equipos médicos. .................................................. 40 
Ilustración 2.6 Representación gráfica del problema de la mochila ........................................................... 48 
Ilustración 2.7 Representación gráfica: estrategia de producción ............................................................... 56 
Ilustración 2.8. Solución óptima de la política de reemplazo ..................................................................... 63 
Ilustración 2.9 Primera representación gráfica de un problema de reemplazo de maquinaria .................... 63 
Ilustración 2.10 Segunda representación gráfica de un problema de reemplazo de maquinaria ................. 65 
Ilustración 2.11 Ruta óptima de la política de reemplazo .......................................................................... 67 
Ilustración 3.1 Problema de programación dinámica probabilística ........................................................... 70 
Ilustración 3.2 Maximizar la probabilidad de ganar un juego .................................................................... 77 
Ilustración 3.3 Representación gráfica del problema de control de inventario ........................................... 78 
Ilustración 3.4 Representación gráfica de la política optima del problema de control de inventario ......... 84 
Ilustración 4.1 Ficha Programador. Visual Basic........................................................................................ 86 
Ilustración 4.2 Arreglo unidimensional (14) ............................................................................................... 87 
vi 
Ilustración 4.3 Arreglo bidimensional (14) ................................................................................................. 87 
Ilustración 4.4 Arreglo tridimensional (14) ................................................................................................ 88 
Ilustración 4.5 Diagrama de flujo: Rutas más cortas .................................................................................. 93 
Ilustración 4.6 Arreglos tridimensionales para el problema de la mochila ................................................. 97 
Ilustración 4.7 Diagrama de flujo: Problema de la mochila (parte 1) ......................................................... 98 
Ilustración 4.8 Diagrama de flujo: Problema de la mochila (parte 2) ......................................................... 99 
Ilustración 4.9 Diagrama de flujo: Solución óptima del problema de la mochila ..................................... 100 
Ilustración 4.10 Diagrama de flujo: Problema de Inventario (parte 1) ..................................................... 104 
Ilustración 4.11 Diagrama de flujo: Problema de Inventario (parte 2) ..................................................... 105 
Ilustración 4.12 Diagrama de flujo: Solución óptima del problema de inventario ................................... 106 
Ilustración 5.1 Habilitar contenido............................................................................................................ 108 
Ilustración 5.2 Menú principal. ................................................................................................................. 108 
Ilustración 5.3 Interfaz: rutas más cortas .................................................................................................. 110 
Ilustración 5.4 Interfaz: problema de la mochila ...................................................................................... 112 
Ilustración 5.5 Interfaz: Problema de inventario ....................................................................................... 114 
Ilustración 5.6 Salir de Prográmica ........................................................................................................... 115 
1 
 
 
 
 
Capítulo 1. Programación dinámica 
 
 
1.1. Antecedentes 
El concepto de Programación Dinámica (PD) fue desarrollado por el matemático Richard Bellman 
alrededor de la década de los cincuenta (1948-1952). El primer artículo sobre este tema fue publicado en 
1952 y es titulado On the theory of Dynamic Programming (1) (2). 
El nombre que se asigna a esta teoría tiene origen en la corporación RAND (Research ANd 
Development), una institución estadounidense sin fines de lucro denominada como laboratorio de ideas, 
que ayuda a mejorar la toma de decisiones a través de la investigación y el análisis. Bellman comenzó a 
colaborar en dicha corporación en el verano de 1949, dado su trabajo en los procesos de decisión 
multietapa. Esta corporación fue contratada por la Fuerza Aérea de los Estados Unidos en una época 
donde la investigación matemática atravesaba por un momento difícil y el término “investigación” no era 
muy bien aceptado por el gobierno. Cuando Bellman trabajaba ahí, buscaba proteger tanto a RAND como 
a la Fuerza Aérea por el hecho de hacer matemáticas dentro de la corporación, por lo que requería definir 
un término que describiera el proceso de decisión multietapa de modo tal que no los involucrara en 
conflictos (3). 
Por un lado, se buscaba reflejar el sentido de planeación, entonces se utilizó el término 
‘programación’. Además, Bellman quería transmitir la idea de que los problemas se realizaban en 
múltiples etapas como parte del proceso y que eran variantes con el tiempo, por lo que uso el término 
‘dinámica’. Finalmente, pensó en una combinación que fuera imposible usar en forma peyorativa, dada la 
difícil época, y que no pudiera ser rechazada, por ello decidió utilizar simplemente el nombre de 
‘Programación Dinámica’ (1). 
En el primer artículo de Bellman se centra el interés en una clase de problemas matemáticos que 
surgen a partir de circunstancias que requieren que una secuencia de operaciones sea realizada con el 
propósito de alcanzar un resultado deseado. Los problemas fundamentales que se clasifican en este grupo 
2 
son aquellos en los que se requiere maximizar el beneficio obtenido en un tiempo determinado o en losque el objetivo es minimizar el tiempo o los recursos requeridos para llevar a cabo cierta tarea (2). 
El matemático se avocó primeramente a investigar 3 áreas: la programación dinámica, la teoría de 
control y los procesos de desfase (time-lag processes). Cuando se dedicó a establecer las bases de la 
programación dinámica se encontró con que al derivar las ecuaciones que utilizaba para determinar la 
funcionalidad seguía la misma técnica, a la que más tarde llamaría ‘principio de optimalidad’. 
Luego de cierto tiempo en el que Bellman había estudiado esta área de la matemática, encontró 
que la solución a este tipo de problemas no era precisamente una serie de funciones que dependían del 
tiempo o un conjunto de números, sino que lo que se necesitaba era una regla o patrón que indicara a los 
tomadores de decisión cómo conducirse durante el proceso; esto es lo que se conoce como ‘política’. 
Originalmente, Bellman desarrolló la teoría de programación dinámica para procesos de decisión 
estocásticos, y más tarde la desarrolló en el contexto de la teoría de control y procesos determinísticos. 
Dado que en el mundo real muchos de los supuestos que se habían planteado no eran aplicables, comenzó 
a abordar temas de incertidumbre basado en la teoría clásica de probabilidad y luego técnicas de 
aproximación (3). 
El desarrollo de la programación dinámica de Richard Bellman constituyó una nueva parte de las 
matemáticas jugando un papel esencial, ya que es una herramienta eficiente para obtener respuesta a una 
amplia clase de problemas cuya metodología puede ser llevada a una gran cantidad de problemas que se 
desarrollan en las matemáticas. En años más recientes, diferentes matemáticos se han dedicado a ahondar 
en la teoría de programación dinámica enriqueciendo el trabajo realizado por Bellman. 
En conclusión, la teoría de la programación dinámica fue creada para resolver problemas 
matemáticos derivados de procesos de decisión en múltiples etapas, los cuales se describen como 
sistemas, cuyo estado en algún momento es determinado por un conjunto de características (parámetros o 
variables de estado). En ciertos momentos se deben tomar decisiones que afectarán el estado del sistema. 
El resultado de decisiones precedentes será utilizado para establecer la elección de las futuras, con el 
propósito de que el estado final del sistema involucre todo el proceso de evaluación sobre los parámetros 
y funciones a lo largo de los estados del sistema (4). 
 
3 
1.2. Introducción 
Las actividades o los procesos cotidianos son muy variados y pueden ser sencillos o complejos; 
sin embargo, todos ellos comparten las siguientes características esenciales: primero, existe una 
interacción entre las decisiones, es decir, una decisión hecha en un momento afectará lo que sucederá en 
un futuro y, por lo tanto, las siguientes decisiones que se tomarán; y segundo, en la mayoría de las 
ocasiones las decisiones son tomadas aún sin el conocimiento de sus resultados, es decir, existe 
incertidumbre (5). A continuación, se describirán formalmente los conceptos involucrados en la 
programación dinámica. 
1.3. Definición 
La programación dinámica es una herramienta originalmente diseñada para mejorar la eficiencia 
computacional de los métodos de solución aplicados a ciertos problemas de optimización. La idea básica 
de la técnica es descomponer el problema en subproblemas más pequeños que son computacionalmente 
más manejables (6). 
En términos generales, la programación dinámica es un procedimiento de optimización que 
convierte un problema, con decisiones múltiples y recursos limitados, en una secuencia de subproblemas 
interrelacionados y organizados en etapas; así, cada subproblema es más manejable que el problema 
original. (7). 
En cada etapa del problema debe tomarse una decisión considerando que los recursos son 
limitados. La mejor decisión será aquella que optimiza la función objetivo con respecto a la etapa actual y 
anteriores (optimización hacia adelante), o bien, la etapa actual y las futuras (optimización hacia atrás) 
(7). El resultado de cada decisión no es completamente predecible, pero puede ser anticipado hasta cierto 
punto, antes de que la siguiente decisión sea tomada (8). 
La programación dinámica permite resolver gran variedad de problemas, tanto determinísticos 
como estocásticos, donde las variables de decisión pueden ser discretas o continuas; la función objetivo y 
las restricciones pueden ser lineales o no lineales; y los datos pueden ser determinísticos, o bien, variables 
aleatorias con función de probabilidad conocida (7). 
Así, la programación dinámica utiliza una colección de herramientas matemáticas para analizar 
procesos de decisión secuencial. 
4 
1.3.1. Características 
Como parte de la introducción a la programación dinámica, se mencionan a continuación las principales 
características que cumple un problema que es resuelto con esta herramienta matemática (9). 
a) El problema puede ser dividido en subproblemas ligados entre sí, los cuales son resueltos en 
etapas. En cada una de estas etapas una toma de decisión es requerida. Por lo general, las etapas 
representan un punto en el tiempo o diferentes elementos de un conjunto (países, personas, actividades, 
periodos, etc.). 
b) En cada etapa se tiene un cierto número de estados asociados; estos incluyen toda la 
información necesaria para tomar decisiones óptimas en cada punto. La definición de estados varía de 
acuerdo con el contexto particular de cada problema. 
c) La decisión elegida en la etapa actual definirá el estado en la etapa siguiente. Esta transición 
entre estados no siempre es certera, es decir, en ocasiones hay incertidumbre en la evolución del 
problema. 
d) Dada la etapa actual, la decisión óptima de cada una de las etapas restantes no debe depender 
de estados previamente alcanzados o decisiones precedentes. 
e) Existe una recursión que relaciona el costo o beneficio de la etapa actual y las subsecuentes. 
Las características mencionadas serán descritas a lo largo de este primer capítulo, donde se 
detallan las propiedades de cada una. 
1.4. Primer problema 
Se considera un problema en el cual un estudiante debe decidir qué asignaturas cursará el próximo ciclo 
escolar. Las materias se dividen en 4 áreas de estudio y el número de créditos otorgados depende de la 
cantidad de materias que se cursan. Este estudiante solamente puede cursar 10 materias al semestre, debe 
incluir al menos una materia de cada área y se tiene un límite de materias a inscribir por área. La tabla 1.1 
muestra los créditos obtenidos por número de materias en cada área, así como la cantidad máxima de 
materias permitida. 
 
5 
Tabla 1.1 Créditos otorgados por cantidad de materias en cada área de estudio 
Área\Materias 1 2 3 4 5 6 7 
Físico Matemáticas e Ingenierías 25 50 60 80 100 -- -- 
Biológicas y de la Salud 20 70 90 100 -- -- -- 
Sociales 40 60 80 100 -- -- -- 
Humanidades y las Artes 10 20 30 40 50 60 70 
 
Entonces la interrogante es: ¿cómo debe elegir 10 materias y obtener la máxima cantidad de 
créditos? El estudiante podría elegir al azar la combinación de materias que desea, pero, ¿cómo asegurar 
que se obtendrá el máximo número de créditos? 
La mejor solución (solución óptima) se obtiene haciendo utilizando la programación dinámica, ya 
que cumple con las principales características que se han enlistado anteriormente: 
• Se puede dividir el problema a partir de las diferentes áreas de las cuales el estudiante puede 
elegir materias. 
• Antes de elegir el número de materias de cierta área se tiene el registro de cuantas materias se han 
seleccionado previamente. Es decir, se conoce la cantidad de materias que resta por elegir, siendo un total 
de 10. 
• Para cada área se debe elegir al menos una materia y un máximo de 7. Esta decisión afectará 
evidentemente la selección para las demás áreas, ya que con cada elecciónla distribución de las materias 
se delimita. 
• Dado que para cada área se va eligiendo la cantidad de materias que otorga el mayor número de 
créditos, tomando en cuenta cuántas materias restan por elegir, se asegura entonces que al considerar las 4 
áreas en conjunto se tendrá la mejor distribución. 
El escenario que se ha planteado en esta sección es un ejemplo de un problema de programación 
dinámica, en el que se muestra la fragmentación del problema en 4 subproblemas y se definen las demás 
variables que intervienen para lograr encontrar la solución óptima al problema completo. 
En los apartados siguientes se especifican los elementos necesarios para la construcción de un 
problema de este tipo, así como el procedimiento o metodología que se sigue para su solución. 
6 
1.5. El problema de programación dinámica 
En esta sección se describen los elementos básicos que forman parte de la formulación de un problema de 
programación dinámica. En particular, se está enfocando a un problema cuyo número de etapas es finito y 
el tiempo es discreto. El planteamiento que se presenta está basado en una de las referencias básicas 
cuando se habla de programación dinámica, escrita por el matemático Dimitri Bertsekas (8). 
1.5.1. Ecuación de transformación de estados 
El primer elemento del problema es un sistema dinámico en tiempo discreto, que se define como sigue: 
𝑥𝑘+1 = 𝑓𝑘(𝑥𝑘, 𝑢𝑘 , 𝑤𝑘) 𝑘 = 0, 1,⋯ ,𝑁 − 1 
(1.1) 
Donde: 
k: es el índice para el tiempo y representa una etapa. Una etapa es un momento en el cual se debe 
tomar una decisión. El problema original es dividido en subproblemas resueltos en N etapas. 
𝒙𝒌: estado del sistema. Resume la información pasada que es relevante para la futura optimización. 
Los estados son las condiciones posibles en las que se puede encontrar el sistema en determinada 
etapa del problema, además representa la conexión entre etapas. Así, cuando se optimiza 
independientemente cada etapa, la decisión será factible para el problema completo (más adelante 
definido como ‘principio de optimalidad’). 
𝒖𝒌: variable de decisión, control o alternativa seleccionada en la etapa k. Se debe tener un panorama 
de las posibilidades de decisión en cada etapa y el beneficio asociado a cada alternativa. 
𝒘𝒌: parámetro aleatorio (perturbación o ruido), representa la incertidumbre. 
N: horizonte de tiempo (veces que el control es aplicado). 
La función definida en (1.1) muestra que el estado actual del sistema depende del estado 
precedente y cambia con base en la decisión e incertidumbre. Esta función también es conocida como la 
ecuación de transformación de estados. 
7 
1.5.2. Función de costo 
La función de costo es el segundo elemento de un problema de programación dinámica. Esta función es 
fundamental pues proporciona el valor del sistema en la etapa k dado el estado en el que se encuentra el 
sistema, la decisión tomada y el elemento aleatorio. Esta función es la herramienta que ayuda a construir 
la función de recursión para el algoritmo de programación dinámica. 
El costo en que se incurre en el tiempo k está en función del estado del sistema, la alternativa 
seleccionada y el parámetro aleatorio. En general, el costo será aleatorio debido a que la perturbación 𝑤𝑘 
es una variable aleatoria. Este es denotado por: 
𝑔𝑘(𝑥𝑘, 𝑢𝑘 , 𝑤𝑘). 
(1.2) 
Si la función de costo tiene la propiedad de ser aditiva, es decir, el costo en que se incurre en cada 
etapa k se acumula con el tiempo, entonces el costo total del problema al final de todas las etapas es: 
𝑔𝑁(𝑥𝑁) + ∑ 𝑔𝑘(𝑥𝑘, 𝑢𝑘 , 𝑤𝑘
𝑁−1
𝑘=0
). 
(1.3) 
La expresión 𝑔𝑁(𝑥𝑁) hace referencia a la condición frontera, es decir, el costo incurrido al final 
del proceso. 
En realidad, puesto que interviene el azar, se optimiza el costo esperado; es decir, la esperanza 
matemática del costo total definido en (1.3): 
𝐸 [𝑔𝑁(𝑥𝑁) + ∑ 𝑔𝑘(𝑥𝑘, 𝑢𝑘 , 𝑤𝑘
𝑁−1
𝑘=0
 )]. 
(1.4) 
La esperanza es calculada con respecto a la distribución conjunta de las variables involucradas: el 
estado del sistema, la decisión y la variable de incertidumbre. La optimización es sobre las variables 𝑢𝑘, 
para 𝑘 = 0, 1,⋯ ,𝑁 − 1; estas son seleccionadas con algún conocimiento del estado actual 𝑥𝑘. 
8 
La Ilustración 1.1 muestra la representación gráfica de cada una de las etapas del problema y el 
planteamiento del mismo. Como se observa, en cada etapa las variables de entrada (inputs) son: el estado 
del sistema (𝑥𝑘), con base en el cual se elige la alternativa o decisión (𝑢𝑘) e interviene un parámetro 
aleatorio (𝑤𝑘). La interacción de estas variables produce un costo 𝑔𝑘(𝑥𝑘, 𝑢𝑘, 𝑤𝑘) y un estado del sistema 
para la etapa posterior determinado por el sistema dinámico (1.1); estas últimas son las variables de salida. 
Ilustración 1.1 Representación gráfica del planteamiento del problema. 
 
Es importante enfatizar que, si bien en este planteamiento las etapas son indexadas por k 
empezando en 0 y terminando en 𝑁 − 1 (k = 0, 1,⋯ , N − 1), en algunas ocasiones –por el contexto y 
para un mejor manejo del problema– las etapas se indexarán de la forma k = 1, 2, ⋯ , N. Esta 
particularidad se ejemplifica más adelante. 
Hasta ahora, se tienen los elementos básicos para un problema donde el horizonte es finito y el 
tiempo es discreto; uno de ellos es la variable 𝑢𝑘, definida como la variable de decisión. El objetivo del 
algoritmo de programación dinámica es minimizar el costo total (1.3) y esto se logra a través de la 
correcta selección de {𝑢𝑘}. Es sobre estas variables sobre las cuales se tiene control en cada una de las 
etapas ya que las demás entradas son aleatorias, o bien, están en función de otras variables. 
Por lo anterior, se reafirma que la selección de {𝑢𝑘} determinará la optimalidad de la solución del 
problema. La forma en la que se realiza tal selección se aborda en la siguiente sección. 
1.5.3. Políticas de selección 
Como se ha mencionado anteriormente, las decisiones son tomadas por etapas, por lo que la información 
que se reúne entre las demás etapas es útil para que las decisiones sean de mejor calidad, es decir, entre 
más información se tenga la decisión tomada será más robusta. Esto es, la selección de la variable 𝑢𝑘 se 
pospone hasta el último momento posible, es decir, se toma una decisión cuando se conoce el estado 
actual del sistema 𝑥𝑘. 
9 
Lo que se busca es establecer reglas para seleccionar 𝑢𝑘 para cada valor posible de 𝑥𝑘 y en cada 
etapa 𝑘, para 𝑘 = 0, 1,⋯ ,𝑁 − 1. Matemáticamente lo que se plantea es buscar una función que determine 
la decisión que debe tomarse en una etapa, teniendo como parámetro el estado del sistema de la etapa de 
interés. 
Con el objetivo de determinar las reglas de decisión, se define a 𝜇𝑘 como la función que asigna el 
valor 𝑢𝑘 a cada 𝑥𝑘 posible, estas son llamadas políticas admisibles (1.4) 
𝜇𝑘(𝑥𝑘) = 𝑢𝑘 
 
𝜇𝑘(𝑥𝑘)≔decisión que debe tomarse en el tiempo 𝑘 si el estado del sistema es 𝑥𝑘 . 
Una vez que se ha determinado la decisión óptima, es decir, la que otorga el máximo beneficio o 
minimiza los costos, esta se denota por 𝜇𝑘
∗ (𝑥𝑘). 
Se define además la política o ley de control para el sistema completo, denotado por 
𝜋 = {𝜇0, 𝜇1, ⋯ , 𝜇𝑁−1} , como el conjunto de decisiones realizadas a lo largo del problema. Cada 𝜋 tiene 
un costo asociado, determinado por un valor inicial del sistema 𝑥0, es denotado por 𝐽𝜋(𝑥0) y se define 
como sigue con base en (1.4): 
𝐽𝜋(𝑥0) = 𝐸 [𝑔𝑁(𝑥𝑁)+ ∑ 𝑔𝑘(𝑥𝑘, 𝜇𝑘(𝑥𝑘), 𝑤𝑘
𝑁−1
𝑘=0
 )]. 
(1.5) 
Así, la finalidad es minimizar el valor de 𝐽𝜋(𝑥0) sobre toda 𝜋 que satisfaga las condiciones del 
problema. 
1.6. El problema básico 
El problema general que se plantea es aquel en el que las decisiones son tomadas bajo incertidumbre 
estocástica sobre un número finito de etapas. En cada uno delos problemas, los elementos necesarios para 
obtener la solución, con base en la programación dinámica, son los siguientes: 
• Etapas: 𝑘. 
• Estados: 𝑥𝑘 . 
• Decisiones: 𝑢𝑘. 
10 
• Ecuación de transformación de estados: 𝑥𝑘+1 = 𝑓𝑘(𝑥𝑘, 𝑢𝑘 , 𝑤𝑘). 
• Parámetros aleatorios independientes con distribución de probabilidad conocida: 𝑤𝑘 . 
• Restricciones de la variable de control 𝒖𝒌. 
• El costo acumulado: 𝐸 [𝑔𝑁(𝑥𝑁) + ∑ 𝑔𝑘(𝑥𝑘, 𝑢𝑘 , 𝑤𝑘
𝑁−1
𝑘=0 )]. 
• Optimización sobre políticas, reglas para seleccionar: 𝑢𝑘 en la etapa k y para cada 𝑥𝑘 posible. 
En el caso particular del problema planteado en la sección 1.4, en el cual no existe parámetro 
aleatorio, se enlistan los componentes necesarios para la solución del problema: 
♦ Etapas: Se definen con base en el número de áreas, en este caso habrá 4 etapas. Se considerará el 
siguiente orden: 𝑘 = 0, Físico Matemáticas e Ingenierías; 𝑘 = 1, Biológicas y de la Salud; 𝑘 = 2, 
Sociales y 𝑘 = 3, Humanidades y las Artes. El número de etapas es 𝑁 = 4. 
♦ Estados: 𝑥𝑘 es la cantidad de materias que pueden ser elegidas al inicio de la etapa 𝑘. El estado 
inicial, condición de frontera, es 𝑥0 = 10, es decir, un máximo de 10 materias debe ser elegido. 
♦ Variable de decisión: En cada etapa se debe decidir qué cantidad 𝑢𝑘 se seleccionará. Dada la 
naturaleza del problema, se supone que el mínimo valor de 𝑢𝑘 es 1 (dado que se debe elegir al 
menos una materia por área) y el valor máximo es 7. Además, se debe cumplir que 𝑢𝑘 ≤ 𝑥𝑘. 
♦ Función de costo: El costo por cursar la materia es representado por los créditos obtenidos. La 
función de costo en la k-ésima etapa está dada por: 
𝑔𝑘(𝑥𝑘, 𝑢𝑘, 𝑤𝑘) = 𝑔𝑘(𝑢𝑘). 
Los valores de esta función se encuentran en la Tabla 1.1 Créditos otorgados por cantidad de 
materias en cada área de estudio. 
♦ Ecuación de transformación de estados: Al inicio del periodo 𝑘 + 1 la cantidad disponible de 
materias es 
𝑥𝑘+1 = 𝑥𝑘 − 𝑢𝑘 . 
 
♦ Función de recurrencia: Esta función es una herramienta que sirve para identificar, en este caso, 
aquella decisión en la etapa k de la cual se obtiene el beneficio máximo. Esta función es de la 
siguiente forma: 
 
𝐽𝑘(𝑥𝑘) = máx
𝑢𝑘
E
𝑤𝑘
{𝑔𝑘(𝑢𝑘) + 𝐽𝑘+1(𝑥𝑘+1)} = máx
𝑢𝑘
 {𝑔𝑘(𝑢𝑘) + 𝐽𝑘+1(𝑥𝑘+1)} . 
 
11 
En términos generales la función de recursión en la etapa 𝑘 acumula el costo de las etapas 𝑘 + 1,
𝑘 + 2,⋯ ,𝑁 dado el estado del sistema 𝑥𝑘, la decisión 𝑢𝑘 y las decisiones óptimas en etapas sucesivas. 
Esta función debe optimizarse sobre la mejor decisión en la etapa actual tomando en cuenta únicamente el 
estado actual. 
La relación entre las etapas es evidente ya que cuando se está en la etapa 𝑘 y se retrocede en el 
tiempo, la nueva función de recurrencia 𝐽𝑘−1(𝑥𝑘−1) se deriva utilizando la función 𝐽𝑘(𝑥𝑘), misma que se 
obtuvo en la iteración anterior del algoritmo y este proceso se mantiene repetitivo hasta llegar a la etapa 
inicial. 
Hasta aquí se han definido los elementos básicos de la formulación de un problema de horizonte 
finito. Como se mencionó anteriormente, la programación dinámica fragmenta el problema original en 
subproblemas interrelacionados, por lo que se resolverá el problema paso a paso, es decir, primero se 
definirán las condiciones iniciales del problema para 𝑘 = 𝑁 = 4 y se empezará a partir de la etapa final 
(𝑁 − 1 = 3), terminando en la etapa inicial 𝑘 = 0 para así obtener la solución óptima del problema del 
estudiante. Este es un ejemplo de algoritmo “hacia atrás”. 
1.6.1. Planteamiento formal 
Se tiene un sistema dinámico discreto 𝑥𝑘+1 = 𝑓𝑘(𝑥𝑘, 𝑢𝑘 , 𝑤𝑘) para 𝑘 = 0, 1,⋯ ,𝑁 − 1, donde el espacio 
para cada una de las variables son los siguientes: 
𝑥𝑘 ∈ 𝑆𝑘 , 𝑢𝑘 ∈ 𝐶𝑘 , 𝑤𝑘 ∈ 𝐷𝑘. 
(1.6) 
El control 𝑢𝑘 está restringido a tomar valores en el conjunto no vacío 𝑈𝑘, el cual cumple la 
propiedad: 𝑈𝑘 ⊂ 𝐶𝑘. Este nuevo espacio definido depende de 𝑥𝑘 para toda 𝑥𝑘 ∈ 𝑆𝑘 y 𝑘 = 0,1,…𝑁. 
La perturbación aleatoria 𝑤𝑘 tiene una distribución de probabilidad 𝑃(∙| 𝑥𝑘 , 𝑢𝑘) la cual, se 
observa, depende de 𝑥𝑘 𝑦 𝑢𝑘 pero no de los valores de 𝑤𝑘−1, 𝑤𝑘−2,⋯ ,𝑤0, es decir, son independientes 
entre ellas. 
Las políticas consisten en la secuencia de funciones 𝜋 = {𝜇0, 𝜇1, ⋯ , 𝜇𝑁−1}. La función 𝜇𝑘 
mapea los estados 𝑥𝑘 en los controles 𝑢𝑘, es decir, 𝑢𝑘 = 𝜇𝑘(𝑥𝑘), donde 𝜇𝑘(𝑥𝑘) ∈ 𝑈𝑘(𝑥𝑘) para toda 
𝑥𝑘 ∈ 𝑆𝑘 . Tales políticas son llamadas admisibles y dependen de la evolución del sistema. 
12 
Por lo que, dado un estado inicial 𝑥0 y una política admisible π, la ecuación del sistema estará 
definida como sigue: 
𝑥𝑘+1 = 𝑓𝑘(𝑥𝑘, 𝜇𝑘(𝑥𝑘),𝑤𝑘) 𝑘 = 0, 1,⋯ ,𝑁 − 1 
(1.7) 
en donde 𝑥𝑘 y 𝑤𝑘 son variables aleatorias con distribuciones bien definidas. 
Entonces, dadas las funciones 𝑔𝑘, el costo esperado (1.8) es una cantidad bien definida. 
𝐽𝜋(𝑥0) = E [𝑔𝑁(𝑥𝑁)+ ∑ 𝑔𝑘(𝑥𝑘, 𝜇𝑘(𝑥𝑘),𝑤𝑘
𝑁−1
𝑘=0
 )]. 
 
(1.8) 
Como se ha mencionado, el objetivo es minimizar los costos tomando siempre la mejor decisión. 
Entonces para el estado inicial 𝑥0 dado, una política óptima Π
∗ es aquella que minimiza el costo, es decir: 
 
𝐽π∗(𝑥0) = min
𝜋𝜖Π
 𝐽𝜋(𝑥0). 
(1.9) 
La función definida en (1.9), asigna a cada valor inicial 𝑥0 el costo óptimo. 
Una vez que se han mostrado los elementos del problema básico de programación dinámica y se 
ha definido formalmente el planteamiento, es posible establecer el algoritmo de programación dinámica. 
Este algoritmo es la herramienta fundamental para la solución óptima de problemas secuenciales. 
1.7. Algoritmo de programación dinámica 
En esta sección se describirá el algoritmo general que sigue la programación dinámica para encontrar la 
solución óptima en un problema finito de tiempo discreto, como se ha descrito anteriormente. Al inicio se 
enuncia el principio de optimalidad, el cual es fundamental en la técnica que se está estudiando. 
1.7.1. Principio de optimalidad 
El principio de optimalidad dice que, dado un estado del sistema, la decisión óptima para cada una de las 
etapas restantes es independientemente de los estados previamente alcanzados o las decisiones tomadas 
13 
(9), es decir, la política óptima para las siguientes etapas no depende de la política utilizada en las etapas 
anteriores. Además, una vez que se conoce la solución óptima de un problema es posible conocer la 
solución óptima para cualquier subproblema. 
Matemáticamente el principio de optimalidad es como sigue: 
Sea 𝜋∗ = {𝜇0
∗, 𝜇1
∗, ⋯ , 𝜇𝑁−1
∗} una política óptima para el problema básico, suponemos que 
cuando usamos 𝜋∗ un estado 𝑥𝑖 ocurre al tiempo i con probabilidad positiva. 
Se considera el subproblema en el que nos encontramos en el estado 𝑥𝑖 en el tiempo i: El objetivo 
es minimizar el costo de transitar del tiempo i al tiempo N; este costo está dado por: 
E [𝑔𝑁(𝑥𝑁) + ∑ 𝑔𝑘(𝑥𝑘, 𝜇𝑘(𝑥𝑘),𝑤𝑘
𝑁−1
𝑘=𝑖
 )]. 
Entonces, lo que dicta el principio de optimalidad es que la política truncada 𝜇𝑖
∗, 𝜇𝑖+1
∗, ⋯ , 𝜇𝑁−1
∗ 
es óptima para este subproblema. 
El principio sugiere que la política óptima puede ser construida paso a paso, es decir, construir 
primero la política óptima para la “cola” del subproblema, es decir, la última etapa, luego se extenderá a 
las 2 últimas etapas y así sucesivamente hasta que la política óptima esté construida para el problema 
completo. Es aquí donde la función de recursión es construida, de manera que se pueda encontrar la 
solución óptima al subproblema a partir de ella. 
El algoritmo de programación dinámica tiene su fundamento en este principio y en la siguiente 
proposición: 
Proposición: Para cada estado inicial 𝑥0, el costo óptimo 𝐽
∗(𝑥0) del problema básico es igual a 
𝐽0(𝑥0), donde la función 𝐽0 está dada por el último paso del siguiente algoritmo, el cualresulta de 
retroceder en el tiempo (backward) del periodo 𝑁 − 1 al periodo inicial 0. Tal proceso es conocido como 
algoritmo de programación dinámica. 
1.7.2. Algoritmo de programación dinámica 
Para resolver un problema con etapas finitas en un tiempo discreto, el algoritmo que se sigue se describe a 
continuación: 
14 
Inicialización del algoritmo (Condiciones frontera): 
𝐽𝑁(𝑥𝑁) = 𝑔𝑁(𝑥𝑁) 
(1.10) 
Iteraciones del algoritmo 
𝐽𝑘(𝑥𝑘) = min
𝑢𝑘∈ 𝑈𝑘(𝑥𝑘)
 E
𝑤𝑘
 [𝑔𝑘(𝑥𝑘, 𝑢𝑘, 𝑤𝑘) + 𝐽𝑘+1 (𝑓𝑘(𝑥𝑘, 𝑢𝑘, 𝑤𝑘))] 
(1.11) 
para 𝒌 = 𝟎, 𝟏,⋯ ,𝑵 − 𝟏 
 
El algoritmo termina cuando se realiza la iteración con k=0. 
 
La esperanza en (1.11) se calcula con respecto a la distribución de probabilidad de 𝑤𝑘, la cual 
depende de 𝑥𝑘 y 𝑢𝑘. Además, si 𝑢𝑘
∗ = 𝜇𝑘
∗ (𝑥𝑘) se minimiza el lado derecho de la expresión (1.11) para 
cada 𝑥𝑘 y la política 𝜋
∗ = {𝜇0
∗, 𝜇1
∗, ⋯ , 𝜇𝑁−1
∗} es óptima. 
𝐽𝑘(𝑥𝑘) es el costo óptimo para un problema de N – k etapas, es el subproblema que inicia en el 
estado 𝑥𝑘 en el tiempo k y termina al tiempo N. A este se le llama el “costo de ir”, a partir del estado 𝑥𝑘. 
Por lo que finalmente se obtiene que 𝐽0(𝑥0) es el costo óptimo de un problema con 𝑁 etapas y un estado 
inicial 𝑥0. 
La función E
𝑤𝑘
 [∙] se define como función de recurrencia dado que relaciona el costo (o beneficio) 
generado durante las etapas 𝑘, 𝑘 + 1,⋯ ,𝑁 con el costo (o beneficio) de las etapas 𝑘 + 1, 𝑘 + 2, ⋯ ,𝑁. 
Esta función es la que permite realizar el procedimiento recursivo descrito en el algoritmo de 
programación dinámica. 
1.7.3. Función de recursión 
Previo a describir la clasificación de los problemas de programación dinámica, se expondrá la 
importancia y naturaleza de la función de recursión, ya que como se ha mencionado es la herramienta 
primordial para el algoritmo de programación dinámica (9). 
 Una manera simplificada de describir las funciones de recurrencia es la siguiente: 
𝐽𝑘(𝑥𝑘) = min{𝑐𝑜𝑠𝑡𝑜 𝑏𝑒𝑛𝑒𝑓𝑖𝑐𝑖𝑜⁄ 𝑑𝑒 𝑙𝑎 𝑒𝑡𝑎𝑝𝑎 𝑘 + 𝐽𝑘+1(𝑥𝑘+1)}. 
15 
Un punto que se debe considerar es que, de acuerdo con el contexto de los problemas, se buscará 
maximizar o bien minimizar el costo/beneficio total del problema. 
La definición de 𝐽𝑘(𝑥𝑘) refleja el hecho de que el mínimo costo acumulado desde la etapa 𝑘 hasta 
la 𝑁 es resultado de seleccionar aquella acción que minimice la suma del costo/beneficio en el que se 
incurre en la etapa 𝑘, más el costo mínimo que tiene el problema acumulado desde la etapa 𝑘 + 1 hasta el 
final del problema. 
Para la función de recurrencia se deben identificar 3 características del problema a ser resuelto: 
a. El conjunto de decisiones posibles depende de la etapa y del estado del sistema. 
b. Se debe especificar cómo se determinan los costos con base en la etapa, el estado del sistema y las 
variables de decisión. 
c. La evolución de los estados, o la ecuación de transformación de estados, debe ser descrito de 
manera que se involucre la etapa, el estado del sistema y las variables de decisión. 
Los ejemplos que se exponen a lo largo del presente trabajo utilizan funciones de recursión 
aditivas, es decir, el costo en el que se incurre en cada etapa sigue un proceso acumulativo, sin embargo, 
también existen problemas en los cuales la función recursiva no involucra la suma de sus elementos. 
Dependiendo de la naturaleza del problema se puede definir una función recursiva multiplicativa o bien, 
alguna otra operación como maximizar o minimizar (max/min). Al final del presente capítulo se muestra 
un ejemplo en donde la función de recursión involucra la multiplicación de sus elementos. 
1.7.4. Solución del primer problema 
Para la solución del problema que se ha planteado en la Sección 1.4 tienen los siguientes datos: 𝑁 = 4 
donde: 𝑘 = 0, se refiere al área de asignaturas Físico Matemáticas e Ingenierías; 𝑘 = 1, Biológicas y de 
la Salud; 𝑘 = 2, Sociales y 𝑘 = 3, Humanidades y las Artes. Además, se definen las siguientes variables: 
• 𝑥𝑘 = número de materias que se pueden elegir al inicio de la etapa 𝑘. 
• 𝑢𝑘 = número de materias del área 𝑘 seleccionadas. 
• 𝑤𝑘 = en este caso no existe parámetro aleatorio. 
• 𝑔𝑘(𝑥𝑘, 𝑢𝑘 , 𝑤𝑘) = 𝑔𝑘(𝑢𝑘), la cantidad de créditos otorgados dependiendo del número de materias 
𝑢𝑘 seleccionadas del área 𝑘 (Ver Tabla 1.2). 
16 
• 𝐽𝑘(𝑥𝑘) = max
𝑢𝑘
{𝑔𝑘(𝑢𝑘) + 𝐽𝑘+1(𝑥𝑘+1)}. 
• 𝑢𝑘
∗ es la selección óptima (que conduce a obtener el valor 𝐽𝑘(𝑥𝑘)) 
 
Tabla 1.2 Función de costo del problema: créditos otorgados 
Área 𝒌 𝒖𝒌 
𝒈𝒌(𝒖𝒌) 
1 2 3 4 5 6 7 
Físico Matemáticas e 
Ingenierías 
0 25 50 60 80 100 -- -- 
Biológicas y de la Salud 1 20 70 90 100 -- -- -- 
Sociales 2 40 60 80 100 -- -- -- 
Humanidades y las Artes 3 10 20 30 40 50 60 70 
 
Las iteraciones del algoritmo se muestran en las siguientes tablas. Se ejemplifica el cálculo paso 
por paso en la etapa 𝑘 = 3; los cálculos son análogos para todas las etapas y variables. 
Etapa 4: Condiciones frontera 
Las condiciones frontera del algoritmo son 𝐽4(𝑥4) = 0 para toda 𝑥4. 
Etapa 3: Humanidades y las Artes 
Primero, se debe considerar que al menos se debe tener capacidad de incluir una materia del área de 
Humanidades y las Artes, además al menos una materia de las 3 áreas restantes debe ser seleccionada, por 
lo tanto, se tiene que 𝑥3 = 1, 2, 3 ⋯ , 7. Por otro lado, las restricciones para la variable de decisión 𝑢3 
son: 
➢ 1 ≤ 𝑢3 ≤ 7 (el máximo número de materias disponibles en esta área son 7) 
➢ 𝑥3 − 𝑢3 ≥ 0 (la selección no debe ser mayor a la cantidad de materias disponibles a ser 
seleccionadas) 
Se toma el caso en el que 𝑥3 = 3 para ejemplificar el procedimiento del algoritmo. 
𝐽3(3) = max
1≤𝑢3≤3
{𝑔3(𝑢3) + 𝐽4(𝑥4)} = max
1≤𝑢3≤3
{𝑔3(𝑢3) + 0} = max {𝑔3(1), 𝑔3(2), 𝒈𝟑(𝟑)} 
=max{10, 20, 𝟑𝟎} = 30 
17 
De lo anterior se obtiene que 𝐽3(3) = 30, con 𝑢3
∗ = 3. Este proceso es de la misma forma para 
todos los valores posibles de 𝑥3. Los resultados se muestran en la siguiente tabla: 
 𝒖𝟑 
 𝒙𝟑 
𝒈𝟑(𝒖𝟑) 𝑱𝟑(𝒙𝟑) 𝒖𝟑
∗ 
1 2 3 4 5 6 7 
1 10 -- -- -- -- -- -- 10 1 
2 10 20 -- -- -- -- -- 20 2 
3 10 20 30 -- -- -- -- 30 3 
4 10 20 30 40 -- -- -- 40 4 
5 10 20 30 40 50 -- -- 50 5 
6 10 20 30 40 50 60 -- 60 6 
7 10 20 30 40 50 60 70 70 7 
 
Etapa 2: Sociales 
Las restricciones de las variables, así como la función de recurrencia de esta etapa son las siguientes: 
➢ 2 ≤ 𝑥2 ≤ 8 (se debe tener capacidad para incluir al menos una materia del área 𝑘 = 2 y una 
del área 𝑘 = 3. Además, se debe seleccionar al menos una materia de las áreas 𝑘 = 1,0). 
➢ 1 ≤ 𝑢2 ≤ 4 (se puede seleccionar un máximo de 4 materias del área). 
➢ 𝑥2 − 𝑢2 ≥ 1 (la selección debe dejar disponible al menos 1 materia para la etapa 𝑘 = 3). 
➢ 𝐽2(𝑥2) = max
𝑢2
{𝑔2(𝑢2) + 𝐽3(𝑥2 − 𝑢2)}. 
Ejemplo de cálculo: 𝑥2 = 5 
𝐽2(5) = max
1≤𝑢2≤4
{𝑔2(𝑢2) + 𝐽3(5 − 𝑢2)} 
= max{𝑔2(1) + 𝐽3(4), 𝑔2(2) + 𝐽3(3), 𝑔2(3) + 𝐽3(2), 𝒈𝟐(𝟒) + 𝑱𝟑(𝟏)} 
= max{40 + 40, 60 + 30, 80 + 20, 𝟏𝟎𝟎 + 𝟏𝟎} = max{80, 90, 100, 𝟏𝟏𝟎} = 110 
De lo anterior se obtiene que 𝐽2(5) = 110, con 𝑢2
∗ = 4. Este proceso es de la misma forma para 
todos los valores posibles de 𝑥2. Los resultados se muestran en la siguiente tabla: 
 𝒖𝟐 
 𝒙𝟐 
𝒈𝟐(𝒖𝟐) + 𝑱𝟑(𝒙𝟐 − 𝒖𝟐) 𝑱𝟐(𝒙𝟐) 𝒖𝟐
∗ 
𝟏 𝟐 𝟑 𝟒 
2 50 -- -- -- 50 1 
3 60 70 -- -- 70 2 
4 70 80 90 -- 90 3 
5 80 90 100 110 110 4 
6 90 100 110 120 120 4 
7 100 110 120 130 130 4 
8 110 120 130 140 140 4 
18 
Etapa 1: Biológicas y de la Salud 
Las restricciones de las variables y la función de recurrencia de esta etapa son las siguientes: 
➢ 3 ≤ 𝑥1 ≤ 9 (se debe tener capacidad para incluir al menos una materia del área 𝑘 = 1 y una de 
las áreas 𝑘 = 2, 3 . Además, se debe seleccionar al menosuna materia del área 𝑘 = 0). 
➢ 1 ≤ 𝑢1 ≤ 4 (se puede seleccionar un máximo de 4 materias del área). 
➢ 𝑥1 − 𝑢1 ≥ 2 (la selección debe dejar disponibles al menos 2 materias para las etapas 𝑘 = 2, 3). 
➢ 𝐽1(𝑥1) = max
𝑢1
{𝑔1(𝑢1) + 𝐽2(𝑥1 − 𝑢1)}. 
Ejemplo de cálculo: 𝑥1 = 9 
𝐽1(9) = max
1≤𝑢1≤4
{𝑔1(𝑢1) + 𝐽2(9 − 𝑢1)} 
= max{𝑔1(1) + 𝐽2(8), 𝑔1(2) + 𝐽2(7), 𝒈𝟏(𝟑) + 𝑱𝟐(𝟔), 𝒈𝟏(𝟒) + 𝑱𝟐(𝟓)} 
= max{20 + 140, 70 + 130, 𝟗𝟎 + 𝟏𝟐𝟎, 𝟏𝟎𝟎 + 𝟏𝟏𝟎} = max{160, 200, 𝟐𝟏𝟎, 𝟐𝟏𝟎} = 210 
De lo anterior se obtiene que 𝐽1(9) = 210, con 𝑢2
∗ = 3, 4 . Este proceso es de la misma forma 
para todos los valores posibles de 𝑥1. Los resultados se muestran en la siguiente tabla: 
 
 𝒖𝟏 
 𝒙𝟏 
𝒈𝟏(𝒖𝟏) + 𝑱𝟐(𝒙𝟏 − 𝒖𝟏) 𝑱𝟏(𝒙𝟏) 𝒖𝟏
∗ 
𝟏 𝟐 𝟑 𝟒 
3 70 -- -- -- 70 1 
4 90 120 -- -- 120 2 
5 110 140 140 -- 140 2 o 3 
6 130 160 160 150 160 2 o 3 
7 140 180 180 170 180 2 o 3 
8 150 190 200 190 200 3 
9 160 200 210 210 210 3 o 4 
Etapa 0: Físico Matemáticas e Ingenierías 
Las restricciones de las variables, así como la función de recurrencia de esta etapa son las siguientes: 
➢ 𝑥0 = 10 (al inicio se tiene la posibilidad de elegir 10 materias). 
➢ 1 ≤ 𝑢1 ≤ 5 (se puede seleccionar un máximo de 5 materias del área). 
➢ 𝑥1 − 𝑢1 ≥ 3 (la selección debe dejar disponibles al menos 3 materias para las etapas 𝑘 = 1,2,3). 
➢ 𝐽0(𝑥0) = max
𝑢0
{𝑔0(𝑢0) + 𝐽1(𝑥0 − 𝑢0)}. 
Los resultados de esta iteración se muestran en la siguiente tabla: 
 
19 
 𝒖𝟎 
 𝒙𝟎 
𝒈𝟎(𝒖𝟎) + 𝑱𝟏(𝒙𝟎 − 𝒖𝟎) 𝑱𝟎(𝒙𝟎) 𝒖𝟎
∗ 
𝟏 𝟐 𝟑 𝟒 5 6 7 
10 235 250 240 240 240 -- -- 250 2 
 
De la última iteración (𝑘 = 0) es posible obtener la solución óptima del problema realizando el 
rastreo de la misma, como se muestra a continuación: 
𝑥0 = 10 ⟹ 𝑢0
∗ = 2 
𝑥1 = 𝑥0 − 𝑢0 = 8 ⟹ 𝑢1
∗ = 3 
𝑥2 = 𝑥1 − 𝑢1 = 5 ⟹ 𝑢2
∗ = 4 
𝑥3 = 𝑥2 − 𝑢2 = 1 ⟹ 𝑢3
∗ = 1 
Lo anterior indica que del área Físico Matemática e Ingenierías debe seleccionar 2 materias, de 
las correspondientes al área Biológicas y de la Salud debe cursar 3 materias, del área de Sociales se deben 
incorporar 4 materias y, finalmente, del área de Humanidades y las Artes el estudiante debe seleccionar 
solamente una materia. Esta forma de elegir las materias otorga al estudiante un total de 𝐽0(10) = 250 
créditos, que es la cantidad máxima. 
El problema anterior ejemplifica de manera sencilla el funcionamiento del algoritmo de 
programación dinámica para obtener la solución óptima tal que se maximice el beneficio obtenido. En los 
capítulos siguientes se aborda una serie de problemas clásicos dentro de este campo, mismos que están 
divididos en dos grupos: Sistemas determinísticos y sistemas estocásticos. 
1.7.5. Función de recursión multiplicativa 
El siguiente problema que se expone es un ejemplo de una función recursiva que no involucra la suma de 
sus elementos, en este caso la función recursiva se define como una multiplicación de sus elementos. 
Problema: Actualmente en una empresa se lleva a cabo un proyecto de mercadotecnia de uno de 
los productos que lanzará a la venta el próximo año. Se cuenta con 3 equipos diferentes y cada uno de 
ellos formula un proyecto diferente. Con base en la experiencia en años pasados, se calcula que la 
probabilidad de que el proyecto de los equipos fracase es de 50%, 60% y 80%, respectivamente. 
Entonces, la probabilidad total de fracaso es de 0.50*0.60*0.80 = 0.24. 
Dado que el objetivo es minimizar la probabilidad total de fracaso, la empresa contratará 2 
expertos más, mismos que se asignarán a uno de los equipos de mercadotecnia. La Tabla 1.3 muestra la 
20 
probabilidad de fracaso para los equipos 1, 2 y 3 en caso de que 0, 1 o 2 expertos sean añadidos al mismo. 
Entonces, el problema a resolver es determinar la manera óptima en que estos 2 nuevos expertos se deben 
asignar a los equipos. 
Tabla 1.3 Probabilidad de fracaso de los equipos al incorporar a los expertos 
 Equipo 
Expertos 
incorporados 
1 2 3 
0 0.50 0.60 0.80 
1 0.20 0.50 0.50 
2 0.15 0.20 0.40 
 
Variables del problema: 
• 𝑁: El número de etapas es igual al número de equipos, es decir, 𝑁 = 3 donde 𝑘 = 1, 2, 3. 
• 𝑥𝑘: El estado del sistema se define como en número de expertos disponibles a ser asignados para los 
equipos 𝑘, 𝑘 + 1,⋯ , 3. En el caso particular de este problema, los valores posibles de 𝑥𝑘 son 0, 1 o 2 
para toda 𝑘. 
• 𝑢𝑘: La variable de decisión en cada etapa es la cantidad de expertos añadidos al equipo 𝑘. Los 
valores posibles para 𝑢𝑘 son 0, 1 o 2 para toda 𝑘. 
• Ecuación de transformación de estados: 𝑥𝑘+1 = 𝑥𝑘 − 𝑢𝑘. 
• Función de costo: Se denota 𝑝𝑖(𝑢𝑖) como la probabilidad de fracaso del equipo 𝑖 si son añadidos 𝑢𝑖 
expertos. Los valores de esta función se determinan con base en la Tabla 1.3. 
• La función de recursión se define de la siguiente manera: 𝐽𝑘(𝑥𝑘) = min
𝑢𝑘
[𝑝𝑘(𝑢𝑘) ∗ 𝐽𝑘+1(𝑥𝑘+1)]. 
 
 
Condiciones frontera: 𝐽4(𝑥4) = 1 
Etapa 𝒌 = 𝟑 
 𝒑𝟑(𝒖𝟑) 
𝑱𝟑(𝒙𝟑) 𝒖𝟑
∗ 𝒖𝟑 
 𝒙𝟑 
0 1 2 
0 0.80 -- -- 0.80 0 
1 0.80 0.50 -- 0.50 1 
2 0.80 0.50 0.40 0.40 2 
 
21 
Etapa 𝒌 = 𝟐 
 𝒑𝟐(𝒖𝟐) ∗ 𝑱𝟑(𝒙𝟑) 
𝑱𝟐(𝒙𝟐) 𝒖𝟐
∗ 𝒖𝟐 
 𝒙𝟐 
0 1 2 
0 0.48 -- -- 0.48 0 
1 0.30 0.40 -- 0.30 0 
2 0.24 0.25 0.16 0.16 2 
 
Etapa 𝒌 = 𝟏 
 𝒑𝟏(𝒖𝟏) ∗ 𝑱𝟐(𝒙𝟐) 
𝑱𝟏(𝒙𝟏) 𝒖𝟏
∗ 𝒖𝟏 
 𝒙𝟏 
0 1 2 
2 0.080 0.060 0.072 0.060 1 
 
De las iteraciones que se muestran en las tablas anteriores es posible concluir que la solución 
óptima al problema es la siguiente: 
• En el primer equipo (𝑘 = 1) se debe asignar 1 experto (𝑢1
∗ = 1). Esta selección deja 1 experto 
disponible para los siguientes equipos. 
• Para el segundo equipo (𝑘 = 2), se tiene 1 experto disponible (𝑥2 = 1). Sin embargo, la decisión 
óptima es no asignar ningún experto a este equipo (𝑢2
∗ = 0). 
• Finalmente, para el tercer equipo (𝑘 = 3) se tiene 1 experto disponible (𝑥3 = 1), mismo que debe 
incorporarse a este equipo (𝑢3
∗ = 1). 
Con esta asignación de los 2 expertos a los equipos 1 y 3, se logra una probabilidad total de 
fracaso del 6% (𝐽1(2) = 0.06). 
23 
 
 
 
Capítulo 2. Sistemas determinísticos 
 
 
Los problemas determinísticos son aquellos en los que cada perturbación 𝑤𝑘 puede tomar un solo valor; 
es decir, no es una variable aleatoria con una función distribución de probabilidad conocida. En contraste 
con los problemas estocásticos, el conocimiento de los resultados no representa ventaja alguna en 
términos de optimización, por lo que minimizar el costo total sobre las políticas admisibles 
𝜇0, 𝜇1,⋯ , 𝜇𝑁−1 resulta en el mismo costo óptimo que cuando se minimiza sobre secuencias de control 
𝑢0, 𝑢1,⋯ , 𝑢𝑁−1 ya que la única diferencia entre estas dos es que la primera depende del estado del 
sistema. 
Lo anterior se debe a que, dado un estado inicial, la evolución del sistema y las decisiones o 
controles futuros son previsibles. Por lo tanto, se tiene que 𝑢𝑘 = 𝜇𝑘(𝑥𝑘) para 𝑘 = 0, 1,⋯ ,𝑁 − 1, en 
donde los estados 𝑥𝑘 son determinados por 2 elementos: primero, el estado inicial 𝑥0 y segundo la 
variable de decisión 𝑢𝑘. Así, la evolución del sistema o la función de transformación de estados es la 
siguiente: 
𝑥𝑘+1 = 𝑓𝑘( 𝑥𝑘, 𝑢𝑘) 𝑘 = 0, 1,⋯ ,𝑁 − 1. 
(2.1) 
Se considera un sistema determinístico en donde el espacio de estados 𝑆𝑘 es un conjunto finito 
para cada 𝑘; entonces, en cualquier estado 𝑥𝑘, la selección de un control 𝑢𝑘 está asociada a una transición 
al estado 𝑓𝑘(𝑥𝑘, 𝑢𝑘), con un costo 𝑔𝑘(𝑥𝑘, 𝑢𝑘) (8). 
Se estará hablando de problemas determinísticos cuando el estado en la próxima etapa esté 
completamente determinado por la política y la decisión tomada en la etapa actual. La programación 
dinámica determinísticase describe gráficamente como se observa en la Ilustración 2.1. 
 
24 
Ilustración 2.1 Problema de programación dinámica determinística 
 
Entonces, en cualquier etapa 𝑘 el proceso estará en algún estado 𝑥𝑘 y aplicando la política 𝑢𝑘 el 
proceso “se mueve” a un estado 𝑥𝑘+1 de la siguiente etapa. De acuerdo con el algoritmo, el costo óptimo 
𝐽𝑘+1(𝑥𝑘+1) ha sido calculado previamente. A este se debe añadir el “costo de ir” del estado 𝑥𝑘 al estado 
𝑥𝑘+1, denotado por 𝑔𝑘(𝑥𝑘, 𝑢𝑘). Optimizando sobre los diferentes valores de 𝑢𝑘, se obtendrá 𝐽𝑘( 𝑥𝑘). 
Existe una amplia variedad de aplicaciones de sistemas determinísticos entre los cuales se 
encuentran aquellos en los que el objetivo es encontrar la ruta más corta entre 2 puntos, asignar 
óptimamente recursos limitados para lograr el máximo beneficio posible o definir una estrategia de 
control de inventario para satisfacer la demanda de cierto producto. Algunos de estos se abordarán a lo 
largo del presente capítulo. 
Este tipo de problemas constituyen una parte importante del estudio de modelos de toma de 
decisiones, ya que –como se ha descrito– pueden ser adaptados a diversos problemas cotidianos. 
Aplicación de programación dinámica determinística 
En las siguientes secciones se exponen algunos problemas resueltos con el algoritmo de programación 
dinámica determinística. En primer lugar, se aborda la resolución del problema de rutas más cortas, ya 
que este tipo de problemas juega un papel fundamental en la programación dinámica. 
2.1. Ruta más corta 
De acuerdo con la literatura, una aplicación de la programación dinámica de particular interés es 
encontrar la ruta más corta de un origen (𝑠) a un destino (𝑡); el interés se basa en que parte de los 
problemas que son resueltos con programación dinámica pueden ser transformados a un problema de ruta 
más corta y viceversa. A continuación, se enlistan conceptos básicos de teoría de gráficas (10) (5): 
• Una red o gráfica es una pareja de conjuntos (X,A), donde X es un conjunto de nodos y A es un 
conjunto de líneas que unen a todos o algunos de los nodos. 
25 
• Si las líneas de una red tienen una dirección, representada por una flecha, se denominan arcos y 
se dice que la red es dirigida. 
• Un arco 𝑎 puede representarse como la pareja (𝑖, 𝑗), donde 𝑖, 𝑗 son los nodos que unen a dicho 
arco. Se define a 𝑖 como el nodo inicial y 𝑗 como el nodo final. 
• Una ruta o camino es una secuencia de arcos 𝑎1, 𝑎2, … , 𝑎𝑛 en la cual el nodo final de 𝑎𝑖 es igual 
al nodo inicial de 𝑎𝑖+1. 
• Se llama ciclo a una ruta en la que el nodo inicial y el nodo final es el mismo (𝑎1 = 𝑎𝑛), de esta 
forma una red se denomina cíclica si al menos contiene un ciclo. Una red será acíclica si no 
contiene ningún ciclo. 
• Una red es finita cuando contiene un numero finito de nodos. 
Los problemas de optimización en una red surgen cuando un valor 𝑐𝑖𝑗 es asociado a los arcos. La 
longitud de una ruta resulta de la suma de los valores 𝑐𝑖𝑗 de los arcos que forman la ruta. Un problema de 
optimización es encontrar la ruta con la menor (o mayor) longitud de un nodo a otro, dicho problema 
puede resolverse de manera eficiente a través de la programación dinámica (5). 
Entonces, como se mencionó previamente, un problema de programación dinámica puede 
transformarse en uno de ruta más corta y viceversa. Este problema debe ser determinístico de estados 
finitos para poder ser formulado como un problema de ruta más corta (8). En otras palabras, resolver un 
problema de programación dinámica es equivalente a encontrar la ruta más corta (o la ruta más larga) de 
una red. Esta red debe ser dirigida, finita y acíclica (5): 
En primera instancia, se ilustra un ejemplo en donde se emplea la herramienta de la programación 
dinámica para su solución y posteriormente se aborda el tema de conversión de problemas determinísticos 
a rutas más cortas. 
2.1.1. El problema del distribuidor 
Una editorial está iniciando el mes y desea tener los ejemplares de su revista para poder comenzar a 
distribuirlos entre sus suscriptores, por lo cual contacta a la imprenta para solicitar que le sean entregados 
lo más pronto posible en sus oficinas. Dada la premura de la solicitud, el encargado de trasladar los 
ejemplares desde la imprenta a la editorial –el distribuidor– debe encontrar la forma más rápida de llegar 
a su destino. 
26 
El problema consiste en encontrar la ruta más rápida de todas las posibles tomando como punto 
de partida la imprenta. Para ello, se ha recolectado información, que le permite tomar esta decisión, 
referente al tiempo de traslado entre los diferentes puntos; la información se representa en la Ilustración 
2.2, en donde el nodo 1 representa la imprenta, el nodo 7 es la editorial y los nodos restantes ilustran los 
cruces de los caminos. El número que se observa adyacente a cada arco indica las horas del viaje entre los 
cruces. Se considera que las calles son de un solo sentido. Esta gráfica cumple con las características 
antes mencionadas. 
Ilustración 2.2 Rutas posibles para el distribuidor. 
 
Primeramente, el problema será resuelto considerando cada nodo 𝑖 como una etapa del problema, 
entonces el número de etapas se determina en base en el número de nodos. En este caso habrá 7 etapas: 
𝑘 = 𝑖 = 1, 2, 3, 4, 5, 6, 7. Además, se define el estado del sistema 𝑥𝑖 como el nodo en el que se encuentra 
el distribuidor, esto es: 𝑥𝑖 = 𝑖. 
La decisión 𝑢𝑖 que se debe tomar en cada etapa es hacia qué nodo ir ( 𝑗 ), dependiendo del nodo 
en que se encuentre ( 𝑖 ). El conjunto sobre el cual se toma la decisión se reduce a aquellas j para las 
cuales existe un arco (𝑖, 𝑗). En el caso de la función de costo 𝑔𝑖(𝑥𝑖, 𝑢𝑖) = 𝑔𝑖(𝑖, 𝑗) hace referencia al 
tiempo que toma ir de un nodo a otro. Este es denotado por 𝑎𝑖𝑗, que es el tiempo de viaje a lo largo del 
arco (𝑖, 𝑗), el cual se muestra adyacente al arco correspondiente. 
Finalmente, se define la función 𝐽𝑖 como el tiempo de viaje mínimo del nodo 𝑖 al nodo final, esto 
es, 𝐽𝑖 = min
𝑗
{ 𝑎𝑖𝑗 + 𝐽𝑗}. La ruta pasa primero por el arco (𝑖, 𝑗) y luego va lo más rápido posible al nodo 
final. De aquí se selecciona aquella 𝑗 con la cual resulte el tiempo mínimo. 
La ruta con el tiempo óptimo es 𝐽1, obtenida en la etapa inicial, que es el tiempo de viaje mínimo 
del nodo 1 (imprenta) al nodo 7 (editorial), las iteraciones del algoritmo se muestran a continuación. Con 
27 
el propósito de encontrar la ruta óptima, en cada iteración del algoritmo se definirá la variable 𝑗∗, que será 
el nodo 𝑗 que minimiza la función de recurrencia. 
Etapa 7 (i=7). Inicialización del algoritmo: establecer la condición frontera. 
 
El tiempo de viaje del nodo 7 al nodo 7 es cero, entonces: 𝐽7 = 0. 
 
Etapa 6 (i=6) 
Los nodos j son aquellos para los cuales existe el arco (6, j), en este caso para el nodo 6 se tiene solo la 
posibilidad de ir al nodo 7: 
𝑗 = 7 
 𝐽6 = min
𝑗
{ 𝑎6,7 + 𝐽7} = 5 
 𝑗∗ = 7 
 
Etapa 5 (i=5) 
 𝑗 = 7 
 𝐽5 = min
𝑗
{ 𝑎5,7 + 𝐽7} = 8 
 𝑗∗ = 7 
 
Etapa 4 (i=4) 
 𝑗 = 5, 6 
 𝐽4 = min
𝑗
{ 𝑎4,5 + 𝐽5, 𝑎4,6 + 𝐽6 } = {6 + 8, 12 + 5} = {14, 17} = 14 
 𝑗∗ = 5 
 
Etapa 3 (i=3) 
 𝑗 = 5, 6 
 𝐽3 = min
𝑗
{ 𝑎3,5 + 𝐽5, 𝑎3,6 + 𝐽6} = {15, 14} = 14 
 𝑗∗ = 6 
Etapa 2 (i=2) 
 𝑗 = 5 
 𝐽2 = min
𝑗
{ 𝑎2,5 + 𝐽5} = {19} = 19 
 𝑗∗ = 4 
 
Etapa 1 (i=1) 
En esta etapa se obtendrá el valor óptimo del problema, es decir, el tiempo mínimo que le tomará ir de la 
imprenta a la editorial. 
 𝑗 = 2, 3,4 
 𝐽1 = min
𝑗
{ 𝑎1,2 + 𝐽2, 𝑎1,3 + 𝐽3, 𝑎1,4 + 𝐽4} = {25, 22,18} = 18 
 𝑗∗ = 4 
 
 
28 
Ruta óptima del distribuidor 
Para obtener la ruta óptima se debe ir rastreando el camino, iniciando desde el nodo 1 hasta alcanzar el 
nodo 7. En cada paso se debe observar el valor 𝑗∗, correspondiente al nodo 𝑖. Luego se sigue el mismo 
proceso tomando 𝑖 = 𝑗∗,lo cual se logra observando el valor correspondiente a 𝐽𝑗∗. El proceso termina 
cuando se llega a 𝑗∗ = 7. 
Rastreo de la ruta óptima: De la etapa 1, obtenemos que 𝑗∗ = 4, por lo tanto, del nodo 1 se debe pasar al 
nodo 4. Lo cual nos lleva a 𝐽4, la cual se obtiene de 𝑗
∗ = 5. Siguiendo con 𝐽5, se observa que el nodo que 
minimiza la función es 𝑗∗ = 5. Finalmente, 𝐽5 se obtiene de 𝑗
∗ = 7. 
Así, se concluye que la ruta que debe seguir el distribuidor es 1 → 4 → 5 → 7 con un tiempo de 
traslado entre la imprenta y la editorial igual a 𝐽1 = 18. 
Por otro lado, se observa que la red que acompaña al problema expuesto puede ser dividida en 
etapas, cada una de las cuales está formada por un conjunto de nodos. Esta división, se muestra en la 
Ilustración 2.3. 
En la siguiente sección se define el algoritmo que resuelve este tipo de problemas, que es 
sumamente útil ya que, como se mencionó al inicio, un problema determinístico de estados finitos puede 
transformarse en un problema de rutas más cortas. 
Ilustración 2.3 Descomposición en etapas del problema de la ruta más corta 
 
 
29 
2.1.2. Algoritmo de programación dinámica para rutas más cortas. 
Para lograr plantear el algoritmo de programación dinámica enfocado a un problema de rutas más cortas 
dividido en etapas, se define lo siguiente: 
 
𝑎𝑖𝑗
𝑘 = 𝑐𝑜𝑠𝑡𝑜 𝑑𝑒 𝑡𝑟𝑎𝑛𝑠𝑖𝑐𝑖ó𝑛 𝑒𝑛 𝑙𝑎 𝑒𝑡𝑎𝑝𝑎 𝑘 𝑑𝑒𝑙 𝑒𝑠𝑡𝑎𝑑𝑜 𝑖 𝑎𝑙 𝑒𝑠𝑡𝑎𝑑𝑜 𝑗. 𝑖 ∈ 𝑆𝑘 , 𝑗 ∈ 𝑆𝑘+1 
𝑎𝑖𝑡
𝑁 = 𝑐𝑜𝑠𝑡𝑜 𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙 𝑑𝑒𝑙 𝑒𝑠𝑡𝑎𝑑𝑜 𝑖 ( 𝑔𝑁(𝑥𝑁) ). 𝑖 ∈ 𝑆𝑁 
En caso de no existir un arco tal que nos permita el traslado del estado i al estado j en el tiempo k 
entonces 𝑎𝑖𝑗
𝑘 = ∞. 
Así, el algoritmo de programación dinámica, para el caso de rutas más cortas, es el siguiente: 
 
Se define 𝐽𝑘(𝑖) como el costo óptimo de ir del estado i al estado final t. 
Inicialización del algoritmo (Condiciones frontera): 
𝐽𝑁(𝑖) = 𝑎𝑖𝑡
𝑁 𝑖 ∈ 𝑆𝑁. 
 
Iteraciones del algoritmo 
𝐽𝑘(𝑖) = min
𝑗 ∈ 𝑆𝑘+1
 [𝑎𝑖𝑗
𝑘 + 𝐽𝑘+1(j)] 𝑖 ∈ 𝑆𝑘, 𝑗 ∈ 𝑆𝑘+1 
para 𝑘 = 0, 1,⋯ ,𝑁 − 1. 
 
El algoritmo termina cuando se realiza la iteración con 𝑘 = 0. 
El costo óptimo 𝑱𝟎(𝒔) es la ruta más corta de s a t. 
Aplicando este algoritmo al problema de la Ilustración 2.3, en las siguientes tablas se muestran 
los resultados de cada una de las iteraciones. En el ejercicio 𝑁 = 3, entonces 𝑘 = 0, 1, 2, 3. 
Etapa 3: Esta es la etapa final, el nodo 𝑖 = 7 ∈ 𝑆3 tiene un costo asociado 𝐽3(7) = 0. Estas son 
las condiciones frontera del algoritmo. 
Etapa 2: El nodo 𝑗 = 7 está conectado a los nodos 𝑖 = 5, 6 pertenecientes a esta etapa. La 
función de recursión es la siguiente: 𝐽2(𝑖) = min
𝑗 ∈ 𝑆3
 [𝑎𝑖𝑗
2 ] 𝑖 ∈ 𝑆2 = {5, 6} , 𝑗 ∈ 𝑆3 = {7}. 
 
30 
 j 
 i 
𝒂𝒊𝒋
𝟐 
𝑱𝟐(𝒊) 𝐣
∗ 
7 
5 8 8 7 
6 5 5 7 
 
Etapa 1: La función de recursión es la siguiente: 𝐽1(𝑖) = min
𝑗 ∈ 𝑆2
 [𝑎𝑖𝑗
1 + 𝐽2(j)] 𝑖 ∈ 𝑆1 =
{2, 3, 4}, 𝑗 ∈ 𝑆2 = {5, 6}. 
 j 
 i 
𝒂𝒊𝒋
𝟏 + 𝑱𝟐(𝐣) 
𝑱𝟏(𝒊) 𝐣
∗ 
5 6 
2 11+8 = 19 ∞ 19 5 
3 7+8= 15 9+5 = 14 14 6 
4 6+8 = 14 12+5 = 17 14 5 
Etapa 0: La función de recursión es la siguiente: 𝐽0(𝑖) = min
𝑗 ∈ 𝑆1
 [𝑎𝑖𝑗
0 + 𝐽1(j)] 𝑖 ∈ 𝑆0 = {1}, 𝑗 ∈
 𝑆2 = {2, 3, 4}. 
 j 
 i 
𝒂𝒊𝒋
𝟎 + 𝑱𝟏(𝐣) 
𝑱𝟎(𝒊) 𝐣
∗ 
2 3 4 
1 6 + 19 = 25 8 + 14 = 22 4 + 14 = 18 18 4 
 
La solución óptima se construye a partir de la etapa 0, que muestra que el nodo 1 se debe conectar 
con el nodo 4; luego, la etapa 2 indica que si se está en el nodo 4 se debe transitar al nodo 5, de aquí al 
nodo 7. Entonces, la ruta óptima es: 1 → 4 → 5 → 7 y la distancia asociada es 18. Este resultado coincide 
con el ejercicio resuelto, considerando un solo nodo como una etapa del problema. 
2.1.3. Representación gráfica del problema determinístico 
La presente sección aborda una de las aplicaciones más relevantes del problema de ruta más cortas. La 
importancia radica en que, como se mencionó al inicio del capítulo, los problemas determinísticos de 
estados finitos pueden ser vistos como uno de rutas más cortas. El primer paso para lograr la conversión 
de un problema determinístico a uno de rutas más cortas es la representación gráfica del problema, cuya 
metodología se define a continuación (8) (9). 
Se considera un problema determinístico de estados finitos, donde el espacio de estados 𝑆𝑘 es un 
conjunto finito para cada 𝑘, entonces: para cualquier estado 𝑥𝑘 , un control 𝑢𝑘 puede ser asociado con una 
31 
transición del estado 𝑥𝑘 al estado 𝑓𝑘(𝑥𝑘, 𝑢𝑘) generando un costo 𝑔𝑘(𝑥𝑘, 𝑢𝑘). Entonces un problema 
determinístico de estados finitos puede ser representado gráficamente siguiendo la siguiente metodología: 
i. Definir los nodos de la red: Estados del sistema. 
ii. Asignar un nodo inicial (𝑠): Estado inicial del sistema. 
iii. Definir arcos (𝑖, 𝑗): Corresponden a la transición entre los estados en etapas sucesivas; cada arco 
tiene un costo asociado denotado por 𝑎𝑖𝑗 
iv. Añadir un nodo artificial (𝑡): Este representa la etapa final del sistema; cada estado posible 𝑥𝑁 
en la etapa 𝑁 está conectado al nodo artificial mediante un arco con costo 𝑔𝑁(𝑥𝑁). 
v. Las secuencias de control corresponden a los “caminos” o “rutas” que se originan en la etapa 
inicial, a partir del nodo s y que terminan en algún nodo 𝑥𝑁 que pertenece a la etapa final N. 
Si el costo en los arcos es visto como su longitud, podemos decir que resolver el problema 
determinístico de estados finitos es equivalente a encontrar la ruta más corta del nodo inicial s al nodo 
terminal t. Una ruta es definida como una secuencia de arcos {(𝑗1, 𝑗2), (𝑗2, 𝑗3),⋯ , (𝑗𝑘−1, 𝑗𝑘)} y la longitud 
queda determinada por la suma de la longitud de sus arcos. 
Finalmente, la Ilustración 2.4 muestra la representación gráfica de un problema determinístico de 
estados finitos. 
Ilustración 2.4 Representación gráfica de un problema determinístico. 
 
 
 
32 
2.2. Problema de asignación de recursos 
Los problemas de asignación de recursos son aquellos en los que recursos limitados deben ser distribuidos 
entre diversas actividades. Este tipo de problemas puede ser resuelto de diversas maneras, una de ellas es 
la programación dinámica. La metodología descrita a continuación se basa en lo descrito en (8) (9). 
En la formulación de este problema se supone que se tienen 𝑤 unidades disponibles de cierto 
recurso y 𝑁 actividades a las cuales este recurso debe ser asignado. Entonces se tiene que en la actividad 
𝑘 se utilizan 𝑔𝑘(𝑢𝑘) unidades del recurso y se obtiene un beneficio de 𝑐𝑘(𝑢𝑘) . El problema consiste en 
determinar la asignación que maximice el beneficio total sujeto a los recursos limitados; en términos 
matemáticos se describe: 
max∑𝑐𝑘(𝑢𝑘)
𝑁
𝑘=1
 
𝑠. 𝑎.∑ 𝑔𝑘(𝑢𝑘)
𝑁
𝑘=1
≤ 𝑤, con 𝑢𝑘 enteros no negativos. 
 Para ser resuelto con el algoritmo de programación dinámica, se define 𝐽𝑘(𝑥𝑘) como el beneficio 
máximo que puede ser obtenido de las actividades 𝑘, 𝑘 + 1,⋯ , 𝑇 si se tienen 𝑥𝑘 unidades disponibles a 
ser asignadas. La recursión se generaliza como sigue: 
𝐽𝑁+1(𝑥𝑘) = 0 para toda 𝑥𝑘 
𝐽𝑘(𝑥𝑘) = max
uk
{𝑐𝑘(𝑢𝑘) + 𝐽𝑘+1(𝑥𝑘 − 𝑔(𝑢𝑘))}. 
Este tipo de problemas tiene una amplia variedad de aplicaciones dependiendo de la 
interpretación que se le dé a cada una de las variables. A continuación, se muestra un ejemplo, en el que 
es necesario asignar un determinado número de equipos médicos a distintas regiones. Las variables se 
interpretan como 𝑤 total de equipos médicos disponibles a ser asignados, 𝑔𝑘(𝑢𝑘) = 𝑢𝑘 número de 
equipos asignados a la región 𝑘 y 𝑐𝑘(𝑢𝑘) es el beneficio que se logra otorgar a la región en el caso de que 
𝑢𝑘 equipos sean enviados. 
33 
2.2.1. Distribución de equipos médicos a distintas regiones 
Una