REPÚBLICA BOLIVARIANA DE VENEZUELA
INSTITUTO UNIVERSITARIO
POLITÉCNICO SANTIAGO MARIÑO
PROGRAMACIÓN DINÁMICA
Jawhari, Lorena
C.I 29.549.150
FEBRERO 2023
La programación dinámica se basa en el principio de optimalidad, el cual establece
que una política óptima está formada por subpolíticas. Pueden definirse como una
técnica matemática que da solución a una serie de decisiones secuenciales, cada una
de las cuales afecta a las soluciones futuras.
La programación dinámica es un método cuantitativo desarrollado por Richard
Bellman alrededor de la década de los años 50, con la finalidad de optimizar
procesos, ya que en ese momento esa era su función como trabajador de RAND
Corporation. Bellman decidió emplear la palabra dinámica a esta técnica, ya que
deseaba analizar las variables de los problemas con respecto al tiempo. Siendo así
Dasgupta, Papadimitriou y Vazirani (2006), entendieron a la programación dinámica
como “optimización de procesos con etapa múltiples”. La idea de Bellman sobre la
teoría de programación dinámica se basa en una estructura de optimización, la cual
consiste en descomponer el problema en subproblemas (más manejables). Los
cálculos se realizan entonces recursivamente donde la solución óptima de un
subproblema se utiliza como dato de entrada al siguiente problema. Por lo cual, se
entiende que el problema es solucionado en su totalidad, una vez se haya solucionado
el último subproblema. Dentro de esta teoría, Bellman desarrolla el Principio de
Optimalidad, el cual es fundamental para la resolución adecuada de los cálculos
recursivos. Lo cual quiere decir que las etapas futuras desarrollan una política óptima
independiente de las decisiones de las etapas predecesoras. Es por ello, que se define
a la programación dinámica como una técnica matemática que ayuda a resolver
decisiones secuenciales interrelacionadas, combinándolas para obtener de la solución
óptima.
El problema se puede dividir por etapas, y cada una de las etapas requiere de
una política de decisión.
2
Cada etapa tiene cierto número de estados, los estados son las distintas
condiciones posibles en las que se puede encontrar el sistema en cada etapa.
El efecto de la política de decisión en cada etapa es transformar el estado actual
en un estado asociado con el inicio de la siguiente etapa, entonces podemos decir que
un estado es una columna de nodos, cada nodo representa un estado y cada rama una
política de decisión.
El procedimiento de resolución de la programación dinámica está diseñado para
encontrar una política óptima para cada etapa logrando así la política óptima general.
Dado el estado actual, una política óptima para las etapas restantes es
independiente de la política adoptada en etapas anteriores, por ende, la decisión
inmediata óptima solo depende del estado actual y no de cómo se llegó ahí, esto es el
principio de optimalidad de la programación dinámica.
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.
Cuando se hace uso de la relación recursiva, el procedimiento de solución
comienza al final se mueve hacia atrás etapa por etapa hasta encontrar la política
óptima en cada etapa hasta la etapa inicial.
Ejemplos: el problema de la mochila.
Hay un conjunto S de n objetos, en el que cada objeto i tiene un beneficio bi y un
peso wi positivo. Se deben seleccionar los elementos que garanticen un beneficio
máximo, pero con un peso global menor o igual que W.
Dado el conjunto S de n objetos, sea Sk el conjunto de los k primeros objetos (de 1 a
k):
Se puede definir B(k,w) como la ganancia de la mejor solución obtenida a partir de
los elementos de S k para una mochila de capacidad w. La mejor selección de
3
elementos del conjunto Sk para una mochila de tamaño w se puede definir en función
de selecciones de elementos de Sk-1 para mochilas de menor capacidad. La mejor
opción para Sk coincide con la mejor selección de elementos de Sk-1 con peso
máximo w (el beneficio máximo para Sk coincide con el de Sk-1), o bien es el
resultado de añadir el objeto k a la mejor selección de elementos de Sk-1 con peso
máximo w−wk (el beneficio para Sk será el beneficio que se obtenía en Sk-1 para una
mochila de capacidad w−wk más el beneficio bk asociado al objeto k).
Ejemplos: coeficientes binomiales.
Cuando se encuentra la solución a un problema y se halla una expresión que define la
solución, es complejo crear un vector o una tabla que conserve los resultados
parciales. De esta forma, se observa que se requiere de una tabla bidimensional que
haga referencia al cálculo de los coeficientes binomiales, definido como:
El algoritmo recursivo que los calcula es de complejidad exponencial por la
repetición de los cálculos que realiza. De esta manera, se puede plantear una notación
con un tiempo de ejecución de orden O (nk) fundamentado en el triángulo de Pascal.
Para su realización, es necesaria la instauración de una tabla en dos dimensiones en
donde se puedan almacenar los valores intermedios que se utilizan posteriormente.
Ejemplo: multiplicación de una secuencia de matrices.
Calcular el producto matricial: M= M1,M2,…Mn Existen varias maneras de realizar
dicho cálculo. Se debe tener en cuenta que el algoritmo resultante de la definición del
producto de dos matrices pxq y qxr necesita pqr multiplicaciones de escalares.
Metodología
4
• Insertar los paréntesis en las matrices de todas las formas posibles.
• Calcular para cada matriz el número de multiplicaciones escalares necesarios.
Ejemplo: la distancia más corta.
Maximizar el beneficio total asignando el recurso a los r proyectos cuando se dispone
de n unidades de un recurso que deben asignarse a r proyectos. Se conoce que si se
dan j unidades (0 ≤ j ≤ n) al proyecto i resulta un beneficio Ni,j.
Primero se formulará como grafo multietapa.
Segundo, se formulará como grafo resultante para r=3 y n=4.
El camino de costo máximo del nódulo o al nódulo d definirá la asignación óptima.
Al cambiar los signos de las etiquetas, el convertir a en un problema de camino de
costo mínimo cambiar los signos de las etiquetas.
5
BIBLIOGRAFÍA:
Bronson, Richard (1993). Investigación de operaciones, México, Editorial
McGraw-Hill.
Chediak, Francisco (2005). Investigación de operaciones, Colombia Ibagué,
Editorial El Poira.
