Investigación de operaciones. Características de los problemas de programación dinámica
Enviado por mamuelga • 8 de Octubre de 2018 • Documentos de Investigación • 5.304 Palabras (22 Páginas) • 561 Visitas
INSTITUTO TECNOLOGICO DE CD. GUZMÁN
[pic 2]
APUNTES
Índice General (Tabla de contenidos).
Unidad I: Programación Dinámica. 4
1.1 Características de los problemas de programación dinámica 5
1.2 Ejemplos de modelos de programación dinámica 5
1.3 Programación dinámica determinista y probabilista 5
[pic 3]
[pic 4]
[pic 5]
Unidad I: Programación Dinámica.
Objetivo de la unidad:
Conocer, formular y resolver problemas obteniendo soluciones sucesivas de subproblemas de menor tamaño y ligándolas con la solución óptima del problema, aplicando los algoritmos de Programación Dinámica para resolver problemas que se adaptan al modelo ▪ Utilizar software.
Introducción.
Existe una serie de problemas matemáticos cuya solución se puede dar mediante el empleo de un algoritmo recursivo o mediante la implementación de una resolución por etapas, planteando una serie de subproblemas a partir del problema principal; en ambos casos, la solución puede ser caótica. Agrandar el tamaño del problema o simplemente, el método empleado puede convertirse en impráctico. Esto puede mejorar sustancialmente mediante la Programación Dinámica (PD).
La Programación Dinámica es una técnica de programación que se emplea típicamente para resolver problemas de optimización en los cuales el problema principal se encuadra en varios sub-problemas, solucionando primero cada uno de ellos y almacenarlos en alguna estructura para utilizarlas posteriormente, ligando las soluciones de una forma óptima, donde la solución final permita resolver y tomar decisiones correctas a problemas actuales y futuros.
Esta técnica se aplica a una variedad de problemas, donde destacan el problema de ordenamiento en planeación de requerimientos de materiales, así como el problema de la mochila, que necesitan un alto costo computacional. La idea de la PD es encontrar la solución a los subproblemas.
1.1 Características de los problemas de programación dinámica
La Programación Dinámica es una metodología para la solución de un amplio espectro de problemas de optimización. Difiere de otras áreas de Programación matemática, como la programación lineal en la cual problemas canónicos específicos y todas las técnicas de solución para estos problemas son estudiados. La Programación Dinámica puede ser aplicada a problemas en los cuales una secuencia de decisiones interrelacionados es requerida.
Procesos de decisión secuencial. El adjetivo “dinámico” es algo desafortunado, resultando de las aplicaciones iniciales a problemas en los cuales el tiempo fue una variable. Verdaderamente, la Programación Dinámica podría ser llamada Programación recursiva (ó secuencial). La Programación Dinámica provee una metodología de solución para muchos problemas, muchos de ellos no pueden ser resueltos por otros métodos. Es un enfoque “divide y vencerás”. Hay que dividir un problema en una secuencia de subproblemas más pequeños los cuales pueden ser resueltos recursivamente uno a la vez, por lo tanto reduciendo significativamente el trabajo de solución.
Antes de entrar de lleno a los fundamentos de la Programación Dinámica veremos el siguiente simple problema de matemáticas recreacionales, el cual ilustra varios conceptos importantes de Programación Dinámica, tomado de los apuntes de Investigación de Operaciones de la maestría en Purdue University, del maestro Thomas L. Morin.
1.2 Ejemplos de modelos de programación dinámica
Existen muchos problemas que pueden ser resueltos por medio de la programación dinámica. Algunos de los más típicos son: El problema de camino más corto, el problema de la mochila y un problema de inventarios con el método conocido como Wagner-Within, el cual es muy utilizado en MRP (Planeación de requerimientos de materiales), los cuales se verán más adelante.
1.3 Programación dinámica determinista y probabilista
Ejemplo 1.1. Juego en un Tablero.
Dada la siguiente matriz (tablero) el jugador desea moverse de la izquierda a la derecha del tablero de manera que se maximicé la suma de los escores (puntuaciones) sobre la trayectoria recorrida. Un movimiento consiste en un paso (columna) a la vez y está restringido a movimientos horizontales o diagonales. Es decir el jugador puede moverse de una celda en una columna a una celda adyacente
0 | 0 | 6 | 8 | 7 | 5 | 6 | 3 | El problema es encontrar la secuencia óptima de movimientos, es decir la mejor ruta (trayectoria) desde la izquierda del tablero a la derecha del tablero. |
3 | 3 | 8 | 8 | 7 | 4 | 7 | 8 | |
2 | 0 | 2 | 9 | 8 | 5 | 9 | 4 | |
Sea rij factible, donde T=(((i1,1),(i2
para los índice [pic 6] I(in) =
| el valor del escore en la celda (i,j), 𝝉 ЄT una ruta ,2),....,(i8,8))|i1Є(1,2,.....8),in+1ЄI(in), n = (1,2,......7) en los cuales el conjunto admisible s de los renglones es: (in, in+1), sí in = 1 [pic 7] (in-1, in, in+1), sí in Є(2,....7) (in-1, in), sí in = 8 | |||||||
1 | 3 | 3 | 5 | 3 | 2 | 1 | 0 | |
1 | 1 | 6 | 8 | 5 | 8 | 3 | 7 | |
6 | 1 | 6 | 2 | 7 | 5 | 2 | 5 | |
4 | 1 | 5 | 5 | 4 | 4 | 8 | 4 | |
8 | 1 | 6 | 9 | 3 | 9 | 4 | 6 | |
El problema puede ser establecido como: 𝑴𝒂𝒙⏟ 𝒓 𝒊𝒋 |
𝝉[pic 8]𝝉
...