第八章动态规划 到现在为止，已研究过的模型都可称为静态模型，这类模型的特点是一次（或者说同 时)处理所有的决策变量，以寻求这些决策变量的最优值.也存在这样一些问题，可以从 时问上或空间上将问题划分为若干个相互联系的阶段，要求依次在每个阶段作出决策 这样的问题我们称之为多阶段决策问题。如果把每个阶段作出的决策所形成的决策序列 称为一个策酪，那么求解多阶段决策问题便在众多的策略中找出向题的最优策略，动态 规划方法是用于寻求某些多阶段决策问题最优策略的一种方法，所谓“动态”，指的是问 题需逐个阶段处理（即时间或空间的转移）这一特性. 动态规划方法可用于求解不少类型的运筹学问题，但并不存在一个如单纯形法那样 适用于各类问题的单一算法。此外，模型中所用符号也比较复杂。我们将先讨论两个具体 问题，阐明动态规划问题的解题步骤，再介绍动态规划的基本概念与基本原理，然后讨论 几个其他问颗顺.以说明动态规划应用的广泛性 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✛
6 第八章动态规划 表86 项法 动动 值 60 0 C 1 64 58.2介绍基本概念与原然后念与其他 一、介绍基本概念与原然 (应)阶段 应用动态规划方类时，问题的广能划分为若干阶段。在每一阶段都可作出不同的决策， 以泛两这个阶段的发过优.这，是所谓多阶段决策过引 已经指出.如果我们细 那么，劲态规划的的便在王从众多的策略中寻求最优策略。这个寻求过优在一单 决策的 个阶段，如此逐阶段规序线号，直至在决策的最处阶段。 态网 态络铺 可解为的某种特铁，算态发此变第少等分设 有了发个 变第。在动态 品佛不度 段决策过优的发可以用过优路阶段算态的演变 出每一阶段说同时的一各可能算态，算态已 可用一个教成一组 表示称为 态络细（或向铺。我们用5表示阶段k的算器变量。例2前动问题中每一阶段说同时 的算态是表未分即的动动，在第1阶段（对C决策），81=0,1,2,3,4在第2阶段（对B 决策)，2=0,1,2,3,4在第3阶段（对A决策） 53=4.例1最短路线向题中各阶段说同时 的算态是铁路线已过地点，如第1阶段可能算态是D1 D2.它们不是数，但如有的要可 模用两个数（例如1 态2)分策表示D 态D.算态府数表示以便于进行计算， (数)决策网决策络细 过优从处同算态说同逐阶段 个 每一阶段达到一个可能算态。下一阶段进 从字么算态，但决于这一阶段作出的膜也 铺或向铺).我们用k表示第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及%而变化.可以把这一关系看成是 1与态的函数关系记为 5k-1=g1(Sk:Tk) (8.1) 这一等式表示了某一阶段的状态 下一阶段状态转移的规律，称为状态转移方程有很多 问题，这种函数关系可以用数学解式表示.例如，对于例2有：k-1=一，S≥x 这给计算带。方便.有的问题，例如例1，这种函数关系很难用解析式表达，但这并不妨得 我们用动态规划方法.解决向题。 (五)优指 动态规划问题的求解就是寻求最优策略，即寻找最优的可行的决策序列.这就需要有 个指 ,用以已量一个策略的优劣，即已量一个可以在现的状态演变过优的优劣，这个 指南欧名优器在圆1中优劣指是从A至E的瑞线总长度，例2是3个项法数资的 决定于过优的最初状态 果斋直 接果，它是s 态的函数记为4(s,。例如例2中有： d4(s1,0)=481=0,1,2,3,4 d山(s3,2)=48,s3=4. 设最个过优从第n阶段新同，由第太阶段化=1,2叫)的状态开同至某一最 终状态的这一段过优，称为 k阶段状态s跳的都可过程（相应的决策序列称为s趾的都 可策略)。从例1例2的解题步骤可知，动态规划方法的每一阶段都要找出该阶段每一状 态的最优后部过怀（最优后部策路）。从第k阶段状态k开同的每一后部过优都可称全 过优那样，规定一个指 具有最优指的后部过优称为最代都可过程。其相应指记为 4(s).例如在例2中，2(3表示从第阶段（对B投资）的状态3（剩余资金为3万方 开同的最优后部过优的总益值。 ()指这推方程 例1 列2中，在计算各个阶段的最优后部过优指，时，都要利用上一阶段已， 最优后部品优指 ，:第大阶段在状专下可采用不同岛决宽每一决数事有修 一流的失黄又对将的过优进从第大一阶段时具有不同的所同 态例2，我们是这样计算第k阶段状态 的最优后部过优指为的： f(sk)=max/min{d(k,k)+fk-1(g(sk,k)lk∈X， k=1,2,m (8.2) f0(so)=0 如果用，)表示第k阶段在果取决策的条特下8的最优后部过优指为即 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 第八章动态规划 则式(8.2)可写为： 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)=d42(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. 式（⑧.2）或（⑧3）称为指标递推方程也称为动态规划的基本方程.只有建立了这个 递推关系才能对一个问题从第一阶段开始逐段进行计算，最终找到全过程的最优解。 这里需要指出，f(k,)可以定义为d4(5k,)和-1(1(sk,》的函数 f(sk,x)=2(d4(sk,工k),fk-1(1(sk,x4)》 (8.4)】 函数2要求能够写出数学表达式，但并不一定是式(83)中相加的形式，例如可以为 f(sk,)=d(sk,x)·fk-1(g1(sk,x》 显然此时还需规定f(s0)=1, 二、动态规划基本原理 建立指标递推方程的基础，在例1中已作介绍.更为一般的表述则是关国Bellman首 先提出的最优化原理： “作为整个过程的最优策略具有这样的性质即无论过去的状态和决策如何，对前面 的决策所形成的状态而言，余下的诸决策必须构成最优策略 根据这个原理和具体向题指标计算的特点，可列出相邻两阶段的指标递推方程.最优 化原理中包含着对所定义的状态的特殊要求.这个要求就是动态规划问题中的状态一定 要具备“无后效性”。所谓“无后效性”，指的是在状态转移过程中，一旦达到某一阶段的某 一状态，以后过程的发展仅仅取决于这一时刻的状态.而与这一时刻以前的状态和决策无 关.例1中，只要第1阶段的初始状态是D2,那么不管前面3个阶段的决策如何，即不管 各阶段是经过什么状态而达到D2的，都不影响从状态D2出发的最优策略（铺设D2至 E的铁路).例2中，第1阶段，只要剩余的投资额为1，那么这1百万元无论是向A投资 3向B投资0剩下的.不是向A投资2向B投资1下的.等待.都不影响在这一状态 下对C的最优策略（投资1百万元）。这个原则是建立动态规划模型的基本要求，十分重 要。如果规定的状态只能描述过程而不具备无后效性，就不是动态规划意义下的状态，即 不能据以建立动态规划镇羽.例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 物两重)引例物两重。)引例 1 3 4 4 2 13 5 5 5 2 3 6 2 6 7 3 问题可以始物两一投划分为6个阶段（ 2,,6),资定实际过程是先决定是香 额物丙6，分而求解时第阶段要决定是香 额物两k,状态张为 鱼根剩余的配公.巢 个阶段的决策定 可取两个起：x=0(不 1=0,124 和第段可脂赢 累8,924并为一结，分为为了 两1至资需要8t利余配公，1=0,17时能够采取的决策是相圈的，即1=倒在这 一阶段f(s1,1)=d1(s ,1).计算金果如表8-8.一百表万在相元状态下最优决策定 易如果状态在8心2 项目内，最优决策是 额物两1： 表8-8 1 fi(s1,x1)=d(s1,x1)xf1(s1) 1=0x1=1 0~7 0 0 824 0 1 3 ()=max(h())=mx0.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 某种章动需逐即 状态转移方程是 $k-1=5k一工k,其中k为物品k的重量 对于本阶段51=2-13x2 在列举本阶段可能的状态时，我性也那序具有计算态果的状态加以一并为规 021分成0、731213、2021数少个小规 第2阶段的决策过程如标89所示。 表8-9 f2(s2,2)-d2(s2,x2)+f1(s2-2x2) f2(s2) 2=0 2= 0w7 0 8~12 13~20 5 2124 3 8 举两个例说说明表8-9中的数学的计算 当2=8~12时： f2(52,0)=d2(s2,0)+f(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.13~13.1418.19~20,21~24，本阶 段的决策如表8-10。 表8-10 83 f(s3,3)=d(s3,3)+f2(s3-w33)f3(s） -0 E3=1 0w5 0 0 0 6w7 0 8~12 3 2 0 3 0 1418 0.1 1920 2124 8 7 0 8 如果可输的物品只有123三次，那么计算到这个阶段就得到了最优解，最优策略 是不物品5(s3=24表8-10中各行=0)，一物品2(s1=24-0=24,表89中各 行1)，物品1(s1=24-13=11,表8-8中客行x=1).如果 一有个心凝路，一个不物品表0中三4一行神有线个我风有业用一 王物品表心中行g.不物品取表0 1=1一行xi=0).此一个最优策略是于 物品3（敢表8-10中3=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 ●✁➈