Programacion dinamica

INSTITUTO TECNOLOGICO DE CERRO AZUL
CAIIOAJ)

MANUAL DE INVESTIGACIÓN
DE OPERACIONES II

CATEDRÁTICO:
m. c. RAÚL LEONEL GUZMÁN SAMPAYO.

REALIADO POR:
CASTRO OCHOA AGUSTIN.
ELIZALDE RAMIREZ FERNANDO.
RODRIGUEZ MARTINEZ JOAQUIN C.
SONI SANTOS IRIS ABRIL.

ESPECIALIDAD:
INGENIERÍA INDUSTRIAL
PERIODO:
AGOSTO-DICIEMBRE 2008
CERRO AZUL, VER.

ÍNDICE
UNIDAD I:
PROGRAMACIÓNDINÁMICA
1.1 Características de la programación dinámica: etapas, estados,
fórmula recursiva, programación en avance y retroceso…….. .........................4
1.2 Algunos modelos de ejemplos de Programación Dinámica………………...6
1.3 Programación dinámica determinística……………………………………..…7
1.4 Programación dinámica probabilística………………………………….……..8
1.5 Problema de dimensionalidad de ProgramaciónDinámica…………………8
Ejercicios resueltos……………………………………………………………..…..10
Ejercicios propuestos……………………………………………………………..…21

UNIDAD II:
TEORÍA DE COLAS
2.1 Introducción y casos de aplicación……………………………………………24
2.2 Definiciones características y suposiciones………………………………….24
2.3 Terminología y notación. …………………………………………………..…..26
2.4 Proceso de nacimiento y muerte
Modelos Poisson.……………………………………………………………....27
2.5 Un servidor, fuente finita, cola finita. ……………….…………………………28
2.6 Un servidor, cola infinita, fuente infinita…………………………………….…30
2.7 Servidores múltiples, cola infinita, fuente infinita. ……………………………32
2.8 Servidores múltiples, cola finita, fuente finita. ……………………………..…34
Ejercicios resueltos…………………………………………………………………..36
Ejercicios propuestos……………………………………………………………..…40

UNIDAD III:
TEORÍA DE DECISIÓN
3.1 Característicasgenerales de la teoría de decisiones. ……………………..43
3.2 Criterios de decisión determinísticos y probabilísticos……………………..44
3.3 Valor de la información perfecta. ……………………………………………..45
3.4 Árboles de decisión. …………………………………………………………...46
3.5 Teoría de dualidad. ………………………………………………………….…47
3.6 Decisiones secuenciales. ………………………………………………….…..49
3.7 Análisis de sensibilidad.…………………………………………………...…..49
Ejercicios resueltos…………………………………………………………………..51
Ejercicios propuestos………………………………………………………………..55

UNIDAD IV:
CADENAS DE MARKOV
4.1 Introducción. …………………………………………………………………….58
4.2 Formulación de las cadenas de Markov. ……………………………….……58

2

4.3 Procesos estocásticos. …………………………………………………….…60
4.4 Propiedad Markoviana de primer orden. ……………………………………60
4.5 Probabilidades de transición estacionarias de un solopaso……………...61
4.6 Probabilidades de transición estacionarias de n pasos…………………...63
4.7 Estados absorbentes. …………………………………………………………64
4.8 Probabilidades de transición estacionarias de estados estables.
Tiempos de primer paso. ………………………………………………….65
Ejercicios resueltos…………………………………………………………………66
Ejercicios propuestos………………………………………………………………72

UNIDAD V:
OPTIMIZACIÓN DE REDES
5.1Terminología……………………………………………………………………75
5.2 Problema de la ruta más corta. Redes cíclicas y acíclicas. ………………77
5.3 Problema del árbol de mínima expansión. …………………………………80
5.4 Problema de flujo máximo. …………………………………………………...81
5.5 Problema de flujo de costo mínimo. ………………………………………...83
5.6 Programación lineal en teoría de redes. ……………………………………86
5.7 Uso de programas de computación. ……………………………………..…88
Ejerciciosresueltos……………………………………………………………..….95
Ejercicios propuestos……………………………………………………………..103
Bibiliografía………………………..………………………………………………..105

3

UNIDAD I:

PROGRAMACIÓN DINÁMICA
1.1
CARACTERÍSTICAS
DE
LOS
PROBLEMAS
DE
PROGRAMACIÓN DINÁMICA : ETAPAS, ESTADOS, FÓRMULA
RECURSIVA, PROGRAMACIÓN EN AVANCE Y EN RETROCESO
La programación dinámica es una técnica matemática que se utiliza para
la solución deproblemas matemáticos seleccionados, en los cuales se toma
una serie de decisiones en forma secuencial.
Proporciona un procedimiento sistemático para encontrar la combinación
de decisiones que maximice la efectividad total, al descomponer el problema en
etapas, las que pueden ser...