离散模拟经典题目分析 85

离散模拟经典题目分析离散模拟经典题目分析 假设某银行有 3 个窗口对外接待客户 从早晨银行开门起就不断有客户进入银行 由于每 个窗口在每个时刻只能接待一位客户 因此在客户比较多的时候需要排队 对于刚进入银 行的客户 如果某个窗口的业务员正空闲 则可上前办理业务 反之 若 3 个窗口前均有 客户 他便会排在人数最少的队伍后面 下面的程序模拟客户在银行的这种活动并计算一 天中客户在银行平均逗留时间 为了计算所有客户在银行的平均逗留时间 需要掌握每个客户到达银行和离开银行的时 间 后者减去前者即为每个客户在银行的逗留时间 用当天的客户数去除以所有客户的逗 留时间之和便是所求的平均逗留时间 称客户到达银行和离开银行这两个时刻发生的事情 为 事件 则整个模拟程序将按照事件发生的先后循序进行处理 程序中要处理的事件有两类 一类是客户到达事件 另一类是客户离开事件 前一类事 件发生的时刻随客户到来自然形成 后一类事件发生的时刻则由客户办理事务所需时间和 等待事件而定 由于程序按事件发生时刻的先后循序进行处理 则事件表应该是有序表 其主要操作是插入和删除事件 模拟程序中需要的另一种数据结构是表示客户排队的队列 由于前面假设银行有 3 个窗 口 因此程序需要 3 个队列 队列中存储有关客户的主要信息 客户到达的时刻和客户办 理事务所需要的时间 每个队列的队头客户即为正在办理业务的客户 他办完业务离开队 列就是即将发生的客户离开事件的时刻 也就是说 每个队头客户都存在一个将要驱动客 户离开事件 因此 在任何时刻即将发生的事件只有下列 4 种可能 一是新的客户到达 二是 1 号窗口客户离开 三是 2 号窗口客户离开 四是 3 号窗口客户离开 所以在该模拟 程序中只需要两种数据类型 有序链表和队列 客户到达事件的处理 在实际的银行中 客户到达的时刻及办理事务所需事件都是随机 的 因此在模拟程序中用随机数来代替 不失一般性 假设第一个客户进门的时刻是 0 即为模拟程序处理的第一个事件 之后每个客户到达时刻在前一个客户到达时设定 因此 在客户到达事件发生时需要产生两个随机数 其一为该时刻到达的客户办理业务所需要的 时间 durtime 其二为下一个客户将要到达的时间间隔 interval 假设当前事件案的发生时 间是 occurTime 则下一个客户到达事件发生的时刻为 occurTime interval 由此应产生一 个新客户到达事件插入事件表 刚到达的客户则应插入到当前所包含元素最少的队列中 若该队列在插入前为空 则还应产生一个客户离开事件插入事件表 客户离开事件处理 首先计算要离开客户在银行逗留的时间 然后从队列中删除该客户 同时查看队列是否为空 若不为空则设定一个新的客户离开事件 程序实现 include include define CLOSETIME 1000 银行终止营业时间 define M 3 服务窗口数 队列节点 typedef struct QueueNode int arrivetime 客户到达时间 int duration 客户办理业务所需的时间 struct QueueNode next QueueNode 窗口客户队列 typedef struct QueueHeader QueueNode front rear 队列的头 尾指针 int length 队列的长度 QueueHeader 事件链表节点 typedef struct EventNode int occurTime eventType 事件发生时间 occurTime 事件类型 eventType 后面的程序中 eventType 0 时表示到达事件 struct EventNode next eventType i 表示第 i 号窗口的离开事件 EventNode 事件链表 typedef struct EventList EventNode front rear int eventNum EventList QueueHeader q M 1 M 为窗口的数量 这里定义了 4 个窗口 实际用到的是 q 1 q 2 q 3 EventList eventlst 事件队列 int seed 300 随机数种子 产生一个事件节点 int generate EventNode p p EventNode malloc sizeof EventNode if p printf allocation error return 1 return 0 下一个客户的到达事件加入事件链表 void InsertEvent EventList eventlst int occurTime int etype EventNode p q qre p EventNode malloc sizeof EventNode p occurTime occurTime p eventType etype eventlst eventNum q eventlst front qre NULL while q q q next if qre 插入事件的发生时间小于队列中任何一个事件的发生时间 p next eventlst front eventlst front p else 找到一个位置插入 事件链表中的节点是按照节点的到达时间有序排 列的 p next q qre next p if eventlst eventNum 1 eventlst rear p 删除事件链表中的第一个事件节点并返回该事件对应的数据 void DeleteEvent EventList eventlst EventNode event EventNode p p eventlst front eventlst front p next if eventlst eventNumrear eventlst front event p 当前客户加入服务窗口 void EnQueue QueueHeader swindow int t1 int t2 QueueNode p p QueueNode malloc sizeof QueueNode p arrivetime t1 p duration t2 swindow length if swindow length 1 p next NULL swindow front p swindow rear p else swindow rear next p swindow rear p 删除指定窗口的排头客户 void DeQueue QueueHeader swindow QueueNode f QueueNode p if swindow length 0 f arrivetime swindow front arrivetime f duration swindow front duration p swindow front swindow front swindow front next swindow length if swindow length 0 swindow rear NULL free p 产生两个随机数 void random int durtime int intevatime durtime rand 1 intevatime rand 1 随机数发生函数 int rand int k int double seed 32767 10000 29 seed 13107 seed 6553 32767 return k 取当前人数最少的窗口号码 int Minlength int minx k i minx q 1 length k 1 for i 2 i M 1 i if q i lengthoccurTime 0 设定第一个客户到达事件 pe eventType 0 pe next NULL eventlst front pe 第一个客户到达事件插入事件表 eventlst rear pe eventlst eventNum 1 for i 1 ieventNum 0 事件表不空 DeleteEvent eventlst 去事件按表中的第一个事件节点 if event eventType 0 处理客户到达事件 printf A client entered count 累计客户数 random 产生当前客户所需的服务时间和下一个客户 到达的时间间隔 if event occurTime inteval occurTime inteval 0 下一个客户到达事件加入事件表 c Minlength 取当前人数最少的窗口号码 EnQueue 当前客户加入到 c 窗口 printf Insert to window d c printf arrive time d duration d n event occurTime durtime if q c length 1 当前客户为其所在队列的唯一客户 则其离开事件 可确定 InsertEvent eventlst event occurTime durtime c else 处理客户离开事件 i event eventType i 号窗口的客户要离开 DeQueue 删除 i 号窗口的排头客户 printf service window d A client left n i totaltime event