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

运筹学与系统工程上机实验指导书机电学院工业工程专业2013-2014（1）学期上机实验五：应用Lingo求解动态规划和排队论问题一、 实验目的在熟练编写和运行Lingo程序的基础上，应用Lingo进行求解动态规划和排队论等深层次优化问题的练习。二、 实验要求1、 根据本指导书学习Lingo对典型动态规划问题进行建模和求解。2、 根据本指导书学习排队论相关函数的具体使用方法，对典型的随机服务系统问题进行建模和求解。3、 独立完成相关应用题目的分析、建模和应用Lingo软件的求解过程。三、 相关知识1、动态规划问题模型及典型应用动态规划（Dynamic Programming）是将一个大型、复杂的问题转换为若干阶段的子问题，从而将动态的多阶段问题简化为静态的单阶段决策问题，一般需要采用递归算法进行求解。动态规划问题的一般模型为：动态规划的典型应用包括：最短路径问题、动态生产计划问题、资源配置问题、背包问题、旅行商问题、随机性采购问题、设备更新问题等。按照决策变量取值的不同，也可以分为连接型动态规划和离散型动态规划问题。无论是连续问题还是离散问题，动态规划解决问题的前提条件是：可将问题划分为k个阶段（k=1,2,n），并能构建多阶段模型（最优指标函数Vk,n，状态Sk、决策uk、状态转移方程Tk）。2、随机服务系统相关Lingo函数随机服务系统由输入过程（反映顾客总体的特征）、排队规则（反映队伍特征）及服务机构（反映服务台的特征）所组成，对随机服务系统的描述如图1所示，可用符号M/M/1表示泊松输入、负指数服务、一个服务台组成的随机服务系统。图 1 随机服务系统的描述描述排队系统的主要数量指标有：队长L=正在服务的顾客数Ls+等待队长Lq，顾客的平均停留时间W=顾客的平均等待时间Wq+平均服务时间Ws。单位时间内顾客到达率、单位时间的服务率。它们之间关系的主要公式为： （1） （2）（1）等待制排队模型1）Lingo函数PEB(, S)：返回到达负荷为，服务系统有S个服务台，且允许排队时系统繁忙的概率，也就是顾客等待的概率Pwait；2）等待制排队模型相关参数计算顾客等待的概率PwaitPwait=PEB(,S)， 其中系统到达负荷=/，顾客平均等待时间（Wq）：顾客平均停留时间（W），队长（L）和排队长（Lq）：（2）损失制排队模型1）Lingo函数PEL(,S)返回到达负荷为，服务系统有S个服务器，且不允许排队时的损失概率，也就是顾客得不到服务离开的概率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时，有限源的泊松服务系统等待或返修顾客数的期望值。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阶段到第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,2 1,3 1,4 2,5 2,6 2,7 3,5 3,6 3,7 4,5 4,6 5,8 5,9 6,8 6,9 7,8 7,9 8,10 9,10/: D; ! D(i, j) 从第i个城市到第j个城市的距离; ENDSETS DATA: !由于并非所有城市间都有道路直接连接，所以将道路具体列出; D = 1 5 2 13 12 11 6 10 4 12 14 3 9 6 5 8 10 5 2; ENDDATA ! 如果本身就在第10个城市，则最短距离就是0; F(SIZE(CITIES) = 0; ! 从任意城市（除了第10个城市）到第10个城市的距离; FOR(CITIES(i)| i #LT# SIZE(CITIES): F(i) = MIN(ROADS(i, j): D(i, j) + F(j) );（5）Lingo求解结果：2、 多阶段生产计划问题（1） 问题描述：设某种材料可用于两种方式生产，用后除产生效益外，还有一部分回收，表1所示为生产方式、效益及回收之间的关系，若有材料100个单位，计划进行3个阶段的生产，如何投入材料，使总效益达到最大?表 1 生产方式、效益和回收之间的关系生产方式12效益函数回收函数（2） 模型阶段变量：k=1，2，3状态变量：Sk表示第k阶段开始生产时原料的数量决策变量：uk(Sk)表示从第k阶段原料的数量Sk中分配给1型产品的数量状态转移方程：Sk+1=0.1uk+0.4(Sk-uk)=0.4Sk-0.3uk, k=1,2,3指标函数：Fk(Sk)（3） 求解过程k=3时：，最优决策为：，即原料配给1型产品k=2时：，最优决策为：0，即原料配给2型产品k=1时：，最优决策为：，即原料配给2型产品总收益为：（4） Lingo模型（5） Lingo程序model:SETS: stage/1.3/:x,y;!三个阶段，每个阶段1型和2型产品分配数量分别为x(k)和y(k);ENDSETS max = sum(stage:0.6*x+0.5*y);!目标函数：总效益最大化;n = size(stage); !阶段总数;x(1)+y(1) = 100; !第一阶段分配总数不超过原料数;for(stage(k) | k #lt# n: x(k+1)+y(k+1) 1/6=e-(10-4/6)=0.3679（2） Lingo程序! 服务台数;S =1;! 顾客到达率（/小时）;lambda = 4;!顾客服务率;mu = 10;!系统到达负荷;load = lambda/mu;! 顾客等待的概率;Pwait = PEB(load, S);! 顾客平均等待时间;W_q = Pwait/mu/(S-load);!等待服务的平均顾客数;L_q = lambda * W_q;!每位顾客在店内的平均停留时间;W=W_q+1/mu;!店内的平均顾客数;L=lambda * W;! 修理店空闲的概率;P0=1-load;!店内恰有3个顾客的概率;P3 = load3 * p0;! 顾客在店内等待时间超过10分钟;Pt10 = exp(-(mu-lambda)*1/6);（3）Lingo求解结果及分析可见，程序运行结果与计算结果一致。五、 实验内容及要求根据本指导书提供的例题练习对动态规划的建模及求解方法，以及应用相关Lingo函数求解排队论问题，完成以下思考练习题，并通过手工计算对程序的运行结果进行验证。将相关的问题分析、模型、程序、运行结果及结果的分析（包括手工计算过程）附在上机实验报告中。练习1：用Lingo软件求解下图所示的从A到E的最短路线及其长度。图 3 练习1相关网络图练习2：用Lingo软件求解多阶段生产安排问题。某公司现有同种施工机械100台，分别用于两类轻重不同的施工任务，该公司面临两年施工工期的每年初各分配多少台机械用于这两类任务的决策，目的是使总收益最大。若每年将x台机械用于重任务，当年收为g(x)=10x2（万元），并将有30%的机械于当年年末报废；若将y台机械用于轻的施工任务，当年收入为g(y)=5y2（万元），但有10%的机械于年末报废。两年施工结束后，未报废的机械可以每台7万元的售价卖出。试