第6章 动态规划.doc

第6章 动态规划动态规划（Dynamic Programming）是解决多阶段决策过程最优化的一种有用的数学方法。它是由美国学者Richard .Bellman 在1951年提出的，1957年他的专著动态规划一书问世，标志着运筹学的一个重要分支动态规划的诞生。动态规划也是一种将多变量问题转化为单变量问题的一种方法。在动态规划中，把困难的多阶段决策问题变换成一系列相互联系的比较容易的单阶段问题一个个地求解。动态规划是考察解决问题的一种途径 ，而不是一种特殊的算法，不像线性规划那样有统一的数学模型和算法（如单纯形法）。事实上，在运用其解决问题的过程中还需要运用其它的优化算法。因此，动态规划不像其它方法局限于解决某一类问题，它可以解决各类多阶段决策问题。动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。许多规划问题用动态规划的方法来处理，常比线性规划或非线性规划更有效。特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。本教材主要介绍动态规划的基本概念、理论和方法，并通过典型的案例说明这些理论和方法的应用。6.1动态规划的基本理论6.1.1多阶段决策过程的数学描述输 出输 入决 策阶 段状态转移（a）Sk+1SkunStage n（b）有这样一类活动过程，其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策，以使整个过程达到最佳的活动效果。任何一个阶段（stage，即决策点）都是由输入（input）、决策（decision）、状态转移律（transformation function）和输出（output）构成的，如图6-1（a）所示。其中输入和输出也称为状态（state），输入称为输入状态，输出称为输出状态。图6-1 某一阶段决策过程示意图由于每一阶段都有一个决策，所以每一阶段都应存在一个衡量决策效益大小的指标函数，这一指标函数称为阶段指标函数，用表示。显然，如图6-1（b）所示。显然，输出是输入和决策的函数，即： （6-1）式（6-1）为状态转移方程。在由n个阶段构成的过程里，前一个阶段的输出即为后一个阶段的输入。6.1.2动态规划的基本概念动态规划的数学描述离不开它的一些基本概念与符号，因此有必要在介绍多阶段决策过程的数学描述的基础上，系统地介绍动态规划的一些基本概念。（1）阶段、阶段变量阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段变量，常用k来表示。阶段的划分一般是根据时间和空间的自然特征来进行的，但要便于将问题的过程转化为多阶段决策的过程。对于具有n个阶段的决策过程，其阶段变量k1，2，n。（2）状态、状态变量状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况。状态既反映前面各阶段系列决策的结局，又是本阶段决策的一个出发点和依据；它是各阶段信息的传递点和结合点。各阶段的状态通常用状态变量Sk来加以描述。作为状态应具有这样的性质：如果某阶段状态给定后，则该阶段以后过程的发展不受此阶段以前各阶段状态的影响。换句话说，过程的历史只能通过当前的状态来影响未来，当前的状态是以往历史的一个总结。这个性质称为无后效性（the future is independent of the past）。状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合。(3) 决策、决策变量过程的某一阶段、某个状态，可以做出不同的决定(选择)，决定下一阶段的状态，这种决定称为决策。描述决策的变量，称为决策变量。决策变量是状态变量的函数，常用uk(sk)表示第k阶段当状态为sk时的决策变量。在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合。常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合，显然有 uk(sk)Dk(sk)(4)状态转移方程多阶段决策过程可以在各个阶段进行决策，去控制过程发展的多段过程；其发展是通过一系列的状态转移来实现的；系统在某一阶段的状态转移不但与系统的当前的状态和决策有关，而且还与系统过去的历史状态和决策有关。其状态转移方程如下（一般形式）能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。(5) 策略策略是一个按顺序排列的决策组成的集合。由过程的第k阶段开始到终止状态为止的过程，称为问题的后部子过程（或称为k子过程）。由每段的决策按顺序排列组成的决策函数序列称为k子过程策略，简称子策略，记为，即当k=1时，此决策函数序列成为全过程的一个策略，简称策略，记为即在实际问题中，可供选择的策略有一定范围，此范围称为允许策略集合，用p表示。从允许策略集合中找出达到最优效果的策略称为最优策略。（6）函数和最优值函数用来衡量所实现过程优劣的一种数量指标，称为指标函数，它是定义在全过程或所有后部子过程上确定的数量函数。Vk, n表示之。即动态规划模型的指标函数，应具有可分离性，并满足递推关系。即可以表示为的函数。即有如下式子常见的指标函数的形式有以下两种情况:情形1 过程和它的任一子过程的指标是它所包含的各阶段的指标和。即其中表示第j阶段的阶段指标。情形2过程和它的任意子过程的指标是它所包含的各阶段的指标的乘积。即最优值函数：表示从第k阶段的状态sk开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。即(7)多阶段决策过程的数学模型具有无后效性的多阶段决策过程所谓求解多阶段决策过程问题，就是要求出 最优策略，即最优决策序列最优目标函数值 （6-2）6.1.3动态规划的数学模型动态规划的数学模型除包括式（6-2）外，还包括阶段的划分、各阶段的状态变量和决策变量的选取、允许决策集合和状态转移律的确定等。如何获得最优指标函数呢？一个n阶段的决策过程，具有如下一些特性：（1）刚好有n个决策点；（2）对阶段而言，除了其所处的状态和所选择的决策外，再没有任何其它因素影响决策的最优性了；（3） 阶段仅影响阶段的决策，这一影响是通过来实现的；（4）贝尔曼（Bellman）最优化原理：在最优策略的任意一阶段上，无论过去的状态和决策如何，对过去决策所形成的当前状态而言，余下的诸决策必须构成最优子策略。根据贝尔曼（Bellman）最优化原理，可以将式（6-2）表示为递推最优指标函数关系式（6-3）或式（6-4）： （6-3） （6-4）利用式（6-3）和式（6-4）可表示出最后一个阶段（第n个阶段，即k=n）的最优指标函数： （6-5） （6-6）其中称为边界条件。一般情况下，第n阶段的输出状态已经不再影响本过程的策略，即式（6-5）中的边界条件，式（6-6）中的边界条件；但当问题第n阶段的输出状态对本过程的策略产生某种影响时，边界条件就要根据问题的具体情况取适当的值，这一情况将在后续例题中加以反映。已知边界条件，利用式（6-3）或式（6-4）即可求得最后一个阶段的最优指标函数；有了，继续利用式（6-3）或式（6-4）即可求得最后两个阶段的最优指标函数；有了，进一步又可以求得最后三个阶段的最优指标函数；反复递推下去，最终即可求得全过程n个阶段的最优指标函数，从而使问题得到解决。由于上述最优指标函数的构建是按阶段的逆序从后向前进行的，所以也称为动态规划的逆序算法。通过上述分析可以看出，任何一个多阶段决策过程的最优化问题，都可以用非线性规划（特殊的可以用线性规划）模型来描述；因此，从原则上讲，一般也可以用非线性规划（或线性规划）的方法来求解。那么利用动态规划求解多阶段决策过程有什么优越性、又有什么局限性呢？动态规划的优点：（1）求解更容易、效率更高。动态规划方法是一种逐步改善法，它把原问题化成一系列结构相似的最优化子问题，而每个子问题的变量个数比原问题少得多，约束集合也简单得多，故较易于确定最优解。（2）解的信息更丰富。非线性规划（或线性规划）的方法是对问题的整体进行一次性求解的，因此只能得到全过程的解；而动态规划方法是将过程分解成多个阶段进行求解的，因此不仅可以得到全过程的解，同时还可以得到所有子过程的解。动态规划的缺点：（1）没有一个统一的标准模型。由于实际问题不同，其动态规划模型也就各有差异，模型构建存在一定困难。（2）应用条件苛刻。由于构造动态规划模型状态变量必须满足“无后效性”条件，这一条件不仅依赖于状态转移律，还依赖于允许决策集合和指标函数的结构，不少实际问题在取其自然特征作为状态变量时并不满足这一条件，这就降低了动态规划的通用性。（3）状态变量存在“维数障碍”。最优指标函数是状态变量的函数，当状态变量的维数增加时，最优指标函数的计算量将成指数倍增长；因此，无论是手工计算还是电算“维数障碍”都是无法完全克服的。6.2确定性动态规划问题确定性动态规划问题即阶段的输出状态完全由其输入状态和决策所决定的动态规划问题。确定性动态规划解决的问题可能包含经济管理的方方面面，可以是最短路线问题，可以是资源配置问题，也可以是其他的规划优化问题。最短路线问题直观、具体地演示了动态规划的基本概念和基本步骤；因此，让我们首先来分析一下最短路线问题。6.2.1最短路线问题例6-1美国黑金石油公司（The Black Gold Petroleum Company）最近在阿拉斯加（Alaska）的北斯洛波（North Slope）发现了大的石油储量。为了大规模开发这一油田，首先必须建立相应的输运网络，使北斯洛波生产的原油能运至美国的3个装运港之一。在油田的集输站（结点C）与装运港（结点P1、P2、P3）之间需要若干个中间站，中间站之间的联通情况如图6-2所示，图中线段上的数字代表两站之间的距离（单位：10千米）。试确定一最佳的输运线路，使原油的输送距离最短。解：最短路线有一个重要性质，即如果由起点A经过B点和C点到达终点D是一条最短路线，则由B点经C点到达终点D一定是B到D的最短路（贝尔曼最优化原理）。此性质用反证法很容易证明，因为如果不是这样，则从B点到D点有另一条距离更短的路线存在，不妨假设为BPD；从而可知路线ABPD比原路线ABCD距离短，这与原路线ABCD是最短路线相矛盾，性质得证。根据最短路线的这一性质，寻找最短路线的方法就是从最后阶段开始，由后向前逐步递推求出各点到终点的最短路线，最后求得由始点到终点的最短路；即动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。按照动态规划的方法，将此过程划分为4个阶段，即阶段变量；取过程在各阶段所处的位置为状态变量，按逆序算法求解。CP3P2P1M11M12M21M22M23M31M32M33M34101286911107697511468643776534k=1k=2k=3k=4图6-2 例6-1的图 当时：由结点M31到达目的地有两条路线可以选择，即选择P1或P2；故： 选择P2由结点M32到达目的地有三条路线可以选择，即选择P1、P2或P3；故： 选择P2由结点M33到达目的地也有三条路线可以选择，即选择P1、P2或P3；故： 选择P3由结点M34到达目的地有两条路线可以选择，即选择P2或P3；故： 选择P2当时：由结点M21到达下一阶段有三条路线可以选择，即选择M31、M32或M33；故： 选择M32由结点M22到达下一阶段也有三条路线可以选择，即选择M31、M32或M33；故： 选择M32或M33由结点M23到达下一阶段也有三条路线可以选择，即选择M32、M33或M34；故： 选择M33或M34当时：由结点M11到达下一阶段有两条路线可以选择，即选择M21或M22；故： 选择M22由结点M12到达下一阶段也有两条路线可以选择，即选择M22或M23；故： 选择M22当时：由结点C到达下一阶段有两条路线可以选择，即选择M11或M12；故： 选择M11从而通过顺序（计算的反顺序）追踪（黑体标示）可以得到两条最佳的输运线路：CM11M22M32P2；CM11M22M33P3。最短的输送距离是280千米。6.2.2资源分配问题资源分配问题就是将数量一定的一种或若干种资源（例如原材料、资金、设备、设施、劳力等等），恰当地分配给若干使用者或地区，从而使目标函数为最优。设有m种资源，总量分别为bi（i = 1,2,m），用于生产n种产品，若用xij代表用于生产第j种产品的第i种资源的数量（j = 1,2,n），则生产第j种产品的收益是其所获得的各种资源数量的函数，即gj = f（x1j,x2j, xmj）。由于总收益是n种产品收益的和，此问题可用如下静态模型加以描述： 若xij是连续变量，当gj = f（x1j,x2j, xmj）是线性函数时，该模型是线性规划模型；当gj = f（x1j,x2j, xmj）是非线性函数时，该模型是非线性规划模型。若xij是离散变量或（和）gj = f（x1j,x2j, xmj）是离散函数时，此模型用线性规划或非线性规划来求解都将是非常麻烦的。然而在此情况下，由于这类问题的特殊结构，可以将它看成为一个多阶段决策问题，并利用动态规划的递推关系来求解。在一维资源的分配问题中，设状态变量Sk表示分配于从第k个阶段至过程最终（第N个阶段）的资源数量，即第k个阶段初资源的拥有量；决策变量xk表示第k个阶段资源的分配量。于是有状态转移律：允许决策集合：最优指标函数（动态规划的逆序递推关系式）： （6-7）利用这一递推关系式，最后求得的即为所求问题的最大总收益，下面来看一个具体的例子。例6-2 某公司拟将500万元的资本投入所属的甲、乙、丙三个工厂进行技术改造，各工厂获得投资后年利润将有相应的增长，增长额如表6-1所示。试确定500万元资本的分配方案，以使公司总的年利润增长额最大。解：将问题按工厂分为三个阶段，设状态变量（）代表从第个工厂到第3个工厂的投资额，决策变量代表第个工厂的投资额。于是有状态转移率、允许决策集合和递推关系式： 表6-1 例6-2的收益表投资额100万元200万元300万元400万元500万元甲307090120130乙50100110110110丙4060110120120当时：于是有表6-2，表中表示第三个阶段的最优决策。表6-2 例6-2中的计算表 （单位：百万元）0 1234501234500.40.61.11.21.2当时：于是有表6-3。表6-3 例6-2中的计算表 （单位：百万元）x2S2g2（x2）+f3（s2 - x2）01234500+00010+0.40.5+00.5120+0.60.5+0.41.0+01.0230+1.10.5+0.61.0+0.41.1+01.4240+1.20.5+1.11.0+0.61.1+0.41.1+01.61，250+1.20.5+1.21.0+1.11.1+0.61.1+0.41.1+02.12当时：于是有表6-4。表6-4 例6-2中的计算表 （单位：百万元）x1S1g1（x1）+f2（s1 x1）01234550+2.10.3+1.60.7+1.40.9+1.01.2+0.51.3+02.10，2然后按计算表格的顺序反推算，可知最优分配方案有两个：（1）甲工厂投资200万元，乙工厂投资200万元，丙工厂投资100万元；（2）甲工厂没有投资，乙工厂投资200万元，丙工厂投资300万元。按最优分配方案分配投资（资源），年利润将增长210万元。这个例于是决策变量取离散值的一类分配问题，在实际问题中，相类似的问题还有销售店的布局（分配）问题、设备或人力资源的分配问题等。在资源分配问题中，还有一种决策变量为连续变量的资源分配问题，请见例6-3。例6-3 机器负荷分配问题。某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的产量（件）函数为，其中为投入高负荷生产的机器数量，年度完好率（年底的完好设备数等于年初完好设备数的70%）；在低负荷下生产的产量（件）函数为，其中为投入低负荷生产的机器数量，年度完好率。假定开始生产时完好的机器数量为1000台，试问每年应如何安排机器在高、低负荷下的生产，才能使5年生产的产品总量最多？解：设阶段表示年度（）；状态变量为第年度初拥有的完好机器数量（同时也是第年度末时的完好机器数量）。决策变量为第年度分配高负荷下生产的机器数量，于是为该年度分配在低负荷下生产的机器数量。这里的和均为连续变量，它们的非整数值可以这样理解：如就表示一台机器在第年度中正常工作时间只占全部时间的60%；就表示一台机器在第年度中只有30%的工作时间在高负荷下运转。状态转移方程为：允许决策集合：设阶段指标为第年度的产量，则：过程指标是阶段指标的和，即：令最优值函数表示从资源量出发，采取最优子策略所生产的产品总量，因而有逆推关系式：边界条件。当时：因是关于的单调递增函数，故取，相应有。当时：因是关于的单调递增函数，故取，相应有；依次类推，可求得：当时：，当时：，当时：，计算结果表明最优策略为：，；即前两年将全部设备都投入低负荷生产，后三年将全部设备都投入高负荷生产，这样可以使5年的总产量最大，最大产量是23700件。有了上述最优策略，各阶段的状态也就随之确定了，即按阶段顺序计算出各年年初的完好设备数量。上面所讨论的过程始端状态是固定的，而终端状态是自由的，实现的目标函数是5年的总产量最高。如果在终端也附加上一定的约束条件，如规定在第5年结束时，完好的机器数量不低于350台（上面的例子只有278台），问应如何安排生产，才能在满足这一终端要求的情况下使产量最高呢？解：阶段表示年度（）；状态变量为第年度初拥有的完好机器数量；决策变量为第年度分配高负荷下生产的机器数量；状态转移方程为：终端约束：允许决策集合：“加”第阶段的终端递推条件对于，考虑终端递推条件有：同理其他各阶段的允许决策集合可在过程指标函数的递推中产生。设阶段指标：过程指标：最优值函数：边界条件。当时：因是关于的单调递增函数，故取，相应有：即： ，当时： 由可得，又因是关于的单调递减函数，故取，相应有：，当时： 由可得，又因是关于的单调递减函数，故取，相应有：由于，所以是恒成立的，即。，当时： 因是关于的单调递减函数，而的取值并不对有下界的约束，故取，相应有：，当时： 因是关于的单调递减函数，故取，相应有：，计算结果表明最优策略为：（1）第1年将全部设备都投入低负荷生产。，（2）第2年将全部设备都投入低负荷生产。，（3）第3年将台完好设备投入高负荷生产，将剩余的台完好设备投入低负荷生产。（4）第4年将台完好设备均投入高负荷生产，将剩余的1台完好设备均投入低负荷生产。（5）第5年将，即将台完好设备均投入高负荷生产。前面讲的是一种资源的分配问题，如果有两种原料，数量各为和个单位，需要分配用于生产种产品。如果用于生产第种产品需要第一种原料个单位，第二种原料个单位，其收入为。问应如何分配这两种原料于种产品的生产，使总收入最大？此问题的静态规划模型如下：种产品的分配分为个阶段（），假设状态变量，其中表示分配用生产第种产品至第种产品的第一种原料的数量，表示分配用生产第种产品至第种产品的第二种原料的数量。决策变量中表示分配给第种产品的第一种原料的数量，表示分配给第种产品的第二种原料的数量。最优化函数表示以第一种原料个单位和第二种原料分配生产第种产品至第种产品时所得的最大收入。那么动态规划的基本方程如下： （6-8)通过这个基本方程得到的就是所求的最大收入。例6-4 如果以上的二维资源分配问题的，其如下表，求如何合理分配，使总收入最大？表6-5 例6-4收益数据表 （单位：万元） g yx012013012001302403514561462572567468479下面用动态规划方法解这个问题，根据上式（6-8）知当时，由于，得，如下表： 表6-6 例6-4中的计算表 f us012003512572479当时，由于可计算得到和相应的最优决策：同理，可得出，。所以，得出的和最优决策如下表。表 6-7 例6-4中的计算表035257479（0，0）（0，0）（0，0），（0，1）（0，0）（0，0）（0，0），（0，1），（1，1）（0，0），（2，0）（0，0），（2，0）（0，0），（0，1），（1，1），（2，0），（2，1） 当时，利用 所以，那么，最大的总收入为。通过反推可得，最优策略为三种为：在实际问题中，由于的复杂性，常采用以下方法格子点法、逐次逼近法和Lagrange乘子法进行简化和降维，来求它的解或近似解。可参阅数学规划的书籍了解这些方法。6.2.3生产存贮控制问题在生产和经营管理中， 由于供给与需求在时间上存在差异，需要在供给与需求之间构建存贮环节以平衡这种差异。存贮物资需要付出资本占用费和保管费等，过多的物资储备意味着浪费；而过少的储备又会影响需求造成缺货损失。存贮控制问题就是要在平衡双方的矛盾中，寻找最佳的采购批量和存贮量，以期达到最佳的经济效果。例6-5 某鞋店销售一种雪地防潮鞋，以往的销售经历表明，此种鞋的销售季节是从10月1日至3月31日。下个销售季节各月的需求预测值如表6-8所示。表6-8 各月的需求预测值表 (单位：双)月份101112123需求402030403020该鞋店的此种鞋完全从外部生产商进货，进货价每双4美元。进货批量的基本单位是箱，每箱10双。由于存贮空间的限制，每次进货不超过5箱。对应不同的订货批量，进价享受一定的数量折扣，具体数值如表6-9所示。表6-9 订货批量的折扣表进货批量1箱2箱3箱4箱5箱数量折扣4%5%10%20%25%假设需求是按一定速度均匀发生的，订货不需时间，但订货只能在月初办理一次，每次订货的采购费（与采购数量无关）为10美元。月存贮费按每月月底鞋的存量计，每双0.2美元。由于订货不需时间，所以销售季节外的其他月份的存贮量为“0”。试确定最佳的进货方案，以使总的销售费用最小。解：阶段：将销售季节6个月中的每一个月作为一个阶段，即；状态变量：第阶段的状态变量代表第个月初鞋的存量；决策变量：决策变量代表第个月的采购批量；状态转移律：（是第个月的需求量）；边界条件：，；阶段指标函数：代表第个月所发生的全部费用，即与采购数量无关的采购费、与采购数量成正比的购置费和存贮费。其中：；最优指标函数：最优指标函数具有如下递推形式当时（3月）计算过程见表6-10，表6-10 例6-4当的计算表S601020x620100f6（S6）86480当时（2月）计算过程见表6-11，表6-11 例6-4中当的计算表x5S501020304050020418816450164101721681424014220134136122301223086989008640505205050404当时（1月）计算过程见表6-12，表6-12 例6-4中当的计算表x4S4010203040500302304403021028228228630、4028220250262264252202503021223024423021810212401641922122101961700164501441741781761520144601261401441320126当时（12月）计算过程见表6-13，表6-13 例6-4中当的计算表x3S30102030405004204224145041410388402392384503842035037037236233250332303023323403423103140302402843023102902922980284当时（11月）计算过程见表6-14，表6-14 例6-4中当的计算表x2S2010203040500500504474468504681046247245444645240446当时（10月）计算过程见表6-15表6-15 例6-4中当的计算表x1S101020304050060660840606利用状态转移律，按上述计算的逆序可推算出最优策略：10月份采购4箱（40双），11月份采购5箱（50双），12月份不采购，1月份采购4箱（40双），2月份采购5箱（50双），3月份不采购；最小的销售费用为606美元。6.2.4 用动态规划求解非线性规划问题非线性规划问题的求解（在第5章中讨论）是非常困难的；然而，对于有些非线性规划问题，如果转化为用动态规划来求解将是十分方便的。例6-6用动态规划求解解：阶段：将问题的变量数作为阶段，即；决策变量：决策变量；状态变量：状态变量代表第阶段的约束右端项，即从到占有的份额；状态转移律：；边界条件：，；允许决策集合：当时：当时：设，于是令，可得或又因，所以：，是的极小值点，是的极大值点于是：当时：同上可得：由，有由，有于是得到最优解，最优值。6.3随机性动态规划问题随机性动态规划不同于确定性动态规划，它在下一个阶段的状态是不完全由当前阶段的状态和决策策略决定。而是对于下一个状态将来会有一个概率分布。然而，这个概率分布完全由当前阶段的状态及决策策略决定。在模型中，由于存在某种不确定性，因此目标的优化是依据期望值来进行的。下面通过几种典型的示例，介绍随机性动态规划的求解。例6-7某公司承担一种新产品的试制任务，合同要求3个月内提供一台合格的样品，否则将支付15万元的赔偿费。据估计，投产一台进行试制时，成功的概率是；投产一批的固定费用为0.5万元，每台的试制费为0.8万元；试制周期为1个月。试确定最佳的试制计划，使总的期望费用最小。解：阶段：将每个试制周期（1个月）作为一个阶段，即；决策变量：决策变量代表第阶段投产试制的台数；状态变量：状态变量代表第阶段初是否已获得合格样品，尚无合格样品时，已获得合格样品时；允许决策集合：状态转移律：，；边界条件：，；阶段指标函数：最优指标函数：当时计算过程见表6-16，表6-16 例6-5中当的计算表x3S3012345600011511.38.777.346.666.486.6256.48当时计算过程见表6-17，表6-17 例6-5中当的计算表x2S2012345600016.485.624.984.824.9834.82当时计算过程见表6-18，表6-18 例6-5中当的计算表x1S1012345614.824.584.245.7624.24即该公司的最佳试制计划为：第一个月初投产试制2台；如果在第二个月初无合格样品出现，再投产试制3台；如果在第三个月初仍然无合格样品出现，再投产试制5台。按此最佳试制方案最小期望总费用是4.24万元。例6-8 某公司生产上需要在近4周内采购一批原材料，估计在未来4周内价格会有一定的波动，假设价格波动具有4种状态50、60、70和80元，其概率分别为0.2、0.3、0.4和0.1。试确定该公司的原材料最佳采购计划，以使期望采购价格最小。解：阶段：将每一周作为一个阶段，即；决策变量：决策变量代表第周是否决定采购，代表第周决定采购，代表第周决定等待；状态变量：状态变量代表第周原材料的市场价格；中间变量：代表第周决定等待，而在以后采取最佳子策略时的采购价格期望值；最优指标函数：是否采购决定于目前市场价格与等待价格期望值的相对大小，如果前者大于后者，应决定等待；如果前者小于后者，则应决定采购。于是：边界条件：对于第4周，因为没有继续等待的余地，所以：即：、当时：只有采购一种选择、当时：于是：即第三周的最佳决策为：当时：于是：即第二周的最佳决策为：当时：于是：即第一周的最佳决策为：由以上计算可知，最佳的采购策略为：第一周只有价格是50时才采购，否则就等待；第二周、第三周只要价格不超过60就要采购，否则继续等待；如果已经等待到了第四周，那么无论什么价格都只有采购，别无选择。6.4 动态规划软件求解简介6.4.1 使用MATLAB求解动态规划简介 Matlab动态规划逆序法函数格式： functionp_opt,fval=dynprog(x,DecisFun,ObjFun,TransFun)这是自由始端和终端的动态规划，求指标函数最小值的逆序算法递归计算程序，是状态变量，每列表示一个阶段状态；函数是阶段指标函数；函数是状态转移函数。其中是阶段的某状态变量，是相应的决策变量，输出由四列组成，=序列组；最优策略组；最优轨线组；指标函数组；是一个列向量，各元素分别表示各最优策略对应始端状态的最优函数值。k=length(x(1,:);f_opt=nan*ones(size(x);d_opt=f_opt;t_vubm=inf*ones(size(x);x_isnan=isnan(x);t_vub=inf;%计算终端相关值tmp1=find(x_isnan(:,k);tmp2=length(tmp1);for i=1:tmp2 u=feval(DecisFun,k,x(i,k);tmp3=length(u);for j=1:tmp3 tmp=feval(ObjFun),k,x(tmp1(i),k),u(j); if tmpt_vub f_opt(i,k)=tmp;d_opt(i,k)=u(j);t_vub=tmp; end;end;end%逆推计算各阶段的递归调用程序for ii=k-1:-1:1 tmp10=find(x_isnan(:,ii);tmp20=length(tmp10); for i=1:tmp20 u=feval(DecisFun,ii,x(i,ii);tmp30=length(u); for j=1:tmp30 tmp00=feval(ObjFun,ii,x(tmp10(i),ii),u(j); tmp40=feval(TransFun,ii,x(tmp10(i),ii),u(j); tmp50=x(:,ii+1)-tmp40; tmp60=find(tmp50=0); ifisempty(tmp60) tmp00=tmp00+f_opt(tmp60(1),ii+1); if tmp00 x=nan * ones(3,5); x(1,1)=1; x(1:3,2)=(2:4); x(1:3,3)=(5:7); x(1:2,4)=(8:9); x(1:5)=10; p,f=dynprog(x,eg6.5.1_1,eg6.5.1_2,eg6.5.1_3)得到，由和可见，最短距离为12，其顺序为1，4，6，9，10，