第一章 系统仿真与GPSS.doc

第一章 系统仿真与GPSS系统仿真是利用系统模型的试验方法来研究现有的或计划的或设计的系统的有效性、合理性或经济性的过程。仿真技术涉及到管理工程、系统工程、信息技术、控制理论、统计学、计算方法和计算机科学与技术等众多学科和领域的知识与应用，并随着这些学科领域的发展而不断发展和完善。1.1基本概念1. 系统与元素系统：系统是一个整体，由相互联系和相互依存的事物组成，它的范围由研究者根据所要解决问题的复杂性而定。元素：也称为实体，即组成系统的基本事物。在定义一个系统时，首先要确定系统的边界。 边界确定了系统的范围，边界以外对系统的作用称为系统的输入，系统对边界以外的环境的作用称为系统的输出。尽管系统千差万别，但人们总结出描述系统的三个要素，即实体、属性和活动。实体确定了系统的构成，属性描述每一实体的特征；活动表示了实体的行为以及它们之间的联系或作用。例如：一个理发馆可以定义为一个管理系统。构成理发馆系统的元素为理发师和顾客。理发师与顾客相互联系而又相互依存，组成一个统一的整体。理发师与顾客存在着服务与被服务的关系，同时理发师和顾客的存在不可或缺。现实中的系统千差万别，常见的分类方式有以下3种：1 .静态（static）和动态（dynamic）：静态系统与时间没有关系，但在动态系统中，时间却扮演着不可或缺的角色。在绪论中介绍的蒲丰投针问题就属于静态系统的仿真，而第2章和第3章描述的理发馆系统则属于动态系统。GPSS/JAVA就是为动态系统建立计算机模型的，因此，本书的主要研究动态模型。2 .连续（continuous）与离散（discrete）：在连续系统中，系统状态随时间连续变化，例如水库蓄水、放水以及出现降水和蒸发时水位的变化等。我国发射的“嫦娥1号”探月飞船在发射过程中和绕月飞行过程中的状态也是时刻变化的，它也属于连续系统。在离散模型中，系统的状态仅在离散的时间点上发生变化，例如在制造系统中，零件会在特定的时间到达和离开，机器会在特定的时间出现故障及被维修，工人也会在特定的时间开始休息。由于在管理系统在大多数情况下都属于离散系统，本书主要研究离散系统。3 .确定（deterministic）与随机（stochastic）：如果一个系统的输出完全取决于系统的输入，那么这个系统就是确定系统，也就是说，没有随机输入的模型为确定模型，严格预约时间与固定服务时间的运作过程即属此类。如果一个系统中包含随机因素，那么这个系统就是随机系统，例如在银行系统中，顾客的到达时间与服务时间都是随机变化的。在管理系统中，很多事情的发生都具有随机性，不确定性，往往以概率的形式出现。本书主要研究随机系统。2. 排队系统日常生活中存在大量有形和无形的排队或拥挤现象，如旅客购票排队，市内电话占线等现象。排队论起源于20世纪初的电话通话。19091920年丹麦数学家、电气工程师爱尔朗（A.K.Erlang）用概率论方法研究电话通话问题，从而开创了这门应用数学学科，并为这门学科建立许多基本原则。排队论(queueing theory), 或称随机服务系统理论, 是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。它是数学运筹学的分支学科。也是研究服务系统中排队现象随机规律的学科。广泛应用于计算机网络, 生产, 运输, 库存等各项资源共享的随机服务系统。 排队论研究的内容有3个方面：统计推断，根据资料建立模型；系统的性态，即和排队有关的数量指标的概率规律性；系统的优化问题。其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。何为排队系统 研究理发馆系统时，我们不考虑如下情况：（1）理发馆的设备与工具（2）理发师的个人行为（道德品质，技术高低）（3）顾客对发型的偏好等我们关注的是：（1）理发馆的服务能力（2）理发师的忙闲状况（3）顾客拥挤程度（等待理发排队的顾客有多少）我们的研究目的为：（1）分析系统运行状况（2）找出系统运行的瓶颈（3）改造系统结构 以此来提高系统运行效率从而产生更大经济效益。例如，分析理发排队系统：（1）如果增加理发师，则排队减少，获得服务的顾客会增多，理发馆收入会增加，但是理发师工资成本也会增加（2）如果减少理发师，则排队严重，获得服务的顾客会减少，理发馆收入会减少，但是理发师工资成本也会降低。由此产生了矛盾的两个方面：（1）增加服务能力，收入会增加但成本也会增加（2）减少服务能力，收入会减少但成本也会减少因此肯定会存在一个最优的服务能力，使理发馆获得的利润最大。排队的基本过程排队过程是接受服务的实体获得服务实体提供的服务的过程，是接受服务的实体的一系列活动按照一定的顺序组成，例如，一个最简单的排队过程由以下活动，按以下顺序组成顾客到达 排入队列 接受服务 顾客离开顾客到达：顾客到达服务机构的间隔时间具有一定规律（服从某种分布）排入队列：顾客到达后按照一定的规则排入队列等待接收服务接受服务：即服务机构向顾客提供服务，与服务密切相关的三个属性为：（1）为一个顾客服务所需要的时间，同样具有一定规律（服从某种分布），一般还应假设到达间隔时间序列与服务时间均为独立同分布随机变量序列，且这两个序列也相互独立。（2）服务机构所具有的服务能力，即同时能够服务的顾客数量（3）服务是否允许被抢占，抢占采取怎样的方式与规则随机排队系统若顾客到达间隔时间或服务时间中有一个为随机变量，则这个排队系统称为随机排队系统。例如以下为常见的随机排队系统：日常生活：（1）商店购物 （2）医院看病 （3）接通电话 （4）等候汽车生产管理：（1）铁路运输 （2）码头装卸 （3）修配系统 （4）生产线 库存 订货 销售3. 离散事件与离散系统状态变量 用若干系统属性变量来描述系统的当前状况，这些变量称为系统状态变量。例如，可以用当前队列长度、理发师当前忙闲率和理发馆当前顾客滞留总数等属性来描述理发馆系统任一时刻的状态。 动态系统与静态系统 如果某系统的状态随时间的变化而变化，则称此系统为动态系统；否则为静态系统。 例如，理发馆系统是一动态系统，描述理发馆状态的变量值如队列长度、理发师忙闲率和理发馆当前顾客滞留总数等是随时间的变化而变化的。事件 某些事情的发生能够引起系统状态的变化，这些事情称为事件或关键事件。例如，（1）顾客到达理发馆 （2）顾客理完发离开 为事件。因为，对于事件1的发生必然会引起或者队列长度、或者理发师忙闲状况的变化，以及顾客滞留总数的变化。对于事件2也会发生相同的情况。至于其他事件，如顾客加入队列和顾客开始理发等也可以称为事件，但不是关键事件，因为这些事件是由关键事件引发的，可称为普通事件。离散事件与连续事件 如果能够引起系统状态变化的事件只出现在系统运行过程的间隔时间点上，则这种事件称为离散事件；如果是连续发生则为连续事件。例如，顾客到达理发馆这一事件的发生时间是离散的而不是连续的。离散系统、连续系统和混合系统 当所有能够引起系统状态发生变化的事件都是离散事件时，则该系统就称为离散系统； 若所有这些事件都是连续的则该系统称为连续系统；若一系统发生的事件。部分为离散的而部分为连续的，则称为混合系统。实际问题中，大多数管理系统可以视为动态离散随机的排队系统。4. 系统模型与仿真模型 模型是对实际系统的一种抽象和本质的描述。首先，模型必须是对现实系统的一种抽象，它是在一定假设条件下对系统的简化。其次，模型必须包含系统中的主要因素。模型不可能与实际系统一一对应，而至少应当包含那些决定系统本质属性的重要因素。再者，为了进行定量分析，模型中必须反映出各主要因素之间的逻辑关系和数学关系，使模型对系统具有代表性。仿真模型同样必须符合以上各项要求，并且适合在仿真环境下，通过模仿系统的行为来求解问题。仿真 仿真是对系统模型进行实验的过程，是一种基于模型的活动。仿真的基本过程是：确立研究的目的后，先建立系统的模型，然后使用某种计算工具求解模型，最后对模拟的结果进行分析，以获得答案。仿真技术即是指以相似原理、系统理论与方法、信息技术以及仿真应用领域的有关专业知识为基础，以计算机系统或与应用有关的物理效应设备及仿真器为工具，利用模型对系统（己有的或设想的）进行研究的一门多学科的综合性的技术。在对系统进行分析、设计和预测的过程中，一方面要运用理论知识对系统进行分析，另一方面还要对系统进行实验研究。由于很多系统的结构非常复杂，又包含大量随机因素，采用解析方法建立数学模型将会遇到很多困难，现实中多采用实验研究的方法。但是其中又有很多系统，由于各种原因，比如：危险性大，或者不经济，或者周期太长，或者不可能建立实物的模型进行实验。在这种情况下，系统仿真技术便成为首选的工具。系统仿真是以多种学科理论为基础，以计算机及相应的仿真软件为工具进行实验研究的理论和方法论体系。它体现了实验思考的方法，用以探索复杂系统深层次的运动机理和规律性，具有科学的先验性。综上所述，“系统、模型、仿真”三者之间有着密切的关系。系统是研究的对象，模型是系统的抽象，仿真是通过对模型的实验以达到研究系统的目的。1.2 离散随机排队系统的模拟方法蒙特卡洛(Monte Carlo)方法，或称计算机随机模拟方法，是一种基于“随机数”的计算方法。这一方法源于美国在第一次世界大战进研制原子弹的“曼哈顿计划”。该计划的主持人之一、数学家冯诺伊曼用驰名世界的赌城摩纳哥的Monte Carlo来命名这种方法，为它蒙上了一层神秘色彩。蒙特卡洛法（Monto Corlo）由著名数学家和物理学家冯纽曼提出，以法国和意大利交界的著名赌城蒙特卡洛命名。蒙特卡洛法是基于概率论的随机抽样的计算方法，可以解决如下两类的静态或动态问题。Monte Carlo方法的基本思想很早以前就被人们所发现和利用。早在17世纪，人们就知道用事件发生的“频率”来决定事件的“概率”。19世纪人们用投针试验的方法来决定圆周率。问题：某人每轮向靶子射10箭，已知其击中靶心的概率为25，问一轮中射中7箭的概率为多少？1. 产生均匀分布随机数 0.000.99（100个），某个数字出现的概率相等。若产生1000个这样的数，则（1）数值为0.000.24大约会有250个，比例大约为0.25（2）数值为0.250.99大约会有750个，比例大约为0.752. 以每产生一个随机数代表射一箭，若产生的随机数小于0.25，则代表击中靶心，如果产生的随机数大于或等于0.25，则表示没有击中靶心。若实验的次数很多（远大于1000），则.击中靶心的频率接近于25。若实验的次数无限多，则.击中靶心的概率等于25。3. 确定一轮中击中7箭的概率（1）每轮由计算机产生10个均匀分布的随机数Ni（i=1，2，3， 10），代表射10箭（2）其中若Ni小于0.25为击中，记下该轮中击中的次数（3）重复（1）（2），进行K轮实验（4）找出K轮中所有每轮击中7次的总轮数M，则K轮中每轮击中7箭的频率为M / K，若K趋向无穷大时，M / K为每轮击中7箭的概率。问题二：有一银行营业点打算添置一台自动存取款机（12小时服务），顾客按一定的间隔时间到来，排队接受服务，先来先用，后来后用，顾客不愿在队列中等待太久，否则会离去。管理人员想了解顾客等待时间超过3分钟的人数占顾客总数的比例为多少，若比例太大，则考虑再增设一台机器。1. 模拟过程顾客到达排队使用存取款机顾客离开2. 调查数据观察100位顾客到达间隔时间和使用机器的持续时间，得到如下统计数据：（1） 顾客到达间隔时间分布 表1.2-1 顾客到达间隔时间统计表间隔（分）人数频率累积频率随机数对应范围1180.180.180.000.172170.170.350.180.343150.150.500.350.494120.120.620.500.615100.100.720.620.71690.090.810.720.80780.080.890.810.88850.050.940.890.93920.020.960.940.951010.010.970.961110.010.980.971210.010.990.981310.011.000.99总计1001.00（2） 顾客使用机时间分布 表1.2-2 顾客用机时间统计表用机时间人数频率累积频率随机数对应范围1480.480.480.000.472200.200.680.480.673160.160.840.680.834120.120.960.840.95520.020.980.960.97620.021.000.980.99总计1001.003. 产生均匀分布的二组随机数产生01（0.00-0.99）间隔两组均匀分布的随机数。 一组用于模拟顾客到达间隔时间，另一组模拟顾客用机时间。由第一组产生的一个随机数代表当前到达存取款机的一位顾客，若此随机数的值为0.70，通过表1.2-1，可以确定所模拟的该顾客到达的时间与前一位顾客到达时的间隔时间为5分钟。由第二组产生的一个随机数代表正在使用存取款机的一位顾客，若此随机数的值为0.90，通过表1.2-2，可以确定所模拟的该顾客使用存取款机的时间为4分钟。4. 手工模拟步骤与结果（假设模拟开始时间为0） 表1.2-3 手工模拟步骤表顾客编号到达间隔随机数间隔时间用机时间随机数用机时间到达时间开始使用时间离开时间等待时间10.5740.502446020.0310.8945610130.9590.311141415040.3830.8031717200用手工方法模拟10位顾客，模拟开始时间设为0. 手工模拟的过程如表1.2-3所示。后6位顾客的模拟留给读者作为练习来完成。如果排队等待时间大于或等于3分钟的人数为W，模拟的总人数为T， 当T足够大时，W/T即可作为结果。 Monte Carlo方法的基本思想很早以前就被人们所发现和利用。早在17世纪，人们就知道用事件发生的“频率”来决定事件的“概率”。19世纪人们用投针试验的方法来决定圆周率。本世纪40年代电子计算机的出现，特别是近年来高速电子计算机的出现，使得用数学方法在计算机上大量、快速地模拟这样的试验成为可能。基于蒙特卡洛法来安排某一离散随机排队系统问题的求解算法就是求解该问题的仿真模型，按照算法进行的一次求解过程就是模型的一次实验过程。与确定性的问题不同，每一步由仿真模型计算结果所获得的模型的状态并不反映或对应实际系统在那一次或那一时刻的真实状态。比如，产生的第14个01间隔的均匀分布的随机数代表向靶子射的第14箭，该箭是否真的射中靶心是不可能根据本次随机数值是否小于0.25来作出判断的。但是当我们不断地实验下去，随着实验次数的增大，会发现一轮射中7箭的比例数的变化越来越小，而趋向一个常数。因此模型的每一个瞬时状态并不一定反映真实系统的实际状态，但是模型在经过大量实验，即模拟较长一段时间后，所获得的模型的统计特性，却可以反映实际系统的整体特性。对于射箭问题，我们对一轮射中7箭的可能性的大小作出了数量性的确定，但是可能性本身就意味着不确定性。而这可能性大小的数量值是一个统计值，即大量观察而获得的期望值。1.3 GPSS1. 专用仿真系统解决以上两个问题的模型可以采用任何计算机高级语言编写其程序，予以运行并获得计算结果。但是存在如下问题：（1）各个问题采取的算法不同，全凭技巧，缺少一个统一的标准算法， （2）大量工作花费在算法实现的编程细节上（3）难以利用他人或过去的工作 因此对某一类型的问题能否做到：采取更加抽象的（接近于实际的）和标准化的模型逻辑构造方法，对这种用标准的逻辑构造方法建立的具有不同逻辑结构的模型，采取统一的或标准的算法来实现。答案是：研究工作者对许多类型的问题完成了这种工作。于是建立解决某一具体问题的模型的工作和实现这一模型的算法得以分离。这样，模型和算法不再统一，模型成为算法的抽象，以更加接近实际业务和流程的面目出现。建模者有章可循，只要掌握了建模的标准方法和熟悉问题的业务流程，就可以建立解决问题的模型。于是对应不同问题的模型实际是由不同的标准逻辑构件（即模型元素或仿真构件）的排列和组合而成。这种模型不是一步一步的算法操作，而是构成问题的实际系统的映射。因此建模者的工作就集中在：根据问题，选择标准逻辑件，然后按照一定的顺序排列它们。模型建立后，建摸着只要将其提交给实现了标准算法的计算程序就可以运行求解，获得最终的模型特征的统计结果。正是基于这样的思考与研究，专用仿真系统产生和发展起来。专用仿真系统解放了建摸者，使他们专注于解决问题而面向建模和实验。因此专用仿真系统的本质工作就是提供一个标准的基于某种建模方法的模型逻辑构件库，和实现这一建模方法的一个通用的标准算法。专用仿真系统为仿真建模者提供了基于某种建模方法的支持平台。它将仿真的输入、输出以及支持该方法的核心算法等，这些所有模型运行时所需要的公共支持部分封装起来，作为支持平台的底层；而其顶层则是向建模者所提供的建模公共接口。这些接口对于不同的系统可能采取不同的形式，如或为组件或为函数或为方法或为模块等。用户使用这些高度功能（仿真功能）化的接口为所研究的实际系统构造模型，然后提交给这个仿真支持平台或通过编译或通过解释的方式来运行。对于采取编译方式的系统，通常提供了仿真函数库或类库，封装了所有接口和公共支持部分，通过编译程序与用户建立的模型文件链接而形成可执行的模型程序。现代的仿真系统通常向用户提供一个集成开发环境，将模型的编辑、编译、调试、运行、结果输出与分析以及建模方法学习等有效组织和集成在一个环境之中，以方便用户的使用。专用仿真系统是对专用仿真语言的发展。某种仿真语言实际上是指某种仿真系统向用户提供的建模接口的用法和语法的描述部分。专用仿真语言和专用仿真系统的出现和使用，大大减轻了仿真建模者的工作，使他们将注意力能够集中在解决问题的建模、实验与结果的验证与分析的业务层面，而不需要在仿真算法与运行机制等方面的实现花费精力与时间。从某种意义上来说，专用仿真语言的作用类似于高级语言，专用仿真系统的作用类似于操作系统。专用仿真语言和专用仿真系统的出现和使用极大促进了仿真技术的普及与应用。2. GPSS从上世纪60年代开始，计算机和运筹学工作者创造性地研制了多种模拟语言，其中GPSS以简洁易用和灵活通用等特点，成为非常受欢迎的离散系统仿真语言。GPSS 是英文 General Purpose Simulation System 的缩写，即通用仿真系统。它是由美国IBM的Geoffery Gordon博士研究和开发的。1961年，Gordon以“通用模拟程序”为题在EJCC（Eastern Joiut Computer Conference 美国东部联合计算机会议）会议论文集上发表了第一篇有关GPSS的论文，该文于1962年刊登于IBM系统杂志第一卷第一期。这个首次发表的GPSS常被人称作“戈登仿真器”，是在IBM的704、709和7090计算机上实现的。其后，在1964年和1965年又相继推出了GPSS的第二和第三个版本GPSS与GPSS；1967年，开发出的GPSS/360（运行于IBM360计算机）被正式更名为通用仿真系统（General Purpose Simulation System）。在将近半个世纪中，GPSS不断得到发展与完善。八十年代初出现了运行于个人计算机的版本GPSS/H和GPSS/PC，分别由美国的Wolverine和Minuteman等软件公司开发和提供技术支持。之后，九十年代Wolverine公司推出基于Windows的具有图形界面的GPSS的集成开发环境 GPSSWorld。GPSS适用于离散系统仿真，对模型文本采取解释方式执行，建模采用面向过程，即面向业务流程的方法。这种建模方法很贴近于现实管理系统的各种实际业务流程。模型中的仿真元素（模块）与元素之间的联系（路径）与实际系统的元素及相互作用关系有很直观的映射，因此模型直观而易于理解。 同时，由于其语言的简洁性和语言规模的适度性，非常易于学习和掌握。GPSS是为那些并不是计算机程序设计专家的管理人员设计的一门用于管理系统建模的语言。它利用程序模块图来描述系统，程序模块图可以看作是仿真模型的图形化表示。