数学建模港口问题-排队论.doc

排队模型之港口系统

本文通过排队论和蒙特卡洛方法解决了生产系统的效率问题，通过对工具到达时间和服务时间的计算机拟合，将基本模型确定在排队模型，通过对此基本模型的分析和改进，在概率论相关理论的基础之上使用计算机模拟仿真（蒙特卡洛法）对生产系统的整个运行过程进行模拟，得出最后的结论。好 。
关键词：问题提出：
一个带有船只卸货设备的小港口，任何时间仅能为一艘船只卸货。船只进港是为了卸货，响铃两艘船到达的时间间隔在15分钟到145分钟变化。一艘船只卸货的时间有所卸货物的类型决定，在15分钟到90分钟之间变化。
那么，每艘船只在港口的平均时间和最长时间是多少？
若一艘船只的等待时间是从到达到开始卸货的时间，每艘船只的平均等待时间和最长等待时间是多少？
卸货设备空闲时间的百分比是多少？
船只排队最长的长度是多少？
问题分析：
排队论：排队论(Queuing Theory) ，是研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法，又称随机服务系统理论，为运筹学的一个分支。本题研究的是生产系统的效率问题，可以将磨损的工具认为顾客，将打磨机当做服务系统。【1】
：较为经典的一种排队论模式，按照前面的Kendall记号定义，前面的M代表顾客(工具)到达时间服从泊松分布，后面的M则表示服务时间服从负指数分布，1为仅有一个打磨机。
蒙特卡洛方法：蒙特卡洛法蒙特卡洛(Monte Carlo)方法，或称计算机随机模拟方法，是一种基于“随机数”的计算方法。这一方法源于美国在第一次世界大战进研制原子弹的“曼哈顿计划”。该计划的主持人之一、数学家冯·诺伊曼用驰名世界的赌城—摩纳哥的Monte Carlo—来命名这种方法，为它蒙上了一层神秘色彩。

（2）
排队论研究的基本问题
1.排队系统的统计推断:即判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行研究。
2.系统性态问题:即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙期分布等统计指标,包括了瞬态和稳态两种情形。
3.最优化问题：即包括最优设计(静态优化)，最优运营（动态优化）。【3】
为了得到一些合理的答案，利用计算器或可编程计算器来模拟港口的活动。
假定相邻两艘船到达的时间间隔和每艘船只卸货的时间区间分布，加入两艘船到达的时间间隔可以是15到145之间的任何数，且这个区间内的任何整数等可能的出现。再给出模拟这个系统的一般算法之间，考虑有5艘传至的假象情况。
对每艘船只有以下数据：

船1
船2
船3
船4
船5
相邻两艘船到达的时间间隔
20
30
15
120
25
卸货时间
55
45
60
75
80
因为船1在时钟于t=0分钟计时开始后20分钟到达，所以港口卸货设备在开始时空空闲了20分钟。船1立即开始卸货，卸货用时55分，其间，船2在时钟开始计时后t=20+30=50分中到达。在船1与t=20+55=75分钟卸货完毕之前，船2不能开始卸货，这意味着船2在卸货前必须等待75-50=25分钟。
在船2开始卸货之前，船2于t=50+15=65分钟到达，因为船2在t=75分钟开始卸货，并且卸货需45分钟，所以在船2与t=75+45=120分钟卸货完毕之前，船3不能开始卸货。这样，船3必须等待120分钟。
船4在t=65+120=185分钟之前没有到达，因此船3已经在t=120+60=180分钟卸货完毕，港口卸货设备空闲185-180=5分钟，并且，船4到达后立即卸货。
最后，在船4于t=185+75=260分钟卸货完毕之前，船5在t=185+25=210到达，于是船5在开始卸货前等待260-210=50分钟。

模型建立：
对于问题中存在的服务系统，建立排队论模型，在仅能为一艘船通过是一个标准的模型：
所谓模型，就是输入过程为泊松流时，服务时间为任意的条件之下的，服务机器只有一个得时候。对于模型，服务时间T的分布式一般的，（但是要求期望值和方差都存在），其他条件和标准的型相同。为了达到稳态还是必要的，其中有。图9-2单服务台单队系统
…
…
船只到达
进入队列
服务台
接受服务
船只离去

单服务员的排队模型设：
（1） 船只到来间隔时间服从参数为0.1的指数分布．
（2） 对船只的服务时间服从［４，１５］上的均匀分布．
（3） 排队按先到先服务规则，队长无限制．
系统的假设：
（1） 船只源是无穷的；
（2） 排队的长度没有限制；
（3） 到达系统的船只按先后顺序依次进入服务， 即“先到先服务”。
符号说明
w：总等待时间；ci：第i个顾客的到达时刻；bi：第i个顾客开始服务时刻；ei：第i个顾客服务结束时刻；xi：第i-1个顾客与第i个顾客之间到达的间隔时间；yi：对第i个顾客的服务时间
ci=ci-1+ xi
ei=bi+yi
bi=max(ci,ei-1)

模拟
框图
初始化：令i=1，ei-1=0，w=0
产生间隔时间随机数xi~参数为0.1的指数分布ci=xi , bi=xi
产生服务时间随机数yi~[4,15]的均匀分布
ei=bi+yi
累计等待时间：w=w+bi-ci
准备下一次服务：i=i+1
产生间隔时间随机数xi~参数为0.1的指数分布
ci=ci-1+ xi
确定开始服务时间：bi=max(ci,ei-1)
bi＞480
Y
N
i=i-1,t=w/i
输出结果：完成服务个数：m=i
平均等待时间：t
停止

模型检验：
表1 100艘船港口和系统的模拟结果
一艘船呆在港口的平均时间
97
79
78
81
85
99
一艘船呆在港口的最长时间
174
121
111
141
140
159
一艘船的平均等待时间
23
8
5
9
12
24
一艘船的最长等待时间
99
46
33
64
68
93
卸货设备空闲时间的百分比
0.067
0.079
0.093
0.07
0.069
0.028

上图为一艘船呆在港口的平均时间

上图为一艘船呆在港口的最长时间

一艘船的平均等待时间

上图为一艘船的最长等待时间

上图为一艘船的最长等待时间
以上就是对港口问题的具体分析，其实港口问题还可以从船只的排队角度出发，我们还可以对多个港口通行做相应的模拟试验，让船主尽量减少等待时间且港口卸货设备的利用率达到最高，从而是港口的主人获得更大的利润。从排队角度来解决问题，可以使问题的广度增加，选秘书问题就是一个很典型的例子，可以从排队角度解决，如果用我在文章中应用的方法来解决也是可以的，
这仅仅是一个港口的小问题，甚至可以说是一个非常简单的问题，但是已经让我感觉到了数学的美，在老师的引导下慢慢接近一种抽象的美，在写论文的这几天中，数据的整理和分析是最值得享受的时刻，在Excel里输入自己的数据，是一种忐忑的感觉，因为在那么多的数据面前，我真的不知道将会发生什么，拟合的过程就更是有意思了，一次一次的尝试，一次一次的比较，在这个过程中，如果有一点点的进步都会让我兴奋，数学建模在生活中处处存在，如果真的能够掌握这个本领，生活一定会变得简单而精彩！

参考文献：
（1）《运筹学》教材编写组编. 运筹学. 北京：清华大学出版社，2008
（2）Jerry Banks，John S.Carson，Barry L Nelson 等著. 离散事件系统仿真.北京：机械工业出版社，2007
(3) <<排队论模型与蒙特卡罗仿真>>
附录一
编程如下：
clear
cs=100;
for j=1:cs

w(j)=0;

i=1;
x(i)=exprnd(10);
c(i)=x(i);
b(i)=x(i);

while b(i)<=480
y(i)=unifrnd(4,15);
e(i)=b(i)+y(i);
w(j)=w(j)+b(i)-c(i);

i=i+1;
x(i)=exprnd(10);
c(i)=c(i-1)+x(i);
b(i)=max(c(i),e(i-1));
end

i=i-1;
t(j)=w(j)/i;
m(j)=i;
end

pt=0;
pm=0;
for j=1:cs
pt=pt+t(j);
pm=pm+m(j);
end
pt=pt/cs
pm=pm/cs
附录二
排队论中一个感兴趣的问题时，当输入过程是Possion流时，顾客相继到达的间隔时间T服从什么规律。
定理 设是具有参数的泊松过程，即是对应的时间间隔序列，则随机变量是独立同分布的，且服从均值为的负指数分布，即 。
证明 因为是Possion过程中第一个顾客到达的时间，所以时间等价于内没有顾客到达。故，进而可得

所以是服从均值为的负指数分布。
1、利用Possion过程的独立、平稳增量性质，得

即，故也是服从均值为的负指数分布。
2、 对于任意的和有

即 ，所以对任一，它都服从均值为的负指数分布。证毕。单纯的课本内容，并不能满足学生的需要，通过补充，达到内容的完善
教育之通病是教用脑的人不用手，不教用手的人用脑，所以一无所能。教育革命的对策是手脑联盟，结果是手与脑的力量都可以大到不可思议。

（注：专业文档是经验性极强的领域，无法思考和涵盖全面，素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注）