第七章动态规划模型与实验。
一个系统依据某种方式分为许多个不同的阶段，这些阶段不仅有着次序推移性，而且相互间有着依赖和影响。这种能分成阶段推移的系统叫做动态系统。动态规划是解决多阶段决策过程最优化的一种数学方法。
动态规划的一个显著特点在于具有明确的阶段性，整个系统按某种方式可分为若干个不同的阶段，在每个阶段由若干种不同的方案可供选择。这样，在多阶段决策过程中，每个阶段决策的选择，不仅要依据次序来考查某阶段的效果外，而且更要顾及此决策对以后各阶段决策的影响，特别是对以后各个阶段决策的影响。系统最优决策问题要求在系统每个阶段可供的多种方案 (决策) 中，选择一个合适的决策，使整个系统达到最优的效果。
整个过程分为多阶段的决策过程。各个阶段所做的决策形成确定整个系统的决策序列，称这样的决策序列为系统的一个策略。对应某一确定的策略，整个系统依据某种数量指标衡量其优劣的决策。
多阶段决策过程就是在所有允许策略集合中。确定一个达到最优指标的最优策略。这种衡量系统的指标一般取最大值或最小值的策略。
因此，多阶段决策过程也是一个可以构成多个变量的最优化问题。一个系统能分为多阶段的决策过程，有时需要数学技巧和艺术来划分，动态规划就是解决此类多阶段决策过程的最优化方法。
7.1动态规划的基本原理。
实际生活的问题，通过构造数学模型，具有特殊的动态系统过程，将基于某种方式把整个过程分成若干个互相联系的阶段，在其每个阶段都需要作出合适决策，从而使整个过程达到最佳效果。同时，各个阶段决策的选择依赖于该阶段的状态以及前或后阶段的变化。各个阶段决策确定后，组成一个决策序列，从而形成了整个过程具有前后关联的链状结构的多阶段决策过程，称为序贯决策过程。
由此，动态规划求解首先关键在于如何将实际问题构造成能形成多阶段的系统，并且在各个阶段能作出序贯性的最佳决策，以使在序贯决策的状态推移进程中达到整个系统的最优决策。
例7.1 能分成阶段的最短路问题。图7.1是一个路线网络图，连线上的数字表示两点之间的距离（或费用），要求寻找一条由a到e的路线，使距离最短（或费用最省）。
b1c1d1
a b2c2e
d2b3c3
图7.1对于这样一个比较简单的问题，可直接使用枚举法列举所有从a到e的路线，共14条，然后，根据每条路线的长度（或费用），确定出所应走的路线（费用）最短（少）。
直观的思想，如果已找到由a到e的最短路线是a—→b1—→c2—→d2—→e（记作l），那么当寻求l中的任何一点（如c2）到e的最短路时，它必然是l中子路线c2—→d2—→e（记作l1）。否则若d2到e的最短路是另一条路线l2 ，则把a—→b1—→c2与l2连接起来，就会得到一条不同于l的从a到e的最短路。根据此特性，可以从最后一段开始，用逐步向前递推的方法，依次求出路段上各点到e的最短路，最后得到a到e的最短路。
上述这种由系统的作后阶段逐段向初是始阶段求最优的过程称为动态规划的逆推解法。该过程揭示了动态规划的基础思想，为使动态规划的思想和方法数学上描述。下面先引入动态规划中基本概念与最优目标函数的建立。
1）分阶段把所给的系统，适当地依据具体情况分成若干个相互联系的阶段，描述阶段的变量称为阶段变量，常用k表示，并将各个阶段按顺序或逆序加以编号，如例7.1可分为5个阶段来求解，k=1，2，3，4，5。
2）状态状态表示系统在某一阶段所处的位置，自然状况或客观条件。一个阶段系统会存在若干个可能的状态。在例7.
1中，状态就是某阶段的出发位置，它既是该阶段某之路的起点，又是前一阶段某之路的终点，一个阶段有若干个状态，第一阶段有一个状态就是初始位置a，第二阶段有三个状态，即使集合，一般第k阶段的状态就是第k阶段所有始点的集合。
描述过程状态的变量称为状态变量，常用sk表示第k阶段的所有可能状态变量的集合，其元素为sk可以是数，数组或向量。如例7.1中第三阶段有三个状态，则sk可能取三个值，即c1,c2,c3，并且s3= 称为第三阶段的可达状态集合。
3）决策决策表示当系统处于某一阶段的某个状态时，可以作出不同的选择，确定下一阶段的状态，这种决定称为决策。描述决策的变量称为决策变量，常用dk(sk)表示第k阶段当状态处于sk时的决策变量，它是状态变量的函数。而用dk (s k) 表示相应的决策变量的函数集，即有dk (sk)∈dk (sk)。
如在例7.1第二阶段中，从状态b2出发，其允许决策集合为d2(b2)=，某一阶段的状态变量及决策变量的值取定之后，那么下一阶段的状态随之确定。例如选取的点为c2，则c2是状态b1在决策d2(b1)作用下的一个新的状态，记作d2(b1)= c2，下一阶段的状态类似地对上阶段的状态和决策变量的依赖关系可用状态转移方程表示：
s k+1=t k (s k，d k (s k7.1)
4) 策略由系统各阶段确定的决策所形成的决策序列称为策略。从初始状态s1出发由系统的所有n个阶段的决策所形成的策略成为全过程策略，记为：
p1，n(s 1)={d 1(s 1)，d 2(s 2)，…d n (s n7.2)
由系统的第k个阶段出发的后面n – k +1个阶段的决策过程称为全过程的后部子过程，相应的策略称为后部子过程策略，记为。
p k，n(s k)={d k(s k)，d k+1(s k+1)，…d n (s n7.3)
所有可供选择的策略集合称为策略集合，用p表示，从允许策略集合中找出达到最优效果的策略称为最优策略。
5）状态转移方程状态转移方程是确定过程由一个状态到另一个状态的演变过程。若给定第k阶段状态的演变过程，并且若该阶段的决策变量dk一经确定，第k+1阶段的状态变量sk+1也就完全确定，这种对应关系为：
sk+1=tk (sk ，dk(s k ))
所描述了由第k个阶段到第k+1个阶段的状态转移规律，称为状态转移方程。tk 称为第k阶段的状态转移系数。如例7.1中，状态转移方程为。
s k+1=d k (s k )
6) 阶段收益系统某一阶段的状态一经确定，执行某一决策所得的效益称为阶段效益，它是整个系统总收益的一部份。阶段效益是阶段状态和决策变量的函数，反映该阶段的价值与目标。对第k阶段的某一状态sk执行某一决策d k(s k )的阶段效益可用r k(s k ，d k(s k ))来表示。
在例7.1中的阶段效益为走完一段路程所花费的距离。
7) 指标函数和最优值函数系统执行某一策略所产生效果的优劣可用数量指标来衡量，这样的数量指标是整个系统总效益的反映，它是各个阶段状态和决策的函数，称为指标函数。它是定义在全进程和所有子进程上确定的数量函数，记。
f k，n(sk, p k，n )，i=n，n-1，…，17.4)
表示从阶段k的某一状态sk 出发的后部子进程上的指标函数，其中pk，n表示从状态sk出发的一个子策略，最优策略下指标函数的指标为最优策略指标，记为。
其中pk, n表示由状态sk出发的所有允许子策略集合，“opt”为英文optimization（最优）的缩写，可以依题意取min或max。
由上述指标函数的定义，可得指标函数（例7.1的指标函数注记r k(s k ，d k(s k ))表示第k 阶段中点s k 到d k(s k )的距离）。其中
而最优策略指标为。
在例7.1中显然有。
fn+1(sn+1) =07.8)
称为边值条件，动态规划的求解对k=n, n-1,…,1由（7.7）式求最优策略指标的过程。
一般地对多数指标函数的形式取（7.6）式，而最优策略指标取形如（7.7）式，以求和形式出现，另一种常用形式是的各阶段的指标函数为乘积，即。
其相应的最优策略指标为。
对更一般的系统来说，指标函数未必是求和或乘积形式，但应具有可分离性，并满足递推关系，一般具有形式。
在第k阶段，指标函数最优策略指标，即最优值，称为最优值函数，即fk(sk)。根据上述确定的阶段编号、状态变量、决策变量、状态转移方程以及指标函数，确定例7.1的最短路线，计算步骤如下：
根据最短路线特性，寻找最短路线的方法，将从最后一段开始，用由后向前逐步递推的方法，求出各点到e点的最短路线，最后求得由a点到e点的最短路线。所以，动态规划的方向是从各点逐段向始点方向寻找最短路线的一种方法，见图7.2显示。
行进方向。
始点终点。动态规划寻优途径。
图7.2当k= 4时，由d1到终点e只有一条路线，故f4(d1) =6，同理，f4(d2) =5。
当k= 3时，出发点有c1、c2、c3三个，若从c1出发，则有两个选择，一是至d1，一是至d2，则。
其相应的决策为d3(c1)=d1，表示由d1至终点e的最短距离为11，其最短路线是c1→d1→e。
同理，从c2和c3出发，则有。
模型 符号的建立与作用
1 模型方法 建立模型是为了来反映和代替客观对象，并通过研究这个模型来提示客观对象的形态和本质特征。2 优点 能简化和理想化地再现原形的与研究目的有关的各种基本因素和基本联系，略去次要的 非本质的细节。3 讲述。模型并不仅仅指我们可以看到的用各种材料制成的某种物体或放大或缩小的复制品，如航模 各种建...
空间结构课程模型报告与感想
本人设计的模型结构为预应力张弦结构体系。是一种将上弦刚性受压构件通过撑杆与下弦悬索结合在一起形成自平衡的受力体系。上弦拱，撑杆 下弦钢索三者形成了一个整体屋架。上弦是立体拱，用来承载屋顶恒荷载和雨雪等活荷载，是刚性受压构件。这种结构的特点是轻盈，风阻小，刚度大，整体性强，结构稳定，可以适用于较大的跨...
物流成本控制模型分析与管理实务
主讲 李文发。一 课程优势 长期在集团公司任职物流中心高层管理和做培训工作，精通集团仓库物流成本控制 集约化管理 集团物流需求 计划 现代立体化物流仓库管理和线路规划 集团物流网上招标运作 物流 商的控制管理系统，具有丰富的物流成本与线路规划图管理经验。多年服务于南方电网物流中心 国家电网物流中心 ...