OR_08 模拟法

1、第八章第八章 模拟法模拟法（Simulation）11. 排队系统的随机模拟法排队系统的随机模拟法2. 模拟法的基本概念模拟法的基本概念3. 模拟法的实现与应用模拟法的实现与应用4. 案例分析案例分析5. 仿真平台简介仿真平台简介2第第1节节 排队系统的随机模拟法排队系统的随机模拟法 当排队系统的到达间隔时间和服务时当排队系统的到达间隔时间和服务时间的概率分布很复杂时，或不能用公式给间的概率分布很复杂时，或不能用公式给出时，那么就不能用解析法求解。这就需出时，那么就不能用解析法求解。这就需要用随机模拟法求解。要用随机模拟法求解。3 某仓库前有一卸货场，货车一般是夜间到达，白某仓库前有一卸货场，

2、货车一般是夜间到达，白天卸货。每天只能卸货天卸货。每天只能卸货2 2车，若一天内到达数量超过车，若一天内到达数量超过2 2车，那么就推迟到次日卸货。根据表车，那么就推迟到次日卸货。根据表1 1所示的经验所示的经验货车到达数的概率分布（相对频率）平均为货车到达数的概率分布（相对频率）平均为1.51.5车车/ /天，求每天推迟卸货的平均车数。天，求每天推迟卸货的平均车数。到达车数到达车数012345=6概率概率0.230.300.300.10.050.020.004表表1分析：分析： u 是单服务台的排队系统是单服务台的排队系统u 可验证到达车数可验证到达车数不服从泊松分布不服从泊松分布u 服务时

3、间也服务时间也不服从负指数分布不服从负指数分布( (这是定长服务时间这是定长服务时间) )u 不能用经典的排队模型求解。不能用经典的排队模型求解。5 随机模拟法首先要求事件能按历史的概率分布规随机模拟法首先要求事件能按历史的概率分布规律出现。律出现。 对该问题的数据进行分析，取对该问题的数据进行分析，取100100张卡片，按表张卡片，按表1 1的概率，取的概率，取2323张卡片填入张卡片填入0 0；取；取3030张卡片填张卡片填2 2；取；取1010张张填填3 3，；去，；去5 5张填张填4 4；取两张填；取两张填5 5等。然后将这些卡片放等。然后将这些卡片放在盒子里在盒子里搅匀搅匀，再随机地

4、一一取出，依次记录卡片上，再随机地一一取出，依次记录卡片上的数码，得到这一系列数据就是的数码，得到这一系列数据就是每天到达车数的模拟每天到达车数的模拟。实际应用时可用随机数表，表实际应用时可用随机数表，表2 2就是随机数表的一部分。就是随机数表的一部分。6表2 随机数表7 表 3 本例在求解时先按到达车数的概率，分别给它们分本例在求解时先按到达车数的概率，分别给它们分配随机数，见表配随机数，见表3。到达车数到达车数概率概率累计概率累计概率对应的随机数对应的随机数00.230.23002210.300.53235220.300.83538230.100.93839240.050.98939750

5、.021.0094991.008 以下开始模拟（见表以下开始模拟（见表4）。前）。前3天作为模拟的预备期，记天作为模拟的预备期，记为为x。然后依次从第一天、第二天。然后依次从第一天、第二天第第50天。如第一天得到天。如第一天得到随机数随机数66，从表，从表3中可见，第一天达到车数为中可见，第一天达到车数为2，将它记入表，将它记入表4中。第二天，得到随机数中。第二天，得到随机数96 ，它在表，它在表3中对应达到中对应达到4车车如如此一直到此一直到50天。表天。表4 的第的第(2)、(3)列数字都填入后，计算出第列数字都填入后，计算出第(4)、 (5) 、(6)列数字，从第一个列数字，从第一个x日

