第6章__动态规划.ppt

第6章 动态规划 一、多阶段决策问题 二、基本概念和基本原理 三、动态规划模型的建立与求解 四、动态规划的应用 例6：机器负荷分配问题 某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u1的关系为 这时，机器的年完好率为b，0b1 。 假定开始生产时完好的机器数量为s，要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高？ 6.2 基本概念和基本原理 一、阶段（Stage）和阶段变量 在多阶段决策过程中，为了表示决策和过程的发展而引入阶段的概念，一个阶段就是需要作出决策的子问题。通常阶段是按照决策进行的时间或空间上的先后顺序划分的，用阶段变量k表示。 二、状态（State）和状态变量 状态表示某一阶段初所处的位置或状况，通常一个阶段包含若干个状态，描述状态的变量称为状态变量。常用sk表示第k阶段的某一状态。所有状态变量组成的集合，称为状态变量集合。常用Sk表示第k阶段的状态变量集合。 三、决策（Decision）和决策变量 决策就是某阶段状态给定以后，从该状态演变到下一阶段某状态的选择。描述决策的变量，称为决策算量。常用xk（sk）表示第k阶段当状态处于sk时的决策变量，在实际问题中，决策变量的取值往往限制在某一范围内，此范围称为允许决策集合，通常用Dk（sK）表示第k阶段的允许决策集合，显然有： 在实际过程中，可供选择的策略有一定的范围，此范围称为允许策略集合，用P表示，从允许策略集合中找出达到最优效果的策略称为最优策略。 五、状态转移方程 在多阶段决策过程中，第K阶段到第（K+1）阶段的演变规律，称为状态转移方程。当给定了第K阶段的状态变量sk和决策变量xk时，根据状态转移方程，第（k+1）阶段的状态sk+1的值也随之而定。也就是说， sk+1将依某种函数关系与（sk，xk（sk））相对应，这种对应关系常记为： 动态规划方法的基本原理 动态规划方法的基本思想： 1．动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件（简言之为基本方程），要做到这一点，必须先将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题化成一族同类型的子问题，然后逐个求解，即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。 2．在多阶段决策过程中，动态规划方法是既把前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的。 3．在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐次变换得到，从而确定了最优路线。 动态规划最优化原理：“作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。” 资源分配问题，是指将供应量有限的一种或若干种资源（如原材料、资金、机器设备、劳力、食品、运输工具等），恰当地分配给若干个使用者，而使目标函数最优。 设有某种原料，总量为M，拟用来进行n种生产活动。若分配数量为Xi的原料用于第i种生产活动，其收益为gi（xi），问应如何分配，才能使n种生产活动的总收益最大？ 机器负荷分配问题 例：某港口有某种装卸设备125台，据估计，这种设备5年后将被其他新设备所代替，此设备如在高负荷下工作，年损坏率为1/2，年利润为10万元；如在低负荷下工作，年损坏率为1/5，年利润为6万元。问应如何安排这些装卸设备的生产负荷，才能使5年内获得最大的利润？ 生产与存贮问题 第四步，状态转移方程 即第k+1阶段船的可装载量等于第k阶段船的可装载量与装载量之差。 第五步，指标函数。阶段指标函数即为第k阶段装载xk件货物时所创的利润vkxk。 第六步，函数基本方程。 k=3时 计算结果见表。 0 1 2 3 0 1 2 0 0 0 0 1 1 1 0 0 0 0 18 18 18 0 0 0 0 0 18 0 18 0