第八章动态规划 到现在为止，已研究过的模型都可称为静态模型，这类模型的特点是一次（或者说同 时)处理所有的决策变量，以寻求这些决策变量的最优值.也存在这样一些问题，可以从 时问上或空间上将问题划分为若干个相互联系的阶段，要求依次在每个阶段作出决策 这样的问题我们称之为多阶段决策问题。如果把每个阶段作出的决策所形成的决策序列 称为一个策酪，那么求解多阶段决策问题便在众多的策略中找出向题的最优策略，动态 规划方法是用于寻求某些多阶段决策问题最优策略的一种方法，所谓“动态”，指的是问 题需逐个阶段处理（即时间或空间的转移）这一特性. 动态规划方法可用于求解不少类型的运筹学问题，但并不存在一个如单纯形法那样 适用于各类问题的单一算法。此外，模型中所用符号也比较复杂。我们将先讨论两个具体 问题，阐明动态规划问题的解题步骤，再介绍动态规划的基本概念与基本原理，然后讨论 几个其他问颗顺.以说明动态规划应用的广泛性 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决策 的效益值 64 2 64 68 6 486468 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的最优快策的效益值是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 1 64 104 2 40 68 108 64 106 50 98 40 78 118 0 60 48 108 40 78 42 78 120 2 68 118 60 64 124 66 48 114 表8-4 状态 决策 最优 最优决策 0 1 2 3 决策 的效益值 0 0 10 % 0 104 108 106 108 3 8 110 108 0 118 4 118 120 118 124 114 3 124 最后，要对A作出决策，此时，我们确切地知道有4百万元未分配的资金.如果对A 不投资，效益值为38，这样在对B决策时状态为4，最优策略的总数益值为124，总数益值 为162。用同样方法也可确定其他的总效益值，从而找出最优决策。见表8-5. 表8-5 状态 最优 最优决策 01234 决策 的效益值 41621591561641543 164 至此，我们按与实际决策过程相反的顺序（逆序）找到了各个决策阶段各种可能状态 下的最优决策.据此，不难顺序找到最优决策，见表8-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✛