运筹学与系统工程上机实验指导书实验五

运筹学与系统工程上机实验指导书实验五

ID:35244283

大小:219.32 KB

页数:9页

时间:2019-03-22

运筹学与系统工程上机实验指导书实验五_第1页
运筹学与系统工程上机实验指导书实验五_第2页
运筹学与系统工程上机实验指导书实验五_第3页
运筹学与系统工程上机实验指导书实验五_第4页
运筹学与系统工程上机实验指导书实验五_第5页
资源描述:

《运筹学与系统工程上机实验指导书实验五》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、运筹学与系统工程上机实验指导书机电学院工业工程专业2013-2014(1)学期上机实验五:应用Lingo求解动态规划和排队论问题一、实验目的在熟练编写和运行Lingo程序的基础上,应用Lingo进行求解动态规划和排队论等深层次优化问题的练习。二、实验要求1、根据本指导书学习Lingo对典型动态规划问题进行建模和求解。2、根据本指导书学习排队论相关函数的具体使用方法,对典型的随机服务系统问题进行建模和求解。3、独立完成相关应用题目的分析、建模和应用Lingo软件的求解过程。三、相关知识1、动态规划问题模型及典型

2、应用动态规划(DynamicProgramming)是将一个大型、复杂的问题转换为若干阶段的子问题,从而将动态的多阶段问题简化为静态的单阶段决策问题,一般需要采用递归算法进行求解。动态规划问题的一般模型为:动态规划的典型应用包括:最短路径问题、动态生产计划问题、资源配置问题、背包问题、旅行商问题、随机性采购问题、设备更新问题等。按照决策变量取值的不同,也可以分为连接型动态规划和离散型动态规划问题。无论是连续问题还是离散问题,动态规划解决问题的前提条件是:可将问题划分为k个阶段(k=1,2,…,n),并能构建多

3、阶段模型(最优指标函数Vk,n,状态Sk、决策uk、状态转移方程Tk)。2、随机服务系统相关Lingo函数随机服务系统由输入过程(反映顾客总体的特征)、排队规则(反映队伍特征)及服务机构(反映服务台的特征)所组成,对随机服务系统的描述如图1所示,可用符号M/M/1表示泊松输入、负指数服务、一个服务台组成的随机服务系统。图1随机服务系统的描述描述排队系统的主要数量指标有:队长L=正在服务的顾客数Ls+等待队长Lq,顾客的平均停留时间W=顾客的平均等待时间Wq+平均服务时间Ws。单位时间内顾客到达率λ、单位时间的

4、服务率µ。它们之间关系的主要公式为:(1)(2)(1)等待制排队模型1)Lingo函数@PEB(ρ,S):返回到达负荷为ρ,服务系统有S个服务台,且允许排队时系统繁忙的概率,也就是顾客等待的概率Pwait;2)等待制排队模型相关参数计算①顾客等待的概率PwaitPwait=@PEB(ρ,S),其中系统到达负荷ρ=λ/μ,②顾客平均等待时间(Wq):③顾客平均停留时间(W),队长(L)和排队长(Lq):(2)损失制排队模型1)Lingo函数@PEL(ρ,S)返回到达负荷为ρ,服务系统有S个服务器,且不允许排队时

5、的损失概率,也就是顾客得不到服务离开的概率Plost;2)损失制排队模型相关参数计算①顾客离开的概率PlostPlost=@PEL(ρ,S),其中系统到达负荷ρ=λ/μ,②单位时间内平均进入系统的顾客数λe,即系统的有效到达率:λe=λ(1-Plost)③系统的相对通过能力:Q=1-Plost④系统在单位时间内占用服务台的均值L=λe/μ。⑤系统服务台的效率η=L/S⑥顾客在系统内平均停留时间W=1/μ。(3)有限源排队模型1)Lingo函数@PFS(ρ,S,K)返回当到达负荷为ρ,顾客数为K,服务台数量为S

6、时,有限源的泊松服务系统等待或返修顾客数的期望值。2)有限源排队模型基本参数①平均队长L=@PFS(Kρ,S,K),其中系统到达负荷ρ=λ/μ。②单位时间平均进入系统的顾客数λe=λ(K-L)③顾客处于正常情况的概率P=K-L/K④每个服务台的工作强度Pwork=λe/Sμ一、动态规划模型与求解1、最短路径问题(1)问题描述:假设有如下的城市网络图,每两点之间的距离已知(已将距离值标在线上),求从第任意一个城市到第10个城市的最短距离。图2城市网络(2)模型阶段变量:k=1,2,…,10状态变量:Sk表示第k

7、阶段到第k+1阶段的距离决策变量:uk(Sk)=D(X,Y)状态转移方程:Sk+1=T(Sk,uk)指标函数:Fk(Sk)(3)求解过程:(4)Lingo程序model:SETS:CITIES/1..10/:F;!城市集合CITIES,属性F;ROADS(CITIES,CITIES)/!路线集合ROADS,属性D;1,21,31,42,52,62,73,53,63,74,54,65,85,96,86,97,87,98,109,10/:D;!D(i,j)从第i个城市到第j个城市的距离;ENDSETSDATA:!

8、由于并非所有城市间都有道路直接连接,所以将道路具体列出;D=15213121161041214396581052;ENDDATA!如果本身就在第10个城市,则最短距离就是0;F(@SIZE(CITIES))=0;!从任意城市(除了第10个城市)到第10个城市的距离;@FOR(CITIES(i)

9、i#LT#@SIZE(CITIES):F(i)=@MIN(ROADS(i,j):D(i,j)+F(j)))

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。