[管理学]动态规划3_4.pptVIP

作业 复习：动态规划及其应用 预习：图与网络分析 书面作业： P228-：习题7.4 7.9 （用动态规划方法求解上述问题后，用LINGO软件验证。） A 3 B1 4 C1 3 D1 4 5 3 2 B2 2 C2 3 D2 E1 1 2 3 4 C3 4 D3 5 E2 2 F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F 求解连续性静态问题 由最优化原理 解 利用递推公式,得到 * §4．3 动态规划的求解与应用 求最短路径： 将问题分成五个阶段，第k阶段到达的具体地点用状态变量xk表示，例如：x2=B3表示第二阶段到达位置B3，等等。这里状态变量取字符值而不是数值。 将决策定义为到达下一站所选择的路径，例如目前的状态是x2=B3，这时决策允许集合包含三个决策，它们是： D2(x2)=D2(B3)={B3?C1,B3?C2,B3?C3} 最优指标函数fk(xk)表示从目前状态到E的最短路径。终端条件为 f5(x5)=f5(E)=0其含义是从E到E的最短路径为0。 第四阶段的递推方程为 其中*表示最优值，在上表中，由于决策允许集合D4(x4)中的决策是唯一的，因此这个值就是最优值。 由此得到f4(x4)的表达式。由于这是一个离散的函数，取值用列表表示： 第三阶段的递推方程为： 由此得到f3(x3)的表达式： 由此得到f2(x2)的表达式： 第一阶段的递推方程为： 由此得到f1(x1)的表达式 例: 有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）关系见下表： 求对三个项目的最优投资分配，使总投资效益最大。 资源分配问题 阶段k：每投资一个项目作为一个阶段； 状态变量xk：投资第k个项目前的资金数； 决策变量dk：第k个项目的投资； 决策允许集合：0≤dk≤xk 状态转移方程：xk+1=xk-dk 阶段指标：vk(xk ,dk)见表中所示； 递推方程： fk(xk)=max{vk(xk ,dk)+fk+1(xk+1)} 终端条件：f4(x4)=0 k=4，f4(x4)=0k=3，0≤d3≤x3，x4=x3-d3 k=2，0≤d2≤x2，x3=x2-d2 k=1，0≤d1≤x1，x2=x1-d1 背包问题 则 Max z= c1x1+c2x2+…+cnxn  s.t. w1x1+w2x2+…+wnxn≤W  x1,x2,…,xn为非负整数 阶段k：第k次装载第k种物品（k=1,2,…,n） 状态变量xk：第k次装载时背包还可以装载的重量； 决策变量dk：第k次装载第k种物品的件数； 4. 决策允许集合： Dk(xk)={dk|0? dk?xk/wk，dk为整数}； 5. 状态转移方程：xk+1=xk-wkdk 6. 阶段指标：vk=ckdk 7. 递推方程 fk(xk)=max{ckdk+fk+1(xk+1)} =max{ckdk+fk+1(xk-wkdk)} 8. 终端条件：fn+1(xn+1)=0 例:对于一个具体问题c1=65，c2=80，c3=30；w1=2，w2=3，w3=1；以及W=5，用动态规划求解 。f4(x4)=0 对于k=3 不定阶段最短路线问题 如图是一个五座城市的及其相连道路的交通图，线上的数字是对应的路长。问：应如何选择行驶路线，才能使从A、B、C、D各城市到E城市的行驶路程最短？ A E D C B 2 5 2 7 5 5 6 1 0.5 3 从图中可以看出，任意两座城市之间都有道路相通。我们把从一座城市直达另一座城市作为一个阶段。例从A城市到E城市的阶段数，少则一个（例从A城