【2017年整理】上海工程技术大学运筹学考试复习资料.pptVIP

例6 最短路程问题 假定从A地到E地要铺设一条管道，其中要经过若干个中间点(如图)。;二、基本概念和基本原理;2、状态：各阶段开始时的客观条件叫做状态。 状态变量：描述各阶段状态的变量，用sk表示第k阶段的状态变量。 状态集合：状态变量的取值集合，用Sk表示。;3、决策：当各段的状态取定以后，就可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。 决策变量：表示决策的变量，称为决策变量，常用uk(sk)表示第k阶段当状态为sk时的决策变量。 允许决策集合：决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合，用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。;策略：各段决策确定后，整个问题的决策序列就构成一个策略，用p1,n{u1(s1),u2(s2),...un(sn)}表示。 允许策略集合：对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作P1,n，使整个问题达到最优效果的策略就是最优策略。; 4、状态转移方程：动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果。 第k段的状态sk，本阶段决策为uk(sk)，则第k+1段的状态sk+1也就完全确定，它们的关系可用公式表示：sk+1=Tk(sk,uk); 5、指标函数：用于衡量所选定策略优劣的数量指标。 它分为阶段指标函数和过程指标函数。 阶段指标函数是指第k段，从状态sk出发，采取决策uk时的效益，用d(sk,uk)表示。d(B1,C2) 一个n段决策过程，从1到n叫作问题的原过程，对于任意一个给定的k(1≤k ≤ n)，从第k段到第n段的过程称为原过程的一个后部子过程。 V1,n(s1,p1,n) 表示初始状态为s1采用策略p1,n时原过程的指标函数值; 　Vk,n(sk,pk,n)表示在第k段，状态为sk采用策略pk,n时,后部子过程的指标函数值。 最优指标函数记为fk(sk)：表示从第k段状态sk采用最优策略到过程终止时的最佳效益值。;最简单的方法－－穷举法。共有多少条路径，依次计算并比较。 动态规划方法－－本方法是从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点的最短路线，最后求得起始点到终点的最短路线。;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2; 某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表7-4所示。试问在各地区如何设置销售点可使每月总利润最大。 表7-4 ;解 如前所述，建立动态规划数学模型： 将问题分为3个阶段，k=1，2，3； 决策变量xk表示分配给第k个地区的销售点数； 状态变量为sk表示分配给第k个至第3个地区的销售点总数； 状态转移方程：sk+1=sk－xk，其中s1=4； 允许决策集合：Dk（sk）=｛xk|0≤xk≤sk｝ 　　阶段指标函数：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）若