第6章_动态规划

第三部分动态规划,第一章动态规划的基本方法1动态规划的研究对象特征：包含有随时同变化的因素和变量，整个过程可以分为若干个相互联系的阶段，而且每个阶段都要做出决策。,应用：企业管理：动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等。,多阶段决策过程及实例在生产和科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干相互联系的阶段。在它的每一个阶段都需要作出决策，从而使整个过程达到最好的活动效果，因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成了一个决策系列，因而也就确定了整个过程的一条活动路线，这种把一个问题可看作是一个前后关联具有链状结构的多阶段过程（如图1所示）就称为多阶段决策过程，也称序贯决策过程，这种问题就称为多阶段决策问题。,图1链状结构的多阶段过程,多阶段决策问题很多，现举例如下：例1：最短路问题如图2，给定一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），试求一条由A到G的铺管线路，使总距离为最短（或总费用最小）。,图2,例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u1的关系为,这时，机器的年完好率为a，即如果年初完好机器的数量为u，到年终时完好的机器就为au，0a1。在低负荷下进行生产时，产品的年产量和投入生产的机器数量u2的关系为,这时，机器的年完好率为b，0b1。假定开始生产时完好的机器数量为s，要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高？,2动态规划的基本概念,一、阶段和阶段变量在多阶段决策过程中，为了表示决策和过程的发展而引入阶段的概念，一个阶段就是需要作出决策的子问题。通常阶段是按照决策进行的时间或空间上的先后顺序划分的，用阶段变量k表示。,二、状态和状态变量状态表示某一阶段初所处的位置或状况，通常一个阶段包含若干个状态，描述状态的变量称为状态变量。常用sk表示第k阶段的某一状态。所有状态变量组成的集合，称为状态变量集合。常用Sk表示第k阶段的状态变量集合。三、决策和决策变量决策就是某阶段状态给定以后，从该状态演变到下一阶段某状态的选择。描述决策的变量，称为决策变量。常用xk（sk）表示第k阶段当状态处于sk时的决策变量，在实际问题中，决策变量的取值往往限制在某一范围内，此范围称为允许决策集合，通常用Dk（sK）表示第k阶段的允许决策集合，显然有：,在实际过程中，可供选择的策略有一定的范围，此范围称为允许策略集合，用P表示，从允许策略集合中找出达到最优效果的策略称为最优策略。五、状态转移方程在多阶段决策过程中，第k阶段到第（k+1）阶段的演变规律，称为状态转移方程。当给定了第K阶段的状态变量sk和决策变量xk时，根据状态转移方程，第（k+1）阶段的状态Sk+1的值也随之而定。也就是说，sk+1将依某种函数关系与（sk,xk（sk）相对应，这种对应关系常记为：,一、动态规划方法的基本原理动态规划方法的基本思想：1动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件（简言之为基本方程），要做到这一点，必须先将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题化成一族同类型的子问题，然后逐个求解，即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。,3动态规划的基本方法,2在多阶段决策过程中，动态规划方法是既把前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的。3在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐次变换得到，从而确定了最优路线。二、动态规划的基本方程动态规划函数基本方程的一般形式为：,其中“opt”是最优化的意思，视具体的问题可能是求“max”，也可能是求“min”。动态规划最优化原理：“作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。”,动态规划最优化原理：“作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。”三、动态规划的解题步骤1划分阶段；2确定状态变量及其取值范围；3确定决策变量及其取值范围；,4建立状态转移方程。写出状态转移方法：的具体形式5确定指标函数6建立动态规划基本方程,四、最短路问题的标号法具体步骤：1给终点标号0。2再标离终点最近的一段，将距离数字分别写在该点上方的方格内。3在标下一段时，正要标号的某点到该段已标号的各点的各段长，分别加上已标号点的数字而取其中最小者，就是某点到终点的最短距离，将距离数字填入某点上方方格内，并且直线连接起来表示某点到终点的最短路线。4继续按逆推过程一直计算到起点（初始点），该点标的数即为起点到终点的最短距离。此解法称为逆序解法，也可用顺序解法，即从起点逐步计算到终点。,资源分配问题，是指将供应量有限的一种或若干种资源（如原材料、资金、机器设备、劳力、食品等），恰当地分配给若干个使用者，而使目标函数最优。设有某种原料，总量为M，拟用来进行n种生产活动。若分配数量为Xi的原料用于第i种生产活动，其收益为gi（xi），问应如何分配，才能使n种生产活动的总收益最大？,第二章动态规划的应用,1资源分配问题,x2,s2,P2(x2)+f3(s2-x2),P1(x1)+f2(5-x1),x1,s1,2机器负荷分配问题,例1：某港口有某种装卸设备125台，据估计，这种设备5年后将被其他新设备所代替，此设备如在高负荷下工作，年损坏率为1/2，年利润为10万元；如在低负荷下工作，年损坏率为1/5，年利润为6万元。问应如何安排这些装卸设备的生产负荷，才能使5年内获得最大的利润？,解：第一步，划分阶段。每一年为一个阶段，5年分为5个阶段，k=1，2，3，4，5。第二步，确定状态变量：状态变量sk为第k年年初拥有的完好设备数，且,第三步，确定决策变量。决策变量xk为第k阶段安排在高负荷下工作的设备数，且,则第k阶段安排在低负荷下工作的设备数为：,第四步，状态转移方程。由于在两种负荷下工作的设备损坏率分别为1/2和1/5，则第k+1年年初拥有的完好设备数为：,第五步，指标函数。第k阶段的指标函数为第k年可得的利润：,第六步，函数基本方程,K=5时,因f5是线性单调增函数，故得最优解x5*=s5，相应的有f5(s5)=10s5,K=4时,因f4是x4线性单调增函数，故得最优解x4*=s4，相应的有f4(s4)=15s4,K=3时,因f3是x3线性单调下降函数，故得最优解x3*=0，相应的有f3(s3)=18s3,K=2时,因f2是x2线性单调下降函数，故得最优解x2*=0，相应的有f2(s2)=20.4s2,K=1时,因f1是x1线性单调下降函数，故得最优解x1*=0，相应的有,3载货问题,例1：今有三种货物需要装船，各种货物的重量与运输利润关系如表1所示。船的最大装载能力为w=6(t)，问应如何装载才能使总利润最大？,解：第一步，划分阶段。每装一种货物为一个阶段，第二步，确定状态变量。状态变量为可用于装载第k种至第n种货物的装载量。且第三步，确定决策变量。决策变量为第k种货物的装载件数。且其中，为不大于的最大整数。,第四步，状态转移方程即第k+1阶段船的可装载量等于第k阶段船的可装载量与装载量之差。第五步，指标函数。阶段指标即为第k阶段装载xk件货物时所创的利润vkxk。第六步，函数基本方程。,k=3时,计算结果见表。,k=2时,k=1时,至此，得最大利润为f1(s1)=26。有两个最优方案：,4生产与存贮问题,例1：某船厂根据合同，从当年起连续4年年末要为客户提供规格型号相同的大型客货船，每年的交船数及生产每艘船的生产费用如表1所示。该厂的生产能力为每年6艘船。在进行生产的年度，船厂还要支出经常费60万元。若造出的船当年不交货，则每艘船每积压一年造成的积压损失费为40万元。假定开始时及第四年年末交货后均无积压船只，问船厂应如何安排这四年的生产计划，使所花的总费用为最低？,解：第一步，划分阶段。每一年度为一个阶段，4年分为4个阶段，第二步，确定状态变量。状态变量为第k阶段初贮存（积压）的船数。且必须满足以下条件：（1）不能超过本年度及以后各年度交船数的总和（2）为保证按时交船，每年年初的存船数加上本年度的最大可能生产量不应小于本年度的交船数（3）此外，还有。,第三步，确定决策变量。决策变量为第k阶段生产的船数。且必须满足以下条件：（1）不能超过每年的库存能力：（2）某年所拥有的存船数，不应超过本年度及以后各年交船数的总和：（3）某年所拥有的存船数，不应少于本年度的交船数：,第四步，状态转移方程