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

作者：ytkug18 | 发布时间：2021-01-07 01:22:50 收藏本文下载本文

运筹学与系统工程上机实验指导书机电学院工业工程专业 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 LW   （1）

1 1()qW W W          s（2）（1）等待制排队模型 1）Lingo 函数@PEB(ρ, S)：返回到达负荷为 ρ，服务系统有 S 个服务台，且允许排队时系统繁忙的概率，也就是顾客等待的概率 Pwait； 2）等待制排队模型相关参数计算 ①顾客等待的概率 Pwait Pwait=@PEB(ρ,S)，其中系统到达负荷 ρ=λ/μ，②顾客平均等待时间（Wq）：()waitqPWS   ③顾客平均停留时间（W），队长（L）和排队长（Lq）：

（2）损失制排队模型 1）Lingo 函数@PEL(ρ,S)返回到达负荷为 ρ，服务系统有 S 个服务器，且不允许排队时的损失概率，也就是顾客得不到服务离开的概率 Plost； 2）损失制排队模型相关参数计算 ①顾客离开的概率 Plost Plost=@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 状态变量：S k 表示第 k 阶段到第 k+1 阶段的距离决策变量：u k(S k)=D(X,Y)状态转移方程：S k+1 =T(S k，u k)指标函数：F k(S k)（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 生产方式、效益和回收之间的关系生产方式 1 2 效益函数回收函数（2）模型

阶段变量：k=1，2，3 状态变量：S k 表示第 k 阶段开始生产时原料的数量决策变量：u k(S k)表示从第 k 阶段原料的数量 Sk 中分配给 1 型产品的数量状态转移方程：S k+1 =0.1u k +0.4(S k-u k)=0.4S k-0.3u k , k=1,2,3 指标函数：F k(S k)（3）求解过程 k=3 时：  3 33 33 3 3 3 303 3 30()max 0.6 0.5(S)max 0.1 0.5S 0.6u Su Sf S u uu u      ，最优决策为：k ku S ，即原料配给 1型产品 k=2 时：  2 22 22 2 2 2 2 2 202 2 20()max 0.6 0.5()0.6(0.4 0.3max 0.74 0.08 0.74u Su Sf S u S u S uS u S        ，最优决策为：k ku S  0，即原料配给 2 型产品 k=1 时：  1 11 11 1 1 1 1 1 101 1 10()max 0.6 0.5()0.6(0.4 0.3max 0.74 0.08 0.74u Su Sf S u S u S uS u S        ，最优决策为：

0ku ，即原料配给 2 型产品总收益为：

0.5 100 0.5(100 0.4)0.6(100 0.4 0.4)79.6         （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)<= 0.1*x(k)+0.4*y(k));!以后各阶段分配总数不超过上阶段回收数;（6）Lingo 求解结果 3、等待制排队问题（1）问题描述某修理店只有一个修理工，来修理店的顾客到达过程为泊松流，平均 4 人/小时，修理时间服从负指数分布，平均需要 6 分钟，试求：1）修理店空闲的概率；2）店内恰好有 3 个顾客的概率；3）店内至少有 1 个顾客的概率；4）店内的平均顾客数；5）每位顾客在店内的平均停留时间；6）等待服务的平均顾客数；7）每位顾客的平均等待服务时间；8）顾客在店内等待时间超过 10 分钟的概率。

解：本题可看成一个 M/M/1/∞排队问题，其中 λ=4，μ=10，ρ=λ/μ=0.4 1)修理店空闲的概率 p0=1-ρ=0.6

2）店内恰有 3 个顾客的概率 p3=ρ3(1-ρ)=0.038 3）店内至少有 1 个顾客的概率：P{N≥1}=1-p0=0.4 4）店内平均顾客数：L=λ/μ-λ=2/3 人 5）每位顾客在店内的平均停留时间为：W=L/λ=1/6 小时=10 分钟 6）等待服务的平均顾客数 Lq=L-ρ=4/15=0.2667 人 7）每位顾客的平均等待服务时间为 Wq=W-1/μ=10-6=4 分钟 8）顾客在店内等待时间超过 10 分钟（1/6 小时）的概率：P{T>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 = load^3 * 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 万元的售价卖出。试为该公司提供你的决策建议。

练习3：某维修中心在周末只安排一名员工为服务提供服务，新来的顾客到达后，若已有顾客正在接受服务，则需要排队等待，假设来维修的顾客到达过程为泊松流，平均每小时 6 人，维修时间服务负指数分布，平均需要 4 分钟，试求该系统的主要数量指标：系统平均队长 Ls、系统平均等待队长 Lq、顾客平均停留时间W、顾客平均等待时间 Wq、系统繁忙概率 Pwait。