INSTITUTO TECNOLOGICO SUPERIOR
DE ALVARADO
Ing. Gestión Empresarial
Semestre:
8vo.
Unidad:
1ra.
Materia:
Cadena de suministro
Ensayo:
Programación dinámica
Nombre:
Demetrio Perez Delgado 176Z0750
Profesor:
María Eréndida León Jerónimo
Lerdo de tejada, ver. 24 de febrero del 2021
1|Page
INTRODUCCIÓN
La Programación Dinámica es un método de optimización de extraordinaria
versatilidad. Si bien fue desarrollada especialmente para la resolución de
problemas en Procesos de Decisión en Múltiples Pasos, diferentes investigaciones
han mostrado que las mismas ideas pueden utilizarse en otro tipo de problemas
de matemática aplicada, e incluso pueden ser útiles en el planteo de algunas
cuestiones teóricas.
La idea básica de la programación dinámica es guardar los resultados de los
subproblemas para no tener que volverlos a calcular después. Con esta simple
técnica, podemos transformar algoritmos que corren en tiempo exponencial a
tiempo polinomial. Este ahorro en tiempo se refleja en un costo en memoria.
Los problemas más comunes que se resuelven mediante esta técnica son los de
optimización, donde podemos encontrar muchas soluciones, pero requerimos
únicamente la mejor (posiblemente la menor o la mayor, según lo que estemos
buscando). Como pueden existir varias combinaciones que resulten en la mejor
solución, decimos que encontramos una respuesta óptima, y no la respuesta
óptima.
2|Page
PROGRAMACIÓN DINÁMICA
La programación dinámica es una técnica matemática que se utiliza para resolver
problemas matemáticos seleccionados en los que se toman una serie de
decisiones en secuencia.
Proporciona un programa sistemático que puede encontrar la combinación de
toma de decisiones que maximiza la eficiencia general al descomponer el
problema en múltiples etapas. Puede descomponer el problema en una o más
formas (estados) y calcular recursivamente las etapas de cada vínculo.
Tenemos como etapa y estado
La etapa es parte del problema, con un conjunto de alternativas mutuamente
excluyentes, de las cuales se seleccionará la mejor alternativa y el estado refleja
las condiciones de restricción o el estado de cada etapa del enlace. Representa el
"vínculo" entre las distintas etapas, de modo que cuando cada etapa se optimiza
por separado, la decisión final es automáticamente factible para todo el problema.
ESQUEMA DE UNA ETAPA
qi =Variable de estado en la etapa i
Xij =Uno de los valores que puede adoptar la
variable de decisión “Xi” en la etapa i
Xi*= Decisión óptima de la etapa i.
3|Page
FORMULACIÓN Y SOLUCIÓN DE PROBLEMAS
No existe una fórmula matemática estándar para la programación dinámica, pero
es un método general para resolver problemas, por lo que se deben desarrollar
ecuaciones específicas para representar cada situación.
Por lo general, resuelve el problema en etapas, donde cada etapa contiene solo
una variable de optimización (u optimización).
La teoría unificada básica de la programación dinámica es el principio de
optimalidad, que básicamente nos dice cómo usar el cálculo recursivo para
resolver el problema de la descomposición adecuada en etapas. "La naturaleza de
la política óptima es que, independientemente de la decisión que se tome para
lograr un cierto estado, en una determinada etapa, las decisiones restantes deben
constituir la política óptima para salir de ese estado".
PARA RESOLVER PROBLEMAS DE PROGRAMACIÓN DINÁMICA SE
NECESITA:
Cierto grado de creatividad, tener una buena comprensión de la estructura general
de los problemas de programación dinámica y puede identificar cuándo y cómo
resolver el problema a través de estos procesos.
CARACTERÍSTICAS DE LOS PROBLEMAS DE PROGRAMACIÓN DINÁMICA
Los problemas se pueden dividir en etapas y cada etapa requiere una
estrategia de decisión.
Cada etapa tiene muchos estados asociados.
El efecto de la estrategia de decisión en cada etapa es transformar el
estado actual en un estado asociado con la siguiente etapa.
El proceso de solución tiene como objetivo encontrar la mejor estrategia
para todo el problema.
4|Page
CARACTERÍSTICAS DE LOS PROBLEMAS DE PROGRAMACIÓN DINÁMICA
Dado un estado actual, una política óptima para las etapas restantes es
independiente de la política adoptada en las etapas anteriores (principio de
optimalidad).
El procedimiento de solución se inicia al encontrar la política óptima para la
última etapa.
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)
RECURSIVIDAD
Existen dos formas de plantear la fórmula de recursividad en los problemas
de programación dinámica:
Recursividad de Retroceso: el problema se resuelva partiendo de la última
etapa hacia la primera.
Recursividad de Avance: el problema se resuelve partiendo de la primera
etapa hacia la última.
RECURSIVIDAD
En términos de cálculos, las fórmulas hacia avance y retroceso son en realidad
equivalentes. Sin embargo, en algunos casos, la eficiencia del cálculo variará
según la fórmula utilizada. Esto es especialmente cierto para cuestiones
relacionadas con la toma de decisiones a lo largo del tiempo. En este caso, las
fases se especificarán de acuerdo con la secuencia de tiempo estricta que
representan las fases, y la eficiencia del cálculo dependerá de si se utiliza la
fórmula hacia adelante o hacia atrás.
5|Page
CONCLUSIÓN
La programación dinámica es una técnica que permite optimizar soluciones a
problemas, adaptarlos para dividir y vencer, dividir el problema en subproblemas y
resolver cada problema mediante la recursividad, y luego combinar estas
soluciones parciales para obtener una solución. problema.
Cabe señalar que para que un problema se resuelva mediante programación
dinámica, debe cumplir ciertas características para que también pueda ser
procesado. Cabe señalar que, a diferencia de la programación lineal, no existe un
formulario estándar para modelar problemas de programación dinámica. Por lo
tanto, para cada problema, se debe especificar cada componente que caracteriza
al problema de programación dinámica.
Sin embargo, un aspecto realmente destacable es que la programación dinámica
tiene una amplia gama de aplicaciones, que pueden provenir de turistas que
desean viajar, o combinar objetos en mochilas para ahorrar espacio, o planificar la
producción y la planificación del inventario. No olvide la importancia de
"programación dinámica" en los cálculos.
[ CITATION Ida21 \l 3082 ]
Bibliography
flores, I. (24 de febrero de 2021). [Link]. Obtenido de [Link]:
[Link]
6|Page