6、开始。日开始。当天倒车数当天倒车数(3)+前一天推迟车数前一天推迟车数(6)=当天需要卸货车数当天需要卸货车数(4)9 分析结果分析结果u不考虑头三天写不考虑头三天写x x的预备阶段的数据。这是为了使的预备阶段的数据。这是为了使模拟在一个模拟在一个稳态过程稳态过程中任一点开始，否则若认为开始中任一点开始，否则若认为开始时没有积压就失去了随机性了。时没有积压就失去了随机性了。u表表4 4中表明了模拟中表明了模拟5050天运行情况，这相当于一个天运行情况，这相当于一个随随机样本机样本。由此可见多数情况下很少发生推迟卸车而造。由此可见多数情况下很少发生推迟卸车而造成积压。只是在第成积压。只是在第36

7、36天比较严重，平均到达车数为天比较严重，平均到达车数为1.581.58，比期望值略高。，比期望值略高。u又知平均每天有又知平均每天有0.90.9车推迟卸货，当然模拟时间越车推迟卸货，当然模拟时间越长结果越准确。长结果越准确。10 这方法适用于对不同方案可能产生的结果进行比这方法适用于对不同方案可能产生的结果进行比较，用计算机进行模拟是更为方便。模拟方法只能得较，用计算机进行模拟是更为方便。模拟方法只能得到到数字结果数字结果，不能得出，不能得出解析式解析式。11表 4(1)日期日期(2)随机数随机数(3)到达数到达数(4)需要卸货需要卸货数数(5)卸货车数卸货车数(6)推迟卸货车推迟卸货车数数

8、x974422x020220 x8022201662220296442235524224954222050231110总计总计7945平均平均1.580.90121. Definition “Simulation is the process of designing a model of a real system and conducting experiments with this model for the purpose of either understanding the behavior of the system and/or evaluating various stra

9、tegies for the operation of the system.” Introduction to Simulation Using SIMAN (2nd Edition)第第2节节 模拟的基本概念模拟的基本概念 Simulation is one of the most widely used techniques in operations research and management scienceNo longer the approach of “last resort”!152. Several basic building blocks in a simulati

10、on model 1. A definition of the state of the system (e.g., the number of customers in a queueing system).2. Identify the possible states of the system that can occur.3. Identify the possible events (e.g., arrivals and service completions in a queueing system) that would change the state of the syste

11、m.4. The simulation clock, that will record the passage of (simulated) time.5. A method for randomly generating the events of the various kinds.6. A formula for identifying state transitions that are generated by the various kinds of Events.163. OUTLINE OF A MAJOR SIMULATION STUDYStep 1: Formulate t

12、he Problem and Plan the StudyStep 2: Collect the Data and Formulate the Simulation ModelStep 3: Check the Accuracy of the Simulation ModelStep 4: Select the Software and Construct a Computer ProgramStep 5: Test the Validity of the Simulation ModelStep 6: Plan the Simulations to Be PerformedStep 7: C

13、onduct the Simulation Runs and Analyze the ResultsStep 8: Present Recommendations to Management - Introduction to Operations Research(P892-951，10th Edition)4.The Advantages of SimulationSome of the reasons why simulation is preferable to direct experimentation :Cost Experimentation with real system

14、is likely to be costly. It is expensive to interrupt day to day operations to try out new ideas If alterations cause operations performance to worsen- loss of customer satisfactionTime Time consuming to experiment with the real system and this may take many weeks and months before a true reflection

15、is obtained.Control of experimental conditions It is useful to control the conditions under which the experiment is being done. e.g. it is not easy to control the arrival of patients at a hospitalThe real system does not exist. The real system may not exist.Flexibility to model things as they are (e

16、ven if messy and complicated)5.Disadvantages of SimulationSome of the problems associated with using simulation Expensive simulation software is not necessarily cheap and cost of model development and use may be considerable. Time consuming simulation is a time consuming approach Data hungry most si

17、mulations require significant amount of data Requires expertise requires skills in conceptual modelling, validation and statistics.6.Applications for which Simulation might be used Manufacturing systems Public systems, health care, military, natural resources Transportation systems Construction syst

