2022年动态规划模型与实验 .pdf

《2022年动态规划模型与实验 .pdf》由会员分享，可在线阅读，更多相关《2022年动态规划模型与实验 .pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最优化模型与实验第169页第七章动态规划模型与实验一个系统依据某种方式分为许多个不同的阶段，这些阶段不仅有着次序推移性， 而且相互间有着依赖和影响。 这种能分成阶段推移的系统叫做动态系统。 动态规划是解决多阶段决策过程最优化的一种数学方法。动态规划的一个显著特点在于具有明确的阶段性，整个系统按某种方式可分为若干个不同的阶段，在每个阶段由若干种不同的方案可供选择。这样，在多阶段决策过程中，每个阶段决策的选择，不仅要依据次序来考查某阶段的效果外，而且更要顾及此决策对以后各阶段决策的影响， 特别是对以后各个阶段决策的影响。系统最优决策问题要求在系统每个阶段可供的多种方案(决策) 中，选择一个合适的决

2、策，使整个系统达到最优的效果。整个过程分为多阶段的决策过程。各个阶段所做的决策形成确定整个系统的决策序列，称这样的决策序列为系统的一个策略。对应某一确定的策略， 整个系统依据某种数量指标衡量其优劣的决策。 多阶段决策过程就是在所有允许策略集合中。确定一个达到最优指标的最优策略。这种衡量系统的指标一般取最大值或最小值的策略。因此，多阶段决策过程也是一个可以构成多个变量的最优化问题。 一个系统能分为多阶段的决策过程，有时需要数学技巧和艺术来划分， 动态规划就是解决此类多阶段决策过程的最优化方法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

3、 - - 名师精心整理 - - - - - - - 第 1 页，共 17 页 - - - - - - - - - 第七章动态规划模型与实验第170页 7.1 动态规划的基本原理实际生活的问题， 通过构造数学模型， 具有特殊的动态系统过程，将基于某种方式把整个过程分成若干个互相联系的阶段，在其每个阶段都需要作出合适决策，从而使整个过程达到最佳效果。同时，各个阶段决策的选择依赖于该阶段的状态以及前或后阶段的变化。各个阶段决策确定后， 组成一个决策序列， 从而形成了整个过程具有前后关联的链状结构的多阶段决策过程，称为序贯决策过程。由此，动态规划求解首先关键在于如何将实际问题构造成能形成多阶段的系统，

4、并且在各个阶段能作出序贯性的最佳决策，以使在序贯决策的状态推移进程中达到整个系统的最优决策。例 7.1 能分成阶段的最短路问题。图7.1 是一个路线网络图，连线上的数字表示两点之间的距离（或费用），要求寻找一条由A 到 E的路线，使距离最短（或费用最省） 。B1C1D1AB2C2ED2B3C3图 7.1 对于这样一个比较简单的问题，可直接使用枚举法列举所有从A到 E 的路线，共 14条，然后，根据每条路线的长度（或费用） ，确定出所应走的路线（费用）最短（少） 。直观的思想，如果已找到由A 到 E 的最短路线是AB1C2D2E（记作 L） ，那么当寻求 L 中的任何一点（如C2）到 E8 6

5、5 7 9 9 9 7 4 5 10 5 5 5 6 8 11 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 17 页 - - - - - - - - - 最优化模型与实验第171页的最短路时，它必然是L 中子路线 C2D2E（记作 L1） 。否则若 D2到 E 的最短路是另一条路线L2 ，则把 AB1C2与 L2连接起来，就会得到一条不同于L 的从 A 到 E 的最短路。根据此特性，可以从最后一段开始， 用逐步向前递推的方法， 依次求出路段上各点到 E 的最短路，最后

6、得到A 到 E 的最短路。上述这种由系统的作后阶段逐段向初是始阶段求最优的过程称为动态规划的逆推解法。该过程揭示了动态规划的基础思想， 为使动态规划的思想和方法数学上描述。下面先引入动态规划中基本概念与最优目标函数的建立。（1）分阶段把所给的系统，适当地依据具体情况分成若干个相互联系的阶段，描述阶段的变量称为阶段变量，常用k 表示，并将各个阶段按顺序或逆序加以编号， 如例 7.1可分为 5 个阶段来求解，k=1，2，3，4，5。（2）状态状态表示系统在某一阶段所处的位置，自然状况或客观条件。一个阶段系统会存在若干个可能的状态。在例7.1 中，状态就是某阶段的出发位置， 它既是该阶段某之路的起点

7、，又是前一阶段某之路的终点， 一个阶段有若干个状态， 第一阶段有一个状态就是初始位置 A，第二阶段有三个状态，即使集合B1，B2，B3，一般第k阶段的状态就是第k 阶段所有始点的集合。描述过程状态的变量称为状态变量，常用Sk表示第 k 阶段的所有可能状态变量的集合，其元素为sk可以是数，数组或向量。如例7.1中第三阶段有三个状态， 则 sk可能取三个值，即C1,C2,C3，并且 S3=C1，C2，C3 称为第三阶段的可达状态集合。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页

8、，共 17 页 - - - - - - - - - 第七章动态规划模型与实验第172页（3）决策决策表示当系统处于某一阶段的某个状态时，可以作出不同的选择， 确定下一阶段的状态， 这种决定称为决策。 描述决策的变量称为决策变量，常用dk(sk)表示第 k 阶段当状态处于sk时的决策变量，它是状态变量的函数。而用Dk (Sk) 表示相应的决策变量的函数集，即有 dk (sk)Dk(Sk)。如在例 7.1第二阶段中，从状态B2出发，其允许决策集合为D2(B2)=C1，C2，C3，某一阶段的状态变量及决策变量的值取定之后，那么下一阶段的状态随之确定。例如选取的点为 C2，则 C2是状态 B1在决策

9、d2(B1)作用下的一个新的状态，记作 d2(B1)= C2，下一阶段的状态类似地对上阶段的状态和决策变量的依赖关系可用状态转移方程表示：sk+1=Tk (sk，d k (sk) ) (7.1) (4) 策略由系统各阶段确定的决策所形成的决策序列称为策略。从初始状态 s1出发由系统的所有 n个阶段的决策所形成的策略成为全过程策略，记为：P1，n(s1)= d1(s1)， d2(s 2)， ， dn(sn) (7.2) 由系统的第 k 个阶段出发的后面 n k +1 个阶段的决策过程称为全过程的后部子过程，相应的策略称为后部子过程策略，记为Pk，n(sk)=d k(sk)， d k+1(s k+

10、1)， ， dn(sn) (7.3) 所有可供选择的策略集合称为策略集合，用 P 表示，从允许策略集合中找出达到最优效果的策略称为最优策略。（5）状态转移方程状态转移方程是确定过程由一个状态到另一个状态的演变过程。 若给定第 k 阶段状态的演变过程，并且若该阶段名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 17 页 - - - - - - - - - 最优化模型与实验第173页的决策变量 dk一经确定，第 k+1 阶段的状态变量sk+1也就完全确定，这种对应关系为：sk

11、+1=Tk(sk，dk(sk) 所描述了由第k个阶段到第 k+1 个阶段的状态转移规律， 称为状态转移方程。Tk称为第 k 阶段的状态转移系数。 如例 7.1 中，状态转移方程为sk+1=dk(sk) (6) 阶段收益系统某一阶段的状态一经确定， 执行某一决策所得的效益称为阶段效益， 它是整个系统总收益的一部份。阶段效益是阶段状态和决策变量的函数，反映该阶段的价值与目标。对第k 阶段的某一状态 sk执行某一决策 dk(sk)的阶段效益可用rk(sk，dk(sk)来表示。在例 7.1中的阶段效益为走完一段路程所花费的距离。(7) 指标函数和最优值函数系统执行某一策略所产生效果的优劣可用数量指标来

12、衡量，这样的数量指标是整个系统总效益的反映，它是各个阶段状态和决策的函数，称为指标函数。 它是定义在全进程和所有子进程上确定的数量函数，记Fk，n(sk, pk，n)，i=n，n-1，1 (7.4) 表示从阶段k 的某一状态 sk出发的后部子进程上的指标函数，其中pk，n表示从状态 sk出发的一个子策略， 最优策略下指标函数的指标为最优策略指标，记为),()(,opt,nkknkPpkkpsFsfnknk(7.5) 其中 Pk, n表示由状态Sk出发的所有允许子策略集合， “opt”为英文名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

13、- - 名师精心整理 - - - - - - - 第 5 页，共 17 页 - - - - - - - - - 第七章动态规划模型与实验第174页Optimization（最优）的缩写，可以依题意取min 或 max。由上述指标函数的定义，可得指标函数（例7.1 的指标函数注记rk(sk，dk(sk)表示第 k 阶段中点 sk到 dk(sk)的距离） 。1 ,1,)()(,()(.1,1nnksFsdsrsknFkknkkkkk其中1, 1,),(,(1nkkjsdsTsjjjjj(7.6) 而最优策略指标为1 , 1,),()(,()(,1, 1)(optnnkpsTfsdsrsfnkkkn

14、kkkkksdkkkk(7.7) 在例 7.1 中显然有fn+1(sn+1) = 0 (7.8) 称为边值条件 ，动态规划的求解对k=n, n-1,1 由（7.7）式求最优策略指标的过程。一般地对多数指标函数的形式取（7.6）式，而最优策略指标取形如（7.7）式，以求和形式出现，另一种常用形式是的各阶段的指标函数为乘积，即1 ,1,),()(,() )(,(),(,1,1,nnkpsFsdsrsdsrpsFnkknkkkkknkjjjjjnkknk(7.9) 其相应的最优策略指标为1 , 1,)(,()(,()(1,1)(optnnksdsTfsdsrsfkkkknkkkkksdkkkk(7.

15、10) 对更一般的系统来说， 指标函数未必是求和或乘积形式，但应具有可分离性，并满足递推关系，一般具有形式名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 17 页 - - - - - - - - - 最优化模型与实验第175页),(,(),(,(),(,1,1,nkkkkknkkkknkknkpsdsTFsdspsF(7.11) )(,(),(,()(1)(optkkkkkkkksdkksdsTfsdssfkk(7.12) 在第 k 阶段，指标函数最优策略指标，即最优值，

16、称为最优值函数，即 fk(sk)。根据上述确定的阶段编号、 状态变量、决策变量、状态转移方程以及指标函数，确定例7.1 的最短路线，计算步骤如下：根据最短路线特性，寻找最短路线的方法，将从最后一段开始，用由后向前逐步递推的方法， 求出各点到 E 点的最短路线， 最后求得由 A 点到 E 点的最短路线。所以，动态规划的方向是从各点逐段向始点方向寻找最短路线的一种方法，见图7.2 显示行进方向1 2 3 4 5 始点终点动态规划寻优途径图 7.2 当 k= 4 时，由 D1到终点 E 只有一条路线， 故 f4(D1) = 6，同理，f4(D2) = 5。当 k= 3 时，出发点有 C1、C2、C3

17、三个，若从 C1出发，则有两个选择，一是至 D1，一是至 D2，则115765min)(),()(),(min)(242131411313DfDCrDfDCrCf其相应的决策为d3(C1)=D1，表示由 D1至终点 E 的最短距离为 11，其最短路线是 C1D1E。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 17 页 - - - - - - - - - 第七章动态规划模型与实验第176页同理，从 C2和 C3出发，则有105566min)(),()(),(min)(2

18、42251412323DfDCrDfDCrCf其相应的决策为d3(C2) = D2。1451168min)(),()(),(min)(242331413333DfDCrDfDCrCf且 d3(C3) = D3。类似地，可计算当k=2 时，有f 2（B1）= 18 d2（B1）= C2f 2（B2）= 19 d2（B2）= C2f 2（B3）= 15 d2（B3）= C2当 k=1 时，出发点只有一个A 点，则23159177185min)(),()(),()(),(min)(3232222212111BfBArBfBArBfBArAf且 d1（A）= B1，于是获得从始点A 至终点 E 的最短

19、距离为 15。为使找出最短路线，再接计算的顺序推之，可求出最优决策函数序列dk，即由 d1（A）= B1，d2（B1）= C2，d3（C2）= D2，d4（D2）= E，组成一个最优策略。那么最短路线为AB1C2D2E。从上述例 7.1的计算过程，可知动态规划的方法比枚举有以下优点：（1）减少计算量，使用枚举法，要对18 条路线比较，即比较运算进行 18次，逐阶段累计加法为64 次。使用动态规划来计算，比较运算为 7 次，加法运算 16 次，可见，动态规划方法比穷举法减少了许多计算量，而且随着规模扩大，计算量将大大地减少。名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

20、 - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 17 页 - - - - - - - - - 最优化模型与实验第177页（2）丰富了计算结果，虽然枚举法执行了较多的运算，其结果只有从起点 A 到终点 E 的一个结果，用动态规划方法以较少的运算不仅得到从 A 至 E 的最优路线，而且还确定了各中间点到终点E 的最优路线。 7.2LINGO 软件计算动态规划使用 LINGO 软件计算上述动态规划问题。设：A顶点（城市） 1，B12，B23，B34，C15，C26，C37，D18，D29，E点（城市） 10。本例使用 LINGO 程序的编制动态规划

21、模型如下：MODEL: SETS: ! Dynamic programming illustration. We have a network of 10 cities. We want to find the length of the shortest route from city 1 to city 10.; ! Here is our primitive set of ten cities, where F( i) represents the shortest path distance from city i to the last city; CITIES /1.10/: F;

22、 ! The derived set ROADS lists the roads that exist between the cities (note: not all city pairs are directly linked by a road, and roads are assumed to be one way.); ROADS( CITIES, CITIES)/ 1,2 1,3 1,4 2,5 2,6 3,5 3,6 3,7 4,5 4,6 5,8 5,9 6,8 6,9 7,8 7,9 8,10 9,10/: D; ! D( i, j) is the distance fro

23、m city i to j; ENDSETS DATA: ! Here are the distances that correspond to the above links; D = 5 7 9 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 17 页 - - - - - - - - - 第七章动态规划模型与实验第178页 9 8 11 7 4 5 10 5 7 6 5 8 11 6 5; ENDDATA ! If you are already in City 10

24、, then the cost to travel to City 10 is 0; F( SIZE( CITIES) = 0; ! The following is the classic dynamic programming recursion. In words, the shortest distance from City i to City 10 is the minimum over all cities j reachable from i of the sum of the distance from i to j plus the minimal distance fro

25、m j to City 10; FOR( CITIES( i)| i #LT# SIZE( CITIES): F( i) = MIN( ROADS( i, j): D( i, j) + F( j) ); END 程序第十行， 集合CITES 表示点，赋值F(i)表示从城市 i 到最后一个城市的最短距离。第十五行中集合ROADS(? , ? ) 表示连接城市间的弧，而数据 D(ji,) 表示从城市i到城市j的距离。动态规划的目标函数，即为从城市i到最后城市 10的最短距离为所有从城市i到城市j可达到路加上从j到城市 10的最短距离的和的最小值。 使用SOLVE求解得结果如下，其中 F（i）表示第

26、 i个（城市）点至最后（城市）终点E的距离。从上述计算过程，可归纳k阶段与 k+1 阶段之间的递推关系)()(,()(,1)(optkknkkkkksDdkksdfsdsrsfkkk(7.13) 称为动态规划的基本方程，以及边值条件为：fn+1 (sn+1 )=0 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 17 页 - - - - - - - - - 最优化模型与实验第179页动态规划方法的基本思想归纳如下：（1） 归纳出基本的递推关系式和恰当的边值条件，即基本方

27、程。（2） 在多阶段决策过程中， 虽是独立的阶段， 但又将当前阶段效益和未来效益阶段结合起来的一种最优化方法。（3） 在求解整个系统的最优策略时，由于初始状态是已知的， 而每阶段的决策都有该阶段的函数，所以最优策略经过的各段状态，便可逐次变递推换得到，从而确定了最优的路线。例如，在例 7.1 中，初始状态 A 已知，上述逐次变换如图7.3。d1(A) d2(B1) d4(D2) （已知）AB1C2E图 7.3 从而可得最优策略为d1(A)，d2(B1)，, ， d4(D2)，相应的最短路线为 AB1C2D2E，计算过程，使用图7.4 直观简明地表示，图中每节点处上方的方格内的数，表示该点到终点

28、 E 的最短距离，用直线连接点表示该点到终点E 的最短路线，未连线的点表示该点到终点 E 不是最短路线，（舍去） ，图中粗线表示由始点A 到终点 E 的最短路线，这种由 E 点开始从后向前， 即从终点至起点求优的过程叫做逆推解法，逆推法不仅求出A 到 E 最优路线，而且确定了任意点到点 E 的最优路线， 如果问题不仅要求确定从点A到点 E 的最优路线，并要求知道 A 到其它点的最优路线， 可采用从始端逐步向终端求优的顺推解法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，

29、共 17 页 - - - - - - - - - 第七章动态规划模型与实验第180页B1C1D1AB2C2ED2B3C3图 7.4 7.3 顺推解法对例 7.1 来说，顺推解法以A 为始端，逐阶段计算各中间点到A的最优路线，直至确定E 到 A 的最优路线，用顺推法求解时，可以根据情况对阶段重新编号，确定各阶段的允许状态集合， 各状态的允许决策集合，状态转移方程，阶段效益及指标函数，如果阶段编号，状态变量与决策变量取值保持不变， 则第 k阶段的状态变量应是sk+ 1，而不是 sk。这由于在顺推算法时sk+1成为 k 阶段的“初始状态”，而sk成为采取某一决策后的“终止状态”。因此，相应的状态转移

30、方程为)(,(11/kkkkksdsTs(7.14)它应是逆推算法中状态转移方程的逆变换，其次从初始阶段向最后阶段过渡的指标函数与最优指标应满足),(,(),(,(),(1 ,111/,1111,kkkkknkkkkkknkpsdsTFsdspsF(7.15) nksdsTfsdssfkkkkkkkksdkkkk,1 ,0,)(,(),(,()(11/111)(opt(7.16) 边值条件为0)(10sf(7.17) 在例 7.1 中，若阶段编号，状态变量与决策变量的定值不变，则顺推解法的指标函数为23 18 19 16 11 10 14 6 5 名师资料总结 - - -精品资料欢迎下载 -

31、- - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 17 页 - - - - - - - - - 最优化模型与实验第181页5,2,1),(,(),(111,1,isdsrpsFjijjjjkkk最优指标为)(,()(,()(1/111)(minkkkkkkkkksdkksdsTfsdsrsfkk在图 7.5 中，表示顺推过程的图解，详细计算不再聱述，每个节点处上方方格内的数表示该点到A 点的最短距离，用直线连接的点表示该点到始点A的最短路线，粗线表示A 到 E 的最短路线。B1C1D1AB2C2ED2B3C3图 7.

32、5注意 A到 D1有两条最短路，即AB1C1D1，或 AB2C3D1。使用 LINGO 软件程序编制软件本例的顺推法， 只要设 E1 点 （城市） ，D12，D23，C14，C25，C36，B17，B28，B39，A10 点（城市）。计算动态规划（顺推法）LINGO 程序如下：MODEL: SETS: ! Dynamic programming illustration. We have a network of 10 cities. We want to find the length of the shortest route from city 1 to city 10.; ! Here

33、 is our primitive set of ten cities, where F( i) represents the shortest path distance from city i to the last city; CITIES /1.10/: F; ! The derived set ROADS lists the roads that exist between the cities (note: not all city pairs are directly linked by a road, and roads are assumed to be one way.);

34、 ROADS( CITIES, CITIES)/ 1,2 1,3 2,4 2,5 2,6 3,4 3,5 3,6 4,7 4,8 23 5 7 9 14 13 11 19 18 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 17 页 - - - - - - - - - 第七章动态规划模型与实验第182页 5,7 5,8 5,9 6,8 6,9 7,10 8,10 9,10/: D; ! D( i, j) is the distance from city i to j

35、; ENDSETS DATA: ! Here are the distances that correspond to the above links; D = 6 5 5 6 8 7 5 11 9 11 8 7 5 4 10 5 7 9; ENDDATA ! If you are already in City 10, then the cost to travel to City 10 is 0; F( SIZE( CITIES) = 0; ! The following is the classic dynamic programming recursion. In words, the

36、 shortest distance from City i to City 10 is the minimum over all cities j reachable from i of the sum of the distance from i to j plus the minimal distance from j to City 10; FOR( CITIES( i)| i #LT# SIZE( CITIES): F( i) = MIN( ROADS( i, j): D( i, j) + F( j) ); END 详细解释参见逆推法，使用SOLVE求解得结果如下，其中 F(i）表示

37、第i个点至起点 A的距离。归纳如下，使用动态规划解一个可分阶段的多阶段决策问题时，必须包含下面步骤。（1）将系统划分成恰当的阶段，并编号；（2）确定状态变量ks，状态变量集合kS；（3）确定决策变量)(kksd，以及允许决策变量集合)(kkSD；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 17 页 - - - - - - - - - 最优化模型与实验第183页（4）建立状态转移方程)(,(1kkkkksdsTS；（5）确定各阶段的阶段效益)(,(kkkksdsr；（

38、6）建立指标函数),(,(),(,(),(,1/,1,1,nkkkkknkkkknkknkpsdsTFsdspsF；（7）0)(,1 ,1,11nnsfnnk为边值条件，求最优指标)(,(),(,()(1)(optkkkkkkkksdkksdsTfsdssfkk并给出相应于最优指标的状态转移方程。（8）对 k=1,2, ， n，从最优指标的状态转移方程求得最优决策。上述求解过程由图7.6 所示，在选择状态变量时应能正确地反映整个多阶段决策的演变过程，同时又必须满足无后效性的要求，即某阶段的状态一旦确定， 则该阶段以后过程的演变不受该阶段以前演变过程的影响， 而只与该状态本身有关， 状态变量应选

39、择尽可能的明确简单。图 7.6S2 f1(s1)Fn, n(sn, p1, n) F1, n(s1, p1, n) fn(sn)rn(sn,dn) 决策d1 d n 决策r1(s1,d1) 阶段 1 T1(s1,d1)阶段 n Tn(sn,dn)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 17 页 - - - - - - - - - 第七章动态规划模型与实验第184页动态规划的最优性原理和最优性定理* 动态规划的最优性定理设阶段数为n的多阶段决策系统，其阶段编号为

40、k =0,1, ,n1。允许策略),(*1*1*0*1,0nndddp是最优策略的重要条件是对任一个k，0kn1和 s0S0有),(),(),(1,*1,)(1,001,0)(*1,001,0optopt1,1,01,01,0nkknksPpnksPpnnpsFpsFpsFknknkkk(7.18) 其中),(),(1,1,01,0111*nkknkkkkpppdsTs它是由给定的初始状态S0和子策略1,0kp所确定的 k 段状态，当 F 是效益函数时， opt 取 max；当F是损失函数时， opt 取 min。（证明省略）推论：若允许策略*1,0 np是最优策略， 则对任意的 0 k n1

41、, 它的子策略*1, nkp对于以),(*1*11*kkkkdsTs为起点的 k 到 n1 子过程来说，必是最优策略。 （注意： k段状态*ks是由 s0和*1,0 kp所 确定的） 。 （证明省略）此推论即是上述提及的动态规划的“最优性原理”，仅是最优策略的必要性。所以，上述定理才是动态规划的理论基础。习题七7.1求下列网络中从起点（左端点）到终点（右端点）的最短路线及其长度：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 17 页 - - - - - - - - -

42、 最优化模型与实验第185页7.2某工厂有100 台机器，拟分4 期使用，在每一周期有两种生产任务，若将1x 台机器投入第一种生产任务，则将余下的机器投入第二种生产任务。根据经验投入第一种生产任务的机器在一个生产周期中将有1/3 的机器报废。投入第二种生产任务的机器，则在一个生产周期中将有 1/10 的机器报废。 如果在一个生产周期中，第一种生产任务每台机器可收益10 元，第二种生产任务每台机器可收益7 元。问怎样分配机器数，使总收益最大？其最大收益是多少？7.3用动态规划方法求解下列各题：(1) 222211295maxxxxxz；(2) 2321294maxxxxz；s.t. 521xx；

43、s.t. 10321xxx；0,21xx。0,321xxx。7.4有一部货车沿着公路的4 个零售点共卸下6 箱货物，各零售点因出售该货物所得的利润如题 7.4 表所示。试求在各零售店各卸下几箱货物，能使获得的总利润最大？其最大利润是多少？题 7.4 表零售点箱数1 2 3 4 0 0 0 0 0 1 4 2 3 4 2 6 4 5 5 3 7 6 7 6 4 7 8 8 6 5 7 9 8 6 6 7 10 8 6 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 17 页 - - - - - - - - -