The Monte Carlo Process


[Page 612 ( continued )]

One characteristic of some systems that makes them difficult to solve analytically is that they consist of random variables represented by probability distributions. Thus, a large proportion of the applications of simulations are for probabilistic models.

The term Monte Carlo has become synonymous with probabilistic simulation in recent years . However, the Monte Carlo technique can be more narrowly defined as a technique for selecting numbers randomly from a probability distribution (i.e., "sampling") for use in a trial (computer) run of a simulation. The Monte Carlo technique is not a type of simulation model but rather a mathematical process used within a simulation.

Monte Carlo is a technique for selecting numbers randomly from a probability distribution .


The name Monte Carlo is appropriate because the basic principle behind the process is the same as in the operation of a gambling casino in Monaco. In Monaco such devices as roulette wheels, dice, and playing cards are used. These devices produce numbered results at random from well-defined populations. For example, a 7 resulting from thrown dice is a random value from a population of 11 possible numbers (i.e., 2 through 12). This same process is employed, in principle, in the Monte Carlo process used in simulation models.

The Monte Carlo process is analogous to gambling devices .


The Use of Random Numbers

The Monte Carlo process of selecting random numbers according to a probability distribution will be demonstrated using the following example. The manager of Computer-World, a store that sells computers and related equipment, is attempting to determine how many laptop PCs the store should order each week. A primary consideration in this decision is the average number of laptop computers that the store will sell each week and the average weekly revenue generated from the sale of laptop PCs. A laptop sells for $4,300. The number of laptops demanded each week is a random variable (which we will define as x ) that ranges from 0 to 4. From past sales records, the manager has determined the frequency of demand for laptop PCs for the past 100 weeks. From this frequency distribution, a probability distribution of demand can be developed, as shown in Table 14.1.


[Page 613]
Table 14.1. Probability distribution of demand for laptop PCs

PCs Demanded per Week

Frequency of Demand

Probability of Demand, P ( x )

20

.20

1

40

.40

2

20

.20

3

10

.10

4

10

.10

 

100

1.00


The purpose of the Monte Carlo process is to generate the random variable, demand, by sampling from the probability distribution, P ( x ). The demand per week can be randomly generated according to the probability distribution by spinning a wheel that is partitioned into segments corresponding to the probabilities, as shown in Figure 14.1.

Figure 14.1. A roulette wheel for demand


In the Monte Carlo process, values for a random variable are generated by sampling from a probability distribution .


Because the surface area on the roulette wheel is partitioned according to the probability of each weekly demand value, the wheel replicates the probability distribution for demand if the values of demand occur in a random manner. To simulate demand for 1 week, the manager spins the wheel; the segment at which the wheel stops indicates demand for 1 week. Over a period of weeks (i.e., many spins of the wheel), the frequency with which demand values occur will approximate the probability distribution, P ( x ). This method of generating values of a variable, x , by randomly selecting from the probability distributionthe wheelis the Monte Carlo process.

By spinning the wheel, the manager artificially reconstructs the purchase of PCs during a week. In this reconstruction, a long period of real time (i.e., a number of weeks) is represented by a short period of simulated time (i.e., several spins of the wheel).

A long period of real time is represented by a short period of simulated time .


Now let us slightly reconstruct the roulette wheel. In addition to partitioning the wheel into segments corresponding to the probability of demand, we will put numbers along the outer rim, as on a real roulette wheel. This reconstructed roulette wheel is shown in Figure 14.2.

Figure 14.2. Numbered roulette wheel
(This item is displayed on page 614 in the print version)


There are 100 numbers from 0 to 99 on the outer rim of the wheel, and they have been partitioned according to the probability of each demand value. For example, 20 numbers from 0 to 19 (i.e., 20% of the total 100 numbers) correspond to a demand of no (0) PCs. Now we can determine the value of demand by seeing which number the wheel stops at as well as by looking at the segment of the wheel.


[Page 614]

When the manager spins this new wheel, the actual demand for PCs will be determined by a number. For example, if the number 71 comes up on a spin, the demand is 2 PCs per week; the number 30 indicates a demand of 1. Because the manager does not know which number will come up prior to the spin and there is an equal chance of any of the 100 numbers occurring, the numbers occur at random; that is, they are random numbers .

Obviously, it is not generally practical to generate weekly demand for PCs by spinning a wheel. Alternatively, the process of spinning a wheel can be replicated by using random numbers alone.

First, we will transfer the ranges of random numbers for each demand value from the roulette wheel to a table, as in Table 14.2. Next, instead of spinning the wheel to get a random number, we will select a random number from Table 14.3, which is referred to as a random number table . (These random numbers have been generated by computer so that they are all equally likely to occur , just as if we had spun a wheel. The development of random numbers is discussed in more detail later in this chapter.) As an example, let us select the number 39, the first entry in Table 14.3. Looking again at Table 14.2, we can see that the random number 39 falls in the range 2059, which corresponds to a weekly demand of 1 laptop PC.


