Metodo Monte Carlos
ThaniaRivera11 de Diciembre de 2012
2.750 Palabras (11 Páginas)620 Visitas
Facultad de Ciencias Exactas Investigación Operativa I
Universidad Nacional del Centro Cursada 2005
de la Pcia de Buenos Aires
1
S IMULACIÓN
MÉTODO MONTE CARLO
¨ Simulación : es el proceso de diseñar y desarrollar un modelo computarizado de un
sistema o proceso y conducir experimentos con este modelo con el propósito de entender
el comportamiento del sistema o evaluar varias estrategias con las cuales se puede operar
el sistema (Shannon Robert)
¨ Modelo de simulación: conjunto de hipótesis acerca del funcionamiento del sistema
expresado como relaciones matemáticas y/o lógicas entre los elementos del sistema.
¨ Proceso de simulación: ejecución del modelo a través del tiempo en un ordenador
para generar muestras representativas del comportamiento.
Métodos de simulación
¨ Simulación estadística o Monte Carlo: Está basada en el muestreo sistemático de
variables aleatorias.
¨ Simulación continua: Los estados del sistema cambian continuamente su valor. Estas
simulaciones se modelan generalmente con ecuaciones diferenciales.
¨ Simulación por eventos discretos: Se define el modelo cuyo comportamiento varía en
instantes del tiempo dados. Los momentos en los que se producen los cambios son los que
se identifican como los eventos del sistema o simulación.
¨ Simulación por autómatas celulares: Se aplica a casos complejos, en los que se divide al
comportamiento del sistema en subsistemas más pequeños denominadas células. El
resultado de la simulación está dado por la interacción de las diversas células.
Etapas del proceso de simulación
¨ Definición, descripción del problema. Plan.
¨ Formulación del modelo.
¨ Programación .
¨ Verificaciçon y Validación del modelo.
¨ Diseño de experimentos y plan de corridas.
¨ Análisis de resultados
Diagrama de flujo del modelo de simulación
Facultad de Ciencias Exactas Investigación Operativa I
Universidad Nacional del Centro Cursada 2005
de la Pcia de Buenos Aires
2
Lenguajes de simulación
¨ Simulación Continua: 1130/CSMP, 360 CSMP y DYNAMO, MISTRAL
¨ Simulación a Eventos Discretos: GPSS, SIMSCRIPT, SDL/SIM.
¨ Para casos simples podemos recurrir a la utilización de planillas de cálculo.
¨ También podemos implementar aplicaciones en los lenguajes Fortran, C++,
Java, Dephi,...
SI
Reunir datos y elaborar el modelo
Programar el modelo
Diseñar el experimento
Documentar y
Está completa? Poner en práctica
Está validada?
Está verificada?
SÍ
NO
NO
NO
SÍ
Facultad de Ciencias Exactas Investigación Operativa I
Universidad Nacional del Centro Cursada 2005
de la Pcia de Buenos Aires
3
Números aleatorios
¨ Deben tener igual probabilidad de salir elegidos.
¨ No debe existir correlación serial
¨ Se generan por tablas (Rand 1955), o por dispositivos especiales: ruleta. En la
práctica se utilizan algoritmos y se generan números pseudo aleatorios.
Números Pseudo aleatorios
¨ Sustituyen a los números aleatorios.
¨ Se generan por algoritmos o fórmulas.
¨ Se debe asegurar la existencia de secuencias largas y densas.
Generación de Números Pseudo aleatorios
¨ Centros Cuadrados:
442 = 1936 93
¨ Métodos Congruenciales:
xn =(axn-1 + c) (mod m
¨ Transformación Inversa
x=F-1(x) siendo F(x)=Prob(X<=x)
S IMULACIÓN MONTE CARLO
Los métodos de Monte Carlo abarcan una colección de técnicas que permiten obtener
soluciones de problemas matemáticos o físicos por medio de pruebas aleatorias repetidas. En
la práctica, las pruebas aleatorias se sustituyen por resultados de ciertos cálculos realizados
con números aleatorios.
¿Por qué Simulación en Investigación Operativa?
¨ Los responsables de la toma de decisiones necesitan información
cuantificable, sobre diferentes hechos que puedan ocurrir.
¨ La simulación constituye una técnica económica que nos permite ofrecer
varios escenarios posibles de un modelo del negocio, nos permite
equivocarnos sin provocar efectos sobre el mundo real.
¨ Podemos afirmar entonces, que la simulación es una rama experimental
dentro de la Investigación Operativa.
Facultad de Ciencias Exactas Investigación Operativa I
Universidad Nacional del Centro Cursada 2005
de la Pcia de Buenos Aires
4
INTRODUCCIÓN
Bajo el nombre de Método Monte Carlo o Simulación Monte Carlo se agrupan una
serie de procedimientos que analizan distribuciones de variables aleatorias usando simulación
de números aleatorios.
El Método de Monte Carlo da solución a una gran variedad de problemas
matemáticos haciendo experimentos con muestreos estadísticos en una computadora. El
método es aplicable a cualquier tipo de problema, ya sea estocástico o determinístico.
Generalmente en estadística los modelos aleatorios se usan para simular fenómenos
que poseen algún componente aleatorio. Pero en el método Monte Carlo, por otro lado, el
objeto de la investigación es el objeto en sí mismo, un suceso aleatorio o pseudo-aleatorio se
usa para estudiar el modelo.
A veces la aplicación del método Monte Carlo se usa para analizar problemas que no
tienen un componente aleatorio explícito; en estos casos un parámetro determinista del
problema se expresa como una distribución aleatoria y se simula dicha distribución. Un
ejemplo sería el famoso problema de las Agujas de Bufón.
La simulación de Monte Carlo también fue creada para resolver integrales que no se
pueden resolver por métodos analíticos, para solucionar estas integrales se usaron números
aleatorios. Posteriormente se utilizó para cualquier esquema que emplee números aleatorios,
usando variables aleatorias con distribuciones de probabilidad conocidas, el cual es usado
para resolver ciertos problemas estocásticos y determinísticos, donde el tiempo no juega un
papel importante.
HI STORIA
El método fue llamado así por el principado de Mónaco por ser ``la capital del juego
de azar'', al tomar una ruleta como un generador simple de números aleatorios. El nombre y el
desarrollo sistemático de los métodos de Monte Carlo datan aproximadamente de 1944 con el
desarrollo de la computadora. Sin embargo hay varias instancias (aisladas y no desarrolladas)
en muchas ocasiones anteriores a 1944.
El uso real de los métodos de Monte Carlo como una herramienta de investigación,
proviene del trabajo de la bomba atómica durante la Segunda Guerra Mundial. Este trabajo
involucraba la simulación directa de problemas probabilísticos de hidrodinámica
concernientes a la difusión de neutrones aleatorios en material de fusión.
Aún en la primera etapa de estas investigaciones, John von Neumann y Stanislao Ulam
refinaron esta curiosa ``Ruleta rusa'' y los métodos``de división''. Sin embargo, el desarrollo
sistemático de estas ideas tuvo que esperar el trabajo de Harris y Herman Kahn en 1948.
Aproximadamente en el mismo año, Fermi, Metropolos y Ulam obtuvieron estimadores para
los valores característicos de la ecuación de Schrödinger para la captura de neutrones a nivel
nuclear.
Alrededor de 1970, los desarrollos teóricos en complejidad computacional comienzan
a proveer mayor precisión y relación para el empleo del método Monte Carlo. La teoría
identifica una clase de problemas para los cuales el tiempo necesario para evaluar la solución
exacta al problema crece con la clase, al menos exponencialmente con M. La cuestión a ser
resuelta era si MC pudiese o no estimar la solución al problema de tipo intratable con una
adecuación estadística acotada a una complejidad temporal polinomial en M. Karp(1985)
Facultad de Ciencias Exactas Investigación Operativa I
Universidad Nacional del Centro Cursada 2005
de la Pcia de Buenos Aires
5
muestra esta propiedad para estimar en una red plana multiterminal con arcos fallidos
aleatorios. Dyer(1989) utiliza MC para estimar el volumen de un convex body en el espacio
Euclidiano M-dimensional. Broder(1986), Jerrum y Sinclair (1988) establecen la propiedad
para estimar la persistencia de una matriz o en forma equivalente, el número de matching
perfectos en un grafo bipartito.
ALGORITMOS
El algoritmo de Simulación Monte Carlo Crudo o Puro está fundamentado en la
generación de números aleatorios por el método de Transformación Inversa, el cual se basa en
las distribuciones acumuladas de frecuencias:
¨ Determinar la/s V.A. y sus distribuciones acumuladas(F)
¨ Generar un número aleatorio
¨ uniforme Î (0,1).
¨ Determinar el valor de la V.A. para el número
aleatorio generado de acuerdo a las clases que
tengamos.
¨ Calcular media, desviación estándar error y realizar el histograma.
¨
...