运筹学课程动态规划.ppt

NEUQ 动态规划动态规划Dynamic Programming 不要过河拆桥不要过河拆桥 追求全局最优追求全局最优1NEUQ 多阶段决策过程的最优化多阶段决策过程的最优化 动态规划的基本概念和基本原理动态规划的基本概念和基本原理 动态规划方法的基本步骤动态规划方法的基本步骤 动态规划方法应用举例动态规划方法应用举例本章内容本章内容2NEUQ一、多阶段决策过程的最优化一、多阶段决策过程的最优化示例示例1 1（工厂生产安排）：（工厂生产安排）：某种机器可以在高、低两种负荷下生产。高负荷生产条某种机器可以在高、低两种负荷下生产。高负荷生产条件下机器完好率为件下机器完好率为0.70.7，即如果年初有，即如果年初有u u台完好机器投入生产，台完好机器投入生产，则年末完好的机器数量为则年末完好的机器数量为0.70.7u u台。系数台。系数0.70.7称为完好率。年称为完好率。年初投入高负荷运行的初投入高负荷运行的u u台机器的年产量为台机器的年产量为8 8u u吨。系数吨。系数8 8称为单称为单台产量。低负荷运行时，机器完好率为台产量。低负荷运行时，机器完好率为0.90.9，单台产量为，单台产量为5 5吨。吨。设开始时有设开始时有10001000台完好机器，要制订五年计划，每年年初将台完好机器，要制订五年计划，每年年初将完好的机器一部分分配到高负荷生产，剩下的机器分配到低完好的机器一部分分配到高负荷生产，剩下的机器分配到低负荷生产，使五年的总产量为最高。负荷生产，使五年的总产量为最高。3NEUQ 设有数量为设有数量为y y的某种资源，将它分别投入两的某种资源，将它分别投入两种生产方式种生产方式A A和和B B，已知收益函数分别是，已知收益函数分别是g(x)g(x)和和h(x)h(x)，x x为资源投入量。设这种资源用于生产后为资源投入量。设这种资源用于生产后还可以回收一部分用于生产，还可以回收一部分用于生产，A A、B B的回收率分别的回收率分别为为a a和和b b（0a10a1，0b1 0b1），），问：问：对总数量为对总数量为y y的资源进行的资源进行n n个阶段的生产，个阶段的生产，应如何分配每个阶段投入应如何分配每个阶段投入A A、B B的资源数量，才能的资源数量，才能使总收益最大？使总收益最大？推广：多阶段资源分配问题推广：多阶段资源分配问题4NEUQ示例示例2 2（设备更新问题）：（设备更新问题）：一般企业用于生产活动的设备，刚买来一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理时故障少，经济效益高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使减少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费因此就卖去旧的买新的，还需要付出更新费因此就需要综合权衡决定设备的使用年限，使总的经需要综合权衡决定设备的使用年限，使总的经济效益最好。济效益最好。5NEUQ 一般化工生产过程中，常包含一系列完成一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工一工序设备的输入，因此，应该如何根据各工序的运行工况，控制生产过程中各设备的输入序的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大。和输出，以使总产量最大。示例示例3 3 （连续生产过程的控制问题）：（连续生产过程的控制问题）：6NEUQ示例示例4 4、最短路径问题、最短路径问题给定一个交通网络图如下，其中两点之间的数字表示距离给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从（或花费），试求从A点到点到G点点的最短距离（总费用最小）。的最短距离（总费用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687636853384222133352566437NEUQ 示例示例5 5（生产与存储问题）：（生产与存储问题）：某工厂生产并销售某种产品。已知今后四个月市场需求某工厂生产并销售某种产品。已知今后四个月市场需求预测及每月生产预测及每月生产j个单位产品的费用如下：个单位产品的费用如下：每月库存每月库存i个个单位产品的费用单位产品的费用E(i)=0.5i(千元），该厂最大千元），该厂最大库存容量为库存容量为3 3个单位，每月最大生产能力为个单位，每月最大生产能力为6 6个单位，计划开个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。满足用户需求条件下，使总费用最小。每个月视为一个阶段，每个月视为一个阶段，每个阶段都须决定生产几个、库存几个每个阶段都须决定生产几个、库存几个 上一个阶段的决策直接影响下一个阶段的决策上一个阶段的决策直接影响下一个阶段的决策月月1234需求需求23248NEUQ 由于航天飞机的运动的环境是不断变化的，由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。使之能最省燃料和实现目的（如软着落问题）。示例示例6 6（航天飞机飞行控制问题）：（航天飞机飞行控制问题）：9NEUQ 所谓所谓多阶段决策问题是多阶段决策问题是指一类活动过程，它可以分指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。的初始状态。每个阶段的决策均确定以后，就得到一个决策序列，每个阶段的决策均确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。的效益的总和达到最优。动态规划是用来解决多阶段决策过程最优化的一种动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个数量方法。其特点在于，它可以把一个n n 维决策问题变维决策问题变换为几个一维最优化问题，从而一个一个地去解决。换为几个一维最优化问题，从而一个一个地去解决。12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策10NEUQ 不包含时间因素的静态决策问题（本质上是一次决策问不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。题用动态规划方法来解决。某些线性规划、非线性规划等静态规划问题也可以通过某些线性规划、非线性规划等静态规划问题也可以通过适当地引入阶段的概念，应用动态规划方法加以解决。适当地引入阶段的概念，应用动态规划方法加以解决。DP是上个世纪五十年代贝尔曼是上个世纪五十年代贝尔曼(B.E.Bellman)为代表为代表的研究成果，属于现代控制理论的一部分。其最优化原理，的研究成果，属于现代控制理论的一部分。其最优化原理，可归结为一个递推公式。可归结为一个递推公式。注意：注意：动态规划是求解某类多阶段决策问题的一种方法，是动态规划是求解某类多阶段决策问题的一种方法，是考察问题的一种考察问题的一种途径途径，不是一种算法。必须对具体问题进，不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。型，然后再用动态规划方法去求解。11NEUQ 动态规划思想示例：动态规划思想示例：BACBDBCDEC41231231232216472483867561106375112NEUQ 以上求从以上求从A到到E的最短路径问题，可以转化为四个性质完的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从全相同，但规模较小的子问题，即分别从 A A到到E E的最短路径问题。的最短路径问题。第四阶段：两个始点第四阶段：两个始点 和和 ，终点只有一个；，终点只有一个；阶段阶段4本阶段始点本阶段始点（状态）（状态）本阶段各终点（决策）本阶段各终点（决策）到到E的最短距离的最短距离本阶段最优终点本阶段最优终点（最优决策（最优决策)E D1 D2 10 6 10 6 E E 分析得知：从分析得知：从 和和 到到E E的最短路径唯一。的最短路径唯一。13NEUQ 第三阶段：有三个始点第三阶段：有三个始点C1，C2，C3，终点有，终点有D1，D2，对始点，对始点和终点进行分析和讨论分别求和终点进行分析和讨论分别求C1，C2，C3到到D1，D2 的最短路的最短路径问题：径问题：分析得知：如果经过分析得知：如果经过C1，则最短路为则最短路为C1-D2-E；如果经过如果经过C2，则最短路为则最短路为C2-D2-E；如果经过如果经过C3，则最短路为，则最短路为C3-D1-E。阶段阶段3本阶段始点本阶段始点（状态）（状态）本阶段各终点（决策）本阶段各终点（决策）到到E的最短距离的最短距离本阶段最优终点本阶段最优终点（最优决策（最优决策)D1 D2 C1 C2 C3 8+10=18 7+10=17 1+10=11 6+6=12 5+6=11 6+6=12 12 11 11 D2 D2 D114NEUQ 第第二二阶阶段段：有有4个个始始点点B1,B2,B3,B4，终终点点有有C1,C2,C3。对对始始点点和和终终点点进进行行分分析析和和讨讨论论分分别别求求B1,B2,B3,B4到到C1,C2,C3 的的最最短路径问题：短路径问题：分析得知：如果经过分析得知：如果经过B1，则走，则走B1-C2-D2-E；如果经过如果经过B2，则走，则走B2-C3-D1-E；如果经过如果经过B3，则走，则走B3-C3-D1-E；如果经过如果经过B4，则走，则走B4-C3-D1-E。阶段阶段2本阶段始点本阶段始点（状态）（状态）本阶段各终点（决策）本阶段各终点（决策）到到E的最短的最短距离距离本阶段最优终本阶段最优终点（最优决策点（最优决策)C1 C2 C3 B1 B2 B3 B4 2+12=14 4+12=16 4+12=16 7+12=19 1+11=12 7+11=18 8+11=19 5+11=16 6+11=17 2+11=13 3+11=14 1+11=12 12 13 14 12 C2 C3 C3 C315NEUQ第一阶段：只有第一阶段：只有1个始点个始点A，终点有，终点有B1,B2,B3,B4。对始点和终。对始点和终点进行分析和讨论分别求点进行分析和讨论分别求A到到B1,B2,B3,B4的最短路径问题：的最短路径问题：最后，可以得到：从最后，可以得到：从A到到E的最短路径为的最短路径为A B4 C3 D1 E 阶段阶段1本阶段始本阶段始点点(状态状态)本阶段各终点（决策）本阶段各终点（决策）到到E的最的最短距离短距离本阶段最优终本阶段最优终点点(最优决策最优决策)B1 B2 B3 B4 A 4+12=16 3+13=163+14=172+12=14 14 B416NEUQ 以上计算过程及结果，可用下图表示，可以看到，以上方以上计算过程及结果，可用下图表示，可以看到，以上方法不仅得到了从法不仅得到了从A到到D的最短路径，同时，也得到了从图中的最短路径，同时，也得到了从图中任一点到任一点到E的最短路径。的最短路径。以上过程，仅用了以上过程，仅用了22次加法，计算效率远高于穷举法。次加法，计算效率远高于穷举法。BACBDBCDEC4123123123321647248386751610601061211111213141412751217NEUQ二、动态规划的基本概念和基本原理二、动态规划的基本概念和基本原理 基本概念基本概念 1、阶段：、阶段：把一个问题的过程，恰当地分为若干个相互联系的把一个问题的过程，恰当地分为若干个相互联系的阶段阶段，以便，以便于按一定的次序去求解。于按一定的次序去求解。描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量。阶段的划分，一般是根据时间。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。和空间的自然特征来进行的，但要便于问题转化为多阶段决策。2、状态：、状态：表示每个阶段开始所处的表示每个阶段开始所处的自然状况或客观条件自然状况或客观条件。通常。通常一个阶段有若干个状态，描述过程状态的变量称为一个阶段有若干个状态，描述过程状态的变量称为状态变量状态变量。年、月、年、月、路段路段一个数一个数一组数一组数一个向一个向量量 状态变量的取值有一定的允许集合或范围，此集合称为状态变量的取值有一定的允许集合或范围，此集合称为状态状态允许集合允许集合。18NEUQ 3、决策：、决策：表示当过程处于某一阶段的某个状态时，可以作表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态出不同的决定，从而确定下一阶段的状态，这种决定称为这种决定称为决策决策。描述决策的变量，称为描述决策的变量，称为决策变量决策变量。决策变量是状态变量的函。决策变量是状态变量的函数。可用一个数、一组数或一向量（多维情形）来描述。数。可用一个数、一组数或一向量（多维情形）来描述。在实际问题中决策变量的取值往往在某一范围之内，此范围在实际问题中决策变量的取值往往在某一范围之内，此范围称为称为允许决策集合允许决策集合。系统在某一阶段的状态转移不但与系统的当前的状态和决系统在某一阶段的状态转移不但与系统的当前的状态和决策有关，而且还与系统过去的历史状态和决策有关。策有关，而且还与系统过去的历史状态和决策有关。4、多阶段决策过程多阶段决策过程 可以在各个阶段进行决策，去控制过程发展的多段过程；可以在各个阶段进行决策，去控制过程发展的多段过程；其发展是通过一系列的状态转移来实现的；其发展是通过一系列的状态转移来实现的；19NEUQ图示如下：图示如下：状态转移方程是确定状态转移方程是确定过程由一个状态到另过程由一个状态到另一个状态的演变过程。一个状态的演变过程。如果第如果第k阶段状态变量阶段状态变量sk的值、该阶段的决策的值、该阶段的决策变量一经确定，第变量一经确定，第k+1阶段状态变量阶段状态变量sk+1的值的值也就确定。也就确定。其状态转移方程如下（一般形式）其状态转移方程如下（一般形式）12ks1u1s2u2s3skuksk+1 能用动态规划方法求解的多阶段决策过程是一类特殊的多能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。阶段决策过程，即具有无后效性的多阶段决策过程。20NEUQ 如果状态变量不能满足无后效性的要求，应适当地改变状如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。态的定义或规定方法。动态规划中能动态规划中能处理的状态转移处理的状态转移方程的形式方程的形式。状态具有无后效性的多阶段决策过程的状态转移方程如下状态具有无后效性的多阶段决策过程的状态转移方程如下无后效性无后效性(马尔可夫性马尔可夫性)如果某阶段状态给定后，则在这个阶段以后过程的发展不如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；受这个阶段以前各段状态的影响；过程的过去历史只能通过当前的状态去影响它未来的发展；过程的过去历史只能通过当前的状态去影响它未来的发展；状态变量要满足无后效性的要求状态变量要满足无后效性的要求；21NEUQ 5 5、策略：、策略：是一个按顺序排列的决策组成的集合。在实际问题是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，称为中，可供选择的策略有一定的范围，称为允许策略集合允许策略集合。从允。从允许策略集合中找出达到最优效果的策略称为许策略集合中找出达到最优效果的策略称为最优策略最优策略。6 6、状态转移方程：、状态转移方程：是确定过程由一个状态到另一个状态的是确定过程由一个状态到另一个状态的演变过程，描述了状态转移规律。演变过程，描述了状态转移规律。7 7、指标函数和最优值函数：、指标函数和最优值函数：用来衡量所实现过程优劣的一用来衡量所实现过程优劣的一种数量指标，为种数量指标，为指标函数指标函数。指标函数的最优值，称为。指标函数的最优值，称为最优值函最优值函数数。在不同的问题中，指标函数的含义是不同的，它可能是距。在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。离、利润、成本、产量或资源消耗等。动态规划模型的指标函数，应具有可分离性，并满足动态规划模型的指标函数，应具有可分离性，并满足递推递推关系关系。22NEUQ小结小结:方程方程 :状态转移方程状态转移方程概念概念 :阶段变量阶段变量k k状态变量状态变量s sk k决策变量决策变量u uk k;指标指标:动态规划本质上是多阶段决策过程动态规划本质上是多阶段决策过程;效益效益指标函数形式指标函数形式:和、和、积积无后效性无后效性可递推可递推23NEUQ原过程的一个后部子过程：原过程的一个后部子过程：原过程的一个原过程的一个后部子过程的策略后部子过程的策略：对于任意给定的对于任意给定的k（1 kn），从第），从第k段到第段到第n段的过程段的过程称为原过程的一个后部子过程称为原过程的一个后部子过程24NEUQ最优策略最优策略25NEUQ解多阶段决策过程问题，求出解多阶段决策过程问题，求出 最优策略最优策略，即最优，即最优决策序列决策序列f1(s1)最优轨线最优轨线，即执行最优策略时的即执行最优策略时的状态序列状态序列 最优目标函数值最优目标函数值从从 k 到终点最优策略到终点最优策略子策略的最优目标函数值子策略的最优目标函数值26NEUQ12345678910北京河北山西陕西甘肃8458961610967738423问题分成问题分成4个阶段：个阶段：k=1，2，3，412，13，1458，7968，59，69，78，线路：线路：第一阶段，甘肃第一阶段，甘肃 陕西陕西第三阶段：山西第三阶段：山西 河北河北 线路：线路：k=1：k=3：阶段阶段27NEUQ状态状态第一阶段的状态：第一阶段的状态：1第二阶段的状态：第二阶段的状态：234sk第第k阶段的状态变量阶段的状态变量s4第第4阶段的状态变量阶段的状态变量s4=8第第4阶段的状态阶段的状态8Sk=sk第第k阶段的状态集合阶段的状态集合S3=s3=5，6，7注注：n个阶段的决策过程有个个阶段的决策过程有个n+1状态变量状态变量sn+1表示表示sn演变的结果演变的结果S5=1012345678910北京北京河北河北山西山西陕西陕西甘肃甘肃845896161096773842328NEUQ决策决策12345678910北京北京河北河北山西山西陕西陕西甘肃甘肃8458961610967738423决策决策第第2阶段当状态为阶段当状态为3时的决策变量时的决策变量可取值为：可取值为：5，6，7=5，6，7允许决策集合允许决策集合29NEUQ策略策略12345678910北京北京河北河北山西山西陕西陕西甘肃甘肃8458961610967738423最短路问题：最短路问题：策略策略=行进方案行进方案如如 允许策略集合允许策略集合最优策略最优策略：使整个问题达到最优效果的策略：使整个问题达到最优效果的策略策略策略：最优策略最优策略=最短的行进路线最短的行进路线策略策略30NEUQ 12345678910北京北京河北河北山西山西陕西陕西甘肃甘肃8458961610967738423最短路问题：最短路问题：原过程的一个策略：原过程的一个策略：后部子过程后部子过程的策略的策略 后部子过程后部子过程的策略的策略后部子过程后部子过程的策略的策略or 31NEUQ 每月库存每月库存i个单位产品的费用个单位产品的费用E(i)=0.5i(千元），该厂最千元），该厂最大库存容量为大库存容量为3个单位，每月最大生产能力为个单位，每月最大生产能力为6个单位，计划个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。在满足用户需求条件下，使总费用最小。k=1，2，3，4i月月1234g(i)需求需求2324阶段阶段第第k阶段的阶段的状态变量状态变量skS1=0，S2=0,1,2,3，S3=0,1,2,3，S4=0,1,2,3=第第k个月月初的库存量个月月初的库存量（生产与存储问题）（生产与存储问题）某工厂生产并销售某种产品。某工厂生产并销售某种产品。已知今四个月市场需求预测如下表，又每月生产已知今四个月市场需求预测如下表，又每月生产j个单位产品的费用为个单位产品的费用为32NEUQ=2,3,4,5=2,3,4,5=0,1,2,3=3一个一个策略策略=一个一个生产方案生产方案2，5，0，42，3，2，4费用：21（千元）费用：23（千元）最优策略：最优策略：使总费用最小的生产方案使总费用最小的生产方案33NEUQ 最优化原理（基本原理）最优化原理（基本原理）作为整个过程的最优策略具有这样的性质：无论作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形过去的状态和决策如何，相对于前面的决策所形成的当前状态而言，余下的决策序列必然构成最成的当前状态而言，余下的决策序列必然构成最优子策略。优子策略。”也就是说，一个最优策略的子策略也就是说，一个最优策略的子策略也是最优的。也是最优的。34NEUQ对最短路问题：对最短路问题：最短路问题的最短路问题的基本方程基本方程：k=4,3,2,1从最后一阶段开始，用由后向前的方法，求出各点到终点的从最后一阶段开始，用由后向前的方法，求出各点到终点的最短路线，最后，求得由起点到终点的最短路线。最短路线，最后，求得由起点到终点的最短路线。12345678910北京北京河北河北山西山西陕西陕西甘肃甘肃845896161096773842335NEUQ 对于生产与存储问题：对于生产与存储问题：某工厂生产并销售某种产品。已知今某工厂生产并销售某种产品。已知今四个月市场需求预测如下表，又每月生产四个月市场需求预测如下表，又每月生产j个单位产品费用为个单位产品费用为 每月库存每月库存i个单位产品的费用个单位产品的费用E(i)=0.5i(千元），该厂最大库存千元），该厂最大库存容量为容量为3个单位，每月最大生产能力为个单位，每月最大生产能力为6个单位，计划开始和计个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。需求条件下，使总费用最小。阶段阶段k=1，2，3，4状态变量状态变量 =第第k个月月初的库存量个月月初的库存量i月月1234g(i)需求需求2324状态转移方程：状态转移方程：36NEUQ当当k=4时，时，u4(s4)对应的总费用对应的总费用=生产费生产费+库存费库存费i月月1234g(i)需求需求2324库存费库存费E(i)=0.5i，最大库存容量为最大库存容量为3个单位，个单位，最大生产能力为最大生产能力为6个单位，个单位，计划开始和计划期末库存量为零计划开始和计划期末库存量为零012347436.5326215.5137NEUQ当当k=3时，时，i月月1234g(i)需求需求2324库存费库存费E(i)=0.5i，最大库存容量为最大库存容量为3个单位，个单位，最大生产能力为最大生产能力为6个单位，个单位，计划开始和计划期末库存量为零计划开始和计划期末库存量为零012301230u3(3)对应的总费用对应的总费用=生产费生产费+库存费库存费38NEUQi月月1234g(i)需求需求2324库存费E(i)=0.5i，最大库存容量为3个单位，最大生产能力为6个单位，计划开始和计划期末库存量为零02 3 4 512 12.5 13 13.512211 2 3 411.5 12 12.5 1311.5120 1 2 38 11.5 12 12.58030 1 288011.5 12012347436.5326215.5139NEUQ当当k=2时，时，i月月1234g(i)需求需求2324u2(s2)对应的总费用对应的总费用=生产费生产费+库存费库存费40NEUQ02 3 4 512 12.5 13 13.512211 2 3 411.5 12 12.5 1311.5120 1 2 38 11.5 12 12.58030 1 28 11.5 1280k=3当当k=2时，时，0123 3 4 5 618 18.5 16 171652 3 4 517.5 18 15.5 16.5 1 2 3 4170 1 2 313.5 17 14.5 15.515.5415313.5017.5 15 1641NEUQ当当k=1时，时，i月月1234g(i)需求需求2324u1(0)对应的总费用对应的总费用=生产费生产费42NEUQk=20123 3 4 5 618 18.5 16 171652 3 4 517.5 18 15.5 16.5 1 2 3 417 17.5 15 160 1 2 313.5 17 14.5 15.515.5415313.50当当k=1时，时，02 3 4 522 21.52122121.543NEUQ生产存储问题的基本方程：生产存储问题的基本方程：44NEUQ最短路问题的基本方程：最短路问题的基本方程：k=4,3,2,145NEUQ三、动态规划方法建模基本要求与步骤三、动态规划方法建模基本要求与步骤建模要素：建模要素：1)阶段数阶段数 k2)状态变量状态变量 sk3)决策变量决策变量 uk（sk）4)指标函数指标函数 Vk,n状态转移方程状态转移方程5)最优值函数最优值函数 fk(sk)46NEUQDP建模基本要求：建模基本要求：1）所研究的问题必须能够分成几个相互联系的阶）所研究的问题必须能够分成几个相互联系的阶段，而且在每一个阶段都具有需要进行决策的问题。段，而且在每一个阶段都具有需要进行决策的问题。2）在每一阶段都必须有若干个与该阶段相关的状态，）在每一阶段都必须有若干个与该阶段相关的状态，建模时总是从与决策有关的条件中，或是从问题的建模时总是从与决策有关的条件中，或是从问题的约束条件中去选择状态变量。约束条件中去选择状态变量。一般情况下，状态是所研究系统在该阶段可能处一般情况下，状态是所研究系统在该阶段可能处于的情况或条件于的情况或条件47NEUQ3)具有明确的指标函数，且阶段指标值可以计算具有明确的指标函数，且阶段指标值可以计算4)能正确列出最优值函数的递推公式和边界条件能正确列出最优值函数的递推公式和边界条件（b）能通过现阶段的决策，使当前状态转移成下）能通过现阶段的决策，使当前状态转移成下一阶段的状态（反映过程的一阶段的状态（反映过程的演变性演变性）即即 能够给出状态转移方程能够给出状态转移方程（c）状态的）状态的无后效性无后效性状态的选取必须注意以下几个要点：状态的选取必须注意以下几个要点：（a）在所研究问题的各阶段，都能直接或间接确）在所研究问题的各阶段，都能直接或间接确定状态变量的取值（定状态变量的取值（可知性可知性）48NEUQ建立建立DPDP模型的步骤模型的步骤 1、划分阶段划分阶段 划划分分阶阶段段是是运运用用动动态态规规划划求求解解多多阶阶段段决决策策问问题题的的第第一一步步，在在确确定定多多阶阶段段特特性性后后，按按时时间间或或空空间间先先后后顺顺序序，将将过过程程划划分分为为若若干干相相互互联联系系的的阶阶段段。对对于于静静态态问问题要人为地赋予题要人为地赋予“时间时间”概念，以便划分阶段。概念，以便划分阶段。2、正确选择状态变量正确选择状态变量 选选择择变变量量既既要要能能确确切切描描述述过过程程演演变变又又要要满满足足无无后后效效性性，而而且且各各阶阶段段状状态态变变量量的的取取值值能能够够确确定定。一一般般地地，状态变量的选择是从过程演变的特点中寻找。状态变量的选择是从过程演变的特点中寻找。3、确定决策变量及允许决策集合确定决策变量及允许决策集合 通通常常选选择择所所求求解解问问题题的的关关键键变变量量作作为为决决策策变变量量，同同时要给出决策变量的取值范围，即确定允许决策集合。时要给出决策变量的取值范围，即确定允许决策集合。49NEUQ 4、确定状态转移方程确定状态转移方程根据根据k 阶段状态变量和决策变量，写出阶段状态变量和决策变量，写出k+1阶段状态变阶段状态变量，状态转移方程应当具有递推关系。量，状态转移方程应当具有递推关系。5、确定阶段指标函数和最优指标函数，建立动态规确定阶段指标函数和最优指标函数，建立动态规划基本方程划基本方程 阶段指标函数是指第阶段指标函数是指第k 阶段的收益，最优指标函数是阶段的收益，最优指标函数是指从第指从第k 阶段状态出发到第阶段状态出发到第n 阶段末所获得收益的最优阶段末所获得收益的最优值，最后写出动态规划基本方程。值，最后写出动态规划基本方程。以上五步是建立动态规划数学模型的一般步骤。由于以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。不断实践总结，才能较好掌握建模方法与技巧。50NEUQ四、动态规划方法应用举例四、动态规划方法应用举例动态规划常用基本方程动态规划常用基本方程：51NEUQ从从A 地到地到D 地要铺设一条煤气管道地要铺设一条煤气管道,其中需经过两级中其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？问应该选择什么路线，使总距离最短？AB1B2C1C2C3D243333211141、最短路径问题最短路径问题52NEUQ 解：整个计算过程分三个阶段，从最后一个阶段开始解：整个计算过程分三个阶段，从最后一个阶段开始。第一阶段（第一阶段（C D）：）：C 有三条路线到终点有三条路线到终点D。AB1B2C1C2C3D24333321114DC1C2C3显然有显然有 f1(C1)=1 ；f1(C2)=3 ；f1(C3)=4 53NEUQ d(B1,C1)+f1(C1)3+1 f2(B1)=min d(B1,C2)+f1(C2)=min 3+3 d(B1,C3)+f1(C3)1+4 4 =min 6 =4 5第二阶段（第二阶段（B C）：）：B 到到C 有六条路线。有六条路线。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为最短路线为B1C1 D)54NEUQ d(B2,C1)+f1(C1)2+1 f2(B2)=min d(B2,C2)+f1(C2)=min 3+3 d(B2,C3)+f1(C3)1+4 3 =min 6 =3 5AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为最短路线为B2C1 D)55NEUQ第三阶段（第三阶段（A B）：）：A 到到B 有二条路线。有二条路线。f3(A)1=d(A,B1)f2(B1)246 f3(A)2=d(A,B2)f2(B2)437 f3(A)=min =min6,7=6d(A,B1)f2(B1)d(A,B2)f2(B2)(最短路线为最短路线为AB1C1 D)AB1B2C1C2C3D24333321114DC1C2C3B1B2A56NEUQAB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路线为最短路线为 AB1C1 D 路长为路长为 657NEUQ2、资源分配问题资源分配问题 某公司有资金某公司有资金a万元，拟投资于万元，拟投资于n个项目，已知对第个项目，已知对第i个项目个项目投资投资xi万元，收益为万元，收益为g i(xi)，问应如何分配资金可使总收益，问应如何分配资金可使总收益最大？最大？解：阶段解：阶段k=1,2,n状态变量状态变量sk决策变量决策变量uk：第第k个项目的投资额个项目的投资额：在第在第k阶段时可以用于投资阶段时可以用于投资 第第k到第到第n个项目的资金数个项目的资金数状态转移方程：状态转移方程：sk+1=sk-uk指标函数指标函数Vk,n第第k至第至第n个项目的最大总收益个项目的最大总收益最优值函数最优值函数58NEUQ边界条件：边界条件：k=n,n-1,2,1资源分配问题的动态规划基本方程：资源分配问题的动态规划基本方程：建立递推公式建立递推公式：59NEUQ投资额投资额收益收益工厂工厂12314.525274.57397.58410.511105121513某有色金属公司拟拨出某有色金属公司拟拨出50万元对所万元对所属三家冶炼厂进行技术改造，若以属三家冶炼厂进行技术改造，若以十万元为最少分割单位，各厂收益十万元为最少分割单位，各厂收益与投资的关系如下表：与投资的关系如下表：问：对三个工厂如何分配，问：对三个工厂如何分配，才能使总收益达到最大？才能使总收益达到最大？状态变量状态变量 sk：阶段阶段 k=1，2，3决策变量决策变量 uk：给工厂给工厂k的投资额的投资额在第在第k阶段时可供工阶段时可供工厂厂k到工厂到工厂3分配的分配的资金数资金数状态转移方程状态转移方程：sk+1=sk-ukg k(uk)=给工厂给工厂k投资投资 uk（十万元）的收益（十万元）的收益指标函数指标函数 Vk,n资源分配问题示例资源分配问题示例60NEUQfk（sk）投资工厂投资工厂k至工厂至工厂3所得的最大总收益所得的最大总收益求求f1（5）=在工厂在工厂k，可供分配的资金数为，可供分配的资金数为sk时时，基本方程：基本方程：k=3001122330 57845451013投资额投资额收益收益工厂工厂12314.525274.57397.58410.51110512151301234561NEUQk=200001020 15 2050 1 27 7 4.50或或1730 1 2 38 9 9.5 7.529.5450 1 2 3 4 10 10 11.512.511312.50 1 2 3 4 513 1212.514.5 1615416投资额投资额收益收益工厂工厂12314.525274.57397.58410.511105121513sk+1=sk-uk001122330 5784545101301234562NEUQk=1sk+1=sk-uk投资额投资额收益收益工厂工厂12314.525274.57397.58410.511105121513516 0 1 2 3 4 517 16.5 16 15.5 12117最大总收益：最大总收益：最优策略：最优策略：00001020 15 2050 1 27 7 4.50或或1730 1 2 38 9 9.5 7.529.5450 1 2 3 4 10 10 11.512.511312.50 1 2 3 4 513 12 12.514.5 161541663NEUQ系统由系统由n个部件串联组成，每一个部件上装有备用件，部件个部件串联组成，每一个部件上装有备用件，部件i(i=1,2,n)上装有上装有xi个备用元件时，正常工作的概率为个备用元件时，正常工作的概率为pi（xi）。设装一个）。设装一