运筹学和系统工程上机实验指导书机电学院工业工程专业2013-2014（1）学期上机实验五：使用Lingo 求解动态规划和排队论问题一、 实验目的在熟练编写和运行Lingo 程序的基础上，使用Lingo 进行求解动态规划和排队论等深层次优化问题的练习。
二、 实验要求1、根据本指导书学习Lingo 对典型动态规划问题进行建模和求解。
2、根据本指导书学习排队论相关函数的具体使用方法，对典型的随机服务系统问题进行建模和求解。
3、独立完成相关使用题目的分析、建模和使用Lingo 软件的求解过程。
三、 相关知识1、动态规划问题模型及典型使用动态规划（Dynamic Programming ）是将一个大型、复杂的问题转换为若干阶段的子问题，从而将动态的多阶段问题简化为静态的单阶段决策问题，一般需要采用递归算法进行求解。
动态规划问题的一般模型为：{}1111()max(min)(,)(),1,,2,1()0k k k k k k k n n f S V S u f S k n n f S ++++=+=-=动态规划的典型使用包括：最短路径问题、动态生产计划问题、资源配置问题、背包问题、旅行商问题、随机性采购问题、设备更新问题等。
按照决策变量取值的不同，也可以分为连接型动态规划和离散型动态规划问题。
无论是连续问题还是离散问题，动态规划解决问题的前提条件是：可将问题划分为k 个阶段（k=1,2,…,n ），并能构建多阶段模型（最优指标函数Vk,n ，状态Sk 、决策uk 、状态转移方程Tk ）。
2、随机服务系统相关Lingo 函数随机服务系统由输入过程（反映顾客总体的特征）、排队规则（反映队伍特征）及服务机构（反映服务台的特征）所组成，对随机服务系统的描述如图1所示，可用符号M/M/1表示泊松输入、负指数服务、一个服务台组成的随机服务系统。
图 1 随机服务系统的描述描述排队系统的主要数量指标有：队长L=正在服务的顾客数Ls+等待队长Lq ，顾客的平均停留时间W=顾客的平均等待时间Wq+平均服务时间Ws 。
单位时间内顾客到达率λ、单位时间的服务率µ。
它们之间关系的主要公式为：1LW λμλ==- （1） 11 ()q W W W λμλμμμλ=-=-=--s （2） （1）等待制排队模型1）Lingo 函数@PEB(ρ, S)：返回到达负荷为ρ，服务系统有S 个服务台，且允许排队时系统繁忙的概率，也就是顾客等待的概率Pwait ；2）等待制排队模型相关参数计算 ①顾客等待的概率PwaitPwait=@PEB(ρ,S)， 其中系统到达负荷ρ=λ/μ，②顾客平均等待时间（Wq ）：()waitq P W S μρ=-③顾客平均停留时间（W ），队长（L ）和排队长（Lq ）：1,,q q q W W L W L W λλμ=+==（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状态变量：S k 表示第k 阶段到第k+1阶段的距离 决策变量：u k (S k )=D(X,Y)状态转移方程：S k+1=T(S k ，u k ) 指标函数：F k (S k ){}(10)0()min (,)(),10X YF F X D X Y F Y X ≠=⎧⎪⎨=+<⎪⎩（3）求解过程：(10)0(9)min{(9,10)(10)}min{20}2(8)min{(8,10)(10)}min{50}5(7,8)(8)85(7)min min 12(7,9)(9)102(6,8)(8)65(6)min min 7(6,9)(9)52(5,8)(5)min F F D F F D F D F F D F D F F D F D F ==+=+==+=+=++⎧⎫⎧⎫===⎨⎬⎨⎬++⎩⎭⎩⎭++⎧⎫⎧⎫===⎨⎬⎨⎬++⎩⎭⎩⎭+=(8)35min 8(5,9)(9)92(4,5)(5)128(4)min min 20(4,6)(6)147(3,5)(5)68(3)min (3,6)(6)min 10714(3,7)(7)412(2,5)(5)(2)min (2,6)F D F D F F D F D F F D F D F D F F D +⎧⎫⎧⎫==⎨⎬⎨⎬++⎩⎭⎩⎭++⎧⎫⎧⎫===⎨⎬⎨⎬++⎩⎭⎩⎭++⎧⎫⎧⎫⎪⎪⎪⎪=+=+=⎨⎬⎨⎬⎪⎪⎪⎪++⎩⎭⎩⎭+=138(6)min 12719(2,7)(7)1112(1,2)(2)119(1)min (1,3)(3)min 51419(1,4)(4)220F D F D F F D F D F +⎧⎫⎧⎫⎪⎪⎪⎪+=+=⎨⎬⎨⎬⎪⎪⎪⎪++⎩⎭⎩⎭++⎧⎫⎧⎫⎪⎪⎪⎪=+=+=⎨⎬⎨⎬⎪⎪⎪⎪++⎩⎭⎩⎭（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,109,10/: D; ! D(i, j) 从第i 个城市到第j 个城市的距离; ENDSETSDATA: !由于并非所有城市间都有道路直接连接，所以将道路具体列出; D =1 52 13 12 11 6 10 412 143 96 58 1052;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效益函数1()0.6g x x=2()0.5g x x=回收函数10.1a x x=20.4a x x=阶段变量：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){}{}3310333330()max 0.60.5()(0.40.3()max 0.60.5(S )k k k k k k k k k k u S u S f S u S u f S u f S u u +≤≤≤≤=+-+-⎧⎪⎨=+-⎪⎩（3） 求解过程k=3时：{}{}33333333303330()max 0.60.5(S )max 0.10.5S 0.6u S u S f S u u u u ≤≤≤≤=+-=+=，最优决策为：k k u S =，即原料配给1型产品k=2时：{}{}2222222222202220()max 0.60.5()0.6(0.40.3max 0.740.080.74u S u S f S u S u S u S u S ≤≤≤≤=+-+-=-=，最优决策为：k u S =0，即原料配给2型产品k=1时：{}{}1111111111101110()max 0.60.5()0.6(0.40.3max 0.740.080.74u S u S f S u S u S u S u S ≤≤≤≤=+-+-=-=，最优决策为：0k u =，即原料配给2型产品总收益为：0.51000.5(1000.4)0.6(1000.40.4)79.6⨯+⨯⨯+⨯⨯⨯= （4） Lingo 模型()31211111max ()()..1000.10.4,1,2,,1,0,1,2,,k k k k k k k k k g x g y s t x y x y x y k n x y k n=+++ +≤ +≤+=- ≥=∑（5） Lingo 程序model :SETS :stage/1..3/:x,y;!三个阶段，每个阶段1型和2型产品分配数量分别为x(k)和y(k);ENDSETSmax = @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分钟的概率。