资源描述：
《运筹学与系统工程上机实验指导书_实验五》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、运筹学与系统工程上机实验指导书机电学院工业工程专业2013-2014（1）学期上机实验五：应用Lingo求解动态规划和排队论问题一、实验目的在熟练编写和运行Lingo程序的基础上，应用Lingo进行求解动态规划和排队论等深层次优化问题的练习。二、实验要求1、根据本指导书学习Lingo对典型动态规划问题进行建模和求解。2、根据本指导书学习排队论相关函数的具体使用方法，对典型的随机服务系统问题进行建模和求解。3、独立完成相关应用题目的分析、建模和应用Lingo软件的求解过程。三、相关知识1、动态规划问题模型及典型应用动态规划（Dyna
2、micProgramming）是将一个大型、复杂的问题转换为若干阶段的子问题，从而将动态的多阶段问题简化为静态的单阶段决策问题，一般需要采用递归算法进行求解。动态规划问题的一般模型为：动态规划的典型应用包括：最短路径问题、动态生产计划问题、资源配置问题、背包问题、旅行商问题、随机性采购问题、设备更新问题等。按照决策变量取值的不同，也可以分为连接型动态规划和离散型动态规划问题。无论是连续问题还是离散问题，动态规划解决问题的前提条件是：可将问题划分为k个阶段（k=1,2,…,n），并能构建多阶段模型（最优指标函数Vk,n，状态Sk、决
3、策uk、状态转移方程Tk）。2、随机服务系统相关Lingo函数随机服务系统由输入过程（反映顾客总体的特征）、排队规则（反映队伍特征）及服务机构（反映服务台的特征）所组成，对随机服务系统的描述如图1所示，可用符号M/M/1表示泊松输入、负指数服务、一个服务台组成的随机服务系统。图1随机服务系统的描述描述排队系统的主要数量指标有：队长L=正在服务的顾客数Ls+等待队长Lq，顾客的平均停留时间W=顾客的平均等待时间Wq+平均服务时间Ws。单位时间内顾客到达率λ、单位时间的服务率µ。它们之间关系的主要公式为：（1）（2）（1）等待制排队模
4、型1）Lingo函数@PEB(ρ,S)：返回到达负荷为ρ，服务系统有S个服务台，且允许排队时系统繁忙的概率，也就是顾客等待的概率Pwait；2）等待制排队模型相关参数计算①顾客等待的概率PwaitPwait=@PEB(ρ,S)，其中系统到达负荷ρ=λ/μ，②顾客平均等待时间（Wq）：③顾客平均停留时间（W），队长（L）和排队长（Lq）：（2）损失制排队模型1）Lingo函数@PEL(ρ,S)返回到达负荷为ρ，服务系统有S个服务器，且不允许排队时的损失概率，也就是顾客得不到服务离开的概率Plost；2）损失制排队模型相关参数计算①顾
5、客离开的概率PlostPlost=@PEL(ρ,S)，其中系统到达负荷ρ=λ/μ，②单位时间内平均进入系统的顾客数λe，即系统的有效到达率：λe=λ(1-Plost)③系统的相对通过能力：Q=1-Plost④系统在单位时间内占用服务台的均值L=λe/μ。⑤系统服务台的效率η=L/S⑥顾客在系统内平均停留时间W=1/μ。（3）有限源排队模型1）Lingo函数@PFS(ρ,S,K)返回当到达负荷为ρ，顾客数为K，服务台数量为S时，有限源的泊松服务系统等待或返修顾客数的期望值。2）有限源排队模型基本参数①平均队长L=@PFS(Kρ,S,
6、K)，其中系统到达负荷ρ=λ/μ。②单位时间平均进入系统的顾客数λe=λ(K-L)③顾客处于正常情况的概率P=K-L/K④每个服务台的工作强度Pwork=λe/Sμ一、动态规划模型与求解1、最短路径问题（1）问题描述：假设有如下的城市网络图，每两点之间的距离已知(已将距离值标在线上)，求从第任意一个城市到第10个城市的最短距离。图2城市网络（2）模型阶段变量：k=1，2，…，10状态变量：Sk表示第k阶段到第k+1阶段的距离决策变量：uk(Sk)=D(X,Y)状态转移方程：Sk+1=T(Sk，uk)指标函数：Fk(Sk)（3）求解
7、过程：（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:!由于并非所有城市间都有道路直接连接，所以将道路具体列出;D=15213121161041214396581052;ENDDATA!如果本身就在第10个城市
8、，则最短距离就是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)))