18、ems Restaurant and entertainment systems Business process reengineering / management Food processing Computer system performance第第3节节 模拟法的实现与应用模拟法的实现与应用1. Single-server queue SimulationDiscrete-event simulation: Modeling of a system as it evolves over time by a representation where the state variabl

19、es change instantaneously at separated points in time More precisely, state can change at only a countable number of points in time These points in time are when events occurEvent: Instantaneous occurrence that may change the state of the system Sometimes get creative about what an “event” is e.g.,

20、end of simulation, make a decision about a systems operationCan in principle be done by hand, but usually done on computer20 Example: Single-server queue Estimate expected average delay in queue (line, not service) State variables Status of server (idle, busy) needed to decide what to do with an arr

21、ival Current length of the queue to know where to store an arrival that must wait in line Time of arrival of each customer now in queue needed to compute time in queue when service starts Events Arrival of a new customer Service completion (and departure) of a customer Maybe end-simulation event (a

22、“fake” event) whether this is an event depends on how simulation terminates (a modeling decision)21Several common components, general organization System state variables to describe state Simulation clock current value of simulated time Event list times of future events (as needed) Statistical count

23、ers to accumulate quantities for output Initialization routine initialize model at time 0 Timing routine determine next event time, type; advance clock Event routines carry out logic for each event type Library routines utility routines to generate random variates, etc. Report generator to summarize

24、, report results at end Main program ties routines together, executes them in right order22（1） Problem Statement Assume interarrival times are independent and identically distributed (IID) random variables Assume service times are IID, and are independent of interarrival times Queue discipline is FI

25、FO Start empty and idle at time 0 First customer arrives after an interarrival time, not at time 0 Stopping rule: When nth customer has completed delay in queue (i.e., enters service) n will be specified as input23 Quantities to be estimated Expected average delay in queue (excluding service time) o

26、f the n customers completing their delays Expected average number of customers in queue (excluding any in service) A continuous-time average Area under Q(t) = queue length at time t, divided by T(n) = time simulation ends see book for justification and details Expected utilization (proportion of tim

27、e busy) of the server Another continuous-time average Area under B(t) = server-busy function (1 if busy, 0 if idle at time t), divided by T(n) justification and details in book Many others are possible (maxima, minima, time or number in system, proportions, quantiles, variances ) Important: Discrete

28、-time vs. continuous-time statistics24（2） Intuitive ExplanationGiven (for now) interarrival times (all times are in minutes):0.4, 1.2, 0.5, 1.7, 0.2, 1.6, 0.2, 1.4, 1.9, Given service times:2.0, 0.7, 0.2, 1.1, 3.7, 0.6, n = 6 delays in queue desired“Hand” simulation: Display system, state variables,

29、 clock, event list, statistical counters all after execution of each event Use above lists of interarrival, service times to “drive” simulation Stop when number of delays hits n = 6, compute output performance measures25123456781239e1=0.4e2=1.6e3=2.1e4=2.4e5=3.1e6=3.3e7=3.8e8=4.0e9=4.9e10=5.6e11=5.8

30、e12=7.2e13=8.6Q(t)tArea under Q(t) = 9.91234567819e1=0.4e2=1.6e3=2.1e4=2.4e5=3.1e6=3.3e7=3.8e8=4.0e9=4.9e10=5.6e11=5.8e12=7.2e13=8.6B(t)t00.9Area under B(t) = 7.7（3） Computer simulation Flowchart Program28Start0.Invoke the initialization routeRepeat1.Invoke the timing routine2.Invoke event routine i

31、0. Update system state1. Update statistical counters 2. Generate future events and add to event listMain programEvent routine iIssimulation over?1.Compute estimates of interest2. Write reportStopReport generatorYesNo1.Set simulationclock2. Initial system state and statistical counters3. Initial even

32、t list1.Determine the next event type,say,i2. Advance the simulation clockGenerate randomvariatesLibrary routinesiInitialization routineTiming routinesArrival eventSchedule the next arrival eventIsthe server busy?Store time of arrival of this customerReturnYesNo+numInQSet delay=0and gather statistic

