DESI-Assignment 4 Four Monte Carlo Simulations Solved

(1)      Develop a Windows application that performs the following four Monte Carlo simulations shown in the textbook: (1) Positive Determinant of a Random Matrix, (2) Two Dial Rolling Game, (3) Hatcheck Girl Problem, and (4) Project Network Analysis Problem.

(2)      The first simulation is to find the probability of a 3x3 random matrix to have a positive determinant, where the matrix is

+u11 −u12 −u13

 A= − u21 +u22 −u23, where uij  0 and A  0  The probability should be 0.0502. −u31 −u32 +u33

(3)      The second simulation is to find the probability of wining the Craps game. Tossing a pair of fair dice one or more times until a won or lost criterion is met. Wining criterion (1): the first roll gets spots 7 or 11. Losing criterion (1): the first roll gets spots 2, 3, or 12. Otherwise, the first roll set "Point" for successive rolls; therefore, Point {4, 5, 6, 8, 9, 10}. Wining criterion (2): keep rolling until Point appears. Losing criterion (2): if 7 is rolled before Point is rolled. The probability using axiomatic approach is (244/495) = 0.4929. (You can derive it)

(4)      The third simulation is to find the probability of the hatcheck girl returning hats totally wrong: Suppose n hats were sequentially stored for a serial of n customers, respectively. The girl returns the hats one after the other randomly. If no one customer receiving his hat correctly, the probability counts. The probability is around 0.368 or 0.369. When n approaches infinitive the probability = 0.36787944.

(5)      The forth simulation is to find the mean time to complete the project network, where the duration times of activities are random variables bounded by the given values. For the given problem in the textbook, the mean time is around values of 14.64, 14.59, and 14.57.

Probabilities for being the critical path of the paths are: 1-3-6: 0.0181,1-2-3-6: 0.0945, 1-2-5-6:

0.0015, 1-4-6: 0.1944, 1-3-4-6: 0.1189, 1-2-3-4-6: 0.5726.

(6)      The number of nodes, node locations, number of activities, and the starting/end node ID/duration time of each activity of a project network problem are sequentially specified in a

text file. The file format is:  

NumberOfNodes  x[1] y[1] x[2] y[2] … x[NumberOfNodes] y[NumberOfNodes] 

NumberOfActivities  

StartNodeID[1] EndNodeID[1] DurationTime[1] StartNodeID[2] EndNodeID[2] DurationTime[1] 

… … …  

StartNodeID[NumberOfActivities] EndNodeID[NumberOfActivities] DurationTime[NumberOfActivities] Sample File:

6 

0.05306604 0.5211492 

0.2739905 0.1729323 

0.5123047 0.5203184 

0.5134903 0.8812344 

0.6936172 0.1736024 

0.9143637 0.5229853 

9 

0 1 3 

0 2 6 

0 3 13 

1 2 9 

2 3 9 

1 4 3 

4 5 3 

2 5 7 

3 5 6 
 

(7)      Note that the location of a node is defined as a 2D point in a rectangular area. The first coordinate is the normalized horizontal coordinate measured from the left edge of the rectangle, where 0 is on the left edge and 1.0 is on the right edge. The second coordinate is the normalized vertical coordinate measured from the top edge of the rectangle, where 0 is on the top edge and 1.0 is on the bottom. Nodes are indexed from 0. The application should be able to read in such

text file and then find the possible paths starting from the first node to the last one. Note that the first node does not have any incoming arcs and the last node does not have any exiting arc.

(8)      The algorithm 2.4.2 of the textbook recursively calculates the completion time is not efficiency. Reasons: (1) an extra matrix N is required, (2) lack of information of all paths. Instead, we can

Yi, j ,if arc(i, j) exists use an nxn matrix storing the duration time such that: T =ti, j nn,ti, j =−1,otherwise .

Therefore, the configuration of the network is also represented by T; i.e., if ti, j 0, activity from node i to j exists whose duration time limit isti, j . All paths from node 0 to node n-1 can be extracted from this matrix in advance.

(9)      Suggestion: develop an algorithm to traverse the network to construct all existing paths. Data structure used in C# coding for the paths might be List<List<int. The algorithm should be a recursive function that adds a possible node to the existing path and submit it to the next recursive step. Back from the recursive call, the algorithm removes the node to add another possible node for next trial. The recursive procedure exits when the last node (node n-1) is appended and the sequence of nodes is copied to construct a new path.  

(10)   The Monte Carlo simulation on the project network is to generate random values for the duration times of all activities. Then evaluate the length (time length) of each path and find the critical one (with the largest length) whose length is therefore the completion time of the network. The application should update the count of being the critical path replicated for each path and finally calculate the probability of being the critical path for each path. In addition, the mean completion time of the network can be easily computed.

Extra Credits:

(1)      Provide graphics display for the project management problem, when it is read from a file.

(2)      Provide fault-proof algorithm to verify the validity of a project network, where the network must be connected, no cycle allowed, no incoming activity to the first node, no outgoing activity of the last one, and at least one path exists.

(3)      Provide graphical UI for user to construct a valid project network and save the model.

Snapshot of a sample app: