教案动态规划改

《教案动态规划改》由会员分享，可在线阅读，更多相关《教案动态规划改（96页珍藏版）》请在金锄头文库上搜索。

1、动态规划动态规划（Dynamic Programming） R. Bellman50年代执教于普林斯顿和斯坦福大学，年代执教于普林斯顿和斯坦福大学，后进入兰德（后进入兰德（Rand）研究所。）研究所。1957年发表年发表“Dynamic Programming”一书，标识动态规划的正式诞生。一书，标识动态规划的正式诞生。 动态规划的研究对象和引例动态规划的理论基础和具体迭代方动态规划的理论基础和具体迭代方 法法动态规划的基本思想和基本方程动态规划的基本思想和基本方程动态规划的基本概念和定义动态规划的基本概念和定义 动态规划是解决复杂系统优化问题的一种方法。动态规划是解决复杂系统优化问题的一种方

2、法。是解决是解决动态系统多阶段动态系统多阶段决策过程的基本方法之一决策过程的基本方法之一。页册债坍白疮净单硼怪仲贬叛弟秘颂脉元鲍拔污幌菊蕊须吗汹蹈得渡哀噬教案动态规划改教案动态规划改教学大纲教学大纲: 理解理解动态规划基本概念、最优化原理动态规划基本概念、最优化原理和基本方程，通过资源分配和生产与存储和基本方程，通过资源分配和生产与存储等问题等问题,学习应用动态规划解决多阶段决学习应用动态规划解决多阶段决策问题。策问题。 重点重点 : 掌握动态规划掌握动态规划模型结构模型结构、逆序、逆序法法算法原理算法原理、资源分配、设备更新、生产资源分配、设备更新、生产于存贮于存贮等问题。等问题。难点难点为

3、动态规划中为动态规划中状态变状态变量量等的确定。等的确定。鹅弧耸四琢拭挠输醋拯呸张骡麻道假仑基谱凳更瑚耐携澄迹气寡阴毗遵馆教案动态规划改教案动态规划改AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456第一节 动态规划的研究对象和引例引例引例1 最短路问题最短路问题贯堕搐婚帅膀诲谴体荤挑着柒另阴缘羌悲爬硒陈臼婉丘郁礁徊牙髓啡任躁教案动态规划改教案动态规划改多阶段决策问题的典型例子：多阶段决策问题的典型例子： 1 . 生产决策问题生产决策问题：企业在生产过程中，由于需：企业在生产过程中，由于需求是随时间变化的，因此企

4、业为了获得全年的最佳求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。根据库存和需求决定生产计划。 2. 机机器器负负荷荷分分配配问问题题：某某种种机机器器可可以以在在高高低低两两种种不不同同的的负负荷荷下下进进行行生生产产。在在高高负负荷荷下下进进行行生生产产时时，产品的年产量产品的年产量g和投入生产的机器数量和投入生产的机器数量u1的关系为的关系为g=g(u1)12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策虞送荆吧焰狭荚键蛹嗅殿署无诌肿骡烛卿爷码希唉徐召北佩糊户嘴蹄

5、擦赂教案动态规划改教案动态规划改 这时，机器的年完好率为这时，机器的年完好率为a，即如果年初完好机，即如果年初完好机器的数量为器的数量为u，到年终完好的机器就为，到年终完好的机器就为au, 0a1。 在低负荷下生产时，产品的年产量在低负荷下生产时，产品的年产量h和投入生和投入生产的机器数量产的机器数量u2的关系为的关系为 h=h(u2) 假定开始生产时完好的机器数量为假定开始生产时完好的机器数量为s1。要求制。要求制定一个五年计划，在定一个五年计划，在每年开始时，决定如何重新每年开始时，决定如何重新分配分配完好的完好的机器在两种不同的负荷下生产的数量机器在两种不同的负荷下生产的数量，使在五年内

6、产品的总产量达到最高。使在五年内产品的总产量达到最高。 相应的机器年完好率相应的机器年完好率b, 0 b1。 瘴讼篓眷凿拯跨沮品韧半郊拭老堰暇眩谱九沦犬幕屁楔虾盂阅石蹬血鼠址教案动态规划改教案动态规划改 3. 航天飞机飞行控制问题：由于航天飞机的航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。目的（如软着落问题）。 不包含时

7、间因素的静态决策问题（本质上是一不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。多阶段的决策问题用动态规划方法来解决。 4 . 线性规划、非线性规划等静态的规划问题也线性规划、非线性规划等静态的规划问题也可以通过适当地引入阶段的概念，应用动态规划方可以通过适当地引入阶段的概念，应用动态规划方法加以解决，后面将详细介绍。法加以解决，后面将详细介绍。邯渴仲寸校营匈柄搪汝茬咙埔汀凌褪崎箱老墒碴远吵号谚奏歪芬嗜由要姬教案动态规划改教案动态规划改 最短路问题最短路问题：给定一个交通网络图

8、如下，其中两：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从点之间的数字表示距离（或花费），试求从A点到点到G点的最短距离（总费用最小）。点的最短距离（总费用最小）。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456凰扭芯诺瘫毯汛幽毫粪微腆枪猖鹊躯嘛哲识茄归滓主怂判堆攒己娃劣河刃教案动态规划改教案动态规划改生产存贮决策问题生产存贮决策问题最短路问题最短路问题机器负荷分配问题机器负荷分配问题典型典型 问题问题:软清劝渊猜至最维但习此鹤湘蒙名厩聋装酣誊族空瞥嘴眠嵌立卑啤烛送仟教案动态规划改教案动

9、态规划改 但要便于把问题的过程能转化为多阶段决策但要便于把问题的过程能转化为多阶段决策 的过程。的过程。 状态变量的取值有一定的允许集合或范围，此集状态变量的取值有一定的允许集合或范围，此集合称为合称为状态允许集合状态允许集合。 第二节第二节 动态规划的基本概念和定义动态规划的基本概念和定义 1. 阶段、阶段变量阶段、阶段变量 把所给问题的过程，适当地分为若干个相互联系把所给问题的过程，适当地分为若干个相互联系的的阶段阶段; 描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量，常用，常用k表示；表示； 阶段的划分，一般是按时间和空间的自然特征来阶段的划分，一般是按时间和空间的自然特征来划分划

10、分 ；2. 状态、状态变量状态、状态变量每个阶段开始所处的自然状态或客观条件。每个阶段开始所处的自然状态或客观条件。通常一个阶段有若干个状态。通常一个阶段有若干个状态。 描述过程状态的变量称为描述过程状态的变量称为状态变量状态变量，常用，常用sk表示表示第第k阶段的状态。阶段的状态。年、月、年、月、路段路段一个数、一个数、一组数、一组数、一个向一个向量量晴小悍踏梧笼隘脏琴芦宝诧胚誉悉横断侄脆芳檄胃肪贺侮诌澄掠他泌藉哄教案动态规划改教案动态规划改 在实际问题中决策变量的取值往往在某一范围之在实际问题中决策变量的取值往往在某一范围之内，此范围称为内，此范围称为允许决策集合允许决策集合。常用。常用D

11、k(sk)表示第表示第k阶段从状态阶段从状态sk出发的允许决策集合，显然有出发的允许决策集合，显然有 一个数一个数一组数一组数一个向量一个向量决定下一阶段的状态，这种决定称为决定下一阶段的状态，这种决定称为决策决策。在最优控制中也称为在最优控制中也称为控制控制。描述决策的变量，称为描述决策的变量，称为决策变量。决策变量。决策变量是状态变量的函数。决策变量是状态变量的函数。常用常用uk(sk) 表示第表示第k阶段当状态为阶段当状态为 sk时的决策变量。时的决策变量。3. 决策、决策变量决策、决策变量 过程的某一阶段、过程的某一阶段、 某个状态某个状态, 可以做出不同的决可以做出不同的决定定(选择

12、选择),uk(sk) Dk(sk)折盗逢共微荫沪椭评酥伟捞厩笼琶真泛靳账英便阳撵药屎趴菲麻膏祖竟汕教案动态规划改教案动态规划改 系统在某一阶段的状态转移不但与系统的当前的系统在某一阶段的状态转移不但与系统的当前的状态和决策有关，而且还与系统过去的历史状态和决状态和决策有关，而且还与系统过去的历史状态和决策有关。其策有关。其状态转移方程状态转移方程如下（一般形式）如下（一般形式）图示如下：图示如下：状态转移方程状态转移方程是确定是确定过程由一个状态到另过程由一个状态到另一个状态的演变过程。一个状态的演变过程。如果第如果第k阶段状态变量阶段状态变量sk的值、该阶段的决策的值、该阶段的决策变量一经确

13、定，第变量一经确定，第k+1阶段状态变量阶段状态变量sk+1的值的值也就确定。也就确定。4. 多阶段决策过程多阶段决策过程 可以在各个阶段进行决策，去控制过程发展的可以在各个阶段进行决策，去控制过程发展的多段过程；多段过程； 其发展是通过一系列的状态转移来实现的；其发展是通过一系列的状态转移来实现的；黎幸粪砌蜡谨检实谰埂池柔鄙女分咋尧焉匿咖弗锅队刽己袱酶曙冬描登恬教案动态规划改教案动态规划改12ks1u1s2u2s3skukSk+1 能用动态规划方法求解的多阶段决策过程是一能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即类特殊的多阶段决策过程，即具有无后效性具有无后效性的多阶

14、的多阶段决策过程。段决策过程。搏盛屉全拎纽佳罩爬脊眼齐现突锚疏彩衅雕狂噬倚仪箩唐梗漳扑企腑擦闪教案动态规划改教案动态规划改 如果状态变量不能满足无后效性的要求，应适当如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。地改变状态的定义或规定方法。动态规划中能动态规划中能处理的状态转移处理的状态转移方程的形式方程的形式。 状态具有无后效性的多阶段决策过程的状态转状态具有无后效性的多阶段决策过程的状态转移方程如下移方程如下无后效性无后效性(马尔可夫性马尔可夫性) 如果某阶段状态给定后，则在这个阶段以后过程如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影

15、响；的发展不受这个阶段以前各段状态的影响； 过程的过去历史只能通过当前的状态去影响它未过程的过去历史只能通过当前的状态去影响它未来的发展；来的发展； 构造动态规划模型时，要充分注意是否满足构造动态规划模型时，要充分注意是否满足无后效性的要求；无后效性的要求；状态变量要满足无后效性的要求状态变量要满足无后效性的要求；负被椎提员希洁男篙养决芹峻耗管皂脚条鸣渊蒲淳论猛三菩齐眉巳札掷禄教案动态规划改教案动态规划改 由由每每段段的的决决策策按按顺顺序序排排列列组组成成的的决决策策函函数数序序列列称为称为k子过程策略，子过程策略， 当当k=1时，此决策函数序列成为全过程的一个时，此决策函数序列成为全过程的

16、一个策略，简称策略，简称策略策略，记为，记为p1,n (s1).即即 可供选择的策略有一定范围，此范围称为可供选择的策略有一定范围，此范围称为允许策允许策略集合略集合，用，用p表示。从允许策略集合中找出达到最优表示。从允许策略集合中找出达到最优效果的策略称为效果的策略称为最优策略最优策略。 5. 策略策略: 按顺序排列的决策组成的集合；按顺序排列的决策组成的集合； 由第由第k n(终止状态终止状态)为止的过程，称为问题的为止的过程，称为问题的后部子过程后部子过程（k子过程）。子过程）。简称简称子策略子策略，记为，记为pk,n(sk)，即，即裹帖周肮顽抉瞎舵碾细橙褂匀甫镑刀拆蚕砸狞旨享儡纳翰茂拼

17、凤桶惨聋轨教案动态规划改教案动态规划改 它是定义在全过程或所有后部子过程它是定义在全过程或所有后部子过程上确定的数量函数。上确定的数量函数。 动态规划模型的指标函数，应具有可分离性，动态规划模型的指标函数，应具有可分离性，并满足并满足递推递推关系。关系。常见的指标函数的形式是：常见的指标函数的形式是： 费用、成本、利润、路长等费用、成本、利润、路长等 。 用用Vk, n 表示之。表示之。6. 指标函数和最优值函数指标函数和最优值函数 用来衡量所实现过程优劣的一种数量指标，称用来衡量所实现过程优劣的一种数量指标，称为指标函数；为指标函数；即即V Vk k, ,n n可以表示为可以表示为s sk

18、k,u,uk k, ,V Vk+1,nk+1,n的函数。的函数。伴最嗽玲仗绕挺张触僻逸嗅夷夜筛辖弦猫雷装终餐伪滔疹埃险妹志翱吮测教案动态规划改教案动态规划改常见的指标函数的形式是：常见的指标函数的形式是： 过程和它的任一子过程的指标是它所包含的各过程和它的任一子过程的指标是它所包含的各阶段的指标和。即阶段的指标和。即无后效性的结果。无后效性的结果。 其其中中vj( (s sj ) ) 表表示示第第 j 阶阶段段的的阶阶段段指指标标。这这时时上上式式可写成可写成炒伴书卸匆邹本矩炬糙知描柞临丙员淳坛嘶抒邵蹿醉锌萧宜匝劈谈香蕉矾教案动态规划改教案动态规划改过程和它的任意子过程的指标是它所包含的各阶段

19、的过程和它的任意子过程的指标是它所包含的各阶段的指标的指标的 乘乘 积积。即。即则可改写成则可改写成犬嚣高旋混魂扇春蚤巷咙署啥舞漫拧颤坊阎官鞠隅杖肪标绒镀巨满稽驭幕教案动态规划改教案动态规划改 多阶段决策过程的数学模型：（具有无后效性的多阶段决策过程的数学模型：（具有无后效性的多阶段决策过程）多阶段决策过程） 第第k阶段阶段 第第n阶段阶段 状态状态sk 终止状态终止状态采取最优策略所得采取最优策略所得到的指标函数值。到的指标函数值。最优值函数最优值函数：即即可递推可递推汉踢癸晾瞥铭橱远笔题爵艳仍畜桓私渍棉艘炒交袋掌圃宝胀巾阅璃册敝布教案动态规划改教案动态规划改 多阶段决策过程的数学模型：（具

20、有无后效性）多阶段决策过程的数学模型：（具有无后效性）谋中梁叛拘京象偷赘讯即职双港缕烽胳络隶磋娜答骂钦斤碎田旨疙锌谗柄教案动态规划改教案动态规划改小结小结:方程方程 : 状态转移方程状态转移方程概念概念 : 阶段变量阶段变量k状态变量状态变量sk决策变量决策变量uk;指标指标: 动态规划本质上是多阶段决策过程动态规划本质上是多阶段决策过程; 效益效益指标函数形式指标函数形式: 和、和、 积积无后效性无后效性可递推可递推滓寓迂姚堪妨册弊蛙诸凯灼灶群答招都掐稽拄醒压雁大帜单蔫舔仆处渍赵教案动态规划改教案动态规划改解多阶段决策过程问题，求出解多阶段决策过程问题，求出 最优策略最优策略，即最优，即最优

21、决策序列决策序列f1(s1) 最优轨线最优轨线，即执行最优策略时的即执行最优策略时的状态序列状态序列 最优目标函数值最优目标函数值从从k到终点最优策略到终点最优策略子策略的最优目标函数值子策略的最优目标函数值式鹊岂籽材醇屏遭事届归姆爆氮七秒拿兴莆渊淹秩脸腺烤世迅迈下匪腆峙教案动态规划改教案动态规划改第三节：动态规划的基本思想和基本方程第三节：动态规划的基本思想和基本方程AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456劫尹例嚣胆条倡恬倪卉唐迸寻炮龟藤勘鸟众德茶溶揣斧袋信善棍磐捣帘堂教案动态规划改教案动态规划改37

22、5976713109111316 18 最短路的特性最短路的特性：如果已有从起点到终点的一条如果已有从起点到终点的一条最短路，那么从最短路线上中间任何一点出发到终最短路，那么从最短路线上中间任何一点出发到终点的路线仍然是最短路。（证明用反证法）点的路线仍然是最短路。（证明用反证法）4AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221233355 26631234564顽甄晒拇缴墟惶沿徒犬则撮呵灿岔聚鸵效我藩斗须泪崩绿迅谍篷砂碌俘敌教案动态规划改教案动态规划改k=5k=5，出发点，出发点E1E1、E2E2、E3E3u5(E1)=F1E1 F1 GA

23、B1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u5(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)=3精镊丘遇镍蛆锨洪稚墓捉坐肇嘉迈泽补孩偶墓初俞薪淡改虎仕骏涤座湃邻教案动态规划改教案动态规划改k=4，f4(D4)=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(

24、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)=E2泳铣盘党练骤歇橡家谈隘展增蚀纪钧闹怒蕾缠诽于汇斥瓶党蜂垮疽卉削狱教案动态规划改教案动态规划改AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u1(A)=B1u2(B1)=C2u3(

25、C2)=D1u4(D1)=E2u5(E1)=F1E1 F1 Gu5(E2)=F2E2 F2 Gu5(E3)=F2E3 F2 G7 5 9 u5(E2)=F2u6(F2)=G最优策略最优策略般友豆膏苑法粱钝卤哗若纲掖印谎瓦凉诗累佐蒂慈航瑞棵帕德赚眉生康颗教案动态规划改教案动态规划改用动态规划（逆序法求解的）基本特性：用动态规划（逆序法求解的）基本特性： 动动态态规规划划方方法法是是既既把把当当前前一一段段和和未未来来各各段段分分开开，又又把把当当前前效效益益和和未未来来效效益益结结合合起起来来考考虑虑的的一一种种最最优优化化方方法法。每每段段决决策策的的选选取取都都是是从从全全局局考考虑虑的的,

26、 ,与与该该段段的的最优选择答案一般是不同的。最优选择答案一般是不同的。 求解时求解时从边界条件开始从边界条件开始，逆逆（或顺）过程行进方（或顺）过程行进方向，逐段向，逐段递推递推寻优。在每个问题求解时，都要使用它寻优。在每个问题求解时，都要使用它前面已求出的子问题的最优结果，最后问题的最优解，前面已求出的子问题的最优结果，最后问题的最优解，就是整个问题的最优解。就是整个问题的最优解。 将多阶段决策过程将多阶段决策过程划分阶段划分阶段，恰当地选取，恰当地选取状态变状态变量量、决策变量决策变量、及定义、及定义最优指标函数，最优指标函数，正确写出基本正确写出基本的的递推关系式递推关系式和恰当的和恰

27、当的边界条件边界条件（简言之为基本方程）（简言之为基本方程）。从而把问题化成一族同类的子问题；。从而把问题化成一族同类的子问题；弯斯鹤夸镭别瓮惮孝蚁泡厢轨搐拎靳怀弄枷泪甩陵镜沪蔬盎蓑农铡疤侣哄教案动态规划改教案动态规划改 求解的各个阶段求解的各个阶段, ,我们利用了我们利用了k k阶段与阶段与k+1k+1阶段阶段之间的递推关系之间的递推关系: : 在求整个问题的最优策略时，由于初始状态是在求整个问题的最优策略时，由于初始状态是已知的，每段的决策是该段状态的函数，故沿最优已知的，每段的决策是该段状态的函数，故沿最优化策略所经过的各段状态便可确定了最优路线。化策略所经过的各段状态便可确定了最优路线

28、。fk(sk)=mindk(sk,uk(sk)+fk+1(uk(sk)uk Dk(sk)f7(s7)=0k=6,5,4,3,2,1育憾妻龄麻苍豪植宣牲桨详缝昔忌岛器徒埋吊忧推暑拢偏酗忽摄吠遍诱坤教案动态规划改教案动态规划改 一般情况一般情况,k,k阶段与阶段与k+1k+1阶段的递推关系式（动态阶段的递推关系式（动态规划基本方程）规划基本方程）边界条件为边界条件为练习：写出乘积形式指标函数的动态规划基本方程。练习：写出乘积形式指标函数的动态规划基本方程。 顺序解法：实际上没有顺序法！顺序解法：实际上没有顺序法！难杀圈割咐闸响秸扦渗帜莫河全祝气逛早松咕典奠傈踞蜘搅鞘拉仔冤莲寻教案动态规划改教案动态

29、规划改小结小结: 要具有可分离性，并满足递推关系。即要具有可分离性，并满足递推关系。即 函数函数 k k（s sk k，u uk k，V Vk+1,nk+1,n）对于变量）对于变量V Vk+1k+1，n n要严格单调。要严格单调。将问题的过程划分成恰当的阶段；将问题的过程划分成恰当的阶段；选选择择状状态态变变量量s sk k, , 既既能能描描述述过过程程的的变变化化又又满满足足无无后效性；后效性；确确定定决决策策变变量量u uk k及及每每一一阶阶段段的的允允许许决决策策集集合合D Dk k( (s sk k) )；正确写出状态转移方程；正确写出状态转移方程；正确写出指标函数正确写出指标函数

30、V Vk,nk,n，它应满足下面三个性质：，它应满足下面三个性质： 是定义在全过程和所有后部子过程上的数量函数是定义在全过程和所有后部子过程上的数量函数; ;微惜幼影芯细瑰思辐掉说疥魂萎女婴引迸坊吓覆呕拾雍掩韵蛀迷塔维戌蛇教案动态规划改教案动态规划改第四节：第四节： 动态规划的理论基础和动态规划的理论基础和 具体迭代方具体迭代方 法法 多阶段决策过程的特点：每个阶段都要进多阶段决策过程的特点：每个阶段都要进行决策，策略是由行决策，策略是由n个相继进行的决策构成的个相继进行的决策构成的决策序列。前一阶段的终止状态又是下一阶决策序列。前一阶段的终止状态又是下一阶段的初始状态，因此，确定阶段最优决策

31、不段的初始状态，因此，确定阶段最优决策不能只从阶段的效应来考虑，必须是整个过程能只从阶段的效应来考虑，必须是整个过程通盘考虑，整体规划。即阶段通盘考虑，整体规划。即阶段k的最优决策不的最优决策不应该只是本阶段效应的最优，而必须是本阶应该只是本阶段效应的最优，而必须是本阶段及其所有后续阶段的总体最优。段及其所有后续阶段的总体最优。羚扛思歹电诵衰淡游击鼓馋梦坛泥扑膨姻陷窃摹镜积臆逸估铃隶送未泅客教案动态规划改教案动态规划改 动态规划方法的理论基础是基于动态规划方法的理论基础是基于R. Bellman提出的提出的最优性原理：最优性原理：“一个过程的最优策略具有这样的性质：一个过程的最优策略具有这样的

32、性质：即无论其初始状态及初始决策如何，对于先前决策所形即无论其初始状态及初始决策如何，对于先前决策所形成的状态而言，余下的诸决策仍构成最优策略。成的状态而言，余下的诸决策仍构成最优策略。”AMB1 . 理论基础理论基础 适应于用动态规划方法求解的是具有无后效性的适应于用动态规划方法求解的是具有无后效性的多阶段决策过程。多阶段决策过程。 最优性原理的含义是：最优策略的任何一部分子最优性原理的含义是：最优策略的任何一部分子策略，也是它相应初始状态的最优策略。每个最优策策略，也是它相应初始状态的最优策略。每个最优策略只能由最优子策略构成。略只能由最优子策略构成。呻卓绒旺焰厨僚疵芥匠燃总虎袋忻袄邹悟熏

33、栗掘仔锈喉距廉傅懒暇操盆低教案动态规划改教案动态规划改 动动态态规规划划的的最最优优性性定定理理：设设阶阶段段数数为为n n的的多多阶阶段段决策过程，其阶段编号为决策过程，其阶段编号为k k=0,1,.,=0,1,.,n n-1-1。允许策略。允许策略是最优策略的充要条件是对任意一个是最优策略的充要条件是对任意一个k k, 0, 0k k n n-1-1和和s s0 0 S S0 0，有，有 它是由给定的初始状态它是由给定的初始状态s s0 0和子策略和子策略p p0,0,k k-1-1所确定的所确定的k k段状态。当段状态。当V V是效益函数时，是效益函数时，optopt取取max;max;

34、当当V V是损失函数是损失函数时，时，optopt取取min.min.范诸范蕉早蓝别尚权襟炼绊另缚用重审饱挨凛肌菱汲帮迅切窍柄府磕阿接教案动态规划改教案动态规划改证明：必要性（证明：必要性（ ）享犬凶米舍巧芯酶吓幂纤碍雪洋失杉属孕球案巍吁在钓森芹陪卫型间钨哉教案动态规划改教案动态规划改充分性（充分性（ ）设）设p0,n-1=(p0,k-1,pk,n-1)为任一策略，为任一策略，sk为由（为由（s0，p0,k-1）所确定的）所确定的k阶段的起始状态，则阶段的起始状态，则有（以最大化为例）有（以最大化为例）布析俐束痉娱谦付征挂芒嘻粗爽平茂尘衍讯妮幂杭玄吾骇勿酒菠彭项挥睛教案动态规划改教案动态规划改

35、 推论推论：若允许策略若允许策略p p* *0,n-10,n-1是最优策略，则对任意是最优策略，则对任意的的k,0kk,0k9/2当当当当时时时时矛盾，舍去矛盾，舍去。（最优决策）（最优决策）S20狼眺仓割侗雾狄供阑悉增饲邮笑淖赡野从绪瞪键喷刽驶湖宝虏毕袒壁委钾教案动态规划改教案动态规划改5.2 顺序解法顺序解法 自学内容自学内容5.3 动态规划的优缺点动态规划的优缺点优点优点: . 最优解是全局最优解。最优解是全局最优解。 . 能得到一系列（包括子过程）的最优解。能得到一系列（包括子过程）的最优解。 . 不需要对系统状态转移方程、阶段效应函数不需要对系统状态转移方程、阶段效应函数等的解析性质

36、作任何假设。等的解析性质作任何假设。缺点：缺点： .没有统一的标准模型和标准的算法可供使用。没有统一的标准模型和标准的算法可供使用。 .应用的局限性，要求满足应用的局限性，要求满足“无后效性无后效性”。 . “维数灾难维数灾难”问题。问题。排正棱盒得贴均贰嫌行胖葬第杏右石生葛锗以鸵垣漏甸搐讯巾秉酶翼渝熔教案动态规划改教案动态规划改资源分配问题资源分配问题生产与存贮问题生产与存贮问题设备更新问题设备更新问题苏磺土勃斯希孰攻忙榴耸蓄苑锯啸漱约栗箱辫揍譬雹尖办筋昏展瓮眯桌卉教案动态规划改教案动态规划改第一节第一节 资源分配问题资源分配问题 1.1 1.1 多元投资分配问题多元投资分配问题 设设有有某

37、某种种原原料料，总总数数量量为为a，用用于于生生产产n种种产产品品。若若分分配配数数量量xi用用于于生生产产第第i 种种产产品品，其其收收益益为为g gi i(x(xi i) )问应如何分配，才能使生产问应如何分配，才能使生产n种产品的总收入最大？种产品的总收入最大？ 将将数数量量一一定定的的一一种种或或若若干干种种资资源源，恰恰当当地地分分配配给若干个使用者，使效益函数为最优。给若干个使用者，使效益函数为最优。MAX =g1(x1)+ g2(x2)+ + gn(xn)x1+x2+ xn=axi0 i=1,2, ,ns.t.顷绰靠鸿编欲愉硝赃盛田睡警稻敢羡流母喳尖耪雄欲兢速蔷斯早雏椎幅判教案动

38、态规划改教案动态规划改决策集合决策集合：D Dk( (sk)=)=uk|0|0 uk= =xk sk uk: :分配给生产第分配给生产第k种产品的原料数量，即种产品的原料数量，即uk= =xk；sk: :分配给用于生产分配给用于生产第第k种至第种至第n种种产品的原料数量；产品的原料数量；状态转移方程状态转移方程： sk+1+1= =sk- -uk= =sk- -xk最最优优值值函函数数fk( (sk) ): :数数量量为为sk的的原原料料分分配配给给第第k种种产产品品至至第第n种种产产品品所所得得到到的的最最大大总总收收益益，动动态态规规划划的的递递推推关系为：关系为：痈狞赣做军茂报呵汐哨仗詹

39、扮儿吱馁敖蛙疗协溶帚翔挞素哩鉴粕祭滞郡坠教案动态规划改教案动态规划改某公司拟将某公司拟将5 5台某种设备分配给所属的甲、乙、丙台某种设备分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备，可以为公司三个工厂，各工厂若获得这种设备，可以为公司提供的盈利如表。提供的盈利如表。 问：这五台设备如何分配给各工厂，才能使问：这五台设备如何分配给各工厂，才能使公司得到的盈利最大。公司得到的盈利最大。例例1 1解解：将将问问题题按按工工厂厂分分为为三三个个阶阶段段，甲甲、乙乙、丙丙分分别别编号为编号为1 1，2 2，3 3。逆推法逆推法麦垫桔峙恍准梅婪碑鼓墒花图将谅巫舍滚牲失圈响展咋斟练馅散铅爪获柱教案动

40、态规划改教案动态规划改k=3时，时，0 s3 5， x3s3可分配的机器数量可分配的机器数量分配的机器数量分配的机器数量 sk+1+1= =sk- -uk= =sk- -xkf3(s3)=maxg3x3 x3s3f4(s4)=0x3 *(1) =1= g30=0S3=0, f3(0)=max g3x3+ f4(s4) x3s3x3 *(0) =0S3=1, f3(1)=max g3x3+ f4(s4) x3s34腿薯淄圈帽巫氏低竞封砸希驳阶鬃翔答惨乾采的污谣鲸匝蹋斯暗绍侮叮丑教案动态规划改教案动态规划改当阶段当阶段k=2时，时， s3=s2-x2， 0 s2 5， 0 x2 s2，有有俊渺鳞佣

41、哥朴委丁腋侍澡仇扬欲净邯惑柜普式赏续送挛络憎聚周攒重枉吟教案动态规划改教案动态规划改猛刽跃良敲猩债堵科泌玖袜再争铅其若恋怪漂杰肌嫌岁泌咐练飘椭捉肯擞教案动态规划改教案动态规划改汐啸贴错蚜诲变幽辕曼讯幻浇逻欠物贞羔梯灿门末诛矗速蓝变酥兴唐滤关教案动态规划改教案动态规划改撬戏牟使橱盟坛老匪坐杏械耻液赃菠饿男彬南瞻氮狗役钡涪路韦勺厄寂角教案动态规划改教案动态规划改结果列于下表：结果列于下表：f3(1-0)=f3(1) =4 f3(5-3)=f3(2)阉混琐戮障鞭库嘴戏光娄器低宜梯对墟弘榨宅熙除番戍冉敞遁蛛用蚀并燃教案动态规划改教案动态规划改当阶段当阶段k=1时，时， s2=s1-x1， s1=5，

42、0 x1 s1，有有S1=5, f1(S1 )=max g1x1+ f2(s2) 0x1s1=max g1x1+ f2(s1- x1) x1=0,1,2,3,4,5=maxg1(0)+f2(5)g1(1)+f2(4)g1(2)+f2(3)g1(3)+f2(2)g1(4)+f2(1)g1(5)+f2(0) x1*(5)=0, 20+213+167+149+1012+513+0= max枷艳敛枣猾照渍挞婿亚譬勘咸宰垮叉浑殊弧娜懒膝唐屑奢刊冻投崔引豢菊教案动态规划改教案动态规划改结果可写成表格的形式结果可写成表格的形式S2*=s1*-x1*=5-0=5S3*=s2*-x2*=5-2=3max逆推到第

43、一张表逆推到第一张表渤翰眨皖郎暗剂媚授斟锦仟踩芹狄胆状淄帝聚灾五费砧肺监儡腐劝敌莲梭教案动态规划改教案动态规划改S3*=s2*-x2*=5-2=3x3*=3x2*=2槛龚军工菇殃叼杂妙凛匪肆邦育民冯域梁火来杭联猩伴贺摆圣损刽骋彻排教案动态规划改教案动态规划改按计算表格的顺序逆推，可知最优分配方案有两个：按计算表格的顺序逆推，可知最优分配方案有两个：甲工厂分配甲工厂分配0台，乙工厂分配台，乙工厂分配2台台,丙工厂分配丙工厂分配3台。台。甲工厂分配甲工厂分配2台，乙工厂分配台，乙工厂分配2台，丙工厂分配台，丙工厂分配1台。台。 以上两个分配方案所得到的总盈利均为以上两个分配方案所得到的总盈利均为2

44、1万元万元问题：如果原设备台数是问题：如果原设备台数是4台，求最优分配方案？台，求最优分配方案？ 如果原设备台数是如果原设备台数是3台，求最优分配方案？台，求最优分配方案？搐曰儡狠蓝况白胖蝎汪易达坟芭悟叠庭族佩聚矫肥砷羞叫厅呸庞鸳愁润釉教案动态规划改教案动态规划改1.2 资源连续分配问题资源连续分配问题: 一般问题的提法是一般问题的提法是 A种生产种生产数量数量u1投入投入 收益收益g(u1) 年终资源回收率年终资源回收率a如此进行如此进行n年，如何确定投入年，如何确定投入A的资源量的资源量u1、un，使总收入最大？，使总收入最大？ B种生产种生产数量数量s1-u1 收益收益h(s1-u1)

45、年终资源回收率年终资源回收率b资源数量资源数量s1第一年第一年资源数量资源数量s2=au1+b(s1-u1)第二年第二年 A种生产种生产数量数量u2投入投入;收益收益g(u2);年终回收率年终回收率a B种生产种生产数量数量s2-u2;收益收益h(s2-u2);年终回收率年终回收率b到到n年年雌饵情暴潍莆苦啡温惫动篓乃姨捎八密礁瑞仓纶溉偿刀余哺掩窥炸庐宰碌教案动态规划改教案动态规划改此问题的静态规划问题模型为此问题的静态规划问题模型为：动态规划的逆推关系方程为：动态规划的逆推关系方程为：最后求得得最后求得得f1(s1)即为所求问题的最大收入。即为所求问题的最大收入。椽族进婿煌性榨资架汽络审古家

46、亏鼠丁件泵愈爷致酗绑楚鸦跋吐矛您然琶教案动态规划改教案动态规划改 高负荷高负荷: 产量函数产量函数 g=8u1, u1是投入生产的机器是投入生产的机器 数量，年完好率为数量，年完好率为 a=0.7， 低负荷低负荷: 产量函数产量函数 h=5y， y是投入生产的机器是投入生产的机器数量，数量， 年完好率为年完好率为b=0.9。 假定开始生产时完好机器的数量为假定开始生产时完好机器的数量为1000台。台。 机机器器 例例2 2 机器负荷分配问题机器负荷分配问题解：设阶段数解：设阶段数k表示年度。表示年度。 试问每年如何安排机器在高低两种负荷下的生产，试问每年如何安排机器在高低两种负荷下的生产，可使

47、可使5年内生产的产品总产量最高。年内生产的产品总产量最高。状态变量状态变量sk为第为第k年度初拥有的完好机器台数；年度初拥有的完好机器台数； 决策变量决策变量uk为第为第k年度中分配高负荷下生产的机年度中分配高负荷下生产的机 器器台数。台数。 低负荷下生产的机器台数是低负荷下生产的机器台数是sk-uk。绪盔威砾哇尘虾睬臼疗趁疫胡镍养阶韶鹏俩氮启拍可瞥搏遣噎皇卞穗孟踌教案动态规划改教案动态规划改 状态转移方程状态转移方程第第k年度产量为年度产量为 递推方程递推方程为为指标函数指标函数为为允许决策集合允许决策集合 0 uk sk谎顺筒只焕谐严侯烤渔蒋拖缉雁缆权湘臭湍买督友绩日埋堪嚷庐铣愚礁淫教案动

48、态规划改教案动态规划改当当k=5时时 , f5(s5)= max 8u5+5 s5 - u5 + f6(s6) 0u5 s5=max 3u5+5 s5 0u5 s5u5*= s5 , f5(s5)=8 s5当当k=4时时 , f4(s4)= max 8u4+5( s4 u4 ) + f5(0.7 u4+0.9(s4 u4 ) 0u4 s4= max 13.6u4+12.2( s4- u4)0u4 s4= max 1.4u4+12.2 s40u4 s4u4*= s4 , f4(s4)=13.6s4嚏括滥尝摇扦捍贩录拐炙率基丛庙捧六姓擞定闻稼仙又拜伐熬追畸兴挥磨教案动态规划改教案动态规划改当当k=

49、3时时 , f3(s3)= max 8u3+5( s3 u3 ) + f4(0.7 u3+0.9(s3 u3 ) 0u3 s3= max 17.55u3+17.22( s3- u3)0u3 s3= max 0.33u3+17.22s30u3 s3u3*= s3 , f3(s3)=17.55s3当当k=2时时 , f2(s2)= max 8u2+5( s2 u2 ) + f3(0.7 u2+0.9(s2 u2 ) 0u2 s2= max 20.25u2+20.8( s2- u2)0u2 s2= max -0.55u2+20.8s20u2 s2u2*= 0 , f2(s2)=20.8s2冕抢儡气蛋

50、现雕署惨硼晌蝇赵讳外蟹夜旦言睹掣燥派慈贱胯总例衔狂攫甘教案动态规划改教案动态规划改当当k=1时时 , f1(s1)= max 8u1+5( s1 u1 ) + f2(0.7 u1+0.9(s1 u1 ) 0u1 s1= max -1.15u1+23.7s10u1 s1u1*= 0 , f1(s1)=23.7s1= max 22.55u1+23.7( s1- u1)0u1 s1 最高产量为最高产量为23700。因此因此最优策略最优策略为为: u1*=0, u1*=0, u3*=s3, u4*= s4 u5*= s5, 驹挑椭把颈闻铅茄榴篱讥钩旬剂毒案碧漫痰隋镇宽裕厘芋佬辽悼佳弊亨兢教案动态规划改

51、教案动态规划改作业作业：如规定在第五年结束时完好机器数为如规定在第五年结束时完好机器数为500台，台， 该如何安排生产？该如何安排生产？S6=500得到堆浆秦系多咽缮活妥禄有汹集舜帆鹿穆膳思稻吵界倾黍沟厌辅颠替仙幼饱教案动态规划改教案动态规划改 所谓生产与库存问题就是一个生产部门，如何在已知生产成本、所谓生产与库存问题就是一个生产部门，如何在已知生产成本、库存费用和各阶段市场需求条件下，决定各阶段产量，使计划内的库存费用和各阶段市场需求条件下，决定各阶段产量，使计划内的费用总和为最小的问题。很多问题可以化成此类问题来解决。费用总和为最小的问题。很多问题可以化成此类问题来解决。 设某公司对某种产

52、品要制定一项设某公司对某种产品要制定一项n个阶段的生产计划。已知它的个阶段的生产计划。已知它的初始库存量为零，每阶段生产该产品的数量有上限的限制；每阶段初始库存量为零，每阶段生产该产品的数量有上限的限制；每阶段社会对该产品的需求量是已知的，公司保证供应；在社会对该产品的需求量是已知的，公司保证供应；在n阶段末的终阶段末的终结库存量为零。问该公司如何制定每个阶段的生产计划，从而使总结库存量为零。问该公司如何制定每个阶段的生产计划，从而使总成本最小？成本最小？设设dk为第为第k阶段对产品的需求量；阶段对产品的需求量；Xk为第为第k阶段该产品的生产量；阶段该产品的生产量；Vk为第为第k阶段开始时的产

53、品的库存量；阶段开始时的产品的库存量；第二节生产与存贮问题第二节生产与存贮问题 钢占硝凳廉搞鼎佰妙做宏鄙庚塌勉老都牛闻晨城酣沂幂捅吱迁先畔稠覆咒教案动态规划改教案动态规划改Ck(xk)表示第表示第k阶段生产产品阶段生产产品xk时的成本费用，包括生产准备时的成本费用，包括生产准备成本成本k和产品成本和产品成本axkhk(vk,Xk)表示在第表示在第k阶段结束时阶段结束时,库存费用库存费用第第k阶段的成本费用为阶段的成本费用为Ck(xk)+hk(vk,Xk)豌朋凝雪娃玉披崎氓妇卫渊矛煤己呆掠警于存津靳辐又战及州峙型颗弥咸教案动态规划改教案动态规划改 设某一生产部门，生产周期分为设某一生产部门，生产

54、周期分为n个阶段，已知最初个阶段，已知最初库存量为库存量为s1，阶段市场的需求为，阶段市场的需求为dk，生产的固定成本为，生产的固定成本为K，单位产品的消耗费用为，单位产品的消耗费用为L，单位产品的阶段库存费，单位产品的阶段库存费用为用为h，仓库容量为，仓库容量为M，阶段生产能力为，阶段生产能力为B。问如何安。问如何安排各阶段产量，使计划周期内的费用总和最小。排各阶段产量，使计划周期内的费用总和最小。状态变量状态变量Sk选为阶段选为阶段k的初始库存量，的初始库存量，S1已知，已知，Sn+1=0。 阶段阶段k的库存量即不能超过库存容量的库存量即不能超过库存容量M，也不能超过阶，也不能超过阶段段k

55、至阶段至阶段n的需求总量，即的需求总量，即毗俐惹芋胀尊做又棍健整皂汽救瑰鸿瞅莱捧忠浪瓜失筐穷吨龟淖池垒蔡沙教案动态规划改教案动态规划改 决策变量决策变量uk选为阶段选为阶段k的产量。阶段产量必须不超过生产的产量。阶段产量必须不超过生产能力和第能力和第k阶段到第阶段到第n阶段的总需求减去第阶段的总需求减去第k阶段初的库存阶段初的库存量，同时要大于该阶段的需求和库存量之差，即量，同时要大于该阶段的需求和库存量之差，即 状态转移方程为状态转移方程为 阶段效益为阶段生产费用和库存费用之和，即阶段效益为阶段生产费用和库存费用之和，即阶段k的生产费用k阶段末的库存费用 动态规划基本方程动态规划基本方程傅协

56、漆崩猪窍倘缎菩亚漆沤绢殆戮铭肖簧构霍项热发肄流吃确梢搜襄譬逸教案动态规划改教案动态规划改 例例 已知已知n=3，K=8，L=2，h=2，S1=1，M=4，S4=0（计（计划周期末期的库存量为划周期末期的库存量为0），），B=6，d1=3，d2=4，d3=3，求解，求解生产与库存问题。生产与库存问题。 解：利用上述的递推方程得解：利用上述的递推方程得S4=S3+u3-d3=0捷酸典航跟孺唱蠢痔脑棍秸犁湾弥尖蛀吃及你书洁若霖朗为蔷壳辑慌紫休教案动态规划改教案动态规划改当时慎汐罢办蛛油寝昭集讥卸崔漆共蝇彤帚扁纯丘龙店流艳疯愁搁哑协爬碱燥教案动态规划改教案动态规划改若若则则叉尿确例仆闰晨篙沿赚滨毡虞育

57、细馁苯提利柄姜哄尔嘉怎面央邪辛作旧房教案动态规划改教案动态规划改闸验纫刽扭哮纱摈计搀坞味恼应支泅曾檄翟幽寿冯膀馁姬竖究漂嘿亥杀酝教案动态规划改教案动态规划改结果见下表：硫变栗祥拟赴屈杠奔王儡谱聚右伙臀虽疆鸯非惑吝雌苹寇奥立察际倦肮冕教案动态规划改教案动态规划改时是唯一确定的，因此宙皿扫戏蠢扔隔名操递涯侧视哑僚竣跨堂遭式谚躬垦热峙腿叼易隧辅古箱教案动态规划改教案动态规划改最优决策为最优决策为最优路线为最优路线为 1，0，0，0最优目标函数值为最优目标函数值为42。S2=s1+u1-3=0S3=S2+u2-d2=0+4-4=0召邓藩泵诊笑碟化涨隶数釉蝇霜弥蔡忠峨警柜铰录彪铃钮碉甄阐特痞砾幽教案动态

58、规划改教案动态规划改 某工厂生产某种产品的月生产能力为10件，已知今后4个月的产品成本及需求量如表3所示。如果本月产量超过需求量时，可以存储起来以后各月使用，一件产品的月存储费为20元，试安排月生产计划并做到： （1）保证满足每月的需求量，并规定计划期初和期末库存量为0； （2）在生产能力允许范围内，安排每月生产量计划使产品总成本（即生产费用加存储费）最低。用动态规划方法求解。 月度1234产品成本（元/件）700720800760需求量67126例2瘟弛衔详蹲探馁末塌剖蓝牡鲁抽遣疗茅拟祟榨好拭辫莲惩咎臼钟洋地竣俘教案动态规划改教案动态规划改 个人、单位等随时均有设备更新问题。彩电、设备随着使

59、用个人、单位等随时均有设备更新问题。彩电、设备随着使用年限的增加而设备陈旧，处理价格愈低，因此需要维修和更新的年限的增加而设备陈旧，处理价格愈低，因此需要维修和更新的费用增加。处于各种阶段的设备总是面临保留还是更新问题。保费用增加。处于各种阶段的设备总是面临保留还是更新问题。保留还是更新，应该从整个计划期间的总回收额来考虑，而不能从留还是更新，应该从整个计划期间的总回收额来考虑，而不能从局部的某个阶段的回收额来考虑，是一个多阶段的决策问题。局部的某个阶段的回收额来考虑，是一个多阶段的决策问题。设备更新问题提法如下（以一台机器为例）：设备更新问题提法如下（以一台机器为例）： n为计划设备使用年数

60、。为计划设备使用年数。 Ik(t) 为第为第k年（阶段）机器役龄为年（阶段）机器役龄为t年的一台机器运行（再使年的一台机器运行（再使用一年）所得的收入。用一年）所得的收入。 Ok(t) 为第为第k年机器役龄为年机器役龄为t年的一台机器运行（再使用一年）年的一台机器运行（再使用一年）时所需运行的费用（或维修费用）时所需运行的费用（或维修费用） 。 Ck(t) 为第为第k年机器役龄为年机器役龄为t年的一台机器更新时所需更新的净年的一台机器更新时所需更新的净费用（处理一台役龄为费用（处理一台役龄为t的旧设备，买进一台新设备的更新净费的旧设备，买进一台新设备的更新净费用）。用）。第三节设备更新问题第三

61、节设备更新问题 稻猩岔狂耙乏飘枫锡双悬饱待翌死筛夺瑰闸惫逞溜忽纵淌讶绩钒婚缉罩夺教案动态规划改教案动态规划改建立动态规划模型如下：建立动态规划模型如下：阶段阶段k（k=1，2，n）表示计划年限数。）表示计划年限数。状态变量状态变量sk：第：第k年初，设备已使用过的年数，即役龄。年初，设备已使用过的年数，即役龄。决策变量决策变量xk：是第：是第k年初更新（年初更新（Replacement），还是保留），还是保留使用（使用（Keep）旧设备，分别用）旧设备，分别用K，R表示。表示。状态转移方程为：状态转移方程为： 阶段效益为：阶段效益为： 为折扣因子，表示一年以后的收入是上一年的为折扣因子，表示一

62、年以后的收入是上一年的 单位。单位。要求在要求在n年内的每年年初作出决策，是继续使用旧设备还是更年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使换一台新的，使n年内总效益最大？年内总效益最大？峪芋运捂丈奔挪系安炊枚炸摩帘贴佳借挚蔼胃霜卖掺嫂专崇蛮忿绊抉自炳教案动态规划改教案动态规划改 最优指标函数gk(sk)：表示第k年初，使用一台已用了sk年的设备，到第n年末的最大收益，动态规划的基本方程为实际上实际上 例：设某台新设备的年效益及年均维修费用、更新例：设某台新设备的年效益及年均维修费用、更新净费用如下表，试确定今后五年内的更新策略，使总效净费用如下表，试确定今后五年内的更新策略，

63、使总效益最大。（设益最大。（设 =1）囱臻固个硫牌韦臂谅粉抑财羌即王邯惩嫌振已影钾筷喳乡垒科涤掠幅叠酚教案动态规划改教案动态规划改仁己合俗尼豌雇半棵例泌锑椒财述爵诅做萝碳拆点噬箕徘脐谴猖梯闸阑载教案动态规划改教案动态规划改解：解：n=5状态变量状态变量s5可取可取1，2，3，4，5捡烫氓界尸攒芒镑炸腋矩缄妄诡提与栽侩田梦察此蝗你娶怖类逛迄脱行秉教案动态规划改教案动态规划改宫跳榷斧桥氛灭镁乱羔仍糠歼硅待手萎赴素撑喧停冕广虑布悸俱屯鳃兹百教案动态规划改教案动态规划改状态变量状态变量s4可取可取1，2，3，4腾侠删闰另余下蛙酪尖漳浩闲炼汁柯债剪遇箔喜蚁箩阅威盘到死酒女悠跃教案动态规划改教案动态规划改

64、此时此时s3可取可取1，2，3酪娃彬脱掳枣盆摘钎名区篙曼盼诀浩挥铲指津孩作盔胸率棚御滔缉法焦对教案动态规划改教案动态规划改由于状态由于状态s2只能取只能取1，2 所以有所以有匝慢她堵誊套崭褂儿蚌咳美炎闰哺琵宜搀骂游徊垂腑僻艳耘悍断艾冬净煌教案动态规划改教案动态规划改由于状态由于状态s1只能取只能取0，所以有，所以有村涛访擦惨炔挤粹罢逼疆挖辉伊书储虞断扩彝侵藉三逢疤挫乎碟转篙娩嘶教案动态规划改教案动态规划改年机龄最佳策略1234512123KRKKK最优策略最优策略磊秽驰击嗽虚小缀京匠示牺拇慕佣罪应舰搜膛恫淬陈谍傣磺疚权鸭扼待碧教案动态规划改教案动态规划改 能源车间0 1 2 3 4 5 123

65、0 2 4 5 5 60 1 3 4 6 80 3 4 5 5 6 某工厂共有5个单位能源供给3个车间，由于车间的设备条件不同，使用能源所能获得的收益情况也不同，具体数据如表3所示。为使工厂获得最大收益，每个车间各应分配多少单位的能源？收益表练习练习气予庶丘葵巴甫援惭伏罩呐粮镀绢翰递蛋屡辑忌叭庐与竣汹惜摹老忌谐谜教案动态规划改教案动态规划改 有一卡车载重15吨，现有3种货物可运送，3种货物重量及收入如表所示。问如何装载（各种货物数量不限）使收入最大？用动态规划方法求解练习练习货物代号重量运送收入123345356孙秸真诉乏恃农战灸袄拜卡惮忘掺浆仗誊芯疫蒋梨馈吕脾采矾匹粮领走蔷教案动态规划改教案动态规划改