[Page 615]
Table 14.2. Generating demand from random numbers
(This item is displayed on page 614 in the print version)


Table 14.3. Random number table

39 65 76 45 45

19 90 69 64 61

20 26 36 31 62

58 24 97 14 97

95 06 70 99 00

73 71 23 70 90

65 97 60 12 11

31 56 34 19 19

47 83 75 51 33

30 62 38 20 46

72 18 47 33 84

51 67 47 97 19

98 40 07 17 66

23 05 09 51 80

59 78 11 52 49

75 12 25 69 17

17 95 21 78 58

24 33 45 77 48

69 81 84 09 29

93 22 70 45 80

37 17 79 88 74

63 52 06 34 30

01 31 60 10 27

35 07 79 71 53

28 99 52 01 41

02 48 08 16 94

85 53 83 29 95

56 27 09 24 43

21 78 55 09 82

72 61 88 73 61

87 89 15 70 07

37 79 49 12 38

48 13 93 55 96

41 92 45 71 51

09 18 25 58 94

98 18 71 70 15

89 09 39 59 24

00 06 41 41 20

14 36 59 25 47

54 45 17 24 89

10 83 58 07 04

76 62 16 48 68

58 76 17 14 86

59 53 11 52 21

66 04 18 72 87

47 08 56 37 31

71 82 13 50 41

27 55 10 24 92

28 04 67 53 44

95 23 00 84 47

93 90 31 03 07

34 18 04 52 35

74 13 39 35 22

68 95 23 92 35

36 63 70 35 33

21 05 11 47 99

11 20 99 45 18

76 51 94 84 86

13 79 93 37 55

98 16 04 41 67

95 89 94 06 97

27 37 83 28 71

79 57 95 13 91

09 61 87 25 21

56 20 11 32 44

97 18 31 55 73

10 65 81 92 59

77 31 61 95 46

20 44 90 32 64

26 99 76 75 63

69 08 88 86 13

59 71 74 17 32

48 38 75 93 29

73 37 32 04 05

60 82 29 20 25

41 26 10 25 03

87 63 93 95 17

81 83 83 04 49

77 45 85 50 51

79 88 01 97 30

91 47 14 63 62

08 61 74 51 69

92 79 43 89 79

29 18 94 51 23

14 85 11 47 23

80 94 54 18 47

08 52 85 08 40

48 40 35 94 22

72 65 71 08 86

50 03 42 99 36

67 06 77 63 99

89 85 84 46 06

64 71 06 21 66

89 37 20 70 01

61 65 70 22 12

59 72 24 13 75

42 29 72 23 19

06 94 76 10 08

81 30 15 39 14

81 33 17 16 33

63 62 06 34 41

79 53 36 02 95

94 61 09 43 62

20 21 14 68 86

84 95 48 46 45

78 47 23 53 90

79 93 96 38 63

34 85 52 05 09

85 43 01 72 73

14 93 87 81 40

87 68 62 15 43

97 48 72 66 48

53 16 71 13 81

59 97 50 99 52

24 62 20 42 31

47 60 92 10 77

26 97 05 73 51

88 46 38 03 58

72 68 49 29 31

75 70 16 08 24

56 88 87 59 41

06 87 37 78 48

65 88 69 58 39

88 02 84 27 83

85 81 56 39 38

22 17 68 65 84

87 02 22 57 51

68 69 80 95 44

11 29 01 95 80

49 34 35 36 47

19 36 27 59 46

39 77 32 77 09

79 57 92 36 59

89 74 39 82 15

08 58 94 34 74

16 77 23 02 77

28 06 24 25 93

22 45 44 84 11

87 80 61 65 31

09 71 91 74 25

78 43 76 71 61

97 67 63 99 61

30 45 67 93 82

59 73 19 85 23

53 33 65 97 21

03 28 28 26 08

69 30 16 09 05

53 58 47 70 93

66 56 45 65 79

45 56 20 19 47

04 31 17 21 56

33 73 99 19 87

26 72 39 27 67

53 77 57 68 93

60 61 97 22 61

61 06 98 03 91

87 14 77 43 96

43 00 65 98 50

45 60 33 01 07

98 99 46 50 47

23 68 35 26 00

99 53 93 61 28

52 70 05 48 34

56 65 05 61 86

90 92 10 70 80

15 39 25 70 99

93 86 52 77 65

15 33 59 05 28

22 87 26 07 47

86 96 98 29 06

58 71 96 30 24

18 46 23 34 27

85 13 99 24 44

