chap6 排队论.ppt

例最短路问题此问题的基本方程为 f k(s k)=Min{d k(u k)+f k+1(s k+1)} uk ∈Dk (sk )k=6,5,4,3,2,1 f 7(s 7)=0 当 k=6 时 s 6 u 6 D(u 6 )+f 7 (s 7)F 6 (s 6) F 1F 1G 4+0=4* 4 F 2F 2G 3+0=3* 3 k=1 k=2 k=3 k=4 k=5 k=6 按基本方程由后向前继续递推有: 当 k=5 时当 k=4 时 s 4u 4 d(u 4 )+f 5 (s 5)f 4 (s 4) D 1D 1E 1D 1E 2 2+7=9 2+5=7* 7 D 2D 2E 2D 2E 3 1+5=6* 2+9=11 6 D 3D 3E 2D 3E 3 3+5=8* 3+9=12 8 s 5u 5 d(u 5 )+f 6 (s 6)f 5 (s 5) E 1E 1F 1E 1F 2 3+4=7 * 5+3=8 7 E 2E 2F 1E 2F 2 5+4=9 2+3=5* 5 E 3E 3F 1E 3F 2 6+4=10 6+3=9* 9当 k=3 时 s 3u 3 d(u 3 )+f 4 (s 4)f 3 (s 3) C 1C 1D 1C 1D 2 6+7=13* 8+6=14 13 C 2C 2D 1C 2D 2 3+7=10* 5+6=11 10 C 3C 3D 2C 3D 3 3+6=9* 3+8=11 9 C 4C 4D 2C 4D 3 8+6=14 4+8=12* 12当 k=2 时当 k=1 时 s 2u 2 d(u 2 )+f 3 (s 3)f 2 (s 2) B 1B 1C 1B 1C 2B 1C 3 1+13=14 3+10=13* 6+9=15 13 B 2B 2C 2B 2C 3B 2C 4 8+9=17 7+9=16* 6+12=18 16 s 1u 1 d(u 1 )+f 2 (s 2)f 1 (s 1) A AB 1 AB 2 5+13=18 * 3+16=19 18 由此可以看出, A到G 的最短路长为 18,路径为: A→B 1→C 2→D 1→E 2→F 2→G 复习第五章图与网络分析问题的提法问题的提法——寻求网络中两点间的最短路就是寻求连接这两个点的边的总权数为最小的通路。求解思路求解思路( (D D 氏标号法( 氏标号法( Dijkstra Dijkstra ) )) ) ——从始点出发,逐步顺序地向外探寻,每向外延伸一步都要求是最短的。最短的。应用背景应用背景——管道铺设、线路安排、厂区布局、设备更新等。---- 图与网络的基本概念---- 最短路问题注意:求解最短路问题中应用动态规划方法和 D D氏标号法氏标号法的区别第六章排队论第一节排队系统模型学习重点:排队模型的表示方法学习难点:排队系统的常见分布第三节单服务台的 M/M/1 系统第四节多服务台的 M/M/C 系统第五节排队论在汽车服务系统中的应用第二节排队系统的常见分布排队论概述?系统的输入与输出是随机变量?排队特征:有形、无形;人排队、物排队?在汽车服务系统中,排队现象普遍存在。例如:修理、加油、保险?排队论也称随机服务系统理论?服务系统存在来自两个矛盾方面的要求: --顾客希望服务质量好,如排队等待时间短,损失率低--系统运营方希望设备利用率高? 于 1909~1920 年发表了一系列根据话务量计算电话机键配置的方法,为随机服务理论奠定了基础,又称为排队论( Queuing Theory )或拥塞理论( Congestion Theory )排队论概述?排队论研究的内容: : 研究各种排队系统的概率规律性,主要研究队长分布、等待时间分布和忙期分布,包括瞬态和稳态。 : 静态最优、动态最优 : 判断系统符合于哪种模型, 再根据排队理论进行分析研究?排队论的应用: 最先应用于电话行业,目前已广泛应用在交通、运输等公用事业系统和其他领域。?排队论研究的内容和目的——提出排队论关心的问题和需要计算的一些量?研究目的: 通过对排队系统中概率规律的研究,使系统达到最优设计和最优控制,以最小费用实现系统的最大效益。第一节排队系统模型?一、服务过程的一般表示排队系统的特征: ①有请求服务的人或物; 顾客、车②有为顾客服务的人或物; 服务员、服务台③顾客到达时间与接受服务时间是随机的。顾客到达排队服务机构服务顾客离去图 6-1 排队过程一般模型第一节排队系统模型?二、服务系统分类 (服务台满时顾客立即离去) (先到先服务,后到先服务,