最优化技术基础 (2).ppt

(1)应将实际问题恰当地分割成n个子问题(n个阶段)。通常是根据时间或空间而划分的。(2)正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性．动态规划中的状态变量必须具备以下三个特征：a)要能够正确地描述受控过程的变化特征。b)要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响，如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划的模型。c)要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。3.动态规划方法的基本步骤第16页,共24页，星期六，2024年，5月(3)正确地定义决策变量及各阶段的允许决策集合Uk(sk).根据经验，一般将问题中待求的量，选作动态规划模型中的决策变量。或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时，常取前者的变量xj为后者的决策变量uk。(4)能够正确地写出状态转移方程。如果给定第k阶段状态变量sk的值，则该段的决策变量uk一经确定，第k+1段的状态变量sk+1的值也就完全确定，即有sk+1=Tk(sk,uk)(5)正确地构造出目标函数.例如常见的指标函数是取各段指标和的形式其中表示第i阶段的指标，它显然满足递推关系：第17页,共24页，星期六，2024年，5月求最短路径4.动态规划方法应用举例第18页,共24页，星期六，2024年，5月将问题分成五个阶段，第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。第19页,共24页，星期六，2024年，5月从f5(x5)到f4(x4)的递推过程用下表表示：第四阶段的递推方程为：在上表中，*表示最优值，由于决策允许集合D4(x4)中的决策是唯一的，因此这个值就是最优值。第20页,共24页，星期六，2024年，5月由此得到f4(x4)的表达式。由于这是一个离散的函数，取值用列表表示：f4(x4)的表达式D15D1?Ex4f4(x4)最优决策d4*D22D2?E第21页,共24页，星期六，2024年，5月

从f4(x4)到f3(x3)的递推过程用表格表示如下：第三阶段的递推方程为：第22页,共24页，星期六，2024年，5月由此得到f3(x3)的表达式,取值用列表表示：

第23页,共24页，星期六，2024年，5月第二阶段的递推方程为：从f3(x3)到f2(x2)的递推过程用表格表示如下：第24页,共24页，星期六，2024年，5月▲最优策略：对应于一个策略，可以由一个量化的指标来确定这个策略对应的效果，不同的策略有各自的效果。在所有可供选择的策略中，对应效果最好的策略称为最优策略。多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。由于各段决策间有机地联系着，本段决策的执行将影响到下一段的决策，以至于影响总体效果，所以决策者在每段决策时不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而作出对全局来讲是最优的决策。动态规划就是符合这种要求的一种决策方法。应指出，动态规划不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。第2页,共24页，星期六，2024年，5月(2)多阶段决策问题举例a)工厂生产过程:为了取得全年最佳经济效益，在全年的生产过程中，根据市场需求，逐月或者逐季度地根据库存和需求情况决定生产计划安排。b)设备更新问题:需要综合权衡决定设备的使用年限，使总的经济效益最好c)连续生产过程的控制问题:一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大。以上问题的发展过程都与时间因素有关，因此阶段的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间