49 18 09 79 49

74 16 32 23 02

93 22 53 64 39

07 10 63 76 35

87 03 04 79 88

08 13 13 85 51

55 34 57 72 69

78 76 58 54 74

92 38 70 96 92

52 06 79 79 45

82 63 18 27 44

69 66 92 19 09

61 81 31 96 82

00 57 25 60 59

46 72 60 18 77

55 66 12 62 11

08 99 55 64 57

42 88 07 10 05

24 98 65 63 21

47 21 61 88 32

27 80 30 21 60

10 92 35 36 12

77 94 30 05 39

28 10 99 00 27

12 73 73 99 12

49 99 57 94 82

96 88 57 17 91


Random numbers are equally likely to occur .


By repeating this process of selecting random numbers from Table 14.3 (starting anywhere in the table and moving in any direction but not repeating the same sequence) and then determining weekly demand from the random number, we can simulate demand for a period of time. For example, Table 14.4 shows demand for a period of 15 consecutive weeks.


[Page 616]
Table 14.4. Randomly generated demand for 15 weeks

Week

r

Demand, x

Revenue

1

39

1

$ 4,300

2

73

2

8,600

3

72

2

8,600

4

75

2

8,600

5

37

1

4,300

6

02

7

87

3

12,900

8

98

4

17,200

9

10

10

47

1

4,300

11

93

4

17,200

12

21

1

4,300

13

95

4

17,200

14

97

4

17,200

15

69

2

8,600

   

S =31

$133,300


From Table 14.4 the manager can compute the estimated average weekly demand and revenue:

The manager can then use this information to help determine the number of PCs to order each week.

Although this example is convenient for illustrating how simulation works, the average demand could have more appropriately been calculated analytically using the formula for expected value. The expected value or average for weekly demand can be computed analytically from the probability distribution, P ( x ):

where

x i

=

demand value i

P ( x i )

=

probability of demand

n

=

the number of different demand values


Therefore,

E ( x )

=

(.20)(0) + (.40)(1) + (.20)(2) + (.10)(3) + (.10)(4)

 

=

1.5 PCs per week


Simulation results will not equal analytical results unless enough trials of the simulation have been conducted to reach steady state .


The analytical result of 1.5 PCs is close to the simulated result of 2.07 PCs, but clearly there is some difference. The margin of difference (0.57 PCs) between the simulated value and the analytical value is a result of the number of periods over which the simulation was conducted. The results of any simulation study are subject to the number of times the simulation occurred (i.e., the number of trials ). Thus, the more periods for which the simulation is conducted, the more accurate the result. For example, if demand were simulated for 1,000 weeks, in all likelihood an average value exactly equal to the analytical value (1.5 laptop PCs per week) would result.


[Page 617]

Time Out: For John Von Neumann

The mathematics of the Monte Carlo method have been known for years; the British mathematician Lord Kelvin used the technique in a paper in 1901. However, it was formally identified and given this name by the Hungarian mathematician John Von Neumann while working on the Los Alamos atomic bomb project during World War II. During this project, physicists confronted a problem in determining how far neutrons would travel through various materials (i.e., neutron diffusion in fissile material). The Monte Carlo process was suggested to Von Neumann by a colleague at Los Alamos, Stanislas Ulam, as a means to solve this problemthat is, by selecting random numbers to represent the random actions of neutrons. However, the Monte Carlo method as used in simulation did not gain widespread popularity until the development of the modern electronic computer after the war. Interestingly, this remarkable man, John Von Neumann, is credited with being the key figure in the development of the computer.


Once a simulation has been repeated enough times that it reaches an average result that remains constant, this result is analogous to the steady-state result, a concept we discussed previously in our presentation of queuing. For this example, 1.5 PCs is the long-run average or steady-state result, but we have seen that the simulation might have to be repeated more than 15 times (i.e., weeks) before this result is reached.

Comparing our simulated result with the analytical (expected value) result for this example points out one of the problems that can occur with simulation. It is often difficult to validate the results of a simulation modelthat is, to make sure that the true steady-state average result has been reached. In this case we were able to compare the simulated result with the expected value (which is the true steady-state result), and we found there was a slight difference. We logically deduced that the 15 trials of the simulation were not sufficient to determine the steady-state average. However, simulation most often is employed whenever analytical analysis is not possible (this is one of the reasons that simulation is generally useful). In these cases, there is no analytical standard of comparison, and validation of the results becomes more difficult. We will discuss this problem of validation in more detail later in the chapter.

It is often difficult to validate that the results of a simulation truly replicate reality .





Introduction to Management Science
Introduction to Management Science (10th Edition)
ISBN: 0136064361
EAN: 2147483647
Year: 2006
Pages: 358

Similar book on Amazon

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net