《动态规划模型》PPT课件.ppt

动态规划模型,例1：最短线路问题,问题：现选择一条从 到 的铺管线路，使总距离最短？,若用穷举法要算23222148种不同线路，比较这48种结果即可得出，但当段数增加，且各段选择也增加时，穷举法将变得非常庞大，以至利用计算机都十分困难。,下面用动态规划的方法计算,最短线路问题的特性：,如果最短线路在第k站通过点，则这一线路在由 出发到达终点的那一部分线路，对于从 点到达终点的所有可能选择的不同线路来说，必定也是距离最短的。（反正法）,最短线路问题的这一特性启示我们，从最后一段 开始，用从后向前逐步递推的方法，求出各点到 的最短线路，最后求得从 到 的最短线路。,k6时：,设 表示由 到 的最短距离；,设 表示由 到 的最短距离；,显然,k5时：,如果 表示由 到 的最短距离。,最短线路是,最短线路是,最短线路是,k4时：,最短线路是,最短线路是,最短线路是,k3时：,最短线路是,最短线路是,最短线路是,最短线路是,k2时：,最短线路是,最短线路是,出发点只有,最短线路是,最短距离为18。,说明,1)此例揭示了动态规划的基本思想。,2)动态规划方法比穷举法（48种）大大节省了计算量。,3)计算结果不仅得到了 到 的最短线路和最短距离，而且得到了其它各点到 的最短线路和最短距离，这对于很多实际问题来说是很有用处的。,动态规划法求解的数学描述,讨论动态规划中最优目标函数的建立，一般有下列术语和步骤：,、阶段,用动态规划求解多阶段决策系统时，要根据具体情况，将系统适当地分成若干个阶段，以便分若干个阶段求解，描述阶段的变量称为阶段变量。,上例分六个阶段，是一个六阶段的决策过程。例中由系统的最后阶段向初始阶段求最优解的过程称为动态规划的逆推解法。,、状态,状态表示系统在某一阶段所处的位置或状态。,上例中第一阶段有一个状态，,第二阶段有两个状态，,过程的状态可用状态变量 来描述，某个阶段所有可能状态的全体可用状态集合来描述，,、决策,某一阶段的状态确定之后，从该状态演变到下一阶段某一状态所作的选择称为决策。描述决策的变量称为决策变量,如上例中在第k阶段用 表示处于 状态时的决策变量。,决策变量限制的范围称为允许决策集合。,用 表示第k阶段从 出发的决策集合。,、策略,由每阶段的决策(i1,2,n)组成的决策函数序列称为全过程策略或简称策略，用p表示，,由系统的第k个阶段开始到终点的决策过程称为全过程的后部子过程，相应的策略称为后部子过程策略。,用 表示k子过程策略，,对于每一个实际的多阶段决策过程，可供选择的策略有一定的范围限制，这个范围称为允许策略集合。,允许策略集合中达到最优效果的策略称为最优策略。,、状态转移,某一阶段的状态变量及决策变量取定后，下一阶段的状态就随之而定。,设第k个阶段的状态变量为，决策变量为，则第k+1个阶段的状态 用 表示从k阶段到k+1阶段的状态转移规律，称它为状态转移方程。,、阶段效益,系统某阶段的状态一经确定，执行某一决策所得的效益称为阶段效益，它是整个系统效益的一部分，是 阶段状态和 阶段决策的函数，记为,、指标函数,指标函数是系统执行某一策略所产生的效益的数量表示，根据不同的实际问题，效益可以是利润、距离、产量或资源的耗量等。,指标函数可以定义在全过程上，也可以定义在后部子过程上。指标函数往往是各阶段效益的某种和式，取最优策略时的指标函数称为最优策略指标。,如上例中，表示从 出发到终点 的最优策略指标。,上例中 显然为零，称它为边值条件。,而动态规划的求解就是对kn,n-1,2,1逐级求出最优策略指标的过程。,、动态规划的基本方程,例2：机器负荷分配问题,某种机器可以在高低两种负荷下生产，年产量与年初投入生产的机器数有关。在高负荷下生产时，年产量，式中 为投入生产的机器数，年终的完好机器数为，称系数0.7为机器完好率。在低负荷下生产时，年产量，式中 为投入生产的机器数，机器完好率为0.9，设开始时，完好的机器数为 台，要求制定一个五年计划，在每年开始时决定如何重新分配完好机器在两种不同负荷下工作的数量，使五年的总产量最高。,解：此问题与上例类似。,设阶段变量k表示年度；,状态变量 是第k年初拥有的完好机器数（也是第k-1年度末完好机器数）。,决策变量 规定为第k年度中分配在高负荷下生产的机器数。,于是 是该年度分配在低负荷下生产的机器数。,k=2 k=3 k=4 k=5,记 表示第k年到第五年末的最高总产量,k5时,这说明第5年初要把全部完好机器投入高负荷下生产。,k4时,k3时,k2时,k1时,由此知五年最高总产量为23700,再由上递推知,高负荷生产的完好机器的最优组合简记：,这表明在前两年年初全部完好机器投入低负荷生产，后三年年初全部完好机器投入高负荷生产。,第五年末的完好机器数为,0.7397278台,在此例中，我们仅考虑最高产量，而未考虑五年计划后的完好机器数。,问题1：若计划为n个年度，怎样决策？,问题2：若要求在第5年末完好的机器数为500台，如何决策使5年总产量最高？,这类问题称为固定终端问题,由上讨论知：,状态转移方程仍为,表示第k年初开始到第5年末的最高产量，称为最优值函数，其递推关系为,k=1,2,3,4,5,其中 为第k段的效益值，即第k年的产量。,表示第6年的产量不计算在总产量之内，故为零。,由假设，,又根据(1)得,一般地，当 确定后，选择 来确定，现在 已经给定，故 已经没有选择余地，它由 和 确定。,于是,由(2)可知,最优值,最优值,类似地得到,这是五年最高产量,这表明，如果限定五年后的完好机器数为500台，则总产量低于无限制的情况，最优策略也相应有所变化，由第一年到第四年全部完好机器投入低负荷生产。,为了计算第5年投入高负荷生产的完好机器数，先计算,所以,即第5年有452台机器投入高负荷生产，其余投入低负荷生产。,