PROGRAMACIÓN DINÁMICA
ÍNDICE
1. Introducción
2. Organiza tus ideas: Conceptos clave
3. Enfoca tus conocimientos: Historia caso real PD
4. Actualízate: Programación dinámica
5. Profundiza tus conocimientos: Recursividad hacia adelante y hacia atrás
6. Fortalece tus ideas: Modelos de Programación dinámica
7. Activa tus aprendizajes: Ejercicio Modelo de programación dinámica
8. Conclusiones: Para terminar
INTRODUCCIÓN
A nivel productivo vas a requerir realizar gran cantidad de cálculos con múl-
tiples variables, siempre buscando mejorar u optimizar los procesos dentro
de la organización. Veamos cómo la programación dinámica aporta a que
esto suceda.
Al finalizar esta unidad podrás:
• Definir la programación dinámica para la aplicación y resolución de pro-
blemas a nivel organización y productivo.
• Analizar el método de recursividad hacia adelante y hacia atrás depen-
diendo las necesidades del sistema o de los clientes.
• Determinar los diferentes modelos de aplicación de programación dinámi-
ca de tamaño de la fuerza de trabajo, de reemplazo y modelo de inversión.
Determinemos algunos de los conceptos que definirán un poco mejor en
qué consiste la programación dinámica.
Organiza tus ideas: Conceptos clave
Los términos que nos acompañan en esta unidad son:
• Recursividad de Retroceso: El problema se resuelve partiendo de la últi-
ma etapa hacia la primera.
• Recursividad de Avance: El problema se resuelve partiendo de la primera
etapa hacia la última.
• Etapa: Es la parte del problema que posee un conjunto de alternativas
mutuamente excluyentes, de las cuales se seleccionará la mejor alterna-
tiva.
• Estado: Es el que refleja la condición o estado de las restricciones que
enlazan las etapas. Representa la “liga” entre etapas, de tal manera que
cuando cada etapa se optimiza por separado, la decisión resultante es au-
tomáticamente factible para el problema completo.
• Agregación: Relación en la que un objeto se compone o está construido
de uno o más objetos, de modo que la colección completa representa un
todo. Las relaciones de agregación se especifican entre clases y se reflejan
en instancias de objeto.
• Algoritmo: Método que describe cómo se resuelve un problema en térmi-
no de las acciones que se ejecutan, y especifica el orden en que se ejecu-
tan estas acciones. Los algoritmos ayudan al programador a planificar un
programa antes de su escritura en un lenguaje de programación.
• Asignación: Almacenamiento de un valor en una variable. La sentencia
de asignación es aquella que implementa la asignación y utiliza un ope-
rador de asignación.
• Binario: Representación numérica en base 2. En esta base sólo se utilizan
los dígitos 0 y 1. Las posiciones de los dígitos representan potencias suce-
sivas de 2.
Ahora vamos a conocer un caso de la vida real en la que se utiliza la pro-
gramación dinámica
Enfoca tus Conocimientos: Historia caso
real PD
Comprendamos la integración de la programación dinámica con el caso de
extracción y transformación de madera:
Aplicación de la vida real
Los árboles maduros se talan y aserran transversalmente en troncos para
fabricar diferentes productos finales.
Madera para construcción, madera contrachapada, tablas de aglomerado
de madera, o papel.
Las especificaciones de los troncos, por ejemplo, la longitud y diámetro
finales, difieren según el aserradero donde se procesan los troncos.
Con árboles talados hasta de 100 pies de altura, la cantidad de combina-
ciones de corte que satisfacen los requerimientos del aserradero puede
ser grande, y la forma de cortar el árbol en troncos puede afectar los in-
gresos.
El objetivo es determinar las combinaciones de corte que maximicen el
ingreso total.
El estudio de la programación dinámica aporta optimizar el proceso.
En nuestro siguiente recurso hablaremos sobre las características de la
programación dinámica.
Actualízate: Programación dinámica
Ahora veremos una descripción detallada sobre la programación dinámi-
ca en relación a la recursividad.
Naturaleza recursiva de los cálculos de programación dinámica (PD)
• Subproblema
La idea principal de la programación dinámica (PD) es des-
componer el problema en subproblemas (más manejables).
• Recursividad
Los cálculos se realizan entonces recursivamente, donde la
solución óptima de un subproblema se utiliza como dato de
entrada al siguiente problema.
• Problema
La solución para todo el problema está disponible cuando se
soluciona el último subproblema. La forma en que se realizan
los cálculos recursivos depende de cómo se descomponga el
problema original.
• Restricciones
Normalmente los subproblemas están vinculados por res-
tricciones comunes. La factibilidad de estas restricciones co-
munes se mantiene en todas las iteraciones.
• PD
La programación dinámica es una técnica matemática que se
utiliza para la solución de problemas matemáticos seleccio-
nados, en los cuales se toma una serie de decisiones en forma
secuencial.
• Esquema
Formulación y solución de problemas
• Formulación
La programación dinámica no cuenta con una formulación matemática
estándar, sino que se trata de un enfoque de tipo general para la solución
de problemas, y las ecuaciones específicas que se usan se deben desarro-
llar para que representen cada situación individual.
• Optimización
Comúnmente resuelve el problema por etapas, en donde cada etapa in-
terviene exactamente una variable de optimización (u optimizadora).
• Recursivo
La teoría unificadora fundamental de la programación dinámica es el
Principio de Optimalidad, que nos indica básicamente como se puede re-
solver un problema adecuadamente descompuesto en etapas utilizando
cálculos recursivos.
Resolver problemas de programación dinámica se necesita:
• Un grado de creatividad
• Un buen conocimiento de la estructura general de los problemas
de programación dinámica para reconocer cuando un problema se pue-
de resolver por medio de estos procedimientos y como esto se puede lle-
var a cabo.
Características
• El problema se puede dividir en etapas que requieren una política
de decisión en cada una.
• Cada etapa tiene cierto número de estados asociados a ella.
• El efecto de la política de decisión en cada etapa es transformar el
estado actual en un estado asociado con la siguiente etapa.
• El procedimiento de solución está diseñado para encontrar una po-
lítica óptima para el problema completo.
• Dado un estado actual, una política óptima para las etapas res-
tantes es independiente de la política adoptada en las etapas anteriores
(principio de optimalidad).
Solución
El procedimiento de solución se inicia al encontrar la política óptima para
la última etapa.
Imprescindibles
Se dispone de una relación recursiva que identifica la política óptima para
la etapa n dada la política óptima para la etapa (n+1).
¡Excelente! Continuemos aprendiendo sobre recursiva hacia adelante o
de avance, en la cual los problemas se resuelven comenzando desde la
primera etapa hasta la última, y recursiva hacia atrás o de retroceso, co-
menzando con la resolución del problema de la última etapa hacia la pri-
mera que es de lo que trataremos a continuación.
Profundiza tus Conocimientos: Recursi-
vidad hacia adelante y hacia atrás
Sabías que… la diferencia principal entre los métodos de avance y de re-
troceso ocurre en la forma como definimos el estado del sistema.
Puedes mejorar tu comprensión del concepto de programación aplican-
do algunos de los modelos matemáticos de la programación dinámica.
Ahora veremos cómo aplicar los cálculos de recursividad existentes en la
PD. ¡Continuemos!
Fortalece tus Ideas: Modelos de progra-
mación dinámica
Descubriremos cómo aplicar algunos de los modelos de PD para así en-
tender mejor como se aplica en casos de la vida real. Aplicaremos un caso
de estudio que permita desarrollar un modelo recursivo e identificar las
variables que intervienen para la resolución de problemas. ¡Vamos!
Activa tus Aprendizajes: Ejercicio Mo-
delo de programación dinámica
¡Perfecto! Tienes la información requerida para resolver el caso. Por últi-
mo, vamos a retomar las ideas principales que nos deja el recorrido por
esta unidad.
Conclusiones:
Hemos llegado a la parte final de esta unidad denominada Programación
Dinámica, de la cual podemos concluir que:
• Un problema de optimización que se pueda dividir en etapas y que
sea dinámico en el tiempo puede resolverse por programación diná-
mica, de manera que proporcione soluciones de manera parcial, pero
no olvidar que pueden validar los resultados mediante la programa-
ción lineal, no lineal, entera o teoría de redes.
• Cuando se presentan problemas a nivel organizacional o productivo
la programación dinámica es un método que disminuye y acopla el
exceso de trabajo por la gran cantidad de cálculos, de manera que in-
centiva la creatividad y aplicación de los diferente modelos de PD y de
recursividad.
• Es importante que a la hora de aplicar el método de PD, los tamaños
de los cálculos sean proporcionales y razonables, de manera que per-
mita subdividir el problema, y así estructurar y solucionar el problema
original.
Antes de finalizar, te invito a realizar las actividades propuestas para esta
unidad.
Nuestra siguiente unidad tratará sobre modelos determinísticos de in-
ventarios para demanda independiente. ¡Te esperamos!