33、s Write error message and stop simulationIsthe queue full?+numCustsDelayed;serverStatus = BUSY; /Schedule a departure event timeNextEvent2 = simuTime + expon(meanService);YesNotimeNextEvent1 = simuTime + expon(meanInterarrival);timeArrivalnumInQ = simuTime;Departure eventIsthe queue empty?/departure

34、 event is impossibletimeNextEvent2 = Double.MAX_VALUE;ReturnYesNo/Make the server idleserverStatus = IDLE;-numInQ;Compute delay of customer entering service and gather statistics /Add 1 to the number of customers delayed +numCustsDelayed; /Schedule a departure event timeNextEvent2 = simuTime + expon

35、(meanService);Move each customer in queue up one place32An Object-Oriented Programming in JavaThe simulation runs until 1000 customers have been served. A continuous (or time-averaged) statistic and a discrete statistic are both collected during the simulation and are printed when the simulation run

36、 is completed. The continuous statistic is the average size of the queue. The discrete statistic is the average time customers spent waiting in the queue. Program 2. Other Examples （1） Multiteller Bank with Jockeying New arrivals: If theres an idle teller, choose leftmost (idle) teller If all teller

37、s are busy, choose shortest queue (ties leftmost) Initially empty and idle Termination: close doors at time 480 min. If all tellers are idle at that time, stop immediately If any tellers are busy, operate until all customers leave serviceInterarrival times:Expon (mean = 1 min.)Service times:Expon (m

38、ean = 4.5 min.) Jockeying (line-hopping) rules Suppose teller i (i fixed) finishes service e.g., i = 3 above Then either teller i becomes idle, or queue i becomes one shorter Maybe a customer at the end of some other queue j ( i) moves to teller i (if now idle) or the the end of the now-shorter queu

39、e i For each teller/queue k, let nk = number of customers facing (in queue + in service) teller k just after teller i finishes service Procedure: If nj ni + 1 for some j i, then a jockey will occur If nj ni + 1 for several values of j i, pick the closest j (min |j i|) If nj ni + 1 for two equally cl

40、osest (left and right) values of j i, pick the left (smaller) value of j Estimate Time-average total number of customers in (all) queues Average, max delay of customers in queue(s)34（2） JOB-SHOP MODELFive workstations Number of identical machines at each workstation as shown Network of multiserver q

41、ueuesThree types of jobs Interarrival times (all job types combined) expon (mean = 0.25 hour) Job type determined just after arrival Type 1, 2, 3 w.p. 0.3, 0.5, 0.2 Workstation routes for job types: Type 1: 3 1 2 5 (shown at left) Type 2: 4 1 3 Type 3: 2 5 1 4 3 Mean service times (2-Erlang distrib.

42、): Type 1: 0.50 0.60 0.85 0.50 Type 2: 1.10 0.80 0.75 Type 3: 1.20 0.25 0.70 0.90 1.035Initially empty and idleStop at time 365 8 hoursEstimate Average total delay in queues for each job type separately Overall average total delay in queues over all job types, weighted by their (known) probabilities

43、 of occurrence For each machine group separately: Average delay in queue there (all job types lumped together) Time-average number of jobs in queue (all job types together) Group utilization = Number of machines in the group36Time-average number of machines that are busyNumber of machines in the gro

44、up第第4节节 案例分析案例分析 经写实得某十字路口某方向车辆的到达时间间隔的经写实得某十字路口某方向车辆的到达时间间隔的219219个抽样数据，提出该总体的理论分布的假设。个抽样数据，提出该总体的理论分布的假设。370.14 0.07 0.01 0.02 0.77 0.51 0.11 0.05 0.79 0.05 0.11 0.51 0.37 0.84 0.22 0.01 0.06 0.88 0.53 0.23 0.38 0.12 0.88 0.12 0.07 0.01 0.27 0.56 0.86 0.38 0.53 0.24 0.12 0.38 0.54 0.09 0.01 0.07 0.01 0.13 0.25 0.93 0.41 0.52 0.39 0.54 0.07 0.07 0.13 0.40 0.25 0.