运筹学基础 课件 第5章.pptx

第5章动态规划;

5.1多阶段决策问题;

;

例5-1(多阶段最短路问题)对如图5-1所示的图求解从起点S到终点E的最短路。

如果将图5-1中的点看作决策问题的状态,则这个问题具有明显的阶段性,且状态仅在相邻的状态之间向后转移,因此这是一个多阶段决策问题。状态集合为;

;

例5-2(背包问题)给定n种物品,每种物品都有自己的质量wi和价值ri,背包的最大承重为W,请选择装入背包物品的种类和数量,使装入背包的物品总价值最高。

假设背包最大承重W=10,可装物品的单件质量和单件价值如表5-1所示,可装物品的数量足够。;;

;

第4阶段:考虑装入C类物品,将第3阶段状态作为起始状态,其对应的决策、到达状态及行动收益如表5-3所示。;

第5阶段:只有一个结束状态,记为x26。从第4阶段的状态到x26的状态转移收益均为0。;

5.2网络模型;

多阶段决策问题网络模型建立的过程如下:

步骤1:分析决策问题的状态有哪些,将时间或者步骤分成n个阶段,分析每个阶段的状态,由此可以确定网络上点的子集Vi。

步骤2:分析状态之间是否有可能存在可行的迁移,如果存在,则分析状态迁移的成本或者费用,并将其作为两点之间的状态转移费用,由此可以确定序号相邻子集之间的边及边的权重。

步骤3:根据问题分析起始状态和最终状态,确定起点和终点。;

5.3Bellman递归方程;

最优子结构定理对满足最优性原则的多阶段决策问题,最优决策序列的子序列也是最优的。

证明:假设路径(A,A1,A2,…,Am,C,B1,B2,…,Bn,B)为从A到B的最优决策序列,那么其子序列一定也是最优的。例如,A,A1,A2,…,Am,C一定是从A到C的最优决策序列,C,B1,B2,…,Bn,B也一定是从C到B的最优决策序列。利用反证法很容易证明(证明略)。

需要注意的是,如果多阶段决策问题不满足最优性原则,则不一定满足最优子结构定理,也就是说,其最优决策序列的子序列不一定是最优的。;

例5-3某导弹部队的导弹火力单元隐蔽待机于待机地p1和p2,接收到3波次火力打击任务。火力单元需要通过网络(见图5-2)机动到某导弹仓库dj(j=1,2,…,5)装载导弹,然后通过网络机动到某一个发射点ri(i=1,2,…,30)发射导弹,完成1波次的发射任务。整个任务需要完成3波次的打击。假设为了提高生存能力,在整个火力打击任务中,所有的火力单元均不会第二次使用同一个发射点,直到所有的火力单元都完成3波次火力打击任务为止,则可以建立如图5-3所示的多阶段决策问题的网络模型。;

;

;

图5-3中,虚线所示的有向边的权重为状态转移所对应的物理上两个地点的最短路的距离。火力单元的任意可行行动路径一定对应图5-3所示模型中的一条从s到e的路,但是,一条从s到e的路未必是火力单元可行的行动路径,因为要满足发射点不重复的约束。例如,存在这种情况:从s到e的最短路如图5-4中加粗实线箭头所示,但是,根据发射点不重复的约束,这不是火力单元的一条可行路径。;

;

因为要满足发射点不重复的约束,这个模型不满足最优性原则,也就是对以后阶段所做出的未来决策将会产生一个最优策略,它与前面各阶段所采用的策略不是无关的。这个模型也不满足最优子结构定理。对于某个火力单元的最优路径,其子路径不一定是最优的。例如,存在这种情况:某火力单元的最优路径如图5-5中加粗实线箭头所示,则从第5阶段的d1到e的子路径不一定是最优的。;

;

5.3.2两个推论;;

5.3.3两个方程;

5.3.4多阶段最短路问题的求解

例5-4利用Bellman逆序方程求解多阶段最短路问题(见图5-1)的具体步骤如下:;;

因此,从S到E的最短路长度为21。最短路的序列可以从求解的过程数据倒推得到。例5-1中,最短路的序列包括以下几个:;

利用Bellman顺序方程求解多阶段最短路问题(见图5-1)的具体步骤如下:;;

5.4典型案例;

如果令装入第i(i=1,2,…,n)种物品的数量为xi,则可以建立如下背包问题的整数规划模型:;

2.建立动态规划模型

建立动态规划模型的具体步骤如下:

步骤1:输入背包问题的参数,确定阶段的数量。将问题分成n+2个阶段,增加一个虚拟的起始状态和一个虚拟的结束状态,中间每个阶段考虑一种类型的物品。因为要最大化背包中物品的价值,所以将单位物品的价值加上一个负号。;

步骤2:建立每个阶段状态的集合,第1阶段的状态设定为一个虚拟的起点,最后一个阶段也就是第NStage阶段的状态设定为一个虚拟的终点。状态为当前背包中物品的质量。状态之间是否可以转