UNIVERSIDAD DOMINICANA (O&M)

NOMBRES Y APELLIDOS:
Edy Joel Abad Heredia

MATRICULA:
12-SIIT-1-017
MATERIA:
Modelo probabilstico y simulacin por computadora
TEMA:
Practica No. 2
SECCION:
0810
PROFESOR/A:
Oscar Moreno

FECHA:
01/10/206

Materia: Modelo probabilstico y simulacin por computadora.

PRACTICA 2 Programacin dinmica (PD). Teora de la probabilidad y
cadenas de Markov
1. Definir programacin dinmica.
2. Caractersticas especiales de la PD
3. Diferencia entre programacin dinmica y programacin lineal.
4. Defina el procedimiento de solucin de un problema PD
5. Los elementos que definen un problema de programacin dinmica.
6. Las dos fases en la que se divide la aplicacin de la programacin
dinmica.
7. Cules son las divisiones en los que se pueden dividir los problemas de
PD
8. Qu es el principio de Optimabilidad?
9. Cules son los pasos a seguir para resolver un problema de programacin
lineal?
10. Enumere las razones por las que NO todo problema de investigacin de
operaciones se puede resolver mediante PD
11. Cundo es recomendable usar la tcnica de PD para la resolucin de
problemas?
12. Qu es la teora de probabilidad?

13. Cul es la diferencia entre los fenmenos aleatorios y los fenmenos

deterministas?
14. Qu se entiende por probabilidad?
15. Por as decirlo, Cul es la ocupacin de la teora de probabilidades?
16. Hable brevemente sobre Andrei Markov
17. Qu son las cadenas de Markov?
18. Qu es un evento estocstico?
19. Mencione varios ejemplos de procesos estocsticos
20. Qu nos permite predecir el anlisis de un proceso estocstico?
21. Para qu tipo de descripcin suelen usarse los procesos estocsticos?
22. Qu es la trayectoria de un proceso estocstico?
23. Por qu se asume que los procesos industriales son procesos
estocsticos?
El presente trabajo comprende la investigacin y ejemplos sobre la teora de la
programacin dinmica (PD) La PD est comprendida dentro de un conjunto de
tcnicas matemticas que a su vez forman parte de un rea ms amplia, conocida
como investigacin de operaciones. Esta ltima puede definirse como una ciencia
interdisciplinaria que tiene por objeto la bsqueda de estrategias que permitan
obtener resultados ptimos en el desarrollo de actividades por parte de sistemas
hombre maquinas, como se ver ms adelante los problemas propios de la
programacin dinmica son aquellos que puede ser divididos en subproblemas
los cuales tienen una estructura igual al problema original. Para este propsito
mtodo consiste en dividir el problema en etapas, resolver la primera de estas,

utilizar esta solucin para resolver la etapa siguiente y continuar as

sucesivamente hasta encontrar el problema en su totalidad.
Son caractersticas esenciales de la P.D. por un lado, la versatilidad con respecto
a la amplia gama de problemas que puede atacar y, por otra parte, que la P.D. se
limita a aportar un esquema de solucin (ya mencionado arriba) dejando al ingenio
de quien resuelva el problema la construccin del modelo matemtico para realizar
la optimizacin de cada caso en particular. En este sentido el trabajo en P.D. est
ms en relacin directa con la labor del matemtico que del ingeniero, pues este
ltimo no necesita comprender la base terica en la cual descansa el
procedimiento, sino nicamente conocer el algoritmo propio del problema
particular que pretende resolver.
El objetivo es ms presentar la potencia de la P.D. que proponerla como la
panacea de los mtodos de Investigacin de Operaciones, pues tambin se ver
que aunque funciona, en ocasiones la tcnica puede resultar imprctica al
momento de resolver problemas de cierta envergadura.
Las caractersticas propias de la Programacin Dinmica (PD) como son: el no
tener un tipo especfico de problemas sobre el cual operar, el carecer de un
algoritmo estndar de solucin, etc., hacen que exista una gran dificultad en el
momento de intentar dar una definicin de ella. Sin embargo, para comenzar, se
debe tener alguna definicin que, aunque

parcial e incompleta, sirva para ir

demarcando el terreno al que se circunscribir este trabajar, se debe tener alguna

definicin que, aunque parcial e incompleta, sirva para ir demarcando el terreno al
que se circunscribir este tema de la materia.
La

programacin

dinmica

es

un

procedimiento

matemtico

diseado

principalmente para mejorar la eficiencia de clculo de problemas de

programacin matemtica seleccionados, descomponindolos en subproblemas
de menor tamao y por consiguiente ms fcil de calcular. La PD normalmente
resuelve el problema en etapas. Los clculos en las diferentes etapas se enlazan

a travs de clculos recursivos de manera que se genere una solucin ptima

factible a todo el problema.
Programacin lineal: Tcnica cuantitativa para encontrar decisiones optimas en
un sistema que evoluciona a lo largo de sus etapas o fases.
Proporciona un procedimiento sistemtico para encontrar la combinacin de
decisiones que maximice la efectividad total, al descomponer el problema en
etapas, las que pueden ser completadas por una o ms formas (estados), y
enlazando cada etapa a travs de clculos recursivos.
Las decisiones tomadas en una etapa condicionan la evolucin futura del sistema,
afectando las situaciones y decisiones futuras.

Etapa (n o N: periodo de tiempo, el lugar, el contexto, la fase o la situacin

en la que se produce un cambio debido a una decisin. Solo se puede
tomar una decisin por cada etapa.

Estados (en): situacin actual del sistema cuando nos encontramos en la

etapa (n o N) cada etapa tiene su propio estado.

Variables de decisin (xn): Hace referencia a toma de decisiones que se

producen en una etapa y que provoca un cambio en el estado actual del
sistema. Cada etapa tiene su propia variable de decisin.

Funcin recurrente (fn): Refleja el comportamiento del sistema en funcin

de los estados y la variable de decisin. Cada etapa tiene su propia funcin
recurrente.

La aplicacin de la programacin dinmica se divide en dos fases:

ANLISIS:
Analizando todas las opciones posibles analizando las etapas de derecha a
izquierda.

DECISIN:

Etapa por etapa de izquierda a derecha buscamos la mejor opcin posible.

Los problemas de la programacin dinmica se pueden dividir en 2:
1. Programacin dinmica determinstica: Son problemas donde el
estado en la siguiente etapa est completamente determinado por el estado y la
decisin actual.
a. Discretos
b. Continuos
2. Programacin dinmica probabilstica: Existe una distribucin de
probabilidad sobre lo que puede ser el siguiente estado.
PRINCIPIO DE OPTIMABILIDAD: La solucin ptima de cualquier instancia no
trivial de un problema es una combinacin de las soluciones ptimas de sus
subproblemas. Se busca la solucin ptima a un problema como un proceso de
decisin como un proceso de decisin multietpico. Se toma una decisin en
cada paso, pero esta depende de la soluciones a los subproblemas que lo
componen.
La programacin lineal: Es el ejercicio de optimizar funciones (sea maximizndolas
o minimizndolas) que estn limitadas por determinadas restricciones.
Las restricciones son inecuaciones y las funciones en este caso son lineales.
(Porque se trata de programacin lineal)
Para resolver un problema de programacin lineal seguimos los siguientes pasos:
1. Identificar las incgnitas
2. Describir la funcin objetivo
3. Escribir las restricciones como inecuaciones
4. Calcular la solucin optima
Las tcnicas de PD nos permiten resolver, entre otros, problemas de programacin
lineal y no lineal, esto no quiere decir que la PD sea la solucin a todos los

problemas de estos campos por dos razones: 1. Porque las tcnicas de PD son
aplicables nicamente a un conjunto reducido de problemas en cada campo y 2.
Porque aunque la tcnica sea aplicable, al resolver problemas grandes (de
programacin lineal por ejemplo) el nmero de evaluaciones de todas las
alternativas crece de forma exagerada (ese problema se conoce como la plaga de
la dimencionalidad) lo cual hace que este enfoque sea imprctico. Sin embargo, el
propsito buscado al resolver este tipo de problema no ha sido proponer una
alternativa a los mtodos estndar de solucin de tales campos (como el mtodo
simple en el caso de la programacin lineal) sino sencillamente poner en evidencia
la versatilidad propia de la PD.
Por otra parte, cuando enfrenta problemas propios de su campo, la PD aporta un
marco de procedimiento que ayuda a disminuir enormemente el exceso de trabajo
ocasionado por la redundancia en los clculos a la vez que estimula la creatividad
al dejar espacios en blanco que deben ser llenados al resolver cada caso en
particular.
Debe emplearse PD cuando la forma del problema permita dividirlo en
subproblemas que tenga la misma estructura del problema original. Tambin es
importante tener en cuenta que el tamao de los clculos tenga proporciones
razonables.
Cadena de Markov: es un proceso matemtico que representa con algn grado
de aproximacin algunos fenmenos naturales o creados por el hombre.
Procesos

estocsticos:

Es

un

modelo

que

sirve

para

representar

matemticamente un fenmeno que evoluciona al azar a lo largo del tiempo.

Es una coleccin de variables aleatorias parametrizado por un espacio parametral
donde las variables aleatorias toman valores llamado espacio de estado.
La trayectoria de un proceso estocstico es una coleccin particular de valores
que pueden tomar las variables aleatorias.

Un proceso estocstico es una cadena de Markov si un estado futuro depende

solo del estado inmediatamente anterior.
Ejemplo de procesos estocsticos son:
1. Juego de apuestas
2. Observacin sobre una maquina al final de cada semana
3. Registro de inventario al final de la semana
4. Observacin hecha cada 30 segundo sobre la cantidad de clientes
esperando en una fila
5. Compra de detergente de un consumidor cuando hay 7 marcas para
escoger
Se aplica en intentar de ajustar un modelo terico que nos permita hacer
predicciones sobre las condiciones futuras del proceso. Entonces conociendo las
condiciones futuras, tomar las decisiones pertinentes en el presente.
Normalmente los estados del proceso tienen que ver con lo que nos interesa
observar en el sistema y son justamente los posibles valores asignados a estas
caractersticas.
Las cadenas de Markov son una sucesin de un evento o proceso, donde la
probabilidad del resultado de este proceso solo depende del resultado del evento
anterior.
Procesos que evolucionan en el tiempo de una manera probabilstica, se llaman
procesos estocsticos.
Los procesos estocsticos son de inters para describir el comportamiento de un
sistema en operacin durante algunos periodos.

El anlisis de procesos estocsticos permite predecir el estado en que se

encontrara el proceso en el futuro a partir de la informacin disponible sobre su
pasado.
Se asume que los procesos industriales son procesos estocsticos. Este supuesto
es vlido de modo general tanto para procesos industriales continuos como por
lotes. La prueba y monitorizacin del proceso se graba utilizando un mapa de
control de procesos que traza un parmetro de un proceso del control en el
tiempo. Tpicamente, una docena o ms de parmetros sern monitorizados de
modo simultneo. Los modelos estadsticos son utilizados para definir lneas lmite
que definen cuando las acciones correctivas deben tomarse para llevar el proceso
hacia su ventana de operaciones intencionales.
La teora de la probabilidad es una rama de las matemticas que estudia los
fenmenos aleatorios y estocsticos. Los fenmenos aleatorios se contraponen a
los fenmenos deterministas, los cuales son resultados nicos y/o previsibles de
experimentos realizados bajo las mismas condiciones determinadas, por ejemplo,
si se calienta agua a 100 oC a nivel del mar se obtendr vapor. Los fenmenos
aleatorios, realizados, otra vez, bajo las mismas condiciones determinadas pero
como resultado posible poseen un conjunto de alternativas, por ejemplo, el
lanzamiento de un dado o de una moneda.
La teora de probabilidades se ocupa de asignar un cierto nmero a cada posible
resultado que pueda ocurrir en un experimento aleatorio, con el fin de cuantificar
dichos resultados y saber si un suceso es ms probable que otro.
Muchos fenmenos naturales son aleatorios, pero existen algunos como el
lanzamiento de un dado, donde el fenmeno no se repite en las mismas
condiciones, debido a que las caractersticas del material hace que no exista una
simetra del mismo, as las repeticiones no garantizan una probabilidad definida.
En los procesos reales que se modelizan mediante distribuciones de probabilidad
corresponden a modelos complejos donde no se conocen a priori todos los
parmetros que intervienen a probabilidad es la caracterstica de un evento, que
hace que existan razones para creer que este se realizara.

La probabilidad p de que suceda un evento S un total de n casos posibles

igualmente probables es igual a la razn entre el nmero de ocurrencias h de
dicho evento (casos favorables) y el nmero total de casos posibles n.
P= prob {S}= h/n
La probabilidad es un nmero (valor) que vara entre 0 y 1. Cuando el evento es
imposible se dice que su probabilidad es 0, si el evento es cierto y siempre tiene
que ocurrir su probabilidad es 1.
La probabilidad de no ocurrencia de un evento est dada por q, donde:
q=prob {no S} = 1-h/n
Sabemos que p es la probabilidad de que ocurra un evento y q es la probabilidad
de que no ocurra, entonces p + q = 1
Simblicamente el espacio de resultados, que normalmente se denota por es el
espacio que consiste en todos los resultados que son posibles. Los resultados,
que se denota por 1 2 etc. Son elementos del espacio .