上海工程技术大学运筹学考试复习资料.ppt

例6最短路程问题假定从A地到E地要铺设一条管道，其中要经过若干个中间点(如图)。,图中两点之间连线上的数字表示两地间的距离，现在要选择一条铺设管道的路线使总长度最短。,一、多阶段决策过程的最优化,二、基本概念和基本原理,1、阶段：将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按次序去求每阶段的解，常用字母k表示阶段变量。,动态规划模型要用到的概念：(1)阶段;(2)状态;(3)决策和策略;(4)状态转移;(5)指标函数。,2、状态：各阶段开始时的客观条件叫做状态。状态变量：描述各阶段状态的变量，用sk表示第k阶段的状态变量。状态集合：状态变量的取值集合，用Sk表示。,一阶段：S1A二阶段：S2B1,B2,B3三阶段：S3C1,C2,C3四阶段：S4D1,D2,二、基本概念和基本原理,3、决策：当各段的状态取定以后，就可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。决策变量：表示决策的变量，称为决策变量，常用uk(sk)表示第k阶段当状态为sk时的决策变量。允许决策集合：决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合，用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。,D2(B1)=C1,C2D2(B2)=C1,C2,C3如状态为B1时选择C2，可表示为：u2(B1)=C2,二、基本概念和基本原理,策略：各段决策确定后，整个问题的决策序列就构成一个策略，用p1,nu1(s1),u2(s2),.un(sn)表示。允许策略集合：对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作P1,n，使整个问题达到最优效果的策略就是最优策略。,p1,4B1,C1,D1,E,二、基本概念和基本原理,4、状态转移方程：动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果。第k段的状态sk，本阶段决策为uk(sk)，则第k+1段的状态sk+1也就完全确定，它们的关系可用公式表示：sk+1=Tk(sk,uk),sk+1=uk(sk),二、基本概念和基本原理,5、指标函数：用于衡量所选定策略优劣的数量指标。它分为阶段指标函数和过程指标函数。阶段指标函数是指第k段，从状态sk出发，采取决策uk时的效益，用d(sk,uk)表示。d(B1,C2)一个n段决策过程，从1到n叫作问题的原过程，对于任意一个给定的k(1kn)，从第k段到第n段的过程称为原过程的一个后部子过程。V1,n(s1,p1,n)表示初始状态为s1采用策略p1,n时原过程的指标函数值;Vk,n(sk,pk,n)表示在第k段，状态为sk采用策略pk,n时,后部子过程的指标函数值。最优指标函数记为fk(sk)：表示从第k段状态sk采用最优策略到过程终止时的最佳效益值。,二、基本概念和基本原理,最简单的方法穷举法。共有多少条路径，依次计算并比较。动态规划方法本方法是从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点的最短路线，最后求得起始点到终点的最短路线。,二、基本概念和基本原理,练习：,求从A到E的最短路径。,二、基本概念和基本原理,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f5(E)=0,二、基本概念和基本原理,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D1)=5,f5(E)=0,二、基本概念和基本原理,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f4(D1)=5,二、基本概念和基本原理,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C1)=8,f4(D1)=5,二、基本概念和基本原理,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C2)=7,f4(D1)=5,f3(C1)=8,二、基本概念和基本原理,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f3(C1)=8,f3(C2)=7,二、基本概念和基本原理,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B1)=20,f3(C2)=7,f3(C1)=8,二、基本概念和基本原理,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B2)=14,f3(C2)=7,f3(C1)=8,f2(B1)=21,二、基本概念和基本原理,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f2(B1)=21,f2(B2)=14,二、基本概念和基本原理,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,二、基本概念和基本原理,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态最优决策状态最优决策状态最优决策状态最优决策状态,A（A，B2）B2,二、基本概念和基本原理,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态最优决策状态最优决策状态最优决策状态最优决策状态,A（A，B2）B2（B2，C1）C1,二、基本概念和基本原理,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态最优决策状态最优决策状态最优决策状态最优决策状态,A（A，B2）B2（B2，C1）C1（C1，D1）D1,二、基本概念和基本原理,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态最优决策状态最优决策状态最优决策状态最优决策状态,A（A，B2）B2（B2，C1）C1（C1，D1）D1（D1，E）E从A到E的最短路径为19，路线为AB2C1D1E,二、基本概念和基本原理,某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表7-4所示。试问在各地区如何设置销售点可使每月总利润最大。表7-4,解如前所述，建立动态规划数学模型：将问题分为3个阶段，k=1，2，3；决策变量xk表示分配给第k个地区的销售点数；状态变量为sk表示分配给第k个至第3个地区的销售点总数；状态转移方程：sk+1=skxk，其中s1=4；允许决策集合：Dk（sk）=xk|0xksk阶段指标函数：gk（xk）表示xk个销售点分配给第k个地区所获得的利润；最优指标函数fk（sk）表示将数量为sk的销售点分配给第k个至第3个地区所得到的最大利润，动态规划基本方程为：,k=3时，数值计算如下表7-5表7-5,k=2时，计算结果见下表7-6表7-6,k=1时，k=1时，只有s1=4的情况。计算结果如表7-7所示。所以最优解为：x1*=2，x2*=1，x3*=1，f1(4)=47，即在第1个地区设置2个销售点，第2个地区设置1个销售点，第3个地区设置1个销售点，每月可获利润47。表7-7,模型五：价格有折扣的存贮问题记货物单价为，设按三个数量等级变化。,当订购量为时，一个周期内所需费用为：,平均每单位货物所需费用,求解步骤：（1）对（不考虑定义域）求得极值点为（2）若，计算由min得到单位货物最小费用的订购批量。例如min，则取。（3）若，计算，由min决定。（4）若，则取,以上步骤易于推广到单价折扣分m个等级的情况比如说订购量为，其单价为，,j=1，2，m,M/M/1/n,令,，因而得,求得系统的各项指标为,【例5】某公司为经营业务的需要，决定要在现有生产条件不变的情况下，生产一种新产品，现可供开发生产的产品有,四种不同产品，对应的方案为A1,A2,A3,A4由于缺乏相关资料背景，对产品的市场需求只能估计为大中小三种状态，而且对于每种状态出现的概率无法预测，每种方案在各种自然状态下的效益值表，如下表：,表效益值表(单位：万元),（1）悲观主义准则（小中取大法maxmin）,则对应的A4方案为决策方案，即生产产品IV,策略值为,(2)乐观主义准则（大中取大法maxmax）,则对应的A1方案为决策方案，即生产产品I,策略值为,(3)折衷法，现实主义准则(Hurwiczcriterion),maxmin法是当0时状态，maxmax是1时状态,原则：决策者给出乐观系数,0,10则说明决策者越接近悲观；1则说明决策者越接近乐观。,则应选择对应的决策方案A4，即生产产品IV。,策略值为,（4）等可能性决策准则(Equallikelihoodcriterion),则应选择对应的A1方案为决策方案，即生产产品I。,（5）后悔值准则（最小机会损失准则，Minimaxregretcriterion）,编制机会损失表:,找出每个方案