数学建模——排队问题ppt课件

快速通行系统排队问题，谢耀03/03/2004谢耀电子工程与信息科学系.尤其是在我们这样一个人口众多的国家，电话亭1978年，北京15%的电话需要一个小时才能接通。电报大楼的打电话人会带午餐去排队的银行窗口、自动取款机医院、理发店、火车售票.游乐园里的娱乐项目。迪士尼乐园的快速通行系统就是为了解决这个问题。工作原理：到达的顾客将他们的票插入快速通行证的槽中，快速通行证计算顾客返回的建议时间间隔或时间点或时间窗口。顾客不需要排队，但在指定时间返回时可以带票进入。4.如何缩短排队等候时间？银行的排队机器只是有序地组织顾客，并没有减少等待时间。知道你需要等多久来选择合适的时间不是很好吗？,5,FastPass:的问题预测返回间隔有一个错误建议的返回间隔太长，无法按时返回，但仍需要排队如果我告诉你4小时后再来，你会怎样？客户可能无法在预定时间返回。如果新客户不想使用快速通行证？现有的快速通行证真的有那么好吗？我们的目标是为快速通道系统建立一个合理的分布式统计模型，以找出最佳的客户返回时间。建模的一般步骤和：*模型改进*灵感和待解决的问题，7，1模型假设，游乐园开放时间为83:00-18:0，一天中不同时间的顾客流量不同，如上午10:0和下午3:0是最大的。客户的到达时间符合非时间非齐次过程。到达率是，8，泊松过程，9，泊松过程，10。分析1:能否获得准确的返回时间？在我们开始建模之前，我们需要问几个问题：11，分析2:使用快速通道后排队是不可避免的吗？快速通道给出的返回时间只是期望值，而不是确定值。假设所有客户都使用快速通道，但是应该考虑到一些客户可能不遵守快速通道给出的返回时间。2在开始建模之前，我们应该首先问几个问题：12，分析3:我们优化的目标函数(或成本函数)是什么？现在是排队时间吗？在我们开始建模之前，我们需要问几个问题：13，优化问题的目标函数是：3模型建立(1)-目标函数，14，3模型建立(1)-目标函数，15，根据排队理论的分类规则，(X/Y/Z/A)代表一种排队规则，其中，客户流量是按照分布的：客户服务时间是按照分布的aZ:服务台数量a3360服务台数量的客户(系统容量)对于每个游乐项目的特点，我们主要讨论两个排队系统：模型建立(2)-排队模型的分类，16，特点：系统容量为1，客户的到达是泊松流，服务时间服从指数分布，并且只有一个队列。 模型建立(3)-展位模型，17，泊松排队模型在加入快速通关系统后，模型建立(3)-展位模型，18，得到该系统的成本函数表达式，模型建立(3)-展位模型，19，总的优化目标函数近似等于顾客的目标函数I:模型建立(3)-电话亭模型，20，模型建立(3)-电话亭模型，21，如果简化的C1和C2是常数并且计算了第二人的期望值而不等待返回时间，则MatLab可以作出的函数是模型(4)的解-电话亭模型，22，模型(4)的解-电话亭模型，23，不用等待返回时间的第三人的期望值可以用同样的方法计算，而模型(4)的解-电话亭模型，但是第四人和第五人呢？这个方法太复杂了，无法使用。有近似算法吗？24和之前模型的区别在于系统容量是c1，服务时间是固定的，客户的到达仍然是泊松流。服务系统的数量是1，模型建立(5)-过山车模型，25，还考虑：实际的快速通道系统有两个队列：快速通道和备用队列不考虑备用队列，希腊算法模型将获得考虑备用队列，效用函数模型将获得，模型建立(5)-过山车，26，最简单的情况是只有一个队列，即所有人只使用快速通道系统。为了防止前排乘客等待时间过长，过山车只有在载满一定数量的乘客时才会启动，假设乘客人数为80%。使用希腊算法，将每位乘客尽可能安排在最接近乘客到达时间且尚未满员的公交车上。假设预定的客户在预定的时间段内按照贝塔分布到达，模型建立(5)-过山车模型，27，贪婪算法，模型建立(5)-过山车模型，28，很容易想到全局优化的目标变量1。如果驾驶时间不固定，最佳a%是多少？也就是说，顾客想开多少座位就开多少座位。2.如果驾驶间隔是固定的，最好是多长时间？衡量标准：目标函数，模型建立(5)-过山车模型，29，区间顾客返回示意图，30，目标函数，模型建立(5)-过山车模型，31，模型建立(5)-过山车模型，如何求解最优a%c和最优行驶区间？对于这样复杂的问题，离散模拟是最好的方法，32。模拟：用计算机生成一些符合一定分布的随机数据点，模拟离散时间的发生。这里的仿真是用MatLab6.5完成的：步骤1。生成泊松客户流(模拟到达时间)2。给定不同的a%c，启动时间间隔是可变的，计算成本函数，并绘制成本函数性能曲线3。启动时间是固定的。给出不同的启动时间间隔，计算并绘制成本函数性能曲线。4.得出最佳结论。模拟过山车模型(5)-过山车模型，33，模拟过山车模型(5.1)-获取，在固定时间收集样本I在第j天，I=1.m，j=1.100来形成样本空间矩阵，3