Informe Final OPT

2014-2015

Tarea Final
de Optimización.
Tema: Programación Dinámica del Problema de la
Mochila.

Autor (es):
Darelys Marimón Baullosa
Arianna Martínez Sánchez
Deilis Carrazana Galán
Karla Águila López

Grupo: 3504

Índice
INTRODUCCIÓN ................................................................................................................................... 1
DESARROLLO....................................................................................................................................... 2
Principio de optimalidad de Bellman .............................................................................................. 2
Ecuaciones recurrentes para el problema ...................................................................................... 3
Implementación.............................................................................................................................. 4
Función Java del problema de la mochila ....................................................................................... 5
BIBLIOGRAFÍA...................................................................................................................................... 6
CONCLUSIONES ................................................................................................................................... 7

INTRODUCCIÓN
En la actualidad existen una serie de problemas cuyas soluciones pueden ser expresadas de
forma recursiva en términos matemáticos, al cual se le puede dar respuesta haciendo uso de un
algoritmo recursivo. Sin embargo, el tiempo deejecución de la solución recursiva, normalmente es
de orden exponencial y por tanto impracticable, puede mejorarse substancialmente mediante la
Programación Dinámica.
La técnica de Programación dinámica fue inventada como un método general de optimización de
procesos de decisión por etapas. Es adecuada para resolver problemas cuya solución puede
caracterizarse recursivamente (como con la técnicadivide y vencerás) y en la que los
subproblemas que aparecen en la recursión se oculta de algún modo, lo que significaría una
repetición de cálculos inaceptable si se programara la solución recursiva de manera directa. Sin
embargo la programación dinámica no utiliza recursividad, sino que evita la repetición de cálculos
mediante la memorización de la solución de cada subproblema en una tabla, demanera que no
haya que calcularlo más de una vez. Es un método ascendente.
La Programación Dinámica se aplica en la resolución de problemas de optimización. En este tipo
de problemas se pueden presentar distintas soluciones, cada una con un valor, y lo que se desea
es encontrar la solución de valor óptimo (máximo o mínimo), como es el caso del problema de la
mochila.

1

DESARROLLO
La programacióndinámica se basa en el Principio de Optimalidad de Bellman. Dicho principio se
debe comprobar para cada problema. En un algoritmo de programación dinámica se deben definir
los siguientes aspectos:
1. Ecuación recurrente, permite calcular la solución de los problemas grandes en función de
los problemas más pequeños.
2. Determinar los casos base.
3. Definir las tablas utilizadas por el algoritmo, ycómo son rellenadas.
4. Cómo se recompone la solución global a partir de los valores de las tablas.

Principio de optimalidad de Bellman
 Cualquier subsecuencia de decisiones de una secuencia óptima de decisiones que
resuelve un problema también debe ser óptima respecto al subproblema que se resuelve.
 Sea y1,…, yn una secuencia óptima de valores 0-1 para x1,…, xn.
 o Si

y1=0, entonces y2,…, ynforman una secuencia óptima para el problema mochila (2,

n, C).
 o Si

y1=1, entonces y2,…, yn forman una secuencia óptima para el problema mochila (2,

n, C - p1).
 Demostración:
Si existe una solución mejor para el problema correspondiente, entonces es mejor que
para el problema

mochila (1, n, C),

en contra de la hipótesis. Lo mismo se cumple en

cualquier etapa de decisión.
El tiempo de...