数模(动态规划)课件

1数学模型电子教案数学模型电子教案重庆邮电大学重庆邮电大学数理学院数理学院沈世云沈世云1数学模型电子教案重庆邮电大学2第第7章章 动动 态态 规规 划划(Dynamic programming)动态规划的基本思想动态规划的基本思想最短路径问题最短路径问题投资分配问题投资分配问题背包问题背包问题2第7章 动 态 规 划动态规划的基本思3 动态规划是用来解决多阶段决策过程最优动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一化的一种数量方法。其特点在于，它可以把一个个n 维决策问题变换为几个一维最优化问题，从维决策问题变换为几个一维最优化问题，从而一个一个地去解决。而一个一个地去解决。需指出：动态规划是求解某类问题的一种需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。用动态规划方法去求解。3 动态规划是用来解决多阶段决策过程最优化的一4即在系统发展的不同时刻（或阶段）根据系统即在系统发展的不同时刻（或阶段）根据系统所处的状态，不断地做出决策；所处的状态，不断地做出决策；每个阶段都要进行每个阶段都要进行决策决策,目的是使整个过程的决策目的是使整个过程的决策 达到最优效果。达到最优效果。动态决策问题的特点：动态决策问题的特点：系统所处的状态和时刻是进行决策的重要因素；系统所处的状态和时刻是进行决策的重要因素；找到不同时刻的最优决策以及整个过程的最优策略。找到不同时刻的最优决策以及整个过程的最优策略。多阶段决策问题：多阶段决策问题：是动态决策问题的一种特殊形式；是动态决策问题的一种特殊形式；在多阶段决策过程中在多阶段决策过程中,系统的动态过程可以按照时间系统的动态过程可以按照时间进程分为进程分为状态状态相互相互联系联系而又相互而又相互区别区别的各个的各个阶段阶段；4即在系统发展的不同时刻（或阶段）根据系统所处的状态，不断地5多阶段决策问题的典型例子：多阶段决策问题的典型例子：1.1.生产决策问题生产决策问题：企业在生产过程中，由于需：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。根据库存和需求决定生产计划。2.2.机机器器负负荷荷分分配配问问题题：某某种种机机器器可可以以在在高高低低两两种种不不同同的的负负荷荷下下进进行行生生产产。在在高高负负荷荷下下进进行行生生产产时时，产品的年产量产品的年产量g和投入生产的机器数量和投入生产的机器数量u1的关系为的关系为g=g(u1)12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策5多阶段决策问题的典型例子：2.机器负荷分配问题：某6 这时，机器的年完好率为这时，机器的年完好率为a，即如果年初完好机，即如果年初完好机器的数量为器的数量为u，到年终完好的机器就为，到年终完好的机器就为au,0a1。在低负荷下生产时，产品的年产量在低负荷下生产时，产品的年产量h和投入生产和投入生产的机器数量的机器数量u2的关系为的关系为 h=h(u2)假定开始生产时完好的机器数量为假定开始生产时完好的机器数量为s s1 1。要求制。要求制定一个五年计划，在定一个五年计划，在每年开始时，决定如何重新每年开始时，决定如何重新分配分配完好的完好的机器在两种不同的负荷下生产的数量机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。使在五年内产品的总产量达到最高。相应的机器年完好率相应的机器年完好率b b,0,0 b b11。6 这时，机器的年完好率为a，即如果年初完好机器的数量为7 3.3.航天飞机飞行控制问题：由于航天飞机的航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。目的（如软着落问题）。不包含时间因素的静态决策问题（本质上是一不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。多阶段的决策问题用动态规划方法来解决。4 4.线性规划、非线性规划等静态的规划问题也线性规划、非线性规划等静态的规划问题也可以通过适当地引入阶段的概念，应用动态规划方可以通过适当地引入阶段的概念，应用动态规划方法加以解决。法加以解决。7 3.航天飞机飞行控制问题：由于航天飞机的运动的8 5.最短路问题最短路问题：给定一个交通网络图如下，其中：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从两点之间的数字表示距离（或花费），试求从A点到点到G点的最短距离（总费用最小）。点的最短距离（总费用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687636853384222133352566438 5.最短路问题：给定一个交通网络图如下，其中两9（一）、基本概念（一）、基本概念 1、阶段：、阶段：把一个问题的过程，恰当地分为若干个相互联系的把一个问题的过程，恰当地分为若干个相互联系的阶阶段段，以便于按一定的次序去求解。，以便于按一定的次序去求解。描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量。阶段的划分，一般是。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。化为多阶段决策。2、状态：表示每个阶段开始所处的、状态：表示每个阶段开始所处的自然状况或客观自然状况或客观条件条件。通常一个阶段有若干个状态，描述过程状态的。通常一个阶段有若干个状态，描述过程状态的变量称为变量称为状态变量状态变量。年、月、年、月、路段路段一个数、一个数、一组数、一组数、一个向一个向量量 状态变量的取值有一定的允许集合或范围，此集合状态变量的取值有一定的允许集合或范围，此集合称为称为状态允许集合状态允许集合。一、动态规划的基本思想一、动态规划的基本思想9（一）、基本概念2、状态：表示每个阶段开始所处的自然状况10 3、决策：表示当过程处于某一阶段的某个状态时，、决策：表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态可以作出不同的决定，从而确定下一阶段的状态，这这种决定称为种决定称为决策决策。描述决策的变量，称为描述决策的变量，称为决策变量决策变量。决策变量是状态。决策变量是状态变量的函数。可用一个数、一组数或一向量（多维情变量的函数。可用一个数、一组数或一向量（多维情形）来描述。形）来描述。在实际问题中决策变量的取值往往在某一范围之内，在实际问题中决策变量的取值往往在某一范围之内，此范围称为此范围称为允许决策集合允许决策集合。系统在某一阶段的状态转移不但与系统的当前的状态系统在某一阶段的状态转移不但与系统的当前的状态和决策有关，而且还与系统过去的历史状态和决策有和决策有关，而且还与系统过去的历史状态和决策有关。关。4、多阶段决策过程多阶段决策过程 可以在各个阶段进行决策，去控制过程发展的多段过可以在各个阶段进行决策，去控制过程发展的多段过程；程；其发展是通过一系列的状态转移来实现的；其发展是通过一系列的状态转移来实现的；10 3、决策：表示当过程处于某一阶段的某个状态时，11图示如下：图示如下：状态转移方程是确定状态转移方程是确定过程由一个状态到另过程由一个状态到另一个状态的演变过程。一个状态的演变过程。如果第如果第k阶段状态变量阶段状态变量sk的值、该阶段的决策的值、该阶段的决策变量一经确定，第变量一经确定，第k+1阶段状态变量阶段状态变量sk+1的值的值也就确定。也就确定。其状态转移方程如下（一般形式）其状态转移方程如下（一般形式）12ks1u1s2u2s3skuksk+1 能用动态规划方法求解的多阶段决策过程是一类能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即特殊的多阶段决策过程，即具有无后效性具有无后效性的多阶段的多阶段决策过程。决策过程。11图示如下：状态转移方程是确定过程由一个状态到另一个状态的12 如果状态变量不能满足无后效性的要求，应如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。适当地改变状态的定义或规定方法。动态规划中能动态规划中能处理的状态转移处理的状态转移方程的形式方程的形式。状态具有无后效性的多阶段决策过程的状状态具有无后效性的多阶段决策过程的状态转移方程如下态转移方程如下无后效性无后效性(马尔可夫性马尔可夫性)如果某阶段状态给定后，则在这个阶段以后如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；过程的发展不受这个阶段以前各段状态的影响；过程的过去历史只能通过当前的状态去影响过程的过去历史只能通过当前的状态去影响它未来的发展；它未来的发展；构造动态规划模型时，要充分注意是构造动态规划模型时，要充分注意是否满足无后效性的要求；否满足无后效性的要求；状态变量要满足无后效性的要求状态变量要满足无后效性的要求；12 如果状态变量不能满足无后效性的要求，应适13 5 5、策略：是一个按顺序排列的决策组成的集合。在、策略：是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，称为实际问题中，可供选择的策略有一定的范围，称为允允许策略集合许策略集合。从允许策略集合中找出达到最优效果的。从允许策略集合中找出达到最优效果的策略称为策略称为最优策略最优策略。6 6、状态转移方程：是确定过程由一个状态到另一个、状态转移方程：是确定过程由一个状态到另一个状态的演变过程，描述了状态转移规律。状态的演变过程，描述了状态转移规律。7 7、指标函数和最优值函数：用来衡量所实现过程优、指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标，为劣的一种数量指标，为指标函数指标函数。指标函数的最优值，。指标函数的最优值，称为称为最优值函数最优值函数。在不同的问题中，指标函数的含义。在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产量或资源是不同的，它可能是距离、利润、成本、产量或资源消耗等。消耗等。动态规划模型的指标函数，应具有可分离性，并满动态规划模型的指标函数，应具有可分离性，并满足足递推递推关系关系。13 5、策略：是一个按顺序排列的决策组成的集合。在实际问14小结小结:方程方程 :状态转移方程状态转移方程概念概念 :阶段变量阶段变量k k状态变量状态变量s sk k决策变量决策变量u uk k;指标指标:动态规划本质上是多阶段决策过程动态规划本质上是多阶段决策过程;效益效益指标函数形式指标函数形式:和、和、积积无后效性无后效性可递推可递推14小结:方程:状态转移方程概念:阶段变量k状态变量15解多阶段决策过程问题，求出解多阶段决策过程问题，求出 最优策略最优策略，即最优，即最优决策序列决策序列f1(s1)最优轨线最优轨线，即执行最优策略时的即执行最优策略时的状态序列状态序列 最优目标函数值最优目标函数值从从 k 到终点最优策略到终点最优策略子策略的最优目标函数值子策略的最优目标函数值15解多阶段决策过程问题，求出 最优策略，即最优决策16 1、动态规划方法的关键在于正确地写出基本的递推、动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。要做到关系式和恰当的边界条件（简称基本方程）。要做到这一点，就必须将问题的过程分成几个相互联系的阶这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。优解，就是整个问题的最优解。（二）、动态规划的基本思想（二）、动态规划的基本思想16（二）、动态规划的基本思想17 2、在多阶段决策过程中，动态规划方法是既把当前、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段分开，又把当前效益和未来效益结合一段和未来一段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不是从全局来考虑的，与该段的最优选择答案一般是不同的同的.最优化原理：作为整个过程的最优策略具有这样的最优化原理：作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优策所形成的状态而言，余下的决策序列必然构成最优子策略。子策略。”也就是说，一个最优策略的子策略也是最也就是说，一个最优策略的子策略也是最优的。优的。3、在求整个问题的最优策略时，由于初始状态是、在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐段变换得到，从而确定策略所经过的各段状态便可逐段变换得到，从而确定了最优路线。了最优路线。17 2、在多阶段决策过程中，动态规划方法是既把当前18（三）、建立动态规划模型的步骤（三）、建立动态规划模型的步骤 1 1、划分阶段、划分阶段划划分分阶阶段段是是运运用用动动态态规规划划求求解解多多阶阶段段决决策策问问题题的的第第一一步步，在在确确定定多多阶阶段段特特性性后后，按按时时间间或或空空间间先先后后顺顺序序，将将过过程程划划分分为为若若干干相相互互联联系系的的阶阶段段。对对于于静静态态问问题题要要人为地赋予人为地赋予“时间时间”概念，以便划分阶段。概念，以便划分阶段。2 2、正确选择状态变量、正确选择状态变量选选择择变变量量既既要要能能确确切切描描述述过过程程演演变变又又要要满满足足无无后后效效性性，而而且且各各阶阶段段状状态态变变量量的的取取值值能能够够确确定定。一一般般地地，状状态态变量的选择是从过程演变的特点中寻找。变量的选择是从过程演变的特点中寻找。3 3、确定决策变量及允许决策集合、确定决策变量及允许决策集合通通常常选选择择所所求求解解问问题题的的关关键键变变量量作作为为决决策策变变量量，同同时时要给出决策变量的取值范围，即确定允许决策集合。要给出决策变量的取值范围，即确定允许决策集合。18（三）、建立动态规划模型的步骤 19 4 4、确定状态转移方程、确定状态转移方程根据根据k 阶段状态变量和决策变量，写出阶段状态变量和决策变量，写出k+1阶段状态变阶段状态变量，状态转移方程应当具有递推关系。量，状态转移方程应当具有递推关系。5 5、确定阶段指标函数和最优指标函数，建立动态规、确定阶段指标函数和最优指标函数，建立动态规划基本方程划基本方程 阶段指标函数是指第阶段指标函数是指第k 阶段的收益，最优指标函数是阶段的收益，最优指标函数是指从第指从第k 阶段状态出发到第阶段状态出发到第n 阶段末所获得收益的最优阶段末所获得收益的最优值，最后写出动态规划基本方程。值，最后写出动态规划基本方程。以上五步是建立动态规划数学模型的一般步骤。由于以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。不断实践总结，才能较好掌握建模方法与技巧。19 4、确定状态转移方程 以上五步是建立动态规划数学20例一、从例一、从A 地到地到D 地要铺设一条煤气管道地要铺设一条煤气管道,其中需经过其中需经过两级中间站，两点之间的连线上的数字表示距离，如两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？图所示。问应该选择什么路线，使总距离最短？AB1B2C1C2C3D24333321114二、最短路径问题二、最短路径问题20例一、从A 地到D 地要铺设一条煤气管道,其中需经过两级21 解：整个计算过程分三个阶段，从最后一个阶段开始。解：整个计算过程分三个阶段，从最后一个阶段开始。第一阶段（第一阶段（C D）：）：C 有三条路线到终点有三条路线到终点D。AB1B2C1C2C3D24333321114DC1C2C3显然有显然有 f1(C1)=1 ；f1(C2)=3 ；f1(C3)=4 21 解：整个计算过程分三个阶段，从最后一个阶段开始。第22 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)22 第二阶段（B C）：B 到C 有六条路线23 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)23 AB1B2C1C2C3D243333211124第三阶段（第三阶段（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)AB1B2C1C2C3D24333321114DC1C2C3B1B2A24第三阶段（A B）：A 到B 有二条路线。25AB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路线为最短路线为 AB1C1 D 路长为路长为 625AB1B2C1C2C3D24333321114DC1C226练习练习1：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最优路线为：最优路线为：A B1 C2 D1 E2 F2 G 路长路长18求从求从A到到G的最短路径的最短路径326练习1：AB1B2C1C2C3C4D1D2D3E1E2E27k=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)=327k=5，出发点E1、E2、E3u5(E1)=F1AB1B28k=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)=D1f3(C4)=12 u3(C4)=D3k=3,=minf1(A)=mind1(A,B1)+f2(B1)d1(A,B2)+f2(B2)5+133+16=18k=1,u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E228k=4，f4(D1)=7 u4(D1)=E2k=2,29u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2u5(E1)=F1E1 F1 Gu5(E2)=F2E2 F2 Gu5(E3)=F2E3 F2 G7 5 9 u5(E2)=F2u6(F2)=G最优策略最优策略AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664329u1(A)=B1u2(B1)=C2u3(C2)=D1u430求从求从A到到E的最短路径的最短路径路线为路线为AB2C1 D1 E，最短路径为最短路径为1919AB2B1B3C1C3D1D2EC25214112610104312111396581052练习练习2：130求从A到E的最短路径路线为AB2C1 D1 E 31 现有数量为现有数量为a（万元）的资金，计划分配给（万元）的资金，计划分配给n 个工厂个工厂,用于扩大再生产。用于扩大再生产。假设：假设：xi 为分配给第为分配给第i 个工厂的资金数量（万元）个工厂的资金数量（万元）；gi(xi)为第为第i 个工厂得到资金后提供的利润值（万元）。个工厂得到资金后提供的利润值（万元）。问题是如何确定各工厂的资金数，使得总的利润为问题是如何确定各工厂的资金数，使得总的利润为最大。最大。据此，有下式：据此，有下式：三、投资分配问题三、投资分配问题31 现有数量为a（万元）的资金，计划分配给n 个工32 令：令：fk(x)=以数量为以数量为x 的资金分配给前的资金分配给前k 个工厂，所得个工厂，所得到的最大利润值。到的最大利润值。用动态规划求解，就是求用动态规划求解，就是求 fn(a)的问题。的问题。当当 k=1 时，时，f1(x)=g1(x)（因为只给一个工厂）（因为只给一个工厂）当当1kn 时，其递推关系如下：时，其递推关系如下：设：设：y 为分给第为分给第k 个工厂的资金（其中个工厂的资金（其中 0y x），此时），此时还剩还剩 x y（万元）的资金需要分配给前（万元）的资金需要分配给前 k-1 个工厂个工厂,如如果采取最优策略，则得到的最大利润为果采取最优策略，则得到的最大利润为fk1(xy),因此因此总的利润为：总的利润为：gk(y)fk1(xy)32 令：fk(x)=以数量为x 的资金分配给前k 个33 如果如果a 是以万元为资金分配单位，则式中的是以万元为资金分配单位，则式中的y 只取只取非负整数非负整数0，1，2，x。上式可变为：。上式可变为：所以，根据动态规划的最优化原理，有下式：所以，根据动态规划的最优化原理，有下式：33 如果a 是以万元为资金分配单位，则式中的34 例题：例题：设国家拨给设国家拨给60万元投资，供四个工厂扩建使用，每万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。利润函数如下表所示。投投资资利润利润0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570解：依据题意，是要求解：依据题意，是要求 f4(60)。34 例题：投资010203040506035按顺序解法计算。按顺序解法计算。第一阶段：求第一阶段：求 f1(x)。显然有。显然有 f1(x)g1(x)，得到下表，得到下表 投投资资利润利润0102030405060f1(x)g1(x)0205065808585最优策略最优策略0102030405060第二阶段：求第二阶段：求 f2(x)。此时需考虑第一、第二个工厂如。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。何进行投资分配，以取得最大的总利润。35按顺序解法计算。投36最优策略为（最优策略为（40，20），此时最大利润为），此时最大利润为120万元。万元。同理可求得其它同理可求得其它 f2(x)的值。的值。36最优策略为（40，20），此时最大利润为120万元。同理37最优策略为（最优策略为（30，20），此时最大利润为），此时最大利润为105万元。万元。37最优策略为（30，20），此时最大利润为105万元。38最优策略为（最优策略为（20，20），此时最大利润为），此时最大利润为90万元。万元。最优策略为（最优策略为（20，10），此时最大利润为），此时最大利润为70万元。万元。38最优策略为（20，20），此时最大利润为90万元。最优策39最优策略为（最优策略为（10，0）或（）或（0，10），此时最大利润，此时最大利润为为20万元。万元。f2(0)0。最优策略为（最优策略为（0，0），最大利润为），最大利润为0万元。万元。得到下表得到下表最优策略为（最优策略为（20，0），此时最大利润为），此时最大利润为50万元。万元。39最优策略为（10，0）或（0，10），此时最大40 投投资资利润利润0102030405060f2(x)020507090105120最优策略最优策略(0,0)(10,0)(0,10)(20,0)(20,10)(20,20)(30,20)(40,20)第三阶段：求第三阶段：求 f3(x)。此时需考虑第一、第二及第三个。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。工厂如何进行投资分配，以取得最大的总利润。40 投资010203041最优策略为（最优策略为（20，10，30），最大利润为），最大利润为155万元。万元。同理可求得其它同理可求得其它 f3(x)的值。得到下表的值。得到下表41最优策略为（20，10，30），最大利润为155万元。同42 投投资资利润利润0102030405060f3(x)0256085110135155最优最优策略策略(0,0,0)(0,0,10)(0,0,20)(0,0,30)(20,0,20)(20,0,30)(20,10,30)第四阶段：求第四阶段：求 f4(60)。即问题的最优策略。即问题的最优策略。42 投资0102030405060f3(x)02543最优策略为（最优策略为（20，0，30，10），最大利润为），最大利润为160万元。万元。43最优策略为（20，0，30，10），最大利润为160万元44 练习：练习：求投资分配问题得最优策略，其中求投资分配问题得最优策略，其中a50 万元，其余万元，其余资料如表所示。资料如表所示。投投资资利润利润01020304050g1(x)02140528085g2(x)015365073100g3(x)0256065687044 练习：投资01020304050g145例：某公司打算在例：某公司打算在3个不同的地区设置个不同的地区设置4个销售点，根个销售点，根据市场部门估计，在不同地区设置不同数量的销售点据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表所示。试问在各地区如何设置每月可得到的利润如表所示。试问在各地区如何设置销售点可使每月总利润最大。销售点可使每月总利润最大。地地区区销售点销售点01234123000161210251714302116322217 x1=2，x2=1，x3=1，f3(4)=47 45例：某公司打算在3个不同的地区设置4个销售点，根据市场部46 有一个徒步旅行者，其可携带物品重量的限度为有一个徒步旅行者，其可携带物品重量的限度为a 公公斤，设有斤，设有n 种物品可供他选择装入包中。已知每种物品种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？的物品（各几件），使所起作用（使用价值）最大？物品物品 1 2 j n重量（公斤重量（公斤/件）件）a1 a2 aj an每件使用价值每件使用价值 c1 c2 cj cn 这就是背包问题。类似的还有工厂里的下料问题、运这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。输中的货物装载问题、人造卫星内的物品装载问题等。四、背包问题四、背包问题46 有一个徒步旅行者，其可携带物品重量的限度为a 公斤47设设xj 为第为第j 种物品的装件数（非负整数）则问题的数学种物品的装件数（非负整数）则问题的数学模型如下：模型如下：用动态规划方法求解，令用动态规划方法求解，令 fx(y)=总重量不超过总重量不超过 y 公斤，包中只装有前公斤，包中只装有前k 种物品种物品时的最大使用价值。时的最大使用价值。其中其中y 0，k 1,2,n。所以问题就是求所以问题就是求 fn(a)47设xj 为第j 种物品的装件数（非负整数）则问题的数学模48其递推关系式为：其递推关系式为：当当 k=1 时，有：时，有：48其递推关系式为：当 k=1 时，有：49例题：求下面背包问题的最优解例题：求下面背包问题的最优解物品物品 1 2 3重量（公斤）重量（公斤）3 2 5使用价值使用价值 8 5 12解：解：a5 ，问题是求，问题是求 f3(5)49例题：求下面背包问题的最优解物品 1 2 505051515252535354所以，最优解为所以，最优解为 X（1.1.0），），最优值为最优值为 Z=13。54所以，最优解为 X（1.1.0），最优值为55 练习练习1：某厂生产三种产品，各种产品重量与利：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售，润的关系如表所示。现将此三种产品运往市场出售，运输能力总重量不超过运输能力总重量不超过 6 吨，问如何安排运输，使吨，问如何安排运输，使总利润最大？总利润最大？种类种类 1 2 3重量（吨重量（吨/公斤）公斤）2 3 4 单件利润（元）单件利润（元）80 130 180最优方案：最优方案：X1=（0.2.00.2.0）X2=（1.0.11.0.1）Z=260=26055 练习1：某厂生产三种产品，各种产品重量与利润的56 练习练习2：求下列问题的最优解：求下列问题的最优解 X=(2.1.0)最优值为最优值为 Z=1356 练习2：求下列问题的最优解 57 排序问题指排序问题指n 种零件经过不同设备加工是的顺序问题。种零件经过不同设备加工是的顺序问题。其目的是使加工周期为最短。其目的是使加工周期为最短。1、n 1 排序问题排序问题 即即n 种零件经过种零件经过1 种设备进行加工，如何安排？种设备进行加工，如何安排？14682023交货日期（交货日期（d）45173加工时间（加工时间（t）零件代号零件代号例例1 五、排序问题五、排序问题57 排序问题指n 种零件经过不同设备加工是的顺序问58 （1）平均通过设备的时间最小）平均通过设备的时间最小 按零件加工时间非负次序排列顺序，其时间最小。（即按零件加工时间非负次序排列顺序，其时间最小。（即将加工时间由小到大排列即可）将加工时间由小到大排列即可）零件加工顺序零件加工顺序 工序时间工序时间13457 实际通过时间实际通过时间1481320 交货时间交货时间82314620 平均通过时间平均通过时间58 （1）平均通过设备的时间最小 按零件加工时59延迟时间延迟时间=13 6=7 （2）按时交货排列顺序）按时交货排列顺序零件加工顺序零件加工顺序 工序时间工序时间13457 实际通过时间实际通过时间56101720 交货时间交货时间82314620 平均通过时间平均通过时间延迟时间延迟时间=059延迟时间=13 6=7 （2）按时交货60 （3）既满足交货时间，又使平均通过时间最小）既满足交货时间，又使平均通过时间最小零件加工顺序零件加工顺序 工序时间工序时间13457 实际通过时间实际通过时间1691320 交货时间交货时间82314620延迟时间延迟时间=0 平均通过时间平均通过时间60 （3）既满足交货时间，又使平均通过时间最小零件加61 2、n 2 排序问题排序问题 即即n 种零件经过种零件经过2 种设备进行加工，如何安排？种设备进行加工，如何安排？例二、例二、49523B53786A 零件零件设备设备ABT61 2、n 2 排序问题例二、49523B5362经变换为经变换为49523B53786A 零件零件设备设备加工顺序图如下：加工顺序图如下：ABT3756895432+2+2-5 加工周期加工周期 T=3+7+5+6+8+2=3162经变换为49523B53786A 63 3、n 3 排序问题排序问题 即即n 种零件经过种零件经过 3 种设备进行加工，如何安排？种设备进行加工，如何安排？例三、例三、3468564683579310CBA63 3、n 3 排序问题例三、3468564664ABCT变换变换4+36+45+86+56+48+65+37+53+910+3B+CA+B64ABCT变换4+36+45+86+56+48+65+3765排序排序4+36+45+86+56+48+65+37+53+910+3B+CA+B复原复原3468564683579310CBA65排序4+36+45+86+56+48+65+37+53+66计算计算T=6+10+8+7+6+4+3=44计算依据：计算依据：66计算T=6+10+8+7+6+4+3=44计算依67练习：练习：11851079827746CBAT=4567练习：11851079827746CBAT=4568一一 动态规划的基本概念和最优化原理动态规划的基本概念和最优化原理1、引例（最短路问题）、引例（最短路问题）假如上图是一个线路网络，两点之间连线上的数字表示假如上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），我们的问题是要将货物从两点间的距离（或费用），我们的问题是要将货物从A地运地运往往E地，中间通过地，中间通过B、C、D三个区域，在区域内有多条路径三个区域，在区域内有多条路径可走，现求一条由可走，现求一条由A到到E的线路，使总距离最短（或总费用的线路，使总距离最短（或总费用最小）。最小）。AB1B2B3C1C2C3D1D2E2437463242653463333468一 动态规划的基本概念和最优化原理1、引例（最短路问题69第四阶段，由第四阶段，由D1到到E只有一条路线，其长度只有一条路线，其长度f4（D1）=3，同理同理f4（D2）=4。第三阶段，由第三阶段，由Cj到到Di分别均有两种选择，即分别均有两种选择，即，决策点为D1,决策点为D1，决策点为D269第四阶段，由D1到E只有一条路线，其长度f4（D1）=370第二阶段，由Bj到Cj分别均有三种选择，即：决策点为C2 决策点为C1或C2决策点为C2 70第二阶段，由Bj到Cj分别均有三种选择，即：决策点为C71第一阶段，由A到B，有三种选择，即：决策点为B3 f1（A）=15说明从A到E的最短距离为12，最短路线的确定可按计算顺序反推而得。即AB3C2D2E 上述最短路线问题的计算过程，也可借助于图形直观的表示出来：71第一阶段，由A到B，有三种选择，即：决策点为B3 72 图图中中各各点点上上方方框框的的数数，表表示示该该点点到到E的的最最短短距距离离。图图中中红箭线表示从红箭线表示从A到到E的最短路线。的最短路线。从引例的求解过程可以得到以下启示：从引例的求解过程可以得到以下启示：对对一一个个问问题题是是否否用用上上述述方方法法求求解解，其其关关键键在在于于能能否否将将问问题转化为相互联系的决策过程相同的多个阶段决策问题。题转化为相互联系的决策过程相同的多个阶段决策问题。AB1B2B3C1C2C3D1D2E243746324265346333343467699111272 图中各点上方框的数，表示该点到E的最短距离。图中73案例案例6、设备更新问题、设备更新问题 在已知一台设备的效益函数r(i)，维修费用函数u(i)及更新费用函数C(i)条件下，在n年内，每年年初作出决策，是继续使用旧设备还是更换一台新设备，使n年总效益最大的这类问题称为设备更新问题。设rk(i)表示在第k年设备已使用i年（或称役令为i年的设备），再使用1年产生的效益：uk(i)表示在第k年设备役令为i年，再使用1年的维修费用；Ck(i)表示在第k年卖掉一台役令为i的设备，买进一台新设备的更新净费用(即新设备的购买费-旧设备折旧费）。P112例题：设某企业在今后4年内需用一辆卡车，现有一辆已使用了2年的旧车，根据统计资料分析，预计卡车的年收入、年维修费（包括油料费）、一次性更新重置费及4年后的残值如下表：73案例6、设备更新问题 在已知一台设备的效益函数r74（1）阶段划分：卡车使用的每一年作为一个阶段，k=1,2,3,4（2）状态变量sk：表示设备的役龄。即在第k年初，设备已使用的年限数。s1=2,s2=1,3,s3=1,2,4,s4=1,2,3,5,s5=1,2,3,4,6（3）决策变量dk：表示在第k年初对役龄为sk的设备的决策，是更新，还是继续使用，即i0123456rk(i)161411852-vk(i)122344-ck(i)-1821252934-t5(i)-15128300试确定4年中的最优更新计划，以使总利润最大？1、建立动态规划模型74（1）阶段划分：卡车使用的每一年作为一个阶段，k=1,275(6)指标函数：指标函数fk(sk)表示第k年初，使用一台役令为sk年的卡车，到第4年末的最大收益。(5)阶段指标：(4)状态转移方程：（7）基本方程为：f5(s5)=t5(s5)75(6)指标函数：指标函数fk(sk)表示第k年初，使用一762、用逆序算法求解结果如下表：s41235f4(s4)14-2+12=24*16-1-18+15=1211-2+8=17*16-1-21+15=98-3+3=8*16-1-25+15=42-4+0=-2*16-1-34+15=-5d4*kkkks3124f3(s3)14-2+17=2916-1-18+24=2111-2+8=1716-1-21+24=185-4-2=-116-1-29+24=10D3*kRR762、用逆序算法求解结果如下表：s41235f4(s4)177s12f1(s1)11-2+19=28*16-1-21+30=24d1*ks213f2(s2)14-2+18=30*16-1-18+29=268-3+10=1516-1-25+29=19*d2*kR由此可得最优更新方案为：d1(2)=k,d2(3)=R,d3(1)=k,d4(2)=k其含义是第一年役龄为2年的卡车不更新，第二年役龄为3年的卡车更新，第三年役龄为1年的卡车不更新，第四年役龄为2年的卡车不更新。77s12f1(s1)11-2+19=28*d1*ks213