第八章动态规划 到现在为止，已研究过的模型都可称为静态模型，这类模型的特点是一次（或者说同 时)处理所有的决策变量，以寻求这些决策变量的最优值.也存在这样一些问题，可以从 时问上或空间上将问题划分为若干个相互联系的阶段，要求依次在每个阶段作出决策 这样的问题我们称之为多阶段决策问题。如果把每个阶段作出的决策所形成的决策序列 称为一个策酪，那么求解多阶段决策问题便在众多的策略中找出向题的最优策略，动态 规划方法是用于寻求某些多阶段决策问题最优策略的一种方法，所谓“动态”，指的是问 题需逐个阶段处理（即时间或空间的转移）这一特性. 动态规划方法可用于求解不少类型的运筹学问题，但并不存在一个如单纯形法那样 适用于各类问题的单一算法。此外，模型中所用符号也比较复杂。我们将先讨论两个具体 问题，阐明动态规划问题的解题步骤，再介绍动态规划的基本概念与基本原理，然后讨论 几个其他问颗顺.以说明动态规划应用的广泛性 s8.1两个引例 一、最短路线问题 例1.图8-1为一线路网络，现在要铺设从地点A到地点E的铁路。中间需经过3个 点，第1点可以是B,B2,B品中的某一个点，第2点可以是C,C2,C中的一个点，等等. 各点之间，若能铺设铁路，则在图中以连线表示，连线上的数字表示两点间的距离.要求选 择一条A至E的最短铺设路线 图8-1 这个问题可分为4个阶段进行决策。第1阶段：从A出发，终点可选择B或B2或 B3,第2阶段：从B1出发（如果第1阶段的决策导致终点为B),终点可选择C或C2: 或从B2出发（如果第1阶段的决策导致终点为B2).终点可选择C或C2或C3:或从 B出发（如果第1阶段的决策导致终点为B终点可选择C2或C.这样继续下去，直 至第4阶段达到E. 为了作出最优决策，可以穷举A到E的所有路线，并计算每条路线的长度，然后找出 1
✂✁✂✄ ☎✂✆✂✝✂✞ ✟✡✠✡☛✡☞✡✌, ✍✏✎✡✑✡✒✡✓✡✔✡✕✡✖✡✗✡✘☞✡✙✡✚✔✡✕✡✛✢✜✡✣✡✔✡✕✡✓✡✤✡✥✡✦✡✧✡★ (✩✡✪✡✫✡✬ ✭ ) ✮✰✯✰✱✰✲✰✓✰✳✰✴✰✵✰✶, ✷✰✸✰✹✰✜✰✺✰✳✰✴✰✵✰✶✰✓✰✻✰✼✰✽✰✛✢✾✰✿☛✜✰❀✰✧✰✺✰❁✰❂, ✗✰✷✰❃ ✭✡❄✡❅✩✡❆❄✡❅✡❇❁✡❂✡❈✡❉☞✡❊✰❋✰●✡❍✰■✡❏✰❑✓▼▲✡◆, ❖✡✹✡P✡★☛✡◗✡●✡❘✡❙✡❚✡❯ ✳✡✴✰✛ ✜✡❀✡✓✡❁✡❂✡❱✡❲✡✘✡❳☞❩❨▲✡◆✡❬✡❭✡❪✡❫✡✛❵❴✡❛✡❜◗✡●✡❘✡❙✡❚✡❯ ✓✡✳✡✴✡✱✡❝✡❞✡✓✡✳✡✴✡❡✡❢ ✘ ☞✧ ● ❭✰❣, ❤✰✐✰✹✰❥✰❦❘✰❙✳✰✴✰❁✰❂✰❧☛✰♠❦✰✓✰✴✰♥♣♦rq❯ ❁✰❂✰✓✰✻✰✼✰✴✰♥✰✛✢s✰t ✉✡✈①✇✡②✦✡③✡④✡✸✡✹✡⑤✡✺✡❦❘✡❙✳✡✴✡❁✡❂✡✻✡✼✡✴✡♥✡✓✡✧✡⑥✇✰②✛✢✱✡⑦ “⑧✚ ”, ⑨✡✓✡✦✡❁ ❂✡⑩✡❶●✡❘✡❙✮✡✯ (❷✭✡❄✩✡❆❄ ✓✡❸✡❹) ✜✡✧✡✤✡❺✡✛ ⑧✚✰❻❈✇✰②✗✰③✰④✰✹✰❥✰❼✰❽✰✣✰✕✰✓✰❾✰❿✰➀✰❁✰❂, ➁✰➂✰❼✰✿☛✧ ● ❴✰➃✰➄✰❝② ❤✰❀ ➅ ③✡④✡➆✡✣✡❁✡❂✡✓✡➃✡✧✡➇② ✛➉➈✡➊, ✔✡✕➋♦✏✱✡③✡➌✡➍✡✾➋➎✏➏✡➐✡➑✡✛➉❱✡❲❇✡➒✡➓✡➔✡→●✡➣✡↔ ❁✰❂, ↕♣➙r⑧✚✰❻❈✰❁✰❂✰✓✰❥✰❂✰➛✰➜, ➝✰➞✰➟✰⑧✚✰❻❈✰✓✰➠✰➡✰➢✰➤✰➥✰➠✰➡✰➦✰✯, ➧✰➨➓✰➔ ➩●✡➫✡➭❁✡❂, ✷✡✫➋➙✏⑧✚✡❻❈✡➯✡③✡✓✡➲✡➳✡❺✡✛ §8.1 ➵➺➸➺➻➺➼ ➽➺➾✏➚➺➪➺➶➺➹➺➘➺➴ ➷ 1. ➬ 8–1 ☞✧✡➮✡➱➋✃✏❐, ✠✡☛❖✡❒✡❮✡❃✡❰✡✥ A ✟❰✡✥ E ✓✡Ï✡➱, ♦❄⑩✡Ð✡✒ 3 ● ✥, Ñ 1 ✥✡✗✡✷✡✦ B1,B2,B3 ♦✏✓✡⑤✡✧● ✥, Ñ 2 ✥✡✗✡✷✡✦ C1,C2, C3 ♦✏✓✡✧● ✥, Ò✡Ò✡✛ ➆Ó✥Ó❳❄ , ❊ÓÔ❒Ó❮ÓÏÓ➱, Õ☛ ➬Ö♦×✷ÓØÓ➮ÓÙÓÚ, ØÓ➮❅ ✓ÓÛÓÜÓÙÓÚ→ ✥ ❄ ✓ÓÝ✡Þ✡✛ß❖Ó✹✡à á ✧✡â A ã E ✓✡✻✡ä✡❒✡❮✡➱✡➮✡✛ ➬ 8–1 ✜ ● ❁✡❂✡✗✡❉☞ 4 ●✡❘✡❙✡å✡æ✳✡✴✡✛✢Ñ 1 ❘✡❙: ❃ A ❯✡ç, è✡✥✡✗✡àá B1 ✩ B2 ✩ B3 ✛✢Ñ 2 ❘✡❙: ❃ B1 ❯✡ç (❴✡❛✡Ñ 1 ❘✡❙✓✡✳✡✴✡é✡ê✡è✡✥☞ B1), è✡✥✡✗✡àá C1 ✩ C2; ✩✰❃ B2 ❯✰ç (❴✰❛✰Ñ 1 ❘✰❙✓✰✳✰✴✰é✰ê✰è✰✥☞ B2), è✰✥✰✗✰àá C1 ✩ C2 ✩ C3; ✩✰❃ B3 ❯✡ç (❴✡❛✡Ñ 1 ❘✡❙✓✡✳✡✴✡é✡ê✡è✡✥☞ B3); è✡✥✡✗✡àá C2 ✩ C3 ✛✢✜✡❀✡ë✡ì✡í✡î, ï ã✡Ñ 4 ❘✡❙✡ð✡✟ E ✛ ☞✡ñ✡❚✡❯ ✻✡✼✡✳✡✴, ✗✡✷✡ò✡ó A ✟ E ✓✡✱✡✲✡➱✡➮, ➂✡ô✡➇◗ â✡➱✡➮✡✓✡õ✡ö, ➧✡➨✡q❯ 1
第八章动态规划 最短路线.本例共有12条不同路线，比较它们的长度，最短路线为 A-→B3-+C2-+D1-→E 其长度为14.当决策阶段较多，各阶段可选择的地点也较多时，计算就相当冗繁，甚至无 法实现。 下面介绍的求最短路线的方法是典羽的动态规别方法。这种方法要用到最短路线回 题的一个特性，这就是如果最短路线通过点，则这条路线从P点至终点的部分，对于 从P至终点的所有路线（称为P的后部路线）而言，必定也是最短的路线(~的最短后部 路线).上例中，路线C2一D1一E就是C2至E所有路线中的最短的路线.这个特性是 易于理解的，因为如果从至终点还有另一更短的路线存在，则把它和原来最短路线从起 点至卫的那一部分连接起来，就会形成·条比原来的最短路线更短的路线。这显然是矛盾 的，因而是不可能的。 现在我们利用上述原理，由最后一段路线开始，向最初阶段递推，作出各个阶段的最 优决策。 首先考虑最后阶段。这一阶段要分别对D1和D2找出最短后部路线。先考虑D1。 由于D,至E只有一条路线因而D的最短后部路线即为D1一E,其长度为3.据上述 最短路线问题的特性可知，如果A至E的最短路线通过D,则从D1至终点E的这 部分必为D:一E.为了记录整个问题的决策过程，按图8-1画出表示各个点的小图（见 图8-2)将D1至E的最短路线长度埴入D,因内.并将D1和E用线连接起来.显然 D1一E就是D1的最短后部路线.再看D2,同样道理，D2一E为D2的最短后部路线 长度为4，把数4填入D2圈内并连接D2和E, 图8-2 接着考虑倒数第2阶段.这一阶段要找出C,C和C的最短后部路线.C的后 部路线的第1段只能是C→D,因而C的最短后部路线是C一D1一E,其长度 是C一D长度与D1圈内数字之和(4+3=7).连接C1和D1,并将C的最短后部 路线的长度填入C1圈内。C2的后部路线的第1段有两种选择：C2→D1和C2一D2 为确定C的最短后部路线，可比较下面两个数字C一D1的长度与D1圈内数字之利 (2+3=5),C2一D2的长度与D2圈内数字之和(3+4=7)，其中最小者应为C2的最短后部 路线的长度.可见C2的最短后部路线是C2→D1→E,长度为5.根据前述最短后部路 线向题的特性，这样决定的最短后部路线，其正确性是无可怀疑的.我们将C2和D1连接
2 ÷✡ø✡ùûú➋ü✏ý✡þ ✻✡ä✡➱✡➮✡✛✢➡✡ÿ✁✡✲ 12 â✡❼✡✬✡➱✡➮, ➎✏➏✁✂✡❲✡✓✡õ✡ö, ✻✡ä✡➱✡➮☞ A −→ B3 −→ C2 −→ D1 −→ E ➫ õ✰ö☞ 14✛☎✄✰✳✰✴❘✰❙➏✰❦, ➆❘✰❙✗✰àá ✓✰❰✰✥✰✾✰➏✰❦✭ , ô✰➇✝✆❍ ✄✝✞✝✟, ✠✰ã✝✡ ②✁☛✡✠✛ í✁☞✡➞✡➟✡✓✡✹✡✻✡ä✡➱✡➮✰✓✇✡②✦✝✌✡✕✰✓✰⑧✚✰❻❈✇✰②✛ ✜✡⑥✇✰②❖✰③ ✟✻✰ä✰➱✡➮✰❁ ❂✰✓✰✧● ✤✰❺, ✜✝✆✰✦: ❴✰❛✰✻✰ä✰➱✰➮✝✍✰✒ p ✥, Õ✰✜✰â✰➱✰➮✰❃ p ✥✰ã✰è✰✥✰✓✝✎✰❉, ✏✰④ ❃ p ã✰è✰✥✰✓✰✱✰✲✰➱✰➮ (✘ ☞ p ✓✰➨✝✎✰➱✰➮) ✑✝✒, ✓✝✔✰✾✰✦✰✻✰ä✰✓✰➱✰➮ (p ✓✰✻✰ä✰➨✝✎ ➱✡➮)✛ ❅ ÿ➋♦, ➱✡➮ C2 → D1 → E ✆✡✦ C2 ã E ✱✡✲✡➱✡➮➋♦✏✓✡✻✡ä✡✓✡➱✡➮✡✛❵✜● ✤✡❺✡✦ ✕④✡✯✡❥✡✓, ✖☞ ❴✡❛✡❃ p ã✡è✡✥✁✗✡✲✁✘✡✧✁✙✡ä✡✓✡➱✡➮✡✿☛ , Õ✡❜✁✂✁✚✡➦✁✛✡✻✡ä✡➱✡➮✡❃✁✜ ✥Óã p ✓Ó❤Ó✧✢✎Ó❉ÓØ✢✣✢✜✢✛, ✆✢✤Ó❝Ó❞Ó✧ÓâÖ➎×➦✢✛Ó✓Ó✻✡äÓ➱✡➮✁✙Óä✡✓Ó➱✡➮✡✛ß✜✁✥Ó➧✡✦✢✦✁✧ ✓, ✖✁✑✡✦✡❼✡✗Ô ✓✡✛ ✠✰☛❱✰❲✝★✰③❅✝✩➦✰✯, ✪r✻✰➨✰✧❙ ➱✰➮✝✫✝✬, ✭r✻✝✮❘✰❙✝✯✝✰, ❚✰❯ ➆ ●✰❘✰❙✓✰✻ ✼✡✳✡✴✡✛ ✱✡➒✁✲✁✳✻✡➨❘✡❙✛✢✜✰✧❘✰❙❖✡❉✝✴✝✏ D1 ✚ D2 q ❯ ✻✡ä✡➨✁✎✡➱✡➮✡✛ ➒✁✲✝✳ D1 ✛ ✪✏④ D1 ã E ✵✡✲✡✧✡â✡➱✡➮, ✖✁✑ D1 ✓✡✻✡ä✡➨✁✎✡➱✡➮✡❷☞ D1 → E, ➫ õ✡ö☞ 3✛✷✶❅✁✩ ✻✰ä✰➱✰➮✰❁✰❂✰✓✰✤✰❺✰✗✝✸, ❴✰❛ A ã E ✓✰✻✰ä✰➱✰➮✝✍✰✒ D1, Õ✰❃ D1 ã✰è✰✥ E ✓✰✜✰✧ ✎✡❉✁✓☞ D1 → E ✛ ☞✡ñ✁✹✁✺✁✻✡●❁✡❂✡✓✡✳✡✴✡✒✝✼, ✽✡➬ 8–1 ✾ ❯ Ù✡Ú✡➆● ✥✡✓✁✿✁❀ (❁ ➬ 8–2)✛ ❇ D1 ã E ✓✰✻✰ä✰➱✰➮✰õ✰ö✝❂✝❃ D1 ❀❅❄, ➂ ❇ D1 ✚ E ③✰➮✰Ø✝✣✝✜✝✛, ✥✰➧ D1 → E ✆✡✦ D1 ✓✡✻✡ä✡➨✁✎✡➱✡➮✡✛✢➝✁❆ D2, ✬✡❀✁❇✡✯, D2 → E ☞ D2 ✓✡✻✡ä✡➨✁✎✡➱✡➮, õ✡ö☞ 4✛✢❜✡Û 4 ❂✁❃ D2 ❀❈❄✏➂✡Ø✁✣ D2 ✚ E ✛ ➬ 8–2 ✣❊❉✲❊✳❊❋ÛÑ 2 ❘❙ ✛ ✜✧❘❙ ❖q ❯ C1,C2 ✚ C3 ✓✻ä➨❊✎➱➮✛ C1 ✓➨ ✎✰➱✰➮✰✓✰Ñ 1 ❙ ✵Ô✦ C1 → D1, ✖✝✑ C1 ✓✰✻✰ä✰➨✝✎✰➱✰➮✰✦ C1 → D1 → E, ➫ õ✰ö ✦ C1 → D1 õ✰ö✰➥ D1 ❀❅❄rÛ✰Ü✰❳✝✚ (4+3=7)✛ Ø✝✣ C1 ✚ D1, ➂ ❇ C1 ✓✰✻✰ä✰➨✝✎ ➱✰➮✰✓✰õ✰ö✝❂✝❃ C1 ❀❅❄r✛ C2 ✓✰➨✝✎✰➱✰➮✰✓✰Ñ 1 ❙ ✲→ ⑥✰àá :C2 → D1 ✚ C2 → D2 ✛ ☞✝●✔ C2 ✓✰✻✰ä✰➨✝✎✰➱✰➮, ✗♣➎r➏✰í✝☞→●Û✰Ü:C2 → D1 ✓✰õ✰ö✰➥ D1 ❀❅❄rÛ✰Ü✰❳✝✚ (2+3=5),C2 → D2 ✓✡õ✡ö✡➥ D2 ❀❈❄✏Û✡Ü✡❳✁✚ (3+4=7), ➫ ♦✏✻✁✿✡✪✡➯☞ C2 ✓✡✻✡ä✡➨✁✎ ➱✡➮✡✓✡õ✡ö✡✛✢✗✁❁ C2 ✓✡✻✡ä✡➨✁✎✡➱✡➮✡✦ C2 → D1 → E, õ✡ö☞ 5✛☎❍✁✶✁■✩ ✻✡ä✡➨✁✎✡➱ ➮✡❁✡❂✡✓✡✤✡❺, ✜✡❀✡✳✁✔✡✓✡✻✡ä✡➨✁✎✡➱✡➮, ➫✁❏✁●❺✡✦✁✡✡✗✁❑✁▲✡✓✡✛ ❱✡❲❇ C2 ✚ D1 Ø✁✣
58.1两个引例 3 起来，并在C2图内填入C2的最短后部路线长度5，用同样的方法可以找出C3的最短后 部路线为C一D2一E,长度为9. 然后考感倒数第3阶段.用同样的方法可以画出B1一C2,B2一C2和B一C2三 条连线，并计算出B1,B2和B3的最短后部路线长度12、10、和10，填入相应圈内. 现在进行最初阶段的决策.这一阶段我们得到了从A开始的最短后部路线：A Bg→C2→D1 ,E,长度为14，其实这就是A至E的最短路线，如图82双线所示.至 此，解题过程结束，整个过程记录在图8-2上。这就是求最短路线的动态规划方法. 通过这个例千可以看出.动态规划的解额特点县把一个大的决箭间题分解为若干个 相关联的小的决策问题，逐个求解而每个小向题的决策方法基本相同，且较简单，应诊 说。动态规划的概念是比较简单的.所以.虽然我们在学习动态规划方法时将会遇到较多 的符号表示.但它们是易于理解的 动态规划比穷举法具有显著的优点.对于本例，用动态规划方法解题时，每一计算阶 段都利用了上一计算阶段的结果，因而较之穷举法减少了很多计算量。阶段数愈多，这种 效果愈显著。此外动态规划方法使我们得到的不仅仅是由A到E的最短路线及其长度， 而且还有每一中间点到终点E的最短路线及其长度，这些结果有时是很有用的 二、投资金额分配问题 例2.某公司有资金4百万元，可以向A、B和C三个项目加投资，各个项目可以 有不同的投资额（以百万元为单位），相应的效益如表8-1所示。问怎样分配资金使总效益 值最大？ 表8-1 投资 投资额（百万） 01234 64 7只 我们可以把这个间题看成在不同的时间阶段对不同的项目做出决策而作为动态规划 问题处理.问题显然可分为3个阶段.第1阶段先对项目A做出决策，第2阶段根据利 下的资金对B做出决策.第3阶段再根据和下的资金对C做出决策（这个页序是任意碳 定的).如果用穷举法解这个问题，要考虑35个方案，现在我们用动态规划方法解这个问 题.既然首先对A,其次对B,最后对C做出决策，则从对项目C进行决策开始解题（这 和例1先考感最后一段路线的决策是同一道理)。 对项目C的最优决策取决于有多少剩余的资金可分配这个数额一般地称之为状 态.表8-2列出了可能出现的一切状态、能够考虑的一切决策（分配给项目C的资金额 以及每个决策的效益值，最后两栏指出每一状态下的最优决策及效益值，“一 号表示在该 状态下不可能的决策
§8.1 ▼❖◆❈P❖◗ 3 ✜✁✛, ➂ ☛ C2 ❀❈❄❖❂✁❃ C2 ✓✡✻✡ä✡➨✁✎✡➱✡➮✡õ✡ö 5✛➉③✡✬✡❀✡✓✇✡②✗✡✷✡q❯ C3 ✓✡✻✡ä✡➨ ✎✡➱✡➮☞ C3 → D2 → E, õ✡ö☞ 9✛ ➧✡➨✲✁✳✁❋Û✡Ñ 3 ❘✡❙✛✢③✡✬✡❀✡✓✇✡②✗✡✷✁✾❯ B1 → C2,B2 → C2 ✚ B3 → C2 ❘ â✡Ø✡➮, ➂✡ô✡➇❯ B1,B2 ✚ B3 ✓✡✻✡ä✡➨✁✎✡➱✡➮✡õ✡ö 12❙ 10❙☎✚ 10, ❂✁❃❍➯✁❀❈❄✏✛ ✠☛åæ ✻❊✮❘❙ ✓✳✴✛ ✜✧❘❙ ❱❲❊❚✟ñ ❃ A ✫❊✬✓✻ä➨❊✎➱➮: A → B3 → C2 → D1 → E, õ✡ö☞ 14, ➫✁☛✜✁✆✡✦ A ã E ✓✡✻✡ä✡➱✡➮, ❴✡➬ 8–2 ❯✡➮✡✱✡Ú✡✛❵ã ➈, ❥✡❂✡✒✁✼✁❱✁❲, ✻✡●✒✁✼✹✁✺✡☛➬ 8–2 ❅ ✛✢✜✁✆✡✦✡✹✡✻✡ä✡➱✡➮✡✓✡⑧✚✡❻❈✇✡②✛ ✍✰✒✰✜● ÿ✝❳✰✗✰✷✝❆❯ , ⑧✚✰❻❈✰✓✰❥✰❂✰✤✰✥✰✦✰❜✰✧●✝❨✓✰✳✰✴✰❁✰❂✰❉✰❥☞✰❊✰❋✰● ❍✝❩✰❏✓✝✿✰✓✰✳✰✴✰❁✰❂, ❶ ● ✹✰❥, ✑◗✰●✿✰❁✰❂✰✓✰✳✰✴✇✰②➠✰➡❍ ✬, ❬✰➏✝❭✰➃✰✛ ➯✝❪ ✫, ⑧✚✰❻❈✰✓✰➢✰➤✰✦♣➎r➏✝❭✰➃✰✓, ✱✰✷, ❫✰➧✰❱✰❲☛ ➀✝❴✰⑧✚✰❻❈✇✰②✭✰❇✤✝❵✟➏✰❦ ✓✡➌✡➍✡Ù✡Ú, ➁✁✂✡❲✡✦✕④✡✯✡❥✡✓✡✛ ⑧✚✡❻❈➋➎✏ò✡ó②✡➣✲✁✥✁❛✡✓✡✼✡✥✰✛☎✏✡④✰➡✡ÿ, ③✡⑧✚✡❻❈✇✡②❥✡❂✭ , ◗ ✧✡ô✡➇❘ ❙ ✖✁★✡③ñ❅✧✡ô✡➇❘✡❙✓✁❱✡❛, ✖✁✑✡➏✡❳✡ò✡ó②✁❜❽ ñ✁❝❦✡ô✡➇✡✶✡✛ ❘✡❙Û✁❞✰❦, ✜✡⑥ ❡ ❛✁❞✁✥✁❛✡✛ ➈✡➊, ⑧✚✡❻❈✇✡②✁❢❱✡❲✁❚✟ ✓✡❼✁❣✁❣✡✦❈✪ A ✟ E ✓✡✻✡ä✡➱✡➮✁❤➫ õ✡ö, ✑✁❬✁✗✡✲◗ ✧➋♦❄ ✥ ✟è✡✥ E ✓✡✻✡ä✡➱✡➮✁❤➫ õ✡ö, ✜✡✺✁❱✡❛✡✲✭ ✦ ❝ ✲✡③✡✓✡✛ ✐➾❖❥❧❦❧♠❧♥❧♦❧♣➺➘➺➴ ➷ 2. ⑤✁q✁r✡✲✁s✁t 4 ✉✁✈✁✇, ✗✡✷❈✭ A❙ B ✚ C ❘ ●✁①③②⑤④✁⑥✁⑦s, ➆ ●✁①③② ✗✡✷ ✲Ó❼Ó✬Ó✓⑦ s✢⑧ (✷✢✉✢✈✢✇☞➃✢⑨), ❍➯Ó✓❡✢⑩❴ÓÙ 8–1 ✱ÓÚÓ✛ ❁✢❶Ó❀Ó❉✢❷✢s✢t❢✁❸❡✁⑩ ✽✡✻❨ ? Ù 8–1 ⑦ s ⑦ s✁⑧ (✉✁✈✁✇) ①③② 0 1 2 3 4 A 38 41 48 60 66 B 40 42 50 60 66 C 48 64 68 78 76 ❱✡❲✡✗✡✷✡❜✡✜● ❁✡❂✁❆✡❞☛ ❼✡✬✡✓✭✡❄❘✡❙✏✡❼✡✬✡✓①③②⑤❹✡❯ ✳✡✴✁✑❚✡☞⑧✚✡❻❈ ❁✡❂✡✮✡✯✡✛✢❁✡❂✁✥✡➧✡✗✡❉☞ 3 ●✡❘✡❙✛✢Ñ 1 ❘✡❙➒✏ ①③② A ❹✡❯ ✳✡✴, Ñ 2 ❘✡❙❍✁✶✁❺ í✡✓✁s✁t✁✏ B ❹✡❯ ✳✡✴, Ñ 3 ❘✡❙➝✁❍✁✶✁❺✡í✡✓✁s✁t✁✏ C ❹✡❯ ✳✡✴ (✜ ●✁❻❡✡✦✁❼✁❽● ✔✡✓)✛✢❴✡❛✡③✡ò✡ó② ❥✡✜● ❁✡❂, ❖✲✁✳ 35 ●✡✇✁❾✛ ✠✡☛❱✡❲✡③✡⑧✚✡❻❈✇✡②❥✡✜● ❁ ❂✡✛☎❿✡➧✱✡➒✏ A, ➫ ★✁✏ B, ✻✡➨✁✏ C ❹✡❯ ✳✡✴, Õ✡❃✁✏①③② C å✡æ✳✡✴✁✫✁✬✡❥✡❂ (✜ ✚✡ÿ 1 ➒✁✲✁✳✻✡➨✡✧❙ ➱✡➮✡✓✡✳✡✴✡✦✡✬✡✧✁❇✡✯)✛ ✏ ①➀② C ✓✰✻✰✼✰✳✰✴✝➁✰✳✰④✰✲✰❦✰❽❊❺✝➂✓❊s✝t✗✰❉❊❷, ✜ ●Û✝⑧✰✧✝➃✰❰✰✘✰❳☞➅➄ t✡✛✢Ù 8–2 ❢ ❯✡ñ✗ Ô✡❯✡✠✓✡✧✁➆✁➇✚ ❙ Ô✁➈✲✁✳✓✡✧✁➆✡✳✡✴ (❉✁❷✁➉①③② C ✓✁s✁t✁⑧) ✷✁❤◗✡●✳✡✴✡✓❡✁⑩✽, ✻✡➨→✁➊⑨ ❯✡◗✧✁➇✚í✡✓✡✻✡✼✡✳✡✴✁❤❡✁⑩✽,“—” ➍✡Ù✡Ú☛❪ ➇ ✚í✡❼✡✗Ô ✓✡✳✡✴✡✛
第八章动态规划 表8-2 状态 决策（分配资金额最优最优共第 (未分配的资金额 0123 4决策 的效益值 0 64 2 64 68 6 48 6 78 76 3 表8-2不指明在这一阶段可能出现的每一状态下的最优行动.不管这状态是怎样 产生的，表中的最优决策不变这一点需要强调指出（虽然很容易理解），因为它是这个间 题能够应用动态规划方法求解的基础。这个特性和我们在例1中指出的最短路线问题的 重要特性是相类似的。关于这一点，后面还要作进一步的讨论. 下面考虑项目B的决策.这一阶段的决策，目的是寻求最后两个阶段（对B和对C) 的最优策略。在对项目B作决策时，可能的状态（剩余资金）也是5个（即0、1、2、3、4）。 假设有4百万元的剩余资金，那么就有5种可能的决策（不投资，投资1百万元投资2百 万元投资3百万元和投资4百万元。如果不投资则效益值为40，这样，到对C决策时 仍有4百万元的剩余资金.在这个状态下，对C最优决策的效益值为T8,因此这个阶段 如果状态为4(4百元的剩余资金).决策为0不对顶目B投资).后两个阶段的品优总效 益值为40+78 118.如果对B投资1百万元则效益值为42，而余下3百万元可对C 投资，此时C的最优快策的效益值是78，因而后两阶段的最优总数兰值为120.我们还可 以计算出状态为4.决策为2的最优策略总效益值为118：快簧为3的最优策略总效益值 为124决策为4的最优策略总效益值为114，比较以上状态为4时的5个不同决策的总 效益值为，便可确定此状态下的最优决策是3，最优总效益值为124，其他状态下寻求最优 快策的过程与上述过程类似.可归纳为表8-3与表8-4
4 ÷✡ø✡ùûú➋ü✏ý✡þ Ù 8–2 ➇ ✚ ✳✡✴ (❉✁❷✁s✁t✁⑧) ✻✡✼ ✻✡✼✡✳✡✴ (➋✡❉✁❷✡✓✁s✁t✁⑧) 0 1 2 3 4 ✳✡✴ ✓❡✁⑩✽ 0 48 — — — — 0 48 1 48 64 — — — 1 64 2 48 64 68 — — 2 68 3 48 64 68 78 — 3 78 4 48 64 68 78 76 3 78 Ù 8–2 ✗✰⑨♣➙☛✜✰✧❘✰❙✗ Ô✰❯✰✠✓◗ ✧✝➇✚í✰✓✰✻✰✼æ ⑧, ❼✝➌✰✜✰⑥✝➇✚✦✝❶✰❀ ➍✝➎✓, Ù♣♦r✓✰✻✰✼✰✳✰✴✰❼✰✵, ✜✰✧✰✥✰⑩✰❖✝➏✝➐✰⑨❯ (❫✰➧❝✝➑✕✯✰❥), ✖☞✂✰✦✰✜● ❁ ❂ Ô✁➈➯✡③✡⑧✚✡❻❈✇✡②✹✡❥✡✓✡➠✁➒✰✛✢✜● ✤✡❺✝✚✡❱✡❲☛ ÿ 1 ♦✏⑨❯ ✓✡✻✡ä✡➱✡➮✡❁✡❂✡✓ ➓ ❖✡✤✡❺✡✦❍✣✁➔✡✓✡✛ ❩ ④✡✜✡✧✡✥, ➨✁☞✁✗✡❖❚✡å✧✡➛✡✓➓✡➔✛ í✁☞✲✁✳①③② B ✓✡✳✡✴✡✛➉✜✡✧❘✡❙✓✡✳✡✴, ② ✓✡✦✡✸✡✹✡✻✡➨→●✡❘✡❙ (✏ B ✚✁✏ C) ✓✡✻✡✼✡✴✡♥✡✛ ☛✏ ①③② B ❚✳✡✴✭ , ✗ Ô ✓✁➇✚ (❺✁➂✁s✁t) ✾✡✦ 5 ● (❷ 0❙ 1❙ 2❙ 3❙ 4)✛ → ❮✡✲ 4 ✉✁✈✁✇✡✓✁❺✁➂✁s✁t, ❤✡✐✁✆✡✲ 5 ⑥✡✗Ô ✓✡✳✡✴ (❼⑦ s, ⑦ s 1 ✉✁✈✁✇, ⑦ s 2 ✉ ✈✁✇, ⑦ s 3 ✉✁✈✁✇✁✚⑦ s 4 ✉✁✈✁✇)✛ ❴✡❛✡❼⑦ s, Õ❡✁⑩✽ ☞ 40✛ ✜✡❀, ✟✏ C ✳✡✴✭ , ➣✲ 4 ✉✁✈✁✇✡✓✁❺✁➂✁s✁t✡✛ ☛✜ ●➇ ✚í, ✏ C ✻✡✼✡✳✡✴✡✓❡✁⑩✽ ☞ 78✛☎✖✡➈✡✜●✡❘✡❙ ❴✡❛✁➇✚✡☞ 4(4 ✉✁✈✁✇✡✓✁❺✁➂✁s✁t), ✳✡✴☞ 0(❼✁✏①③② B ⑦ s), ➨→●✡❘✡❙✓✡✻✡✼❸❡ ⑩✽ ☞ 40 + 78 = 118✛✢❴✡❛✁✏ B ⑦ s 1 ✉✁✈✁✇, Õ❡✁⑩✽ ☞ 42, ✑✁➂✡í 3 ✉✁✈✁✇✡✗✁✏ C ⑦ sÓ✛ ➈✭ C ✓Ó✻Ó✼Ó✳Ó✴Ó✓❡✢⑩✽✡✦ 78, ✖✢✑Ó➨→❘Ó❙✓Ó✻Ó✼❸❡✁⑩✽ ☞ 120✛ ❱Ó❲✢✗Ó✗ ✷✡ô✡➇❯ ➇ ✚✡☞ 4, ✳✡✴☞ 2 ✓✡✻✡✼✡✴✡♥❸❡✁⑩✽ ☞ 118; ✳✡✴☞ 3 ✓✡✻✡✼✡✴✡♥❸❡✁⑩✽ ☞ 124; ✳✡✴☞ 4 ✓✡✻✡✼✡✴✡♥❸❡✁⑩✽ ☞ 114✛×➎✏➏✡✷ ❅➇ ✚✡☞ 4 ✭ ✓ 5 ● ❼✡✬✡✳✡✴✡✓❸ ❡✢⑩✽ ☞ , ❧Ó✗●✔Ó➈✢➇✚íÓ✓Ó✻✡✼Ó✳✡✴✡✦ 3, ✻Ó✼❸❡✢⑩✽ ☞ 124✛ ➫Ó➭➇ ✚íÓ✸Ó✹Ó✻Ó✼ ✳✡✴✡✓✡✒✁✼✡➥❅✁✩✒✁✼✡✣✁➔, ✗✁↔✁↕☞Ù 8–3 ➥✡Ù 8–4✛
$8.1两个引例 5 表8-3 状对B的策C的状B的效益值C的效益值最程总效益值 0 0 40 48 88 64 104 2 40 68 108 64 106 50 40 78 118 50 0 60 48 108 40 78 42 78 120 2 68 118 60 64 124 66 114 表8-4 状 最程 最程策 1 的效置值 0 104 104 108 106 108 3 118 110 108 118 4 118 120 118 124 114 3 124 最后，要对作出 策 否投资，效益值 038.这释在对B 我智意批会超位 2用同样目也还确定其他寄总效益值，从而找出最程策，见表5 表8-5 01丁34 最程最程策 策 的效置值 41621591561641543 164 至影我们按与实际害策过程相反的顺京逆父找到了各确唐策阶'各种还能状和 下的最蓄，多不到最程餐见6
§8.1 ▼❖◆❈P❖◗ 5 Ù 8–3 ➇ ✚ ✏ B ✓✡✳✡✴ C ✓✁➇✚ B ✓❡✁⑩✽ C ✓❡✁⑩✽ ✻✡✼❸❡✁⑩✽ 0 0 0 40 48 88 1 0 1 40 64 104 1 0 42 48 90 2 0 2 40 68 108 1 1 42 64 106 2 0 50 48 98 3 0 3 40 78 118 1 2 42 68 110 2 1 50 64 114 3 0 60 48 108 4 0 4 40 78 118 1 3 42 78 120 2 2 50 68 118 3 1 60 64 124 4 0 66 48 114 Ù 8–4 ➇ ✚ ✳✡✴ ✻✡✼ ✻✡✼✡✳✡✴ 0 1 2 3 4 ✳✡✴ ✓❡✁⑩✽ 0 88 — — — — 0 88 1 104 90 — — — 0 104 2 108 106 98 — — 0 108 3 118 110 114 108 — 0 118 4 118 120 118 124 114 3 124 ✻✡➨, ❖✁✏ A ❚✡❯ ✳✡✴, ➈✭ , ❱✡❲●➆✡❰✁✸✁❇✡✲ 4 ✉✁✈✁✇✁➋✡❉✁❷✡✓✁s✁t✡✛✢❴✡❛✁✏ A ❼⑦ s, ❡✁⑩✽ ☞ 38, ✜✡❀☛✏ B ✳✡✴✭ ➇ ✚✡☞ 4, ✻✡✼✡✴✡♥✡✓❸❡✁⑩✽ ☞ 124, ❸❡✁⑩✽ ☞ 162✛✢③✡✬✡❀✇✡②✾✡✗●✔➫✡➭✓ ❸❡✁⑩✽, ❃✁✑✡q❯ ✻✡✼✡✳✡✴✡✛☎❁✡Ù 8–5✛ Ù 8–5 ➇ ✚ ✳✡✴ ✻✡✼ ✻✡✼✡✳✡✴ 0 1 2 3 4 ✳✡✴ ✓❡✁⑩✽ 4 162 159 156 164 154 3 164 ã✡➈, ❱✡❲✁✽✡➥☛✁➙✳✡✴✡✒✁✼❍✁➛✓❻ ❡ (➜✡❡) q ✟✡ñ➆ ●✳✡✴❘✡❙➆✡⑥✡✗Ô➇ ✚ í✡✓✡✻✡✼✡✳✡✴✡✛☎✶✡➈, ❼✁➝❻ ❡✡q✟✻✡✼✡✳✡✴, ❁✡Ù 8–6✛
6 第八章动态规划 表86 项目投资额 数益值 3 60 0 40 1 64 S82动态规划的基本概念和基本原理 一、动态规划的基本概念 (一人、阶段 应用动态规划方法时，问题必须能划分为若干阶段。在每一阶段都可作出不同的决策 以控制这个阶段的发展过程.这就是所谓多阶段决策过程.前面已经指出，如果我们把一 个可能实现的从最初阶段到最后阶段的一系列决策（每个阶段一个决策）称为一个策略 那么，动态规划的目的便在于从众多的策略中寻求最优策略。这个寻求过程，在一般情况 下和实际决策过程的方向相反，即所谓逆序求解。通常用k作为表示阶段的变量.本书以 k=1表示计算的第1阶段，即实际决策的最后1个阶段，k=2表示实际决策的倒数第2 个阶段，如此逐阶段顺序编号，直至实际决策的最初阶段。 (二入、状态和状态变量 状态可理解为事物的某种特征。状态发生变化，意味着事物有了发展、变化。在动态 规划问题中，状态是划分阶段和各阶段决策的依据，阶段的推移意味着状态的变化，多阶 段决策过程的发展可以用过程各阶段状态的演变来措术。应用动态规划必须能够完格列 举出每一阶段开始时的一切可能状态 状态通带可以用一个数 组数)来表示，称为 状态变量（或向量）。我们用k表示阶段k的状态变量。例2投资间题中每一阶段开始时 的状态是尚未分配的投资额，在第1阶段（对C决策），81=0,1,2,3,4在第2阶段（对B 决策)，2=0,12,34在第3阶段（对A决策， 53 4.例1最短路线向题中各阶段开始时 的状态是铁路线通过地点，如第1阶段可能状态是D1和D2,它们不是数但如有必要可 约定用两个数（例如1和2）分别表示D1和D2。状态用数表示，以便于进行计算 (但入、决策和决策变量 实际过程从初始状态开始逐阶段向前发展，每一阶段达到一个可能状态。下一阶段进 入什么状态，取决于这一阶段作出的决策，也就是说，决策就是各阶段对状态演变诸种可 能性的选择。在许多何题中，决策可以自然而然地用一个数（或一组数）表示，称为决策变 量（或向量），我们用xk表示第k阶段的决策变量。例如，例2中的决策变量表示的是对 某一投资项目的选择，例1中各阶段的决策是路线的选择，不是数为了计算方便，可以 将不同的决策人为地规定为不同的数.各阶段全部可能的决策称为该阶段允许决策集合 记为Xk.每个阶段的允许决策集合不一定相同.每一阶段某一状态下可能的决策一般也 只能是该阶段允许决策集合的一个子集 (四)、状态转移方程 如果第k阶段开始时状态为，作出的决策为k,那么第k阶段末（即第k一1阶段
6 ÷✡ø✡ùûú➋ü✏ý✡þ Ù 8–6 ①③② ⑦ s✁⑧ ❡✁⑩✽ A 3 60 B 0 40 C 1 64 §8.2 ➞❧➟❧➠❧➡❧➢❧➤❧➥❧➦❧➧❧➨➩➤❧➥➩➫❧➭ ➽➺➾ ➞❧➟❧➠❧➡❧➢❧➤❧➥❧➦❧➧ (➯)❙✢▲✡◆ ➯Ó③Ó⑧✚Ó❻❈✇Ó②✭ , ❁Ó❂✢✓✢➲Ô ❈Ó❉☞Ó❊Ó❋Ó❘Ó❙, ☛Ó◗✧❘Ó❙✖Ó✗❚Ó❯ ❼Ó✬Ó✓Ó✳✡✴, ✷✢➳✢➵Ó✜●Ó❘Ó❙✓ç✢➸✒✁✼✡✛ ✜✢✆✡✦✡✱Ó⑦ ❨▲Ó◆Ó❬Ó❭✢➺✢➻Ó✛➼■✢☞Ö✍✏ÐÓ⑨❯ , ❴Ó❛Ó❱Ó❲Ó❜Ó✧ ● ✗ Ô✁☛✡✠✓✡❃✡✻✁✮❘✡❙✡✟✻✡➨❘✡❙✓✡✧❑❢✡✳✡✴ ( ◗✡●✡❘✡❙✧ ●✳✡✴) ✘ ☞✧ ● ❭✡❣, ❤✡✐, ⑧✚✡❻❈✡✓ ② ✓✡❧☛ ④✡❃♠ ❦✡✓✡✴✡♥➋♦r✸✡✹✰✻✡✼✰✴✡♥✡✛ ✜ ● ✸✰✹✡✒✝✼, ☛✧✁➃✁➽✁➾ í✢✚☛✢➙✳Ó✴Ó✒✢✼Ó✓✇ ✭❍✁➛, ❷Ó✱Ó⑦➪➚✢➶✢➹✢➘Ó✛➴✍✢➷Ó③ k ❚Ó☞ÙÓÚ❘Ó❙✓Ó✵Ó✶Ó✛ß➡✢➬✡✷ k = 1 Ù✡Ú✡ô✡➇✡✓✡Ñ 1 ❘✡❙, ❷☛✁➙✳✡✴✡✓✡✻✡➨ 1 ●✡❘✡❙,k = 2 Ù✡Ú☛✁➙✳✡✴✡✓❋Û✡Ñ 2 ●✡❘✡❙, ❴✡➈✡❶❘✡❙✁❻❡✁➮✡➍, ï✡ã☛✁➙✳✡✴✡✓✡✻✁✮❘✡❙✛ (➱)❙ ➄ t✁✃➄ t✁❐✁❒ ➄ t ✗✡✯✡❥☞✁❮✁❰✓✡⑤✡⑥✡✤✁Ï✡✛Ð➇✚✡ç➎✵✁Ñ, ❽✁Ò✁❉❮✁❰✲ ñ✡ç✁➸❙ ✵✁Ñ✡✛ ☛ ⑧✚ ❻ ❈✡❁✡❂➋♦, ➇ ✚✦✡❈✡❉❘✡❙✚✡➆❘✡❙✳✡✴✡✓✡P✝✶, ❘✡❙✓✰❹✁❽✁Ò✁❉✁➇✚ ✓✡✵✁Ñ✡✛✢❦❘ ❙✳✡✴✡✒✁✼✡✓ç✁➸✗✡✷✡③✰✒✝✼✡➆❘✰❙➇ ✚ ✓✝Ó✰✵✁✛✝Ô✩ ✛✢➯✰③✰⑧✚✰❻❈✁✓✝➲Ô✝➈✝Õ✁✻❢ ó ❯✰◗✧❘✰❙✫✝✬✭ ✓✰✧✝➆✰✗Ô➇ ✚ ✛☎➇✚✍✝➷✰✗✰✷✰③✰✧●Û (✩✰✧✝Ö✰Û) ✛✰Ù✰Ú, ✘ ☞ ➄ t✁❐✁❒(✩Ø×✁❒)✛➉❱✡❲✡③ sk Ù✡Ú❘✡❙ k ✓✁➇✚✵✡✶✡✛➉ÿ 2 ⑦ s✡❁✡❂➋♦◗ ✧❘✡❙✫✁✬✭ ✓✁➇✚✦❈Ù❖➋✡❉✁❷✡✓⑦ s✝⑧, ☛ Ñ 1 ❘✡❙ (✏ C ✳✡✴), s1 = 0,1,2,3,4; ☛ Ñ 2 ❘✡❙ (✏ B ✳✡✴),s2 = 0,1,2,3,4; ☛ Ñ 3 ❘✡❙ (✏ A ✳✡✴), s3 = 4✛➉ÿ 1 ✻✡ä✡➱✡➮✡❁✡❂➋♦✏➆❘✡❙✫✁✬✭ ✓✁➇✚✦✡Ï✡➱✡➮✁✍✡✒✡❰✡✥, ❴✡Ñ 1 ❘✡❙✗ Ô➇ ✚✦ D1 ✚ D2, ✂✡❲✡❼✡✦✡Û, ➁✡❴✡✲✁✓✡❖✡✗ Ú✔✡③→●Û (ÿ✡❴ 1 ✚ 2) ❉✁✴✡Ù✡Ú D1 ✚ D2 ✛☎➇✚ ③✡Û✡Ù✡Ú, ✷✡❧✡④å✡æô✡➇✡✛ (Û)❙✢❬✡❭✁✃✡❬✡❭✁❐✁❒ ☛✢➙✒✢✼Ó❃✢✮✢✬✢➇✚ ✫✢✬✡❶❘✡❙✭❖■ç✁➸, ◗ ✧❘Ó❙ÓðÓ✟✧ ● ✗ Ô➇ ✚ ✛ íÓ✧❘Ó❙✡å ❃✝Ü✰✐✝➇✚ , ➁✰✳✰④✰✜✰✧❘✰❙✰❚✰❯ ✓✰✳✰✴, ✾✝✆✰✦✰✫,❬✰❭Ý✆✰✦✰➆❘✰❙✏✝➇✚ Ó✰✵✝Þ✰⑥✰✗ Ô❺Ó✓Óàá ✛ ☛✢ß❦Ó❁Ó❂➋♦, ✳Ó✴Ó✗Ó✷áà✢➧✢✑Ó➧Ó❰Ó③✡✧●Û (✩Ó✧✢ÖÓÛ) ÙÓÚ, ✘ ☞ ❬Ó❭✢❐ ❒(✩â×✁❒)✛✢❱✡❲✡③ xk Ù✡Ú✡Ñ k ❘✡❙✓✡✳✡✴✡✵✡✶✡✛✢ÿ✡❴, ÿ 2 ♦✏✓✡✳✡✴✡✵✡✶✡Ù✡Ú✡✓✡✦✁✏ ⑤✰✧⑦ s ①➀② ✓✰àá , ÿ 1 ♦r➆❘✰❙✓✰✳✰✴✰✦✰➱✰➮✰✓✰àá , ❼✰✦✰Û✰✛ ☞✰ñ ô✰➇✇ ❧, ✗✰✷ ❇ ❼Ó✬Ó✓Ó✳Ó✴✢ã☞❰ ❻ ✔ ☞❼✡✬✡✓ÓÛ✡✛ ➆❘✡❙✢ä✎Ó✗Ô ✓Ó✳✡✴✡✘☞❪ ❘✡❙æå✢ç❬Ó❭✢è✢é, ✹✡☞ Xk ✛ ◗✡●✡❘✡❙✓✁êß ✳✡✴✁ë✁ì✡❼✡✧✁✔❍ ✬✡✛ ◗ ✧❘✡❙⑤✡✧✁➇✚í✡✗Ô ✓✡✳✡✴✡✧✁➃✡✾ ✵Ô✦✁❪❘✡❙êß ✳✡✴✁ë✁ì✡✓✡✧● ❳✁ë✡✛ (í)❙ ➄ t✁î✁ï✁ð✁➻ ❴✡❛✡Ñ k ❘✡❙✫✁✬✭ ➇ ✚✡☞ sk, ❚✡❯ ✓✡✳✡✴☞ xk, ❤✡✐✡Ñ k ❘✡❙✁ñ (❷✡Ñ k − 1 ❘✡❙
$82动态规划的基本概念和基本原理 7 初)的状态8k-1就已被确定.这就是说，Sk-1随sk及%而变化.可以把这一关系看成是 Sk-1与k和的函数关系，记为 Sk-1=g1(Sk:Tk) (8.1) 这一等式表示了某一阶段的状态向下一阶段状态转移的规律，称为状态转移方程.有很多 问题，这种函数关系可以用数学解析式表示.例如，对于例2有：5k-1=k一工k,S≥xk 这给计算带来方便.有的问题，例如例1，这种函数关系很雄用解析式表达，但这并不妨碍 我们用动态规划方法来解决向题。 (伍)、优劣指标 动态规划题的求解就是寻求最优策略，即寻找最优的可行的决策序列.这就需要有 一个指标，用以衡量一个策略的优劣，即衡量一个可以实现的状态演变过程的优劣，这个 指标称为优劣指标。例1中优劣指标是从A至E的路线总长度，例2是3个项目投资的 总效益值，优劣指标决定于过程的最初状态和各阶段所采取的决策，即它是初始状态和决 策序列的函数。而在各个阶段，在每一状态下所作出的每一决策都有一个影响总效果的直 接效果，它是sk和x的函数，记为dk(s,E)。例如例2中有： d山(s1,0)=48,51=0,1,2,3,4 d山(s3,2)=48,s3=4. 设整个过程从第n阶段开始.由第k阶段(k=1,2,)的状态sk开始至某一最 终状态的这一段过程，称为第k阶段状态跳的后部过程（相应的决策序列称为的后 部策略)。从例1、例2的解题步骤可知，动态规划方法的每一阶段都要找出该阶段每一状 态的最优后部过程（品优后部策路）从第k阶段状态开始的每一后部时程都可可象全 过程那样，规定一个指标，具有最优指标的后部过程称为最优后部过程。其相应指标记为 fk(s).例如在例2中，2(3)表示从第2阶段（对B投资）的状态3（剩余资金为3百万元） 开始的最优后部过程的总效益值。 (六)、指标递推方程 例1、例2中，在计算各个阶段的最优后部过程指标时，都要利用上一阶段已得到的 最优后部过程指标.第k阶段在状态5k下可采用不同的决策，每一决策都有一个影响目 标的直接指标d4(5k,xk):不同的决策又将使得过程进入第k-1阶段时，具有不同的开始 状态（各有不同的最优后部过程指标）.对于例1和例2，我们是这样计算第k阶段状态s 的最优后部过程指标的 fu(sk)=max/min{dx(sk,)+fk-1(g1(sk K)EX}, k=1,2,, (8.2) f0(so)=0 如果用f(sk,工)表示第k阶段在采取决策x的条件下影的最优后部过程指标，即 f(k,s)=d(sk,k)+fk-1(g1(sk,工k)》
§8.2 ú➋ü✏ý✡þ❈ò❖ó✁ô✁õ✁ö✁÷✁ó✁ô✁ø✁ù 7 ✮) ✓✁➇✚ sk−1 ✆➋✍❖ú●✔✡✛ ✜✁✆✡✦✡✫,sk−1 û sk ❤ xk ✑✡✵✁Ñ✡✛ ✗✡✷✡❜✡✜✡✧❩✡❑❆✡❞✡✦ sk−1 ➥ sk ✚ xk ✓✁ü✡Û❩✡❑, ✹✡☞ sk−1 = g1(sk, xk) (8.1) ✜Ó✧ÓÒ✢ýÓÙÓÚñ⑤Ó✧❘Ó❙✓✢➇✚ ✭×íÓ✧❘Ó❙➇ ✚❸Ó❹Ó✓❻✢þ, ✘ ☞ÿ➄t✢î✢ï✢ð✢➻Ó✛ ✲❝ ❦ ❁Ó❂, ✜Ó⑥✢üÓÛ❩Ó❑✗Ó✷Ó③ÓÛÓ➀✡❥✁✁ý✡ÙÓÚ✡✛ ÿ✡❴, ✏Ó④Óÿ 2 ✲: sk−1 = sk − xk, sk ≥ xk ✛ ✜✁➉✡ô✡➇✄✂✁✛✇ ❧✡✛ ✲✡✓✡❁✡❂, ÿ✡❴✡ÿ 1, ✜✡⑥✁ü✡Û❩✡❑✁❝➝✡③✡❥✄✁ý✡Ùð , ➁✡✜✡➂✡❼✄☎✄✆ ❱✡❲✡③✡⑧✚✡❻❈✇✡②✛✡❥✡✳✡❁✡❂✡✛ (✝)❙✟✞✄✠✄✡✄☛ ⑧✚Ó❻❈Ó❁Ó❂Ó✓Ó✹Ó❥✢✆Ó✦✡✸Ó✹✡✻✡✼Ó✴✡♥, ❷Ó✸ÓqÓ✻Ó✼Ó✓Ó✗æ ✓Ó✳Ó✴Ó❡✡❢Ó✛ ✜✢✆✡⑩Ó❖✡✲ ✧ ● ⑨✌☞, ③✰✷✌✍✰✶✰✧● ✴✰♥✰✓✰✼✌✎, ❷✌✍✰✶✰✧● ✗✰✷ ☛✰✠✓✝➇✚ Ó✰✵✰✒✝✼✰✓✰✼✌✎, ✜ ● ⑨✄☞✡✘☞ ✞✄✠✄✡✄☛✡✛ ÿ 1 ♦✏✼✄✎✡⑨✄☞✡✦✡❃ A ã E ✓✡➱✡➮❸õ✡ö, ÿ 2 ✦ 3 ●✁①③②⑤⑦s✡✓ ❸❡✁⑩✽, ✼✄✎✡⑨✄☞✡✳✁✔✡④✡✒✁✼✡✓✡✻✁✮✁➇✚ ✚✡➆❘✡❙✱✄✏✁➁✡✓✡✳✡✴, ❷✁✂✡✦✁✮✁✬✁➇✚ ✚✡✳ ✴Ó❡Ó❢Ó✓✢üÓÛÓ✛➼✑☛➆ ●Ó❘Ó❙, ☛Ó◗✧✢➇✚íÓ✱❚Ó❯ ✓◗ ✧✡✳Ó✴✡✖✡✲Ó✧●✁✑✄✒✁❸❡ ❛Ó✓✡ï ✣ ❡ ❛, ✂✡✦ sk ✚ xk ✓✁ü✡Û, ✹✡☞ dk(sk, xk)✛✢ÿ✡❴✡ÿ 2 ♦✏✲: d1(s1, 0) = 48, s1 = 0, 1, 2, 3, 4; d3(s3, 2) = 48, s3 = 4. ❮ ✻✰●✒✝✼✰❃✰Ñ n ❘✰❙✫✝✬✰✛❖✪rÑ k ❘✰❙ (k = 1,2,. . .,n) ✓✝➇✚ sk ✫✝✬✰ã✰⑤✰✧✰✻ è✝➇✚ ✓✰✜✰✧❙ ✒✝✼, ✘ ☞✔✓ k ▲✰◆➄ t sk ✕✌✖✌✗➺✝➻(❍➯✰✓✰✳✰✴✰❡✰❢✰✘☞ sk ✕✌✖ ✗❭✡❣)✛ ❃✡ÿ 1❙ ÿ 2 ✓✡❥✡❂✡➛✡➜✡✗✁✸, ⑧✚✡❻❈✇✡②✓◗ ✧❘✡❙✖✡❖✡q❯ ❪ ❘✡❙✡◗✧✁➇ ✚ ✓✰✻✰✼✰➨✝✎✰✒✝✼ (✻✰✼✰➨✝✎✰✴✰♥)✛ ❃✰Ñ k ❘✰❙➇ ✚ sk ✫✝✬✰✓◗ ✧✰➨✝✎✰✒✝✼✰✖✰✗✌✘ä ✒✁✼✡❤✡❀, ❻ ✔✡✧● ⑨✄☞, ➣ ✲✡✻✡✼✡⑨✄☞✡✓✡➨✁✎✡✒✁✼✡✘☞✚✙✞✖✄✗➺✁➻✡✛ ➫✡❍➯✡⑨✄☞✹✡☞ fk(sk)✛ ÿ✡❴☛ ÿ 2 ♦,f2(3) Ù✡Ú✡❃✡Ñ 2 ❘✡❙ (✏ B ⑦ s) ✓✁➇✚ 3(❺✁➂✁s✁t☞ 3 ✉✁✈✁✇) ✫✁✬✡✓✡✻✡✼✡➨✁✎✡✒✁✼✡✓❸❡✁⑩✽✡✛ (✛)❙✟✡✄☛✄✜✄✢✁ð✁➻ ÿ 1❙✢ÿ 2 ♦, ☛ô✡➇✡➆●✡❘✡❙✓✡✻✡✼✡➨✝✎✰✒✝✼✡⑨✌☞✭ , ✖✡❖✁★✡③❅✧❘✡❙ ✍❚ ✟ ✓ ✻✡✼✡➨✁✎✡✒✁✼✡⑨✄☞✡✛✢Ñ k ❘✡❙✡☛➇ ✚ sk í✡✗✄✏✡③✡❼✡✬✡✓✡✳✡✴, ◗ ✧✡✳✡✴✡✖✡✲✡✧●✄✑✄✒③② ☞✡✓✡ï✁✣✡⑨✄☞ dk(sk, xk); ❼✡✬✡✓✡✳✡✴✄✣❇❢ ❚✡✒✁✼å ❃✡Ñ k − 1 ❘✡❙✭ , ➣ ✲✡❼✡✬✡✓✁✫✁✬ ➇ ✚ (➆Ó✲Ó❼Ó✬Ó✓Ó✻Ó✼Ó➨✢✎Ó✒✁✼Ó⑨✄☞)✛ ✏Ó④✡ÿ 1 ✚Óÿ 2, ❱Ó❲Ó✦Ó✜Ó❀ÓôÓ➇ÓÑ k ❘Ó❙➇ ✚ sk ✓✡✻✡✼✡➨✁✎✡✒✁✼✡⑨✄☞✡✓: fk(sk) = max/min{dk(sk, xk) + fk−1(g1(sk, xk))|xk ∈ Xk}, k = 1, 2, . . . , n; f0(s0) = 0 (8.2) ❴✡❛✡③ fk(sk, xk) Ù✡Ú✡Ñ k ❘✡❙✡☛✏✁➁✡✳✡✴ xk ✓✡â✄✤✡í sk ✓✡✻✡✼✡➨✁✎✡✒✁✼✡⑨✄☞, ❷ fk(sk, xk) = dk(sk, xk) + fk−1(g1(sk, xk))
8 第八章动态规划 则式(82)可点为 f(sk)=max/min{fu(sx,rk)EX),k =1.2.....n; f(sk,工k)=d(sk,k)+f-1(g1(sk,工k)月 (8.3) fo(so)=0. 以例2中儿确具体数字为例（是见表8-3）： f2(3,0)=d2(3,0)+1(3-0)=40+78=118 f2(3.1)=d2(3.1)+f(3-1)=42+68=110 f2(3,2)=d2(3,2)+五3-2)=50+64=114. f26,3)=d2(3,3)+3-3)=60+48=108 2(3)=max{f2(3.0,f(3,1),f2(3,2).f2(3,3)} -max{118,110,114,108}-118. 诺推奢关政款为指被推方程电所为货全西的本方程只有建可这 ,策变对以理寻求从蕞以优值也始样值问题计算，， 宝零R》 fu(sk,x)=g2(dk(sk,K),fr-1(g1(sk,A))) (8.4) 出我要们变够写出我学表达式，但如不以每果式(8)中相加个形式例那要以段 f(sk,)=d(sk,x)·fk-1(g1(sk,x》 么解，此便还需 每6()-1, 中、动态规划基方原法 建同指用递推程←基种在例1中动指介即，更段以性个表规不果类国Bmam首 先提出，最优化原算： 此理过程不 个两警明 “据这理余甘 策略.。 具体寻求指用计算 ,要应盘相邻两优值，指用递推程. 化然后中包含着对 韩他这理要们就果动。略划寻求中 上相 安具备无后发安凭效式有县在甘论转移过阅护以设法划某鲨美 ,以后过程。发展仅仅取 省讨接中只要最1优位 表膜能这以质 各优值果经过什么 金法桨含西是优值个路 ,而与这以便则以前 债无 策要不管 路.例2中，股1优值只要剩余。投资额 泰不弹做针其A线 3奇有投资0剩下 ,还果向A投资2向B投资剩下，等待，都不影响在这以 属邦香上相策略较资1百下.这理然不果建同动 下对C ,论略划模计个基本要们十 、只变动过程而不具备无后效性就米果动， 不变据以建计诊划棋计靓例1，例2 无资果商阶下个计论较 对以理划例导求建同动论略划模计， 个 段以下儿理步：
8 ÷✡ø✡ùûú➋ü✏ý✡þ Õ✁ý (8.2) ✗✄✥☞ : fk(sk) = max/min{fk(sk, xk)|xk ∈ Xk}, k = 1, 2, . . . , n; fk(sk, xk) = dk(sk, xk) + fk−1(g1(sk, xk)); f0(s0) = 0. (8.3) ✷✡ÿ 2 ♦➩●✡➣✡↔Û✡Ü☞ ÿ (✦✁❁✡Ù 8–3): f2(3, 0) = d2(3, 0) + f1(3 − 0) = 40 + 78 = 118, f2(3, 1) = d2(3, 1) + f1(3 − 1) = 42 + 68 = 110, f2(3, 2) = d2(3, 2) + f1(3 − 2) = 50 + 64 = 114, f2(3, 3) = d2(3, 3) + f1(3 − 3) = 60 + 48 = 108, f2(3) = max{f2(3, 0), f2(3, 1), f2(3, 2), f2(3, 3)} = max{118, 110, 114, 108} = 118. ý (8.2) ✩ (8.3) ✘ ☞ ✡✄☛✄✜✄✢✁ð✁➻, ✾✡✘☞ s✡t✉✡✈✕✄✧✄★ð✁➻✄✩☎✵✄✪✄✫✄✬✄✭✄✮✄✯ ✰✄✱✄✲✄✳, ✴✄✵✄✶✄✷✄✯✄✸✄✹✄✺✄✻✄✷✄✼✄✽✄✾✄✿✄❀✄✽✄❁✄❂✄❃✄❄, ❅✄❆✄❇✄❈✄❉✄❊✄❋✄●✄❅✄❍✄■✄✩ ✮✄❏✄❑✄▲✄▼✄◆,fk(sk, xk) ❖✄P✄◗✄❘✄❙ dk(sk, xk) ❚ fk−1(g1(sk, xk)) ●✄❯✄❱: fk(sk, xk) = g2(dk(sk, xk), fk−1(g1(sk, xk))) (8.4) ❯✄❱ g2 ▲✄❲✄✵✄❳✄❨✄◆✄❱✄❩✄❬✄❭✄❪, ❫✄❴✄❵✄✷✄◗✄❛✄❪ (8.3) ❜❞❝✄❡✄●✄❢✄❪, ❣✄❤✄❖✄P✄❙ fk(sk, xk) = dk(sk, xk) · fk−1(g1(sk, xk)) ✐✄❥, ❦✄❧✄♠✄❑✄♥✄◗ f0(s0) = 1✩♦q♣❞rqsqtq✉q✈q✇q①q② ✫✁✬✁▼✁③✰✁✱✁④❋✁●✁⑤✄⑥, ⑦✁❣ 1 ❜✁⑧⑩⑨✁❶✁❷✁✩❹❸✁❙✁✷✁❺✁●✁❬✄❻✄❼✁❛✄❽✁❾ Bellman ❿ ➀✄➁◆✄●➃➂✄➄✄➅✄➆✄➇: “⑨✌❙✌➈✌✯✌❊✌❋✌●✌❅✌❍✌➉✌➊✌➋✌✪✌✮✌➌✌●✌➍✌➎: ➏✌➐✌➑✌❊✌➒✌●✌➓✌➔✌❚✌→✌➉✌❤✌➣, ✶✌↔✌↕ ●✄→✄➉✄➙✄❢✄➛✄●✄➓✄➔✄➜✄➝, ➞✄➟✄●✄➠✄→✄➉✄➡✄➢✄➤✄➛✄❅✄❍✄➉✄➊✄✩ ” ➥✁➦✮✁✯✁➧✁➨✁❚✁➋✁➩✁✸✁✹✄▼✁③✄❃✁❄✄●✁➫✄➭, ❖✁➯✁◆✁❝✁➲✁➳✁✼✁✽✁●✁▼✁③✰✁✱✄④❋✁✩➵❅✄❍ ➸➧✄➨➺❜❞➻✄➼✄➽✄✶✄➙✄◗✄❘✌●✌➓✄➔✌●✌➫✄➾✌▲✄❲✌✩✟✮✌✯✌▲✄❲✌➚✄❛✌➪✌➔✄♥✌➶✌✸✄✹➹❜❞●✌➓✌➔✄✷✌◗ ▲✄➋✄➘ “➴✄➷✄➬✄➮”✩➱➙✄✃ “➴✄➷✄➬✄➮”, ▼✄●✄❛✄⑦✄➓✄➔✄❐✄❒✄❊✄❋➺❜, ✷✄❮✄❭✄❈✄❰✄✷✄✼✄✽✄●✄❰ ✷✄➓✄➔, P✄Ï✄❊✄❋✄●✄Ð✄Ñ✄Ò✄Ò✄Ó✄→✄Ô✄✮✄✷✄❧✄Õ✄●✄➓✄➔, ➜✄Ö✄✮✄✷✄❧✄Õ✄P✄↔✄●✄➓✄➔✄❚✄→✄➉✄➐ ✲ ✩×❣ 1 ❜, Ø✄▲✄✻ 1 ✼✄✽✄●✄Ù✄✿✄➓✄➔✄❛ D2, Ú✄Û✄❵✄Ü✄↔✄↕ 3 ✯✄✼✄✽✄●✄→✄➉✄❤✄➣, ➏✄❵✄Ü Ý✼✌✽✌❛✌Þ✌❊✌ß✌Û✌➓✌➔✌➜✌❭✌❈ D2 ●, à✌❵✌á✌â✌✺✌➓✌➔ D2 ◆✌Ð✌●✌❅✌❍✌➉✌➊ (ã✌ä D2 å E ●✄æ✄ç)✩×❣ 2 ❜, ✻ 1 ✼✄✽, Ø✄▲✄è✄➞✄●✄é✄ê✄ë✄❙ 1, Ú✄Û✄✮ 1 ì✄í✄î✄➐✄➑✄❛➺ï A é✄ê 3 ï B é✄ê 0 è✄➟✄●, ♠✄❛➺ï A é✄ê 2 ï B é✄ê 1 è✄➟✄●, ð✄ñ, à✄❵✄á✄â✄⑦✄✮✄✷✄➓✄➔ ➟✌✶ C ●✌❅✌❍✌➉✌➊ (é✌ê 1 ì✌í✌î)ò✟✮✌✯✌➧✌❼✌❛✌✫✌✬✌➪✌➔✌♥✌➶✌ó✌ô✌●✌⑤✌õ✌▲✌❲, ö✌÷✌ø ▲✄ò✟❤✄ù✄♥✄◗✄●✄➓✄➔✄Ø✄✵✄ú✄❻✄❊✄❋✄➜✌❵✄➋✄➘✌➐✄Ï✌û✄➍, ➚✄❵✄❛✄➪✄➔✄♥✄➶✄ü✄❘✄➟✄●✄➓✄➔, ➏ ❵✄✵➦ P✄✫✄✬✄➪✄➔✄♥✄➶✄ó✄ô✄ò✟❣ 1, ❣ 2 ➓✄➔✄●✄➐✄Ï✄û✄➍✄❛✄ö✄÷➺ý✐ ●✄ò ✶✄✷✄✯✄þ✄ÿ✄✸✄✹✄✫✄✬✄➪✄➔✄♥✄➶✄ó✄ô, ❖✁✁✂✄❙✄P✄➟✁✄✄✯✁☎✁✆:
58.3背包问题 9 1.将向题恰当地划分为若干个阶段： 2.正确地规定状态变量，使它即能描述过程的演变，又具备无后效性，并注意到每个 阶段的可能状态变量值是可以列举出来的： 3.规定决策变量，确定每个阶段的允许决策集合： 4.写出状态转移方程 5.确定各阶段各种决策的直接指标：列出计算各阶段最优子策略指标的递推方程. 根据状态转移方程和指标递推方程，按与实际过程相反的方向，从实际决策的最后阶 段向最初阶段递推，以寻求最优策略，这种作法称为逆序解法。本章例题都是采用这一解 法，顺便指出，很多问题也可以按与实际过程相同的方向逐阶段递推，寻求最优策略，这称 为顺序解法。例1和例2也都可以用顺序解法求解。 58.3背包问题 一架货运飞机，有效载重量为24t,可运输物品的重量及运费收入见表8-7，问题是选 运哪几件物品使收入最多.这类问题称为背包问题（一个徒步旅行者在他容量有限的背包 里放置哪些旅行必需品使总价值最大的问题) 表8-7 物品重量收入物品重量)收入 1 8 4 9 4 2 13 5 5 5 2 2 6 7 3 问题可以按物品依次划分为6个阶段（化=，2，，6），假定实际过程是先决定是香运 送物品6，因而求解时第飞阶段要决定是否运送物品k,状态k为飞机剩余的吨位。每 个阶段的决策变量xk可取两个值：x=0(不运)和k=1(运).第1阶段可能的状态是 1=0,124,但可以将0,17合并为一类，8,924合并为一类，因为为了运送物 品1至少需要8t剩余吨位，1=0,1，，7时能够采取的决策是相同的，即1=0.在这 一阶段万(s1,工1)=d1(s1,1).计算结果如表8-8.x一栏表示在相应状态下最优决策变 量。如果状态在8~24范围内，最优决策是运送物品1： 表8-8 51 f(s1.n1)=di(s1.r1)i f(s1) 1=0x1=1 0~7 0 0 824 0 1 3 (s1）=max{(s1,x1}=max0,3}=3,i=1(运) 第2阶段 d2(s2,0)-0,对一切s2 d2(s2,1)=5,2≥13
§8.3 ✝✁✞✠✟☛✡ 9 1. ☞✄✸✄✹✁✌✁✍✁✎✄➶✄÷✄❙✁✏✁✑✄✯✄✼✄✽; 2. ✒✁✓✁✎✄♥✄◗✄➓✄➔✁✔✁✕, ✖✁✗✄➏✄✵✄ú✄❻✄❊✄❋✄●✁✘✁✔, ✙✄➋✄➘✄➐✄Ï✄û✄➍, ❴✁✚✄ü✄❈✁✛✄✯ ✼✄✽✄●✄❖✄✵✄➓✄➔✁✔✁✕✁✜✄❛✄❖✄P✄➯✁✢✄◆✁✣✄●; 3. ♥✄◗✄→✄➉✁✔✁✕, ✓✄◗✁✛✄✯✄✼✄✽✄●✁✤✁✥✄→✄➉✁✦✁✧; 4. ❨✄◆✄➓✄➔✄❐✄❒④ ❋; 5. ✓✄◗Ý✼✄✽Ý✁★→✄➉✄●✁✩✁✪✄▼✄③; ➯✄◆✄❃✄❄Ý✼✄✽✄❅✄❍✁✫✄➉✄➊✄▼✄③✄●✰✄✱✄④❋✄ò ➥✄➦➓✄➔✄❐✄❒④ ❋✄❚✄▼✄③✰✄✱✄④❋, ✬✄Ö✄þ✄ÿ✄❊✄❋✄❝✁✭✄●④ ï, ✺✄þ✄ÿ✄→✄➉✄●✄❅✄Ï✄✼ ✽➺ï❞❅✄Ù✄✼✄✽✰✄✱, P✁✮✄❲✄❅✄❍✄➉✄➊, ✮ ★ ⑨✁✯✁✰✄❙✲✱✁✳✁✴✁✵✄ò õ✁✶✄❣✄✹✄à✄❛✁✷✁✸✄✮✄✷✄■ ✯✁ò✺✹✼✻✁▼✁◆, ✽✼✾✁✸✁✹✼✿✁❖✁P✼✬✁Ö✁þ✁ÿ✁❊✄❋✁❝✁❀✁●④ ï⑩❀✄✼✁✽✰✄✱, ✮✁❲✁❅✁❍✁➉✁➊, ✮✼✰ ❙❂❁✁✳✁✴✁✵✄ò✟❣ 1 ❚✄❣ 2 ✿✄à✄❖✄P✁✸✁✹✁❃✄■✁✯✄❲✄■✄ò §8.3 ❄❆❅❆❇❆❈ ✷✁❉✁❊✁❋✁●✁❍, ■✄û✁❏✄ø✁✕✄❙ 24t, ❖✁❋✁❑✁▲✁▼✄●✄ø✁✕✁◆✁❋✁❖✁P✁◗✁❘✄❬ 8–7, ✸✄✹✄❛✁❙ ❋✼❚✼✄✼❯✼▲✼▼✼✖✼P✼◗✁❅✼✾✁ò ✮✁❱✁✸✄✹✼✰✄❙❳❲✼❨✼❩✼❬(✷✁✯✼❭✼☎✼❪✁❂✼❫✁⑦✼❴✁❵✼✕✁■✼❛✄●✼❜✄➻ ❏✁❝✁❞✁❚✁❡✁❪✄❂✄➡✄❑✁▼✁✖✁❢✁❣✁✜✄❅✁❤✄●✄✸✄✹)ò ❬ 8–7 ▲✁▼ ø✁✕ (t) P✁◗ ▲✁▼ ø✁✕ (t) P✁◗ 1 8 3 4 9 4 2 13 5 5 5 2 3 6 2 6 7 3 ✸✄✹✄❖✄P✁✬✁▲✁▼✁✐✁❥✄➶✌÷✄❙ 6 ✯✄✼✄✽ (k =, 2, . . . , 6), ❦✄◗✄þ✄ÿ✄❊✄❋✄❛➀→✄◗✌❛✁❧♠❋ ♥ ▲♠▼ 6, ♦✌➜✌❲✌■✌❧✌✻ k ✼✌✽✌▲✌→✌◗✌❛♠❧♠❋♥ ▲♠▼ kò✟➓✌➔ sk ❙♠●♠❍✌è✌➞✌●♠♣♠q✌òr✛ ✯✌✼✌✽✌●✌→✌➉♠✔♠✕ xk ❖✌Ó✌➳✌✯♠✜:xk = 0(❵♠❋) ❚ xk = 1(❋)ò✟✻ 1 ✼✌✽✌❖✌✵✌●✌➓✌➔✌❛ s1 = 0, 1,. . .,24, ❫✌❖✌P♠☞ 0, 1,,. . .,7 ✧✌❴✌❙✌✷♠❱, 8, 9,. . .,24 ✧✌❴✌❙✌✷♠❱, ♦✌❙✌❙✌✭♠❋♥ ▲ ▼ 1 å♠s❑✌▲ 8t è✌➞♠♣♠q, s1 = 0, 1,. . .,7 ❧✌✵✌❳♠✷✌Ó✌●✌→✌➉✌❛✌❝♠❀✌●, ➏ x1 = 0ò✟⑦✌✮ ✷✄✼✄✽ f1(s1, x1) = d1(s1, x1)ò✟❃✄❄✁t✄ù✄❤✄❬ 8–8ò x ∗ 1 ✷✁✉✄❬✁✈✄⑦✄❝✁✇✄➓✄➔✄➟✄❅✄❍✄→✄➉✁✔ ✕✄ò✟❤✄ù✄➓✄➔✄⑦ 8 ∼ 24 ①✠②✁③, ❅✄❍✄→✄➉✄❛✁❋♥ ▲✁▼ 1: ❬ 8–8 s1 f1(s1, x1) = d1(s1, x1) x ∗ 1 f1(s1) x1 = 0 x1 = 1 0 ∼ 7 0 — 0 0 8 ∼ 24 0 3 1 3 f1(s1) = max{f1(s1, x1)} = max{0, 3} = 3, x ∗ 1 = 1 (❋). ✻ 2 ✼✄✽: d2(s2, 0) = 0, ✶✄✷✁④s2, d2(s2, 1) = 5, s2 ≥ 13
10 第八章动态规划 状态转移方程是 5k-1=5k一kk,其中g为物品k的重量 对于本阶段51=2-13x2 在列举本阶段可能的状态时，我们也将那些具有相同计算结果的状态加以合并将区 间0~24分成0~7,8~12,13~20,21~24四个小区间. 第2阶段的决策过程如标89所示。 表8-9 f2(s2,r2)-d2(s2,x2)+fh(s2-2x2) f2(s2) 2=0 2=1 0w7 8~12 13~20 5 2124 3 8 举两个例子说明表8-9中的数字的计算 当2=8~12时： f2(52,0)=d2(s2,0)+fh(s2-0)=0+3=3. 当2=21~24时： f2(s2,1)=d(2,1)+f(s2-13)=5+3=8。 现在考虑第3阶段】 阶段3的状态小区间为0~5.6~7,8~12,1313,14~18,1920,21~24本阶 段的决策如表8-10。 表8-10 83 f(s,x3)=d(s3,3)+f2(3-u33) 9-0 3=1 05 0 0 0 67 0 8~12 0 3 0 1418 1920 21w24 8 7 0 8 如果可运输的物品只有1,2,3三种那么计算到这个阶段就得到了最优解.最优策略 是不运物品3(s3=24,表8-10中末行x=0),运物品2(51=24-0=24，表8-9中末 行吃=1)，运物品1(s1=24-13=11,表8-8中末行x=1).如果飞机吨位只有14，则 有两个最优策略。一个是不运物品3（表8-10中s3-14一行中x3有两个值，取x-0) 云物品2(82=14.表89中82=14一行：x=1).不坛物品1(s1=14-13=1.表8-8 中s1=1一行x=0).另一个最优策略是运送物品3（取表8-10中=14一行对的另
10 ⑤✁⑥✁⑦⑨⑧✠⑩☛❶✁❷ ➓✄➔✄❐✄❒④ ❋✄❛: sk−1 = sk − wkxk, ❸➺❜ wk ❙✁▲✁▼ k ●✄ø✁✕✄ò ✶✄Ô✄õ✄✼✄✽:s1 = s2 − 13x2 ò ⑦✄➯✁✢✄õ✄✼✄✽✄❖✄✵✄●✄➓✄➔✄❧, ❹✁❺✁✿✁☞✄Ú✁❡✄➋✁■✄❝✁❀✄❃✄❄✁t✄ù✄●✄➓✄➔✄❡✄P✁✧✄❴, ☞✁❻ ❼ 0 ∼ 24 ÷✄➛ 0 ∼ 7,8 ∼ 12,13 ∼ 20,21 ∼ 24 ❽✄✯✁❾✁❻❼ ò ✻ 2 ✼✄✽✄●✄→✄➉✄❊✄❋✄❤✄③ 8–9 ➙✁✈✄ò ❬ 8–9 s2 f2(s2, x2) = d2(s2, x2) + f1(s2 − w2x2) x ∗ 2 f2(s2) x2 = 0 x2 = 1 0 ∼ 7 0 — 0 0 8 ∼ 12 3 — 0 3 13 ∼ 20 3 5 1 5 21 ∼ 24 3 8 1 8 ✢✄➳✄✯✄❣✁✫✁❿➺ý❞❬ 8–9 ❜❞●✄❱✁➀✄●✄❃✄❄: ✍ s2 = 8 ∼ 12 ❧: f2(s2, 0) = d2(s2, 0) + f1(s2 − 0) = 0 + 3 = 3. ✍ s2 = 21 ∼ 24 ❧: f2(s2, 1) = d2(s2, 1) + f1(s2 − 13) = 5 + 3 = 8. ➁⑦✁➂✁➃✄✻ 3 ✼✄✽✄ò ✼✄✽ 3 ●✄➓✄➔✁❾✁❻❼❙ 0 ∼ 5,6 ∼ 7,8 ∼ 12,13 ∼ 13,14 ∼ 18, 19 ∼ 20, 21 ∼ 24ò✟õ✄✼ ✽✄●✄→✄➉✄❤✄❬ 8–10ò ❬ 8–10 s3 f3(s3, x3) = d3(s3, x3) + f2(s3 − w3x3) x ∗ 3 f3(s3) x3 = 0 x3 = 1 0 ∼ 5 0 — 0 0 6 ∼ 7 0 2 1 2 8 ∼ 12 3 2 0 3 13 5 2 0 5 14 ∼ 18 5 5 0,1 5 19 ∼ 20 5 7 1 7 21 ∼ 24 8 7 0 8 ❤✄ù✄❖✁❋✁❑✄●✁▲✁▼✄Ø✁■ 1,2,3 ➄ ★ , Ú✄Û✄❃✄❄✄❈✄✮✄✯✄✼✄✽✄➚✁➅✄❈✄✭✄❅✄❍✄■✌ò✟❅✄❍✌➉✄➊ ❛✌❵♠❋♠▲♠▼ 3(s3 = 24, ❬ 8–10 ❜➇➆✌❂:x ∗ 3 = 0), ❋♠▲♠▼ 2(s1 = 24 − 0 = 24, ❬ 8–9 ❜➇➆ ❂:x ∗ 2 = 1), ❋✁▲✁▼ 1(s1 = 24 − 13 = 11, ❬ 8–8 ❜☛➆✄❂:x ∗ 1 = 1)ò➱❤✄ù✁●✁❍✁♣✁q✄Ø✁■ 14t, ❼ ■✄➳✄✯✄❅✄❍✄➉✄➊✄ò✟✷✄✯✄❛✄❵✁❋✁▲✁▼ 3(❬ 8–10 ❜ s3 = 14 ✷✄❂➺❜ x ∗ 3 ■✄➳✄✯✁✜, Ó x ∗ 3 = 0), ❋✁▲✁▼ 2(s2 = 14, ❬ 8–9 ❜ s2 = 14 ✷✄❂: x ∗ 2 = 1), ❵✁❋✁▲✁▼ 1(s1 = 14 − 13 = 1, ❬ 8–8 ❜ s1 = 1 ✷✄❂:x ∗ 1 = 0)ò➉➈✄✷✄✯✄❅✄❍✄➉✄➊✄❛✁❋♥ ▲✁▼ 3(Ó✄❬ 8–10 ❜ s3 = 14 ✷✄❂ x ∗ 3 ●✁➈