运筹学-动态规划.ppt

动动 态态 规规 划划(Dynamic programming)一、引例一、引例二、动态规划的基本思想二、动态规划的基本思想三、应用举例三、应用举例 动态规划作为运筹学的一个重要分支是解决多动态规划作为运筹学的一个重要分支是解决多阶段决策过程最优化的一种非常有效的方法。阶段决策过程最优化的一种非常有效的方法。1951年，年，美国数学家贝尔曼（美国数学家贝尔曼（R.Bellman）等人，根据一类）等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联系的单阶段决策问题，然后分阶段逐个加系列相互联系的单阶段决策问题，然后分阶段逐个加以解决。贝尔曼等人在研究和解决了大量实际问题之以解决。贝尔曼等人在研究和解决了大量实际问题之后，提出了解决这类问题的后，提出了解决这类问题的所谓所谓“最优性原理最优性原理”，通常称为，通常称为“贝尔曼最优化原理贝尔曼最优化原理”，从而创建了解决，从而创建了解决最优化问题的一种新的方法最优化问题的一种新的方法 动态规划动态规划（Dynamic Programming ）。）。贝尔曼的名著贝尔曼的名著动动态规划态规划于于1957年出版，这成了动态规划的第一本著年出版，这成了动态规划的第一本著作作。一、引例一、引例动态：相对于静态：只考虑一个计划期。动态：相对于静态：只考虑一个计划期。动态规划：考虑多个计划期，多个阶段的优化问题。动态规划：考虑多个计划期，多个阶段的优化问题。研究对象：多阶段决策问题研究对象：多阶段决策问题例例1（时间阶段）某种设备可在高低两种不同的负荷下进行（时间阶段）某种设备可在高低两种不同的负荷下进行生产，设在高负荷下投入生产的设备数量为生产，设在高负荷下投入生产的设备数量为x，产量为，产量为g=10 x，设备年完好率为，设备年完好率为a=0.75；在低负荷下投入生产的；在低负荷下投入生产的设备数量为设备数量为y，产量为，产量为h=8y,年完好率为年完好率为b=0.9。假定开始生。假定开始生产时完好的设备数量产时完好的设备数量s1=1000台。台。制定一个制定一个5年计划，确定每年投入高、低两种负荷下生年计划，确定每年投入高、低两种负荷下生产的设备数量，使产的设备数量，使5年内产品的总数量达到最大。年内产品的总数量达到最大。下图为一个线路网络图，要从下图为一个线路网络图，要从A到到E地铺设一条输油地铺设一条输油管道，各点间连线上的数字表示距离，问应选择什管道，各点间连线上的数字表示距离，问应选择什么路线，可使总距离么路线，可使总距离最短。最短。例例2（空间阶段）（空间阶段）AB2B1B3C1C3D1D2EC252141126101043121113965810521A1234DBCE即在系统发展的不同阶段，根据系统所处的状即在系统发展的不同阶段，根据系统所处的状态，不断地做出决策；态，不断地做出决策；每个阶段都要进行每个阶段都要进行决策决策,目的是使整个过程的决策目的是使整个过程的决策 达到最优效果。达到最优效果。动态决策问题的特点：动态决策问题的特点：系统所处的状态和时刻是进行决策的重要因素；系统所处的状态和时刻是进行决策的重要因素；找到不同时刻的最优决策以及整个过程的最优策略。找到不同时刻的最优决策以及整个过程的最优策略。多阶段决策问题：多阶段决策问题：在多阶段决策过程中在多阶段决策过程中,系统的动态过程可以按照时间系统的动态过程可以按照时间进程分为进程分为状态状态相互相互联系联系而又相互而又相互区别区别的各个的各个阶段阶段；12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策多阶段决策问题的典型例子：多阶段决策问题的典型例子：1.1.生产决策问题生产决策问题：企业在生产过程中，由于需：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。根据库存和需求决定生产计划。2.2.机机器器负负荷荷分分配配问问题题：某某种种机机器器可可以以在在高高低低两两种种不不同同的的负负荷荷下下进进行行生生产产。在在高高负负荷荷下下进进行行生生产产时时，产品的年产量产品的年产量g和投入生产的机器数量和投入生产的机器数量u1的关系为的关系为g=g(u1)这时，机器的年完好率为这时，机器的年完好率为a，即如果年初完好机即如果年初完好机器的数量为器的数量为u，到年终完好的机器就为到年终完好的机器就为au,0a1。在低负荷下生产时，产品的年产量在低负荷下生产时，产品的年产量h和投入生产和投入生产的机器数量的机器数量u2的关系为的关系为 h=h(u2)假定开始生产时完好的机器数量为假定开始生产时完好的机器数量为s s1 1。要求制要求制定一个五年计划，在定一个五年计划，在每年开始时，决定如何重新每年开始时，决定如何重新分配分配完好的完好的机器在两种不同的负荷下生产的数量机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。使在五年内产品的总产量达到最高。相应的机器年完好率相应的机器年完好率b b,0,0b b11。3.不包含时间因素的静态决策问题（本质上是不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作一次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。为多阶段的决策问题用动态规划方法来解决。4 4.线性规划、非线性规划等静态的规划问题也线性规划、非线性规划等静态的规划问题也可以通过适当地引入阶段的概念，应用动态规划方可以通过适当地引入阶段的概念，应用动态规划方法加以解决。法加以解决。（一）基本概念（一）基本概念 1、阶段、阶段 把一个问题的过程，一般根据时间和空间的自然特征把一个问题的过程，一般根据时间和空间的自然特征来恰当地分为若干个来恰当地分为若干个阶段阶段，把问题转化为多阶段求解的，把问题转化为多阶段求解的问题，以便于按一定的次序去求解。问题，以便于按一定的次序去求解。阶段：分段求解的过程。描述阶段的变量称为阶段：分段求解的过程。描述阶段的变量称为阶段变阶段变量量。常用字母。常用字母k表示阶段变量，表示阶段变量，k=1，2，n。2、状态：表示每个、状态：表示每个阶段初阶段初所处的所处的情形或位置情形或位置。通常一个。通常一个阶段初有若干个状态，描述过程状态的变量称为阶段初有若干个状态，描述过程状态的变量称为状态变状态变量量。状态变量常用。状态变量常用sk表示第表示第k阶段的状态变量。状态变量阶段的状态变量。状态变量的取值有一定的允许集合或范围，此集合称为的取值有一定的允许集合或范围，此集合称为状态集合状态集合，用用Sk表示表示。S2=B1，B2,B3，S3=C1,C2,C3 二、动态规划的基本思想二、动态规划的基本思想AB2B1B3C1C3D1D2EC252141126101043121113965810521A1234DBCE 3、决策：表示当过程处于某一阶段的某个状态时，、决策：表示当过程处于某一阶段的某个状态时，可以作出不同的决定（选择），从而确定下一阶段的可以作出不同的决定（选择），从而确定下一阶段的状态，这种决定就称决策。状态，这种决定就称决策。常用常用uk(sk)表示第表示第k阶段当阶段当状态为状态为sk时的决策变量。时的决策变量。从而确定下一阶段的状态从而确定下一阶段的状态。表示决策的变量，称为表示决策的变量，称为决策变量决策变量。决策变量是状态变。决策变量是状态变量的函数。量的函数。在实际问题中决策变量的取值往往在某一范围之内，在实际问题中决策变量的取值往往在某一范围之内，此范围称为此范围称为允许决策集合允许决策集合。常用。常用Dk(sk)表示第表示第k阶段从阶段从状态状态sk出发的允许决策集合，显然出发的允许决策集合，显然AB2B1B3C1C3D1D2EC252141126101043121113965810521A1234DBCED2(B1)=C1，C2，C3D2(B2)=C1，C2，C3 4 4、状态转移方程：是由本阶段的状态转变为下一阶、状态转移方程：是由本阶段的状态转变为下一阶段状态的规律。第段状态的规律。第k+1k+1阶段的状态完全由本阶段的状阶段的状态完全由本阶段的状态和本阶段的决策决定，所以这个规律可以用下面的态和本阶段的决策决定，所以这个规律可以用下面的函数表示为：函数表示为：sk+1=T(sk,uk)状态转移方程：状态转移方程：sk+1=uk（sk）5 5、策略：策略是一个按顺序排列的决策组合的集合，、策略：策略是一个按顺序排列的决策组合的集合，各个阶段的决策求出之后，各个阶段的决策序列就构各个阶段的决策求出之后，各个阶段的决策序列就构成一个策略。即是一个按顺序排列的决策组成的集合。成一个策略。即是一个按顺序排列的决策组成的集合。用用p1,n=u1(s1),u2(s2),un(sn)表示从第一阶段到第表示从第一阶段到第n阶段整个问题的策略。阶段整个问题的策略。pk,n=uk(sk),un(sn)表示表示后部子策略。后部子策略。在实际问题中，可供选择的策略有一定在实际问题中，可供选择的策略有一定的范围，称为的范围，称为允许策略集合允许策略集合。从允许策略集合中找出。从允许策略集合中找出达到最优效果的策略称为达到最优效果的策略称为最优策略最优策略，用，用p1,n*或或pk,n*表示。表示。AB2B1B3C1C3D1D2EC252141126101043121113965810521A1234DBCE 6 6、指标函数和最优值函数：、指标函数和最优值函数：指标函数是指标函数是衡量实现过程优劣的一种数量指标。具衡量实现过程优劣的一种数量指标。具体体含义是不同的，它可能是距离、利润、成本、产量或含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。资源消耗等。阶段指标函数：第阶段指标函数：第k阶段阶段(单个阶段单个阶段)，从状态，从状态sk出发，出发，采取决策采取决策uk时的效益，用时的效益，用vk(sk，uk)表示。表示。过程指标函数：各个阶段过程指标函数：各个阶段(多个阶段多个阶段)的总效益。即的总效益。即从第从第k k阶段到第阶段到第n n阶段的总效益，记为阶段的总效益，记为vk，n(sk，pk,n)，表，表示初始状态为示初始状态为sk，采用策略采用策略pk,n时从第时从第k阶段到第阶段到第n阶段的阶段的过程指标函数。过程指标函数。最优指标函数记为最优指标函数记为fk(sk),表示从第表示从第k阶段，状态阶段，状态sk采采用最优策略用最优策略pk,n*到过程终止时的最佳效益值，到过程终止时的最佳效益值，fk(sk)与与 vk，n(sk，pk,n)间的关系为间的关系为fk(sk)=vk，n(sk，pk,n*)=当当k=1时，时，f1(s1)就就是从初始状态是从初始状态s1到全到全过程结束的整体最优过程结束的整体最优函数。函数。AB2B1B3C1C3D1D2EC252141126101043121113965810521A1234DBCE过程指标函数过程指标函数Vk,n表示表示在第在第k阶段由点阶段由点sk至终点至终点E的距离。用的距离。用dk(sk,uk)=vk(sk,uk)表示在第表示在第k阶阶段由点段由点sk到点到点sk+1的距离的距离。7 基本方程：基本方程：（1）指标函数为和的形式）指标函数为和的形式（2）指标函数为乘积的形式指标函数为乘积的形式AB2B1B3C1C3D1D2EC252141126101043121113965810521A1234DBCE8、基本方程的原理、基本方程的原理AB2B1B3C1C3D1D2EC252141126101043121113965810521A1234DBCE（二）建立动态规划模型的步骤（二）建立动态规划模型的步骤（逆推法）（逆推法）1、正确、明确地划分阶段正确、明确地划分阶段 k，k=1，2，3，n。依据决策过程的时间和空间的顺序关系。依据决策过程的时间和空间的顺序关系。2、正确选择并确定状态变量正确选择并确定状态变量 sk 及状态集合及状态集合 Sk。状。状态变量的确定有时并非显而易见，要确定它，通常态变量的确定有时并非显而易见，要确定它，通常可对问题作如下分析而帮助确定状态变量可对问题作如下分析而帮助确定状态变量 a.什么关系将各个阶段联系在一起？什么关系将各个阶段联系在一起？b.为了决定今后的最优（子）策略，需要事件为了决定今后的最优（子）策略，需要事件现状的哪些信息？现状的哪些信息？3、确定决策变量确定决策变量 uk 及及决策集合决策集合 Dk（sk）。）。4、写出写出状态转移方程状态转移方程 sk+1=Tk（sk，uk）。）。5、定义阶段指标值（函数）定义阶段指标值（函数）vk（sk，uk）。）。6、定义第定义第 k至至 n 阶段（后部子过程）的最优指标（目标）函阶段（后部子过程）的最优指标（目标）函数数 fk（sk）。）。7、作出动态规划结构图：作出动态规划结构图：sk sk+1=Tk（sk，uk）k阶段阶段fk（sk）k+1阶段阶段fk+1（sk+1）opt（，）vk（sk，uk）uk Dk（sk）8、建立动态规划基本方程：（逆序递推方程）建立动态规划基本方程：（逆序递推方程）fk（sk）=opt vk（sk，uk）+fk+1（sk+1），k=n，2，1uk Dk（sk）fn+1（sn+1）=0或者或者 9、逆序递推求解动态规划基本方程。逆序递推求解动态规划基本方程。求出最优决策序列求出最优决策序列 u*n，u*n-1，u*2，u*110、顺序确定顺序确定最优策略。最优策略。p*1n=u*1，u*2，u*n s1u*1u*2u*nsns2 例、从例、从A 地到地到D 地要铺设一条煤气管道地要铺设一条煤气管道,其中需经其中需经过两级中间站，两点之间的连线上的数字表示距离，过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？如图所示。问应该选择什么路线，使总距离最短？AB1B2C1C2C3D24333321114（一）最短路径问题（一）最短路径问题三、动态规划的应用举例三、动态规划的应用举例 解：整个计算过程分三个阶段，从最后一个阶段开始。解：整个计算过程分三个阶段，从最后一个阶段开始。(1)k=3即（即（C D）：）：C 有三条路线到终点有三条路线到终点D。AB1B2C1C2C3D24333321114DC1C2C3 当当s3=C1时，时，f3(C1)=mind(C1,D)0=1 ；同样有：；同样有：f3(C2)=3 ；f3(C3)=4 第二阶段第二阶段第三阶段第三阶段第一阶段第一阶段显然有显然有 d(B1,C1)+f3(C1)3+1 f2(B1)=min d(B1,C2)+f3(C2)=min 3+3 d(B1,C3)+f3(C3)1+4 4 =min 6 =4 5（2）k=2（B C）：）：B 到到C 有六条路线。有六条路线。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为最短路线为B1C1 D)f3(C1)=1 ；f3(C2)=3 ；f3(C3)=4 d2(B2,C1)+f3(C1)2+1 f2(B2)=min d2(B2,C2)+f3(C2)=min 3+3 d2(B2,C3)+f3(C3)1+4 3 =min 6 =3 5AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为最短路线为B2C1 D)f3(C1)=1 ；f3(C2)=3 ；f3(C3)=4(3)k=1（A B）：）：A 到到B 有二条路线有二条路线。f1(A)=min =mind1(A,B1)f2(B1)d1(A,B2)f2(B2)(最短路线为最短路线为AB1C1 D)AB1B2C1C2C3D24333321114DC1C2C3B1B2A 6,7=6=min 2+44+3f2(B1)=4 ；f2(B2)=3 AB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路线为最短路线为 AB1C1 D 路长为路长为 6练习练习1：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最优路线为：最优路线为：A B1 C2 D1 E2 F2 G 路长路长18求从求从A到到G的最短路径的最短路径3k=5k=5，出发点出发点E1E1、E2E2、E3E3u5(E1)=F1E1 F1 GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u5(E2)=F2E2 F2 Gu5(E3)=F2E3 F2 Gk=6k=6,F1 G f f6 6(F1)=4(F1)=4F F2 2 G ,f,f6 6(F2)=3(F2)=34k=4，f4(D1)=7 u4(D1)=E2f4(D2)=6 u4(D2)=E2f4(D3)=8 u4(D3)=E2k=2,f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3f3(C1)=13 u3(C1)=D1f3(C2)=10 u3(C2)=D1f3(C3)=9 u3(C3)=D2f3(C4)=12 u3(C4)=D3k=3,=min f1(A)=mind1(A,B1)+f2(B1)d1(A,B2)+f2(B2)5+133+16=18k=1,u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E24AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876683533822123335526643u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2 u5(E2)=F2u6(F2)=G最优策略最优策略AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643练习练习2B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G第一阶段第一阶段第二阶段第二阶段第三阶段第三阶段第四阶段第四阶段第五阶段第五阶段第六阶段第六阶段531368766835342138223335526643437597681310912131618该点到该点到G点的最短距离点的最短距离练习练习2 2：求从：求从A到到G的最短路径的最短路径(二)资源分配问题 例1（连续）：某公司有资金10万元，若投资于项目i（i=1，2，3）的投资额为 时，其收益分别为 问题：如何分配投资数额才能使总收益最大？资源分配问题是将数量一定的一种或若干种资源资源分配问题是将数量一定的一种或若干种资源（原材料、资金、设备、劳动力等）分配给若干个使（原材料、资金、设备、劳动力等）分配给若干个使用者，使总用者，使总 收益最大。收益最大。动态规划模型的建立阶段k：按项目为3个阶段，k=1，2，3。状态变量 ：第k阶段初拥有的可以分配给第k到第3个项目的资金和。决策变量 ：决定给第k阶段（项目）的资金。状态转移方程：阶段指标函数：过程指标函数：状态 ：第k阶段初可以分配给第k到第3个项目的资金额。状态转移方程：过程指标函数：就是最大收益。基本方程：S2-9/4最大收益最大收益200万元顺推求出最优方案即决策变量的值顺推求出最优方案即决策变量的值例例2（离散）（离散）某公司新引进了某公司新引进了 6 台高效率生产设备，该设备可用于台高效率生产设备，该设备可用于生产生产 4 种不同的产品，当生产每种产品所投入的设备数量不同时所种不同的产品，当生产每种产品所投入的设备数量不同时所带来的利润也不相同。其详细资料如下：带来的利润也不相同。其详细资料如下：利润表利润表 单位：万元单位：万元设备数量设备数量4 种种 产产 品品产产 品品 1产产 品品 2产产 品品 3产产 品品 401234560204260758590025455765707301839617890950284765748085产品产品利润利润该公司这该公司这 6 台设备在台设备在 4 种产品的生产中能够发挥最大的效益，应该种产品的生产中能够发挥最大的效益，应该如何分配这如何分配这 6 台设备，才能获得最大的总利润？台设备，才能获得最大的总利润？分析、建模分析、建模 此决策问题如按此决策问题如按 4 种产品的一种顺序（可以任意排列，不妨按种产品的一种顺序（可以任意排列，不妨按产品的自然顺序），将产品产品的自然顺序），将产品 1 分配的设备数量作为分配的设备数量作为第一阶段第一阶段需作出需作出的决策，将产品的决策，将产品 2 分配的设备数量作为分配的设备数量作为第二阶段第二阶段需作出的决策，将需作出的决策，将产品产品 3 分配的设备数量作为分配的设备数量作为第三阶段第三阶段需作出的决策，将产品需作出的决策，将产品 4 分配分配的设备数量作为的设备数量作为第四阶段第四阶段需作出的决策，这显然就是一个多阶段决需作出的决策，这显然就是一个多阶段决策问题。因此有：策问题。因此有：1、阶段阶段 k：第第 k 种产品，种产品，k=1，2，3，42、状态变量状态变量 sk ：当按顺序用于第当按顺序用于第 k 种产品分配设备时所余有的设种产品分配设备时所余有的设备总量。备总量。3、决策变量决策变量 uk：分配给第分配给第 k 种产品的设备数量。种产品的设备数量。Dk（sk）=uk|uk=0，1，2，sk 4、状态转移方程：状态转移方程：sk+1=sk-uk5、定义阶段指标值（函数）定义阶段指标值（函数）vk（sk，uk）=vk（uk）：）：即分配给第即分配给第 k 种产品的设备数量为种产品的设备数量为 uk 时，第时，第 k 种产品所创造的利润（如利种产品所创造的利润（如利润表）。润表）。6、定义定义 fk（sk）：）：第第 k 种产品分配设备时所余有的设备数量为种产品分配设备时所余有的设备数量为 sk ，第，第 k 种产品至第四种产品所创造的种产品至第四种产品所创造的利润总和利润总和。（第。（第 k 种产品种产品至第四种产品按某种设备分配策略所创造的至第四种产品按某种设备分配策略所创造的最大总利润最大总利润。7、作出动态规划结构图：作出动态规划结构图：sk sk+1=sk-uk k阶段阶段fk（sk）k+1阶段阶段fk+1（sk+1）max（）vk（uk）uk=0，1，2，sk 8、建立动态规划基本方程：（逆序递推方程）建立动态规划基本方程：（逆序递推方程）fk（sk）=max vk（uk）+fk+1（sk+1），k=4，3，2，1uk=0，1，2，skf5（s5）=09、逆序递推求解动态规划基本方程。逆序递推求解动态规划基本方程。k=4 时，状态集合时，状态集合 S4=0，1，2，3，4，5，6 f4（s4）=max v4（u4）0 u4 s4v4（u4）f4（s4）u*401234560000102828120284747230284765653402847657474450284765748080560284765748085856设备数量设备数量4 种种 产产 品品产产 品品 1产产 品品 2产产 品品 3产产 品品 401234560204260758590025455765707301839617890950284765748085 k=3 时，状态集合时，状态集合 S3=0，1，2，3，4，5，6 f3（s3）=max v3（u3）+f4（s4）u3 s3v3（u3）+f4（s4）f3（s3）u*3012345600+00010+2818+028020+4718+2839+047030+6518+4739+2861+067240+7418+6539+4761+2878+089350+8018+7439+6561+4778+2890+0108360+8518+8039+7461+6578+4790+2895+01263s40123456f4（s4）0284765748085S4=s3-u3设备数量设备数量4 种种 产产 品品产产 品品 1产产 品品 2产产 品品 3产产 品品 401234560204260758590025455765707301839617890950284765748085k=2 时，状态集合时，状态集合 S2=0，1，2，3，4，5，6 f2（s2）=max v2（u2）+f3(s3）u2 s2v2（u2）+f3（s3）f2（s2）u*2012345600+00010+2825+028020+4725+2845+053130+6725+4745+2857+073240+8925+6745+4757+2865+0921，250+10825+8945+6757+4765+2870+0114160+12625+10845+8957+6765+4770+2873+01342s30123456f3（s3）028476789108126S3=s2-u2设备数量设备数量4 种种 产产 品品产产 品品 1产产 品品 2产产 品品 3产产 品品 401234560204260758590025455765707301839617890950284765748085k=1 时，状态集合时，状态集合 S1=6 f1（s1）=max v1（u1）+f2（s2）u1 s1v1（u1）+f2（s2）f1（s1）u*1012345660+13420+11442+9260+7375+5385+2890+01340，1，210、顺序确定顺序确定最优策略之一。最优策略之一。s2=6s1=6u1=0u4=1u2=2u3=3s4=1s3=4s20123456f2（s2）028537392114134设备数量设备数量4 种种 产产 品品产产 品品 1产产 品品 2产产 品品 3产产 品品 401234560204260758590025455765707301839617890950284765748085该公司设备分配的所有最优方案：该公司设备分配的所有最优方案：最大总利润最大总利润 （万元）（万元）产品产品1产品产品2产品产品3产品产品4方案方案10台台2台台3台台1台台134方案方案21台台1台台3台台1台台134方案方案32台台1台台1台台2台台134方案方案42台台2台台0台台2台台134 有一个徒步旅行者，其可携带物品重量的限度为有一个徒步旅行者，其可携带物品重量的限度为w 公斤，设有公斤，设有n 种物品可供他选择装入包中。已知每种物种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大带的物品（各几件），使所起作用（使用价值）最大？物品物品 1 2 j n重量（公斤重量（公斤/件）件）w1 w2 wj wn每件使用价值每件使用价值 c1 c2 cj cn 背包问题等同于车、船、人造卫星等工具最优装载。背包问题等同于车、船、人造卫星等工具最优装载。例例3（离散）背包问题（离散）背包问题设设xj 为第为第j 种物品的装件数（非负整数）则问题的数学种物品的装件数（非负整数）则问题的数学模型如下：模型如下：阶段阶段k:第第k次装载第次装载第k种物品（种物品（k=1,2,n）状态变量状态变量sk:第第k次装载时背包还可以装的重量或体次装载时背包还可以装的重量或体积；积；决策变量决策变量xk:第第k次装载第次装载第k种物品的装件数；种物品的装件数；状态转移方程：状态转移方程：决策集合：决策集合：阶段指标：阶段指标：递推方程：递推方程：例例4：设有：设有3种物品，每种的数量无限，其重量和价值如下表。种物品，每种的数量无限，其重量和价值如下表。现有一只可装载重量为现有一只可装载重量为W=5kg的背包。试问：各种物品应各取的背包。试问：各种物品应各取多少件放入背包，才能使背包中的所有物品总价值最高？多少件放入背包，才能使背包中的所有物品总价值最高？物品编号物品编号 1 2 3重量重量Wi（kgkg）2 3 1价值价值Ci(元元/件件)65 80 30决策变量决策变量 ：决定第：决定第k阶段装入物品的件数。阶段装入物品的件数。动态规划模型的建立阶段阶段k：按物品种类分为按物品种类分为3个阶段，个阶段，k=1，2，3。状态变量状态变量 ：第：第k阶段初背包可装入的重量。阶段初背包可装入的重量。0,1,20,10,1,2,3,4，5状态转移方程：状态转移方程：阶段指标函数：阶段指标函数：过程指标函数：过程指标函数：基本方程：基本方程：利用表格计算利用表格计算k=3时：时：012350123500000303030306060609090150030906015001325412015010k=2时：时：1350+30=303000+90=9080+0=809000+150=15080+60=1400s3012345f3（s3）030609012015065+90=1550+150=1505021k=1时：时：130+30=1601602由此可知：由此可知：s1=5,此时此时 =2；最优策略为：最优策略为：s2135f3（s3）3090150例例5 机器负荷分配问题机器负荷分配问题 某种某种机器可在两种负荷下进行生产。在高负荷下机器可在两种负荷下进行生产。在高负荷下生产的产量函数为生产的产量函数为 g=8 u1（u1 为投入的机器数量），为投入的机器数量），年完好率为年完好率为 a=0.7 ；在低高负荷下生产的产量函数在低高负荷下生产的产量函数为为 h=5y（y 为投入的机器数量），年完好率为为投入的机器数量），年完好率为 b=0.9 。开始生产时完好机器数量开始生产时完好机器数量 s1=1000台，问每年台，问每年如何分配机器在两种负荷下进行生产，使五年内生产如何分配机器在两种负荷下进行生产，使五年内生产的产品总产量最高。的产品总产量最高。建立动态规划模型：建立动态规划模型：1、阶段阶段 k：生产年度，生产年度，k=1，2，3，4，52、状态变量状态变量 sk ：第第 k 年度初安排时拥有的完好机器数量，（此也年度初安排时拥有的完好机器数量，（此也为第为第 k-1 年度末时的完好机器数量）。年度末时的完好机器数量）。3、决策变量决策变量 uk：第第 k年度初安排在年度初安排在高高负荷下进行生产的机器数量，负荷下进行生产的机器数量，于是于是 sk-uk 为该年度初安排在为该年度初安排在低低负荷下进行生产的机器数量。负荷下进行生产的机器数量。决策集合决策集合 Dk（sk）=uk|0 uk sk 4、状态转移方程：状态转移方程：sk+1=0.7 uk +0.9（sk-uk）5、定义阶段指标值（函数）定义阶段指标值（函数）vk（sk，uk）=8 uk+5（sk-uk）6、定义定义 fk（sk）：）：第第 k 年度初拥有的完好机器数量为年度初拥有的完好机器数量为 sk 时，将其时，将其安排（分配）于第安排（分配）于第 k 至第至第 5 年中两种负荷下进行生产时所生产的年中两种负荷下进行生产时所生产的最大最大产量。产量。7、作出动态规划结构图：作出动态规划结构图：sk sk+1=0.7 uk +0.9（sk-uk）k阶段阶段fk（sk）k+1阶段阶段fk+1（sk+1）max（）8 uk+5（sk-uk）0 uk sk 8、建立动态规划基本方程：（逆序递推方程）建立动态规划基本方程：（逆序递推方程）fk（sk）=max 8 uk+5（sk-uk）+fk+1（sk+1），k=5,4,3，2，1f6（s6）=09、逆序递推求解动态规划基本方程。逆序递推求解动态规划基本方程。0 uk sk k=5f5（s5）=max 8 u5+5（s5-u5）=max 3u5+5s5 =8s5 0 u5 s5 u*5（s5）=s5 k=4f4（s4）=max 8 u4+5（s4-u4）+f5（s5）0 u4 s4=max 8 u4+5（s4-u4）+8s5 =max 8 u4+5（s4-u4）+8（0.7 u4 +0.9（s4-u4）=max 1.4 u4+12.2 s4 =13.6s4 u*4（s4）=s4k=3f3（s3）=max 8 u3+5（s3-u3）+f4（s4）0 u3 s3=max 8 u3+5（s3-u3）+13.6s4 =max 8 u3+5（s3-u3）+13.6（0.7 u3 +0.9（s3-u3）=max 0.28 u3+17.24 s3 17.5s3 u*3（s3）=s3 k=2f2（s2）=max 8 u2+5（s2-u2）+f3（s3）0 u2 s2=max 8 u2+5（s2-u2）+17.5s3 =max 8 u2+5（s2-u2）+17.5（0.7 u2 +0.9（s2-u2）=max-2.5 u2+20.75 s2 20.8s2 u*2（s2）=0k=1f1（s1）=max 8 u1+5（s1-u1）+f2（s2）0 u1 s1=max 8 u1+5（s1-u1）+20.8s2 =max 8 u1+5（s1-u1）+20.8（0.7 u1 +0.9（s1-u1）=max-1.16 u1+23.72 s1 23.7s1 u*1（s1）=0 10、顺序确定顺序确定最优策略。最优策略。p*15=u*1，u*2，u*5 s1=1000s2=900s5 397s3=810s4=567u*1=0u*2=0u*3=810u*4=567u*5=397 最大产量最大产量 f1（s1=1000）=23700 ，五年生产期结束时五年生产期结束时（即第六年初还剩余）有完好机器（即第六年初还剩余）有完好机器 s6=0.7 397=278（台）台）sk+1=0.7 uk +0.9（sk-uk）思考题：如果要求思考题：如果要求5年结束完好机器为年结束完好机器为500台，求解过程又如何？台，求解过程又如何？上面所讨论的最优策略过程，初始端状态s1=1000台是固定的，终点状态s6没有要求。这种情况下得到最优决策称为初始端固定终点自由的最优策略。如果终点附加一定的条件，则问题就称为“终端固定问题”。例如，规定在第5年度结束时仍要保持500台机器完好（而不是278台），应如何安排生产才能使得总产量最大？由得 显然，由于固定了终点的状态，显然，由于固定了终点的状态，x5的取值受到了的取值受到了约束。因此有约束。因此有 类似的，容易解得 ，f4(s4)=21.7s4-7500。动态规划模型的要点1.将问题的过程划分成恰当的阶段；将问题的过程划分成恰当的阶段；2.正确选择状态变量正确选择状态变量sk；3.确定决策变量确定决策变量uk以及每阶段允许的决策集合以及每阶段允许的决策集合Dk(sk);4.正确写出状态转移方程正确写出状态转移方程sk+1=T(sk,uk)；5.正确写出指标函数以及基本方程；正确写出指标函数以及基本方程；谢谢大家！谢谢大家！