Investigaci?

n Operativa I Cursada 2005 ncias Exactas Universidad Nacional del Centro de la Pcia de Buenos Aires

SIMULACI N MTODO MONTE CARL O

Simulacin : es el proceso de disear y desarrollar un modelo computarizado de un sistema o proceso y conducir experimentos con este modelo con el propsito de entender el comportamiento del sistema o evaluar varias estrategias con las cuales se puede operar el sistema (Shannon Robert) Modelo de simulacin: conjunto de hiptesis acerca del funcionamiento del sistema expresado como relaciones matemticas y/o lgicas entre los elementos del sistema. Proceso de simulacin: ejecucin del modelo a travs del tiempo en un ordenador para generar muestras representativas del comportamiento.

Mtodos de simulacin
Simulacin estadstica o Monte Carlo: Est basada en el muestreo sistemtico de variables aleatorias. Simulacin continua: Los estados del sistema cambian continuamente su valor. Estas simulaciones se modelan generalmente con ecuaciones diferenciales. Simulacin por eventos discretos: Se define el modelo cuyo comportamiento vara 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 simulacin. Simulacin por autmatas celulares: Se aplica a casos complejos, en los que se divide al comportamiento del sistema en subsistemas ms pequeos denominadas clulas. El resultado de la simulacin est dado por la interaccin de las diversas clulas.

Etapas del proceso de sim ulacin

Definicin, descripcin del problema. Plan. Formulacin del modelo. Programacin . Verificacion y Validacin del modelo. Diseo de experimentos y plan de corridas. Anlisis de resultados

Diagrama de flujo del modelo de simulacin

Reunir datos y elaborar el modelo

NO

Programar el modelo NO

Est validada?

Est verificada?

S
Disear el experimento

SI

NO
Documentar y Poner en prctica

Est completa?

Investigaci?n Operativa I Cursada 2005 ncias Exactas Universidad Nacional del Centro de la Pcia de Buenos Aires

Lenguajes de simulacin Simulacin Continua: 1130/CSMP, 360 CSMP y DYNAMO, MISTRAL Simulacin a Eventos Discretos: GPSS, SIMSCRIPT, SDL/SIM. Para casos simples podemos recurrir a la utilizacin de planillas de clculo. Tambin podemos implementar aplicaciones en los lenguajes Fortran, C++, Java, Dephi,...

Por qu Sim ulacin en Investigacin Operativa?

Los responsables de la toma de decisiones necesitan informacin cuantificable, sobre diferentes hechos que puedan ocurrir. La simulacin constituye una tcnica econmica 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 simulacin es una rama experimental dentro de la Investigacin Operativa. Nmeros aleatorios Deben tener igual probabilidad de salir elegidos. No debe existir correlacin serial Se generan por tablas (Rand 1955), o por dispositivos especiales: ruleta. En la prctica se utilizan algoritmos y se generan nmeros pseudo aleatorios. . Nmeros Pseudo aleatorios Sustituyen a los nmeros aleatorios. . Se generan por algoritmos o frmulas. Se debe asegurar la existencia de secuencias largas y densas. Generacin de Nmeros Pseudo aleatorios Centros Cuadrados: 442 = 1936 93 Mtodos Congruenciales: xn =(axn-1 + c) (mod m Transformacin Inversa x=F-1(x) siendo F(x)=Prob(X<=x)

SIMULACIN MONTE CAR LO

Los mtodos de Monte Carlo abarcan una coleccin de tcnicas que permiten obtener soluciones de problemas matemticos o fsicos por medio de pruebas aleatorias repetidas. En la prctica, las pruebas aleatorias se sustituyen por resultados de ciertos clculos realizados con nmeros aleatorios.

Investigaci?n Operativa I Cursada 2005 ncias Exactas Universidad Nacional del Centro de la Pcia de Buenos Aires

INTRODUCCIN
Bajo el nombre de Mtodo Monte Carlo o Simulacin Monte Carlo se agrupan una serie de procedimientos que analizan distribuciones de variables aleatorias usando simulacin de nmeros aleatorios. El Mtodo de Monte Carlo da solucin a una gran variedad de problemas matemticos haciendo experimentos con muestreos estadsticos en una computadora. El mtodo es aplicable a cualquier tipo de problema, ya sea estocstico o determinstico. Generalmente en estadstica los modelos aleatorios se usan para simular fenmenos que poseen algn componente aleatorio. Pero en el mtodo Monte Carlo, por otro lado, el objeto de la investigacin es el objeto en s mismo, un suceso aleatorio o pseudo-aleatorio se usa para estudiar el modelo. A veces la aplicacin del mtodo Monte Carlo se usa para analizar problemas que no tienen un componente aleatorio explcito; en estos casos un parmetro determinista del problema se expresa como una distribucin aleatoria y se simula dicha distribucin. Un ejemplo sera el famoso problema de las Agujas de Bufn. La simulacin de Monte Carlo tambin fue creada para resolver integrales que no se pueden resolver por mtodos analticos, para solucionar estas integrales se usaron nmeros aleatorios. Posteriormente se utiliz para cualquier esquema que emplee nmeros aleatorios, usando variables aleatorias con distribuciones de probabilidad conocidas, el cual es usado para resolver ciertos problemas estocsticos y determinsticos, donde el tiempo no juega un papel importante.

HISTORIA
El mtodo fue llamado as por el principado de Mnaco por ser ``la capital del juego de azar'', al tomar una ruleta como un generador simple de nmeros aleatorios. El nombre y el desarrollo sistemtico de los mtodos 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 mtodos de Monte Carlo como una herramienta de investigacin, proviene del trabajo de la bomba atmica durante la Segunda Guerra Mundial. Este trabajo involucraba la simulacin directa de problemas probabilsticos de hidrodinmica concernientes a la difusin de neutrones aleatorios en material de fusin. An en la primera etapa de estas investigaciones, John von Neumann y Stanislao Ulam refinaron esta curiosa ``Ruleta rusa'' y los mtodos``de divisin''. Sin embargo, el desarrollo sistemtico de estas ideas tuvo que esperar el trabajo de Harris y Herman Kahn en 1948. Aproximadamente en el mismo ao, Fermi, Metropolos y Ulam obtuvieron estimadores para los valores caractersticos de la ecuacin de Schrdinger para la captura de neutrones a nivel nuclear. Alrededor de 1970, los desarrollos tericos en complejidad computacional comienzan a proveer mayor precisin y relacin para el empleo del mtodo Monte Carlo. La teora identifica una clase de problemas para los cuales el tiempo necesario para evaluar la solucin exacta al problema crece con la clase, al menos exponencialmente con M. La cuestin a ser resuelta era si MC pudiese o no estimar la solucin al problema de tipo intratable con una adecuacin estadstica acotada a una complejidad temporal polinomial en M. Karp(1985)

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 nmero de matching perfectos en un grafo bipartito.

ALGORITMO S
El algoritmo de Simulacin Monte Carlo Crudo o Puro est fundamentado en la generacin de nmeros aleatorios por el mtodo de Transformacin Inversa, el cual se basa en las distribuciones acumuladas de frecuencias: Determinar la/s V.A. y sus distribuciones acumuladas(F)
Iterar tantas veces como Generar un nmero aleatorio muestras necesitamos uniforme (0,1). Determinar el valor de la V.A. para el nmero aleatorio generado de acuerdo a las clases que tengamos. Calcular media, desviacin estndar error y realizar el histograma.

Analizar resultados para distintos tamaos de muestra. Otra opcin para trabajar con Monte Carlo, cuando la variable aleatoria no es directamente el resultado de la simulacin o tenemos relaciones entre variables es la siguiente: Disear el modelo lgico de decisin Especificar distribuciones de probabilidad para las variables aleatorias relevantes. Incluir posibles dependencias entre variables. Muestrear valores de las variables aleatorias. Calcular el resultado del modelo segn los valores del muestreo (iteracin) y registrar el resultado Repetir el proceso hasta tener una muestra estadsticamente representativa Obtener la distribucin de frecuencias del resultado de las iteraciones Calcular media, desvo. Analizar los resultados Las principales caractersticas a tener en cuenta para la implementacin o utilizacin del algoritmo son:

Investigaci?n Operativa I Cursada 2005 ncias Exactas Universidad Nacional del Centro de la Pcia de Buenos Aires El sistema debe ser descripto por 1 o ms funciones de distribucin de probabilidad (fdp) Generador de nmeros aleatorios: como se generan los nmeros aleatorios es importante para evitar que se produzca correlacin entre los valores muestrales.

 Establecer lmites y reglas de muestreo para las fdp: conocemos que valores pueden adoptar las variables. Definir Scoring: Cuando un valor aleatorio tiene o no sentido para el modelo a simular. Estimacin Error: Con que error trabajamos, cuanto error podemos aceptar para que una corrida sea vlida? Tcnicas de reduccin de varianza. Paralelizacin y vectorizacin: En aplicaciones con muchas variables se estudia trabajar con varios procesadores paralelos para realizar la simulacin.

EJEMPLO PRACTICO I
Tenemos la siguiente distribucin de probabilidades para una demanda aleatoria y queremos ver que sucede con el promedio de la demanda en varias iteraciones:
Demanda

Frecuencia

1.00 0.80 0.40 0.60 0.20 0.40 0.10 0.20 0.10 0.20 0.00
42 45 48 51 54

Unidades

Utilizando la distribucin acumulada(F(x) es la probabilidad que la variable aleatoria tome valores menores o iguales a x) podemos determinar cual es el valor obtenido de unidades cuando se genera un nmero aleatorio a partir de una distribucin continua uniforme. Este mtodo de generacin de variable aleatoria se llama Transformacin Inversa.
Unidades 42 45 48 51 54 Frecuencia 0.10 0.20 0.40 0.20 0.10 Frecuencia Acumulada 0.10 0.30 0.70 0.90 1.00

Generando los valores aleatorios vamos a ver como se obtiene el valor de la demanda para cada da, interesndonos en este caso como es el orden de aparicin de los valores. Se busca el nmero aleatorio generado en la tabla de probabilidades acumuladas, una vez
N?mero de Simulaci?n N?meros aleatorios Valor de

Frecuenci

1 0.92 54 2 0.71

Investigaci?n Operativa I Cursada 2005 51 ncias Exactas Universidad Nacional del Centro de la Pcia de Buenos Aires 3 0.85 51 ... encontrado( si no es el valor exacto, ste debe ser menor que el de la fila seleccionada pero mayor que el de la fila anterior), de esa fila ... tomada como solucin se toma el valor de las ... tomar el lmite inferior del intervalo para unidades (Cuando trabajamos en Excel debemos n busca en las acumuladas, para poder emplear la funcin BUSCARV(), para 42 sera 0, para 43 0.46Supongamos que el nmero aleatorio generado sea 0,100001 y as sucesivamente). Ejemplo: 48 0,52, a qu valor de unidades corresponde? Nos fijamos en la columna de frecuencias acumuladas, ese valor exacto no aparece, Demanda el siguiente mayor es 0,70 y corresponde a 48 unidades. Se puede apreciar mejor en el 1.20 1.00 grfico, trazando una recta desde el eje de 0.90 1.00 la frecuencia hasta que intersecta con la 0.7 0.80 0 lnea de la funcin acumulada, luego se 0.60 baja a la coordenada de unidades y se 0.4,5 0.30 obtiene el valor correspondiente; en este 2 0.1 0 caso 48. 0
0.20 0.00

Cuando trabajamos con variables discretas la funcin acumulada tiene un Unidades intervalo o salto para cada variable( para casos prcticos hay que definir los intervalos y luego con una funcin de bsqueda hallar el valor). Para funciones continuas se puede hallar la inversa de la funcin acumulada. De esta forma logramos a partir de la distribucin de densidad calcular los valores de la variable aleatoria dada.

42

45

48

51

54

En la siguiente tabla, vemos como a medida que aumenta el numero de simulaciones, el valor simulado se acerca al valor original de la media y desviacin estndar, adems de la disminucin del error tpico.
Cantidad de Medi Desv Erro simulacione a o r s 10 100 1000 48.60 48.12 47.87 3.41 3.16 3.28 1.08 0.32 0.10

10000

47.87

3.30

0.03

Investigaci?n Operativa I Cursada 2005 ncias Exactas Universidad Nacional del Centro de la Pcia de Buenos Aires

EJEMPLO PRACTICO II
Analizaremos ahora una propuesta para la fabricacin de un nuevo artculo durante 4 aos. Con los datos de la siguiente tabla: Costos de puesta en marcha Precio de Venta Costos fijos Amortizacin anual $ 150000 $ 35000 $ 15000 $ 10000 75% de los ingresos 10%

Costos variables Costos del capital Fiscal Tasa

34% 10 Demanda promedio anual unidades

La demanda es la variable aleatoria de nuestro modelo, ya que puede tomar los siguientes valores: 8,9,10,11,12, es una distribucin discreta uniforme. Para poder simular los valores de esta variable utilizaremos la frmula ENTERO(8+5*ALEATORIO()). Debido a que los intervalos son todos de igual tamao (1/5), es igualmente posible que ALEATORIO() llegue a cada uno de ellos, y por lo tanto es igualmente posible que la frmula de cualquiera de los cinco valores posibles. La funcin ALEATORIO() de Excel genera un nmero en el intervalo (0:1) de una distribucin uniforme continua. A travs de la simulacin veremos que valores va a tomar el valor neto actual (VNA, El VNA es calculado mediante la formula correspondiente del Excel con un inters del 10% (VNA =
n

valores
i

). En la columna

i =1

( 1 + tasa ) i

correspondiente al ao 1 se han indicado las formulas que definen cada valor) en los 4 aos, utilizando el siguiente modelo matemtico de la situacin:
Ao 0 Demanda Ingresos Costo Fijo Costo Variable Amortizacin Utilidad antes de Impuestos Impuestos Utilidad despus de impuestos Flujo neto de efectivo Valor Neto Actual -150000 -21160 Ao 1 ENTERO(8+5*ALE ATORIO()) Precio de Venta*Demanda Costo fijo 75% Ingresos 10000 Ingresos Suma(costos) 34 % anterior Utilidad Impuestos Utilidad Amortizacin Ao 2 12 420000 15000 315000 10000 80000 27200 52800 62800 Ao 3 9 315000 15000 236250 10000 53750 18275 35475 45475 Ao 4 9 315000 15000 236250 10000 53750 18275 35475 45475

Ahora realizaremos varias corridas con diferentes tamaos de muestra para ver que sucede con el VNA. Armamos en otra hoja un cuadro con dos columnas y tantas filas como iteraciones(tamao de la muestra) deseemos realizar. En la columna VNA copiamos con pegado especial(frmula) la celda del modelo en la cual se calcula el VNA. Seleccionamos toda la tabla y con la herramienta Tabla en Datos se forma una tabla dinmica que contendr las simulaciones para la cantidad de iteraciones que hagamos.

Luego para cada tamao de muestra aplicaremos Estadstica descriptiva(En herramientas, Anlisis de datos) e Histograma (las clases que utilizamos son: -30000, -20000,

Cantidad de Iteraciones Media

-10000, 0, 10000, 20000, 30000) Desviaci?n

Est?ndar M?ximo M?nimo Error 10 13253.55 18445.01 44294.82 -9711.94

13515.19 13395.87 44728.71 -14567.50 1339.59 500 Investigaci?n Operativa I Cursada 2005 12686.22 ncias Exactas Universidad Nacional del Centro de la Pcia de Buenos Aires 13208.55 49067.55 -19817.50 590.70 Ahora 1000 realizamos una 12147.81 sntesis de las 12999.81 simulaciones 49067.55 desarrolladas -24156.34 para poder ver 411.09 5000 que sucedi con 12612.65 el modelo: 13085.18 49067.55 Histograma para 10 iteraciones -24156.34 185.05 10000 4.5 120.00 % 12537.13 4 12954.22 100.00 3.5 Frecu % 49067.55 3 encia -24156.34 2.5 80.00% 2 129.54 60.00%
Frecuenci
1.5 1 0.5 0 40.00% 20.00% .00%

% acum ulado

Cl ase

El valor de la media y desviacin estndar se estacionan a medida que aumenta la cantidad de iteraciones. Tambin, como podemos observar en el grfico, disminuye notablemente el error. Tambin el modelo nos presenta mayor variabilidad para los valores mximo y mnimo.

Resumen
60000 50000 40000 30000 20000 10000 0 -10000 -20000 -30000 NExperimentos Media Desviacin Estandar Maximo Minimo Error

APLICACIONES
Criptografa. Cromo dinmica cuntica. Densidad y flujo de trfico. Diseo de reactores nucleares. Diseo de VLSI. Ecologa. Econometra. Evolucin estelar. Fsica de materiales. Mtodos cuantitativos de organizacin industrial. Programas de computadora. Pronstico del ndice de la bolsa. Prospecciones en explotaciones petrolferas. Radioterapia contra el cncer. Sistemas de colas. Sistemas de inventario P y Q. Valoracin de cartera de valores.

SINTESIS

Investigaci?n Operativa I Cursada 2005 ncias Exactas Universidad Nacional del Centro de la Pcia de Buenos Aires El mtodo de Monte Carlo es una herramienta de investigacin y planeamiento; bsicamente es una tcnica de muestreo artificial, empleada para operar numricamente sistemas complejos que tengan componentes aleatorios o determinsticos, manteniendo tanto

la entrada como la salida un cierto grado de incertidumbre. En Investigacin Operativa, Monte Carlo es utilizado con fines experimentales, es decir se pueden elaborar distintos modelos e ir intercambiando parmetros para estudiar cuales son los posibles resultados. Cuando el tamao de las muestras es relativamente reducido, los resultados obtenidos No debemos confundir la simulacin con un mtodo de optimizacin, como por ejemplo el Simplex. En los mtodos de Optimizacin las variables de decisin son las salidas de la tcnica a las cuales buscamos calcular el/los valor/es ptimo/s, por el contrario en Monte Carlo u otro tipo de simulacin dichas variables constituyen las entradas del mismo; el modelo simulado propuesto evala distintas alternativas para un conjunto particular de soluciones. en la simulacin pueden ser muy sensibles a las condiciones iniciales. Un rea de investigacin est constituida por los mtodos Quasi-Monte Carlo, estos mtodos bsicamente acotan la generacin de los nmeros aleatorios.

REFERENCIAS
[1] A brief overview of what the Monte-Carlo http://www.physics.gla.ac.uk/~donnelly/files/montecarlo/ method to is and does.

[2] Arsham H. System Simulation: The Shortest Route http://home.ubalt.edu/ntsbarsh/Business-stat/simulation/sim.htm.

Applications.

[3] Barreto H. and Howland F. Introductory Econometrics via Monte Carlo Simulation with Microsoft Excel. http://www.wabash.edu/econometrics [4] Bong D. Monte Carlo http://www.visionengineer.com/mech/monte_carlo_simulation.shtml. [5] Bustamante A. Evaluacin de riesgos mediante http://www.cema.edu.ar/~alebus/riesgo/MONTECARLO.PPT simulacin Simulation. Monte Carlo.

[6] Deutsch, Leuangthong, Nguyen, Norrena, Ortiz, Oz, Pyrcz, and Zanon. Principles of Monte Carlo Simulation. http://www.ualberta.ca/~cdeutsch/MCS-course.htm [7] Eppen G., Gould F., Schmidt C., Mootre J., y Weatetherford L. Investigacin de Operaciones en la Ciencia Administrativa. Editorial Prentice Hall. 5 Edicin. 2000. [8] Hillier F, Lieberman G. Introduccin a la Investigacin de Operaciones. McGraw-Hill Editores. 1997. [9] Impact of Monte Carlo methods on scientific research. http://www.csm.ornl.gov/ssi-

Investigaci?n Operativa I Cursada 2005 ncias Exactas Universidad Nacional del Centro de la Pcia de Buenos Aires expo/MChist.html

[10]

Introduction to Monte Carlo Methods. http://csep1.phy.ornl.gov/mc/mc.html

[11] Monte Carlo Simulation rio.br/marco.ind/sim_stoc_proc.html

of

Stochastic

Processes.

[12] Padilla Shannon Ho. Monte Carlo Method. http://www.ccs.uky.edu/~douglas/Classes/cs521-01/montecarlo/MonteCarloMethod2.ppt [13] Quasi Monte Carlo Simulation. http://www.puc-rio.br/marco.ind/quasi_mc.html [14] Real options with Monte Carlo Simulations. http://www.puc-rio.br/marco.ind/montecarlo.html [15] Silvestre, Moreno, Toscana y Luis. Curso de Simulacin Monte Carlo. III Encuentro Nacional de docentes de Investigacin Operativa. Facultad de Cs. Econmicas. Universidad Nacional del Centro de la Provincia de Buenos Aires. 1990 [16] Simulacin. Introduccin a la investigacin de Operaciones. Facultad de Ingeniera . UDELAR. http://www.fing.edu.uy/inco/cursos/io/archivos/teorico/simulacion.pdf [17] Taha H. Investigacin de Operaciones una introduccin. Ed. Prentice Hall. 6 edicin. 1998. [18] Tcnicas de http://mural.uv.es/juanama/astronomia/montecarlo.htm Monte Carlo.

[19] THE WWW VIRTUAL LIBRARY: RANDOM NUMBERS and MONTE CARLO METHODS SUBSECTION: MONTE CARLO METHODS. http://random.mat.sbg.ac.at/links/monte.html [20] Winston W. (2005) Investigacin de Operaciones. Aplicaciones y algoritmos. 4 edicin. International Thomson Editores. [21] Woller J. Basics of Monte Carlo Simulations. http://www.chem.unl.edu/zeng/joy/mclab/mcintro.html
ta

Univ. of Nebraska-Lincoln