§2最优化原理与动态规划的数学模型.

1§2最优化原理与动态规划的数学模型•一、动态规划问题的解题思路•动态规划方法的基本思路就是将一个n阶段的决策问题转化为依次求解n个具有递推关系的单阶段决策问题，从而简化计算过程。在例8-1中，这种转化的实现是从终点E出发一步步反推，这种算法称为逆序算法。具体步骤如下：•（1）考虑一个阶段的最优选择，旅行者到达E点前，上一站必然到达D1或D2，若上一站的起点为D1，则该阶段的最优决策必然是D1→E，距离d(D1,E)=3,记f((D1)=3,f((D1)表示从D1出发到终点的最短距离，若旅行者上一站的起点为D2，则该阶段最优选择为D2→E，f((D2)=4.2AB1B2B3C1C2C3D1D2E25367532451514633334图8-13•（2）综合考虑两个阶段的最优选择，当旅行者离终点还有两站时，他必然位于C1,C2,C3中的某一点。若他位于C1，则他有两条路线可以选择：C1→D1→E或C1→D2→E，若将从C1到E的最短距离记为f(C1)，则•f(C1)=min{d(C1,D1)+f(D1),d(C1,D2)+f(D2)}•=min{1+3,4+4}=4;类似的：•f(C2)=min{d(C2,D1)+f(D1),d(C2,D2)+f(D2)}•=min{6+3,3+4}=7;•f(C3)=min{d(C3,D1)+f(D1),d(C3,D2)+f(D2)}•=min{3+3,3+4}=6;4•（3）综合考虑三个阶段的最优选择，当旅行者离终点还有三站时，他必然位于B1,B2,B3中的某一点。若他位于B1，则他有三条路线可以选择：B1→C1→E或B1→C2→E，或B1→C3→E，若将从B1到E的最短距离记为f(B1)，则•f(B1)=min{d(B1,C1)+f(C1),d(B1,C2)+f(C2),•d(B1,C3)+f(C3)}=min{7+4,5+7,6+6}=11;类似的：•f(B2)=min{d(B2,C1)+f(C1),d(B2,C2)+f(C2),•d(B2,C3)+f(C3)}=min{3+4,2+7,4+6}=7;•f(B3)=min{d(B3,C1)+f(C1),d(B3,C2)+f(C2),•d(B3,C3)+f(C3)}=min{5+4,1+7,5+6}=8;5•(4)四个阶段综合考察，设旅行者从A到E的最短距离为f(A)，则•f(A)=min{d(A,B1)+f(B1),d(A,B2)+f(B2),•d(A,B3)+f(B3)}=min{2+11,5+7,3+8}=11.•因此，从到的最短路线为：•A→B3→C2→D2→E，最短路线长为：11。6•二、动态规划的基本概念1.阶段(stage)是指一个问题需要作出决策的步数，通常用k表示阶段数，称为阶段变量。2.状态(state)各阶段开始时的客观条件,是动态规划问题中最关键的参数，它既反映前面各阶段决策的结局，又是本阶段决策的出发点和依据。描述各阶段状态的变量称为状态变量，通常用表示第k阶段的状态变量。状态集合状态变量的取值集合。状态的性质——无后效性。kskkkSsS,ks7所谓无后效性是指：一旦到达某一状态，那么今后的选择只与这一状态有关，而与先前是如何到达这一状态是无关的。3.决策(decision)某阶段状态取定，可以作出不同的决定，从而决定这一阶段所收到的效果以及下一阶段的状态，这种决定称为“决策”。表示决策的变量称决策变量。决策变量取值范围构成允许决策集合：•。)(kksu()()kkkkusDs(),kkDs8•4.策略(policy)和子策略(subpolicy)各阶段决策组成的决策序列的总体称为一个策略，含n个阶段的动态规划问题的策略可写成：从某一阶段开始到过程最终的决策序列称为子过程策略或子策略。从第k阶段起的子策略可写成：{(),,()}kknnusus1122{(),(),,()}nnususus。9•5.状态转移律从sk的某一状态值出发，当决策变量的取值决定后，下一阶段的状态变量的取值也就随之确定，这种从上一阶段的某一状态值到下一阶段某一状态值的转移的规律称为状态转移律。显然下一阶段状态变量•的取值是上一阶段状态变量sk以及上一阶段决策变量的函数记为：•或简记为：•状态转移律有时也称为状态转移方程。)(kksu)(kksu),(1kkkkusTs1ks1ks1(,())kkkkksTsus10•6.指标函数有阶段指标函数和过程指标函数之分，阶段的指标函数是对应某一阶段状态和从该状态出发的一个阶段的决策的某种效益度量用表示。过程的指标函数是指从状态sk(k=1,…,n)出发至过程最终，当采取某种子策略时，按预定标准得到的效益值，记为：•过程指标函数又是它所包含的各阶段指标函数的函数，按问题的性质不同，可以是各阶段指标函数之和、积或其它函数形式。当sk的值确定后，指标函数值就只与k阶段起的子策略有关。),(kkkusv,11(,,,,,,)knkkkknnVsususu11•7.最优指标函数•是指对某一确定的状态选取最优子策略后得到的指标函数值。实际上也就是对应某一最优子策略的某种效益度量（可以是产量、成本、收益、距离等）。对应于从状态sk出发的最优子策略的效益值记为，则。•其中opt代表最优化，根据效益值的具体含义可以是求最大(max)或求(min)最小。,()kkknfsoptV()kkfs阶段kT(sk,uk)阶段k+1T(sk+1,uk+1)状态状态状态vk(sk,uk)vk(sk+1,uk+1)sksk+1sk+2决策uk(sk)决策uk+1(sk+1)12三、最优化原理动态规划的数学模型1.最优化原理美国的利•别尔曼(R.Bellan)提出的求解动态规划的最优化原理如下：作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对先前决策所形成的状态而言，余下的诸决策必构成最优策略。简而言之“一个最优策略的子策略总是最优的”。2.动态规划的数学模型根据上述原理写出的计算动态规划问题的递推关系式称为动态规划的基本方程。),,(,1nkkkkVus13•当且采用逆序解法时的基本方程为•当且采用逆序解法时的基本方程为•动态规划的数学模型除基本方程外还包括边界条件，上述两种情形的边界条件依次为：•和。11()()opt{(,)()}(,1,,1)kkkkkkkkkkuDsfsvsufsknn,(,)nkniiiikVvsu,(,)nkniiiikVvsu11()()opt{(,)()}(,1,,1)kkkkkkkkkkuDsfsvsufsknn0)(11kksf11()1kkfs14•为了构造和求解动态规划的数学模型，需要明确模型中有关阶段的划分、状态变量、决策变量、允许决策集合、状态转移方程等相关因素。并注意如下几点：•（1）状态变量的确定是构造动态规划模型的关键，状态变量首先必须能够反映研究过程的演变特征，其次应包含到达这个状态前的足够信息，并且具有无后效性，即到达这个状态前的过程的决策将不影响到该状态以后的决策。状态变量可以是离散的，也可以是连续的。15•（2）决策变量是对过程进行控制的手段，复杂问题中的决策变量可以是多维变量，它的取值可以是离散的也可以是连续的。允许决策集合相当于线性规划问题中的约束条件。•（3）状态转移律sk+1=T(sk,uk),当给定sk,uk的取值后，如果sk+1的取值唯一确定，相应的多阶段决策问题称为确定性的多阶段决策问题，如果给定sk,uk的取值后，sk+1的取值不是唯一确定的，而是具有某种概率分布的随机变量，但其概率分布则由sk和uk唯一确定，这类多阶段决策过程称为随机性的多阶段决策过程。16•（4）指标函数是衡量决策过程效益高低的指标，它是定义在全过程或从k到n阶段的子过程的数量函数，为了进行动态规划的计算，指标函数必须具有递推性，即可以写成如下关系式：•Vk,n=vk(sk,uk)+Vk+1,n•或Vk,n=vk(sk,uk)•Vk+1,n17•4.逆序解法与顺序解法•动态规划问题的求解有两种疾病方法：逆序解法与顺序解法。所谓逆序解法，是从问题的最后一个阶段开始，逆多阶段决策的实际过程反向寻优，而顺序解法则从问题的最初阶段开始，顺同多阶段决策的实际过程顺序寻优。•一般地说，当初始状态给定时，用逆序解法较方便，当终止状态给定时，用顺序解法较方便。•动态规划的求解多采用逆序解法，前面讲述的都是采用逆序解法时的思路和模型。下面简单介绍顺序解法的思路与模型。18•在顺序解法中状态变量sk对应的子过程是第1阶段到第k-1阶段，阶段的指标函数是vk-1(sk,uk-1),过程的指标函数可记为：V1,k-1(u1,s2,…,uk-1,sk)。•状态转移方程可记为sk-1=T(sk,uk-1).•当V1,k-1=时，基本递推方程与边界条件为；•当V1,k-1=时，基本递推方程与边界条件为：1111()()opt{(,)()}(1,2,,)kkkkkkkkkkuDsfsvsufskn0)(10sf01()1fs1111()()opt{(,)()}(1,2,,)kkkkkkkkkkuDsfsvsufskn11kiiv11kiiv192s1s1nsns1v2v1ksks1ks1kvkvnv1kkfs当前状态121kkn已推得结果状态转移：sk=T(sk+1,uk)当前阶段本阶段递推公式fk(sk+1)=opt{vk(sk+1,uk)+fk-1(sk)}顺序解法示意图边界条件f0(s1)=02s1s1nsns1v2v1ksks1ks1kvkvnv11kkfs当前状态121kkn已推得结果状态转移：sk+1=T(sk,uk)当前阶段本阶段递推公式fk(sk)=opt{vk(sk,uk)+fk+1(sk+1)}逆序解法示意图边界条件fn+1(sn+1)=0逆序解法与顺序解法的对比图20•五、动态规划模型的分类•按过程演变的特征，动态规划模型可划分为确定性的动态规划模型与随机性动态规划模型两类；按状态变量的取值是离散还是连续的，动态规划模型又可分为离散型动态规划模型与连续型动态规划模型两类。因此动态规划的模型有：离散确定性动态规划模型、离散随机性动态规划模型、连续确定性动态规划模型和连续随机性动态规划模型四大类。