1第八章 动态规划2引引 言言动态规划是划是处理多理多阶段决策段决策过程最程最优化的一种方法。化的一种方法。该方法是由美国数学家方法是由美国数学家贝尔曼曼R. E. Bellman等人在等人在20世世纪50年代初提出的。并年代初提出的。并胜利地利地处理了消理了消费管理、工程技管理、工程技术等方等方面的面的许多多问题，从而建立了运筹学的一个新的分支，即，从而建立了运筹学的一个新的分支，即动态规划。划。Bellman在在1957年出版了年出版了一一书，是，是动态规划划领域中的第一本著作。域中的第一本著作。3动态规划与其他划与其他规划方法的不同之划方法的不同之处在于：在于： 动态规划是求解某划是求解某类问题多多阶段决策段决策问题的一种方法，的一种方法，是是调查问题的一种途径，而不是一种特定算法。的一种途径，而不是一种特定算法。 因此，它不像因此，它不像线性性规划那划那样有一个有一个规范的数学表达式和明确范的数学表达式和明确定定义的一的一组算法算法规那么，而必需那么，而必需对详细问题进展展详细分析分析处理。因此，学理。因此，学习动态规划划时，除，除对根本概念和根本方法正确了解根本概念和根本方法正确了解外，外，还应在一定在一定阅历积累根底上，以丰富的想像力去建立模型，累根底上，以丰富的想像力去建立模型，用用发明性的技巧去求解。明性的技巧去求解。4提提 纲1 动态规划实例动态规划实例2 动态规划的根本概念动态规划的根本概念3 动态规划的根本思想与根本原理动态规划的根本思想与根本原理4 逆序解法与顺序解法逆序解法与顺序解法5学习目的：学习目的：1 1 明明确确什什么么是是多多阶阶段段的的决决策策问问题题，特特别别要要留留意意没没有明显有明显 的的时时段段背背景景的的问问题题如如何何化化归归为为多多阶阶段段的的决决策策问题。问题。1 动态规划实例动态规划实例6P156 例例2 机器机器负荷分配荷分配问题时间阶段段问题设有有某某种种机机器器设备，用用于于完完成成两两类任任务A和和B。假假设第第k年初完好年初完好机机器器的的数数量量为 xk ，假假设以以数数量量 uk 用用于于A，余余下下的的xkuk用于用于任任务B，那那么么该年年的的预期期收收入入为 g( uk ) + h( xkuk )。这里里g( uk )和和 h( xkuk )是知函数，且是知函数，且 g( 0 ) = h( 0 ) = 0。又又机机器器设备在在运运用用中中会会有有损坏坏，设机机器器用用于于任任务A时，一年后一年后能能继续运运用用的的完完好好机机器器数数占占年年初初投投入入量量的的70%；假假设用用于任于任务B时，一一年年后后能能继续运运用用的的完完好好机机器器数数占占年年初初投投入入量量的的90%。那么在。那么在下下 一一 年年 初初 能能 继 续 用用 于于 A、 B任任 务 的的 设 备 数数 为 xk+1=0.7uk+0.9(xkuk)。设第第1年年初初完完好好的的机机器器总数数为1000台台，问在在延延续5年年内内每年每年应如如何何分分配配用用于于A、B两两项任任务的的机机器器数数，使使5年年的的总收收益益为最大。最大。1 动态规划实例动态规划实例7相相应的的问题称称为多多阶段决策段决策问题。这是一个多是一个多阶段决策段决策过程。程。该过程可以分程可以分为相互相互联络的假的假设干干阶段，每一段，每一阶段都需作出决段都需作出决 策，从而构成全策，从而构成全过程的决策。程的决策。第第1年年x1=1000u1第第2年年x2=0.7u1+ 0.9(x1-u1)u2第第3年年x3=0.7u2+ 0.9(x2-u2)u3第第4年年u4第第5年年x5=0.7u4+ 0.9(x4-u4)u5x4=0.7u3+ 0.9(x3-u3)x6P156 例例1 最短道路问题空间阶段的例子最短道路问题空间阶段的例子 设设有有一一个个游游览览者者从从以以下下图图中中的的A点点出出发发，途途中中要要经经过过B、C、D等等处处，最最后后到到达达终终点点E。从从A到到E有有很很多多条条道道路路可可以以选选择择，各点之间的距各点之间的距离离如如下下图图，问问该该游游览览者者应应选选择择哪哪一一条条道道路路，使使从从A到到达达E的总的路程的总的路程为最短。为最短。25375632455114633334C1C3D1AB1B3B2D2EC21234形状形状1决策决策1形状形状2形状形状3形状形状4形状形状5决策决策2决策决策3决策决策4可看成可看成 4阶段段 的决策的决策 问题。9从以上两个例子，可以知道从以上两个例子，可以知道 所所谓多多阶段决策段决策问题是指是指这样的决策的决策问题：其：其过程可分程可分为假假设干个相互干个相互联络的的阶段，每一段，每一阶段都段都对应着一着一组可供可供选择的决策，的决策，每一决策的每一决策的选定既依定既依赖于当前面于当前面临的形状，又影响以后的形状，又影响以后总体的效体的效果。果。 当每一当每一阶段的决策段的决策选定以后，就构成一个决策序列，称定以后，就构成一个决策序列，称为一一个个战略，它略，它对应着一个确定的效果。多着一个确定的效果。多阶段决策段决策问题就是就是寻觅使使此效果最好的此效果最好的战略。略。10多多阶段决策段决策过程的特点程的特点1.各各阶段的决策相互关段的决策相互关联多多阶段决策段决策过程最程最优化的目的，是要到达整个活化的目的，是要到达整个活动过程的程的总体体效果最效果最优，而不是某个，而不是某个阶段段“部分的效果最部分的效果最优。因此，各个。因此，各个阶段段决策的决策的选取不是恣意确定的。取不是恣意确定的。前一个决策的前一个决策的选取决取决议了当前形状，当前形状了当前形状，当前形状进展决策后又影展决策后又影响到下一响到下一阶段的形状和决策，以致于影响段的形状和决策，以致于影响总体效果。所以决策者体效果。所以决策者在每个在每个阶段决策段决策时，不，不应仅思索本思索本阶段最段最优，还应思索思索对最最终目目标的影响，从而做出的影响，从而做出对全局而言是最全局而言是最优的决策。的决策。动态规划就是符合划就是符合这一要求的一种最一要求的一种最优化方法。化方法。112.各个各个阶段的决策普通与段的决策普通与“时间有关有关动态规划方法与划方法与“时间关系很关系很亲密，随着密，随着时间过程的开展而决程的开展而决定各定各阶段的决策，从而段的决策，从而产生一个决策序列，生一个决策序列，这就是就是“动态的意的意思。思。但是，一些与但是，一些与时间无关的静无关的静态问题，只需在，只需在问题中人中人为引引入入“时间要素，也可将其看成是多要素，也可将其看成是多阶段的决策段的决策问题，用，用动态规划划方法去方法去处置。置。12学习目的：学习目的：1 1 准准确确、熟熟练练地地掌掌握握动动态态规规划划的的根根本本概概念念、特特别别是形状是形状 变变量量、决决策策变变量量、形形状状转转移移律律、目目的的函函数数、根本方程根本方程 等。等。2 动态规划的根本概念动态规划的根本概念为了便于求解和表示决策及了便于求解和表示决策及过程的开展程的开展顺序，而把所序，而把所给问题恰恰当地划分当地划分为假假设干个相互干个相互联络又有区又有区别的子的子问题，称之，称之为多段决多段决策策问题的的阶段。一个段。一个阶段，就是需求作出一个决策的子段，就是需求作出一个决策的子问题。 通常，通常，阶段是按决策段是按决策进展的展的时间或空或空间上先后上先后顺序划分的。序划分的。描画描画阶段的段的变量称量称为阶段段变量，常量，常记为k，k=1,2, ,n。如本例可按空如本例可按空间分分为4个个 阶段来求解，段来求解， k=1, 2, 3, 4。1阶段段stage14形状：每形状：每阶段初的客段初的客观条件。描画各条件。描画各阶段形状的段形状的变量称量称为形状形状变量，常用量，常用xk表示第表示第k阶段的形状。段的形状。2形状形状state例例1中，形状就是某中，形状就是某阶段的出段的出发位置。位置。x1x2x3x4x5按形状按形状变量的取量的取值是延是延续还是离散，可将是离散，可将动态规划划问题分分为离离 散型和延散型和延续型。型。15动态规划中的形状划中的形状应满足无后效性足无后效性马尔科夫性：科夫性： 所所谓无后效性指系无后效性指系统到达某个形状前的到达某个形状前的过程的决策将不影响程的决策将不影响到到该形状以后的决策。指系形状以后的决策。指系统从某个从某个阶段往后的开展，段往后的开展，仅由本由本阶段所段所处的形状及其往后的决策所决的形状及其往后的决策所决议，与系，与系统以前以前阅历的形状的形状和决策和决策历史无关。史无关。过程的程的过去去历史只能史只能经过当前的形状去影当前的形状去影响它未来的开展响它未来的开展例例1中，当某中，当某阶段的形状已段的形状已选定某个点定某个点时，从，从这个点以后的路个点以后的路线只与只与该点有关，不受点有关，不受该点以前的道路的影响，所以点以前的道路的影响，所以满足形状的足形状的无后效性。无后效性。16形状集合：形状形状集合：形状变量量 xk 的取的取值集合称集合称为形状集合，形状集合形状集合，形状集合实践上是关于形状的践上是关于形状的约束条件。束条件。通常用通常用Sk表示形状集合，表示形状集合，xkSk。第第1阶段段 S1=A；第第2阶段具有段具有3个状个状态B1、B2和和B3，故，故 S2=B1, B2, B3。x1x2x3x4x53决策决策decision当当过程程处于某一于某一阶段的某形状段的某形状时，可以做出不同的决，可以做出不同的决议，从而，从而确定下一确定下一阶段的形状，段的形状，这种决种决议称称为决策。决策。 描画决策的描画决策的变量称量称为决策决策变量，常用量，常用uk( xk )表示第表示第k阶段当状段当状态处于于xk时的决策的决策变量，它是形状量，它是形状变量的函数。量的函数。例例1中，从第中，从第2阶段的段的形状形状B1出出发，可以，可以选择下一下一阶段的段的C1、C2、C3。如我如我们决决议选择C1，那么可表示那么可表示为：u2( B1 ) = C1。B1C1C2C3x218决策集合：第决策集合：第k阶段当形状段当形状处于于xk时决策决策变量量uk( xk )的取的取值范范称称为决策集合，常用决策集合，常用Dk( xk ) 表示。表示。例例1中，从第中，从第2阶段的段的形状形状B1出出发，可以，可以选择下一下一阶段的段的C1、C2、C3。即即 D2( B1 ) = C1、C2、C3 ；B1C1C2C3决策集合决策集合实践上是决策的践上是决策的约束条件，束条件，uk( xk ) Dk( xk ) 。19小小结 阶段段 k、 形状形状 xk、 形状集合形状集合 Sk、 决策决策 uk( xk )、 决策集合决策集合 Dk( xk )。x1x2x3x4x5204形状形状转移律方程移律方程形状形状转移律：从移律：从xk的某一形状的某一形状值出出发，当决策，当决策变量量uk(xk) 的的取取值决决议后，下一后，下一阶段形状段形状变量量xk+1的取的取值也随之确定。描画也随之确定。描画从从 xk 转变为 xk+1 的的规律称律称为形状形状转移移规律方程。律方程。从第从第2阶段的形状段的形状B1出出发，如我，如我们决决定定选择C2也即确也即确定了下一定了下一阶段的状段的状态。B1C2B1C2上例中，上例中， u2( B1 ) = C2形状形状转移律移律为： xk+1 = uk( xk )普通来普通来说，下一，下一阶段形状段形状变量量xk+1的取的取值是上是上阶段的某一形状段的某一形状变量量xk和上和上阶段决策段决策变量量uk(xk)的函数，的函数，记为 xk+1=Tk( xk, uk(xk) )12nx1u1x2u2x3xnunxn+15战略略policy和子和子战略略subpolicy战略：由依次略：由依次进展的展的n个个阶段决策构成的决策序列就构成一个段决策构成的决策序列就构成一个 战略，用略，用 p1n u1(x1), u2(x2), , un(xn) 表示。表示。25375632455114633334C1C3D1AB1B3B2D2EC2本例中，如本例中，如p14 u1(A)=B1, u2(B1) = C2, u3(C2) = D1, u4(D1) = E 表示其中一个表示其中一个战略，其略，其总间隔隔为2+5+6+3=16。23战略集合：在略集合：在实践践问题中，由于在各个中，由于在各个阶段可供段可供选择的决策有的决策有许多个，因此，它多个，因此，它们的不同的不同组合就构成了合就构成了许多可供多可供选择的决策序的决策序列列战略，由它略，由它们组成的集合，称成的集合，称为战略集合，略集合，记作作 P1n。从从战略集合中，找出具有最略集合中，找出具有最优效果的效果的战略称略称为最最优战略。略。24子子战略：从略：从k阶段到第段到第n阶段，依次段，依次进展的展的阶段决策构成的段决策构成的决策序列称决策序列称为k部子部子战略，表示略，表示为 pkn = uk(xk), uk+1(xk+1), , un(xn) 如从第如从第3阶段的段的C2形状开形状开场的一个子策的一个子策略可表示：略可表示： p34=u3(C2) = D1, u4(D1) = E C2256目的函数目的函数用来衡量用来衡量战略或子略或子战略或决策的效果的某种数量目的，就称略或决策的效果的某种数量目的，就称为目的函数。目的函数。 它是定它是定义在全在全过程或各子程或各子过程或各程或各阶段上确段上确实定数量函数。定数量函数。对不同不同问题，目的函数可以是，目的函数可以是诸如如费用、本用、本钱、产值、利、利润、产量、耗量、量、耗量、间隔、隔、时间、成效，等等。、成效，等等。阶段段目的函数目的函数过程程目的函数目的函数26阶段目的函数：是指第段目的函数：是指第 k 阶段从形状段从形状 xk 出出发，采取决策，采取决策 uk 时产生的效益，用生的效益，用 vk(xk, uk) 表示。表示。例例1中，目的函数是中，目的函数是间隔。隔。如如 v2(B1, C2) 表示表示由由B1 出出发，采用决策，采用决策到到C2 点的两点点的两点间距距离，即离，即 v2( B1, C2) = 5。B1C227过程目的函数：是指从第程目的函数：是指从第 k 阶段的某形状段的某形状 xk 出出发，采取子策，采取子策略略 pkn 时所得到的效益，所得到的效益，记作作 Vkn( xk, uk, xk+1, uk+1, , xn )例例1中，如中，如V34( C2, u3(C2)=D1, D1, u4(D1)= E, E ) = 6+3 =9C228过程目的函数程目的函数Vkn通常是描画所通常是描画所实现的全的全过程或程或k后部子后部子过程效程效果果优劣劣的的数数量量目目的的，它它是是由由各各阶段段的的阶段段目目的的函函数数vk(xk,uk)累累积形形成的。成的。1可分性：适于用可分性：适于用动态规划求解的划求解的问题的的过程目的函数即目程目的函数即目标函数，必需具有关于函数，必需具有关于阶段目的的可分段目的的可分别方式，即方式，即对于后部子于后部子过程的目的函数可以表示程的目的函数可以表示为： Vkn( xk, uk, xk+1, uk+1, , xn ) = vk(xk, uk) vk+1(xk+1, uk+1) vn(xn, un) 式中，式中，表示某种运算，可以是加、减、乘、除、开方等。表示某种运算，可以是加、减、乘、除、开方等。29多多阶段决策段决策问题中，常中，常见的目的函数方式之一是取各的目的函数方式之一是取各阶段效段效应 之和的方式，即之和的方式，即: 有些有些问题，如系，如系统可靠性可靠性问题，其目的函数是取各，其目的函数是取各阶段效段效应的的 连乘乘积方式，如：方式，如： 总之，之，详细问题的目的函数表达方式需求的目的函数表达方式需求视详细问题而定。而定。Vkn = vixi, uii=kn (8.3a) Vkn = vixi, uii=kn (8.3b) 302可递推：过程目的函数可递推：过程目的函数Vkn要满足递推关系，即要满足递推关系，即可递推可递推Vkn( xk, uk, xk+1, uk+1, , xn )k xk, uk, V(k+1)n(xk+1, uk+1, , xn ) vk(xk,uk) vk+1(xk+1, uk+1) vn(xn,un) vk(xk,uk) V(k+1)n( xk+1, uk+1, , xn )31最最优目的函数：表示从第目的函数：表示从第 k 阶段形状段形状为 xk 时采用最采用最优战略略 pkn*到到过程程终止止时的最正确效益的最正确效益值。记为 fk( xk )。 fk( xk ) = Vkn( xk , pkn*) = opt Vkn( xk , pkn )例例1中，如中，如 f3( C2 ) = 3+4 = 7。其中其中 opt 可根据详细情况取可根据详细情况取max 或或min。C2动态规划的目的？划的目的？最最优解：最解：最优战略略 p1n最最优值：最：最优目的目的 f1(A)32多多阶段决策段决策问题的数学模型的数学模型 综上所述，适于运用上所述，适于运用动态规划方划方法求解的一法求解的一类多多阶段决策段决策问题的数学模型呈以下方式的数学模型呈以下方式: f1 = opt V1n( x1 , p1n ) 最最优目的函数目的函数 xk+1=Tk( xk, uk(xk) ) 形状形状转移方程移方程 ukDk 决策决策变量量 xkSk 形状形状变量量 k=1,2,n 阶段段变量量st.上述数学模型上述数学模型阐明了明了对于于给定的多定的多阶段决策段决策过程，求取一程，求取一个个(或多个或多个)最最优战略或最略或最优决策决策序序列列 u1, u2, , un ，使使之之既既满足左式足左式给出的全部出的全部约束条件，束条件，又使左式所示的目的函数又使左式所示的目的函数获得得极极值，并且同，并且同时指出指出执行行该最最优战略略时，过程形状演化序列程形状演化序列即是最即是最优道路。道路。小结小结: :概念概念 : :阶段变量阶段变量kk形状变量形状变量xkxk决策变量决策变量uk;uk;动态规划本质上是多阶段决策过程动态规划本质上是多阶段决策过程; ; 效益目的函数方式目的函数方式: :和、和、积无后效性无后效性可递推可递推方程方程 : :形状转移方程形状转移方程xk+1=Tk( xk, uk(xk) )目的目的 : : Vkn( xk, uk, xk+1, uk+1, , xn )fk( xk ) = Vkn( xk , pkn*) = opt Vkn( xk , pkn )Vkn( xk, uk, xk+1, uk+1, , xn )k xk, uk, V(k+1)n(xk+1, uk+1, , xn ) 34解多阶段决策过程问题，求出解多阶段决策过程问题，求出 最优战略，即最优决策序列 最优轨线，即执行最优战略时的形状序列 u1*, u2*, , un* x1*, x2*, , xn* 最优目的函数值最优目的函数值p1nP1nf1( x1 ) = V1n( x1 , p1n*) = opt V1n( x1 , p1n )1.划分划分阶段段2.正确正确选择形状形状变量量 3.确定决策确定决策变量及允量及允许决策集合决策集合4.确定形状确定形状转移方程移方程 5.确定确定阶段目的函段目的函数和最数和最优目的函目的函数，建立数，建立动态规划划根本方程根本方程划分划分阶段是运用段是运用动态规划求解多划求解多阶段决策段决策问题的第一的第一步，在确定多步，在确定多阶段特性后，按段特性后，按时间或空或空间先后先后顺序，序，将将过程程划划分分为假假设干干相相互互联络的的阶段段。对于于静静态问题要要人人为地地赋予予“时间概念，以便划分概念，以便划分阶段。段。建立动态规划模型的步骤建立动态规划模型的步骤 选择形状形状变量既要能确切描画量既要能确切描画过程演化又要程演化又要满足无后足无后效性，而且各效性，而且各阶段形状段形状变量的取量的取值可以确定。可以确定。通常通常选择所求解所求解问题的关的关键变量作量作为决策决策变量，同量，同时要要给出决策出决策变量的取量的取值范范围，即确定允，即确定允许决策集合。决策集合。根据根据k 阶段形状段形状变量和决策量和决策变量，写出量，写出k+1阶段形状段形状变量，形状量，形状转移方程移方程该当具有当具有递推关系。推关系。阶段目的函数是指第段目的函数是指第k 阶段的收益，最段的收益，最优目的函数是目的函数是指从第指从第k 阶段形状出段形状出发到第到第n 阶段末所段末所获得收益的最得收益的最优值，最后写出，最后写出动态规划根本方程。划根本方程。36 以上五步是建立动态规划数学模型的普通步骤。以上五步是建立动态规划数学模型的普通步骤。由于动态规划模型与线性规划模型不同，动态规划模由于动态规划模型与线性规划模型不同，动态规划模型没有一致的方式，建模时必需根据详细问题详细分型没有一致的方式，建模时必需根据详细问题详细分析，只需经过不断实际总结，才干较好掌握建模方法析，只需经过不断实际总结，才干较好掌握建模方法与技巧。与技巧。 下面我们看一个详细的例子下面我们看一个详细的例子 P156 例例2 机器负荷分配问题时间阶段问题机器负荷分配问题时间阶段问题37P156 例例2 机器机器负荷分配荷分配问题时间阶段段问题设有有某某种种机机器器设备，用用于于完完成成两两类任任务A和和B。假假设第第k年初完好年初完好机机器器的的数数量量为 xk ，假假设以以数数量量 uk 用用于于A，余余下下的的xkuk用于用于任任务B，那那么么该年年的的预期期收收入入为 g( uk ) + h( xkuk )。其中其中g( uk ) 8uk ， h( xkuk ) = 5xkuk。又又机机器器设备在在运运用用中中会会有有损坏坏，设机机器器用用于于任任务A时，一年后一年后能能继续运运用用的的完完好好机机器器数数占占年年初初投投入入量量的的70%；假假设用用于任于任务B时，一一年年后后能能继续运运用用的的完完好好机机器器数数占占年年初初投投入入量量的的90%。那么在。那么在下下 一一 年年 初初 能能 继 续 用用 于于 A、 B任任 务 的的 设 备 数数 为 xk+1=0.7uk+0.9(xkuk)。设第第1年年初初完完好好的的机机器器总数数为1000台台，问在在延延续5年年内内每年每年应如如何何分分配配用用于于A、B两两项任任务的的机机器器数数，使使5年年的的总收收益益为最大。最大。1.划分划分阶段段按年度来划分按年度来划分阶段，段，k=1,2,3,4,52.正确正确选择形状形状变量量形状形状变量量xk为第第k年度初年度初拥有的完好机器数量有的完好机器数量 3.确定决策确定决策变量及允量及允许决策集合决策集合决决策策变量量uk为第第k年年度度中中分分配配于于A任任务的的机机器器数数量量，那那么么xkuk为用于用于B任任务的机器数量。的机器数量。第第k阶段决策集合段决策集合Dk( xk ) = uk | 0ukxk 这里里xk和和uk均取延均取延续变量，它量，它们的非整数的非整数值可以可以这样理理解，如解，如xk=0.6，就表示一台机器在第，就表示一台机器在第k年度中正常任年度中正常任务时间只只占占6/10；uk=0.3，就表示一台机器在，就表示一台机器在该年度只需年度只需3/10的的时间能能正常用于正常用于A任任务。394.确定形状确定形状转移方程移方程形状形状转移方程移方程为 xk+1=0.7uk+0.9(xkuk) 5.确定确定阶段目的函数和最段目的函数和最优目的函数，建立目的函数，建立动态规划根本方程划根本方程目的函数目的函数为V1,5 = vixi, uii=15 = g( ui ) + h( xiui )i=15令最令最优目的函数目的函数fk( xk ) 表示由表示由资源量源量xk出出发，从第，从第k年开年开场到到第第5年年终了了时所所获得的最大得的最大预期收入。因此有：期收入。因此有： fk( xk ) = max Vk,5 = vixi, uii=k5 = 8ui + 5( xiui )i=k5 = 8ui +5(xiui)i=1540学习目的：学习目的：1 1 掌握最优化原理的内容掌握最优化原理的内容2 2 掌握逆序解法掌握逆序解法3 动态规划的根本思想与根本原理动态规划的根本思想与根本原理多多阶段决策段决策过程的最程的最优化普通有三种思化普通有三种思绪求解求解1.1.全枚全枚举法或法或穷举法：它的根本思想是列法：它的根本思想是列举出一切能出一切能够发生的生的方案和方案和结果，再果，再对它它们一一一一进展比展比较，求出最，求出最优方案。方案。 可可以以计算算：从从A A到到E E的的路路程程可可分分为4 4个个阶段段。第第一一段段走走法法有有3 3种，第二段走法有种，第二段走法有3 3种，第三段走法有种，第三段走法有2 2种，第四段走法种，第四段走法仅1 1种，种，共有共有332133211818条能条能够的道路，分的道路，分别算出各条道路的算出各条道路的间隔，隔，最后最后进展比展比较，可知最，可知最优道路是道路是AB3C2 D2EAB3C2 D2E，最短，最短间隔隔是是1111。 用用穷举法求最法求最优道路的道路的计算算 任任务量将会非常量将会非常庞大，而且大，而且 其中包含着其中包含着许多反复多反复计算。算。2.部分最部分最优途径法：某人从途径法：某人从k点出点出发，并不，并不顾及全及全线能否最短，能否最短，只是只是选择当前最短途径，当前最短途径，“逢近便走，逢近便走，错误地以地以为部分最部分最优会会致整体最致整体最优，在，在这种想法指点下，所取决策必是种想法指点下，所取决策必是AB1C2D2E，全全程程长度度是是14；显然然，这种种方方法法的的结果果常常是是错误的。的。43小小结： 全枚全枚举法法虽可找出最可找出最优方案，但不是个好算法，方案，但不是个好算法， 部分最部分最优法那么完全是个法那么完全是个错误方法，方法， 只需只需动态规划方法属划方法属较科学有效的算法科学有效的算法作作为一个全一个全过程的最程的最优战略具有略具有这样的性的性质：对于最于最优战略略过程中的恣意形状而言，无程中的恣意形状而言，无论其其过去的形状和决策如何，余下去的形状和决策如何，余下的的诸决策必构成一个最决策必构成一个最优子子战略。一个最略。一个最优战略的子略的子战略略总是最是最优的的3. 贝尔曼最优化原理动态规划方法贝尔曼最优化原理动态规划方法作作该原理的原理的详细解解释是，假是，假设某一全某一全过程最程最优战略略为： p1n*( x1 )= u1*(x1), , uk*(xk), uk+1*(xk+1), , un*(xn) 那么那么对上述上述战略中所略中所隐含的任一形状含的任一形状xk而言，第而言，第k子子过程程上上对应于于 xk 的最的最优战略必然包含在上述全略必然包含在上述全过程最程最优战略略p1n*中，中，即即为 pkn*( xk )= uk*(xk), uk+1*(xk+1), , un*(xn) 45C1D1AB3D2EC2反反证法法进展展证明明最最优性原理在最短道路中的运用性原理在最短道路中的运用 在最短道路中，假在最短道路中，假设找到了找到了AB3C2D2E是由是由A到到E的最的最短道路，那么短道路，那么B3C2D2E必是由必是由B3出出发到到E点的一切能点的一切能够选择的的不同道路中的最短道路。一个最不同道路中的最短道路。一个最优战略的子略的子战略略总是最是最优的的464.函数根本方程函数根本方程 基于这个原理，提出了一种逆序递推法；该法的关键在于给基于这个原理，提出了一种逆序递推法；该法的关键在于给出一种递推关系。普通把这种递推关系称为动态规划的函数根本出一种递推关系。普通把这种递推关系称为动态规划的函数根本方程。方程。对于求最小的加法的根本方程为如例对于求最小的加法的根本方程为如例1： fk( xk ) = min vk(xk, uk ) + fk+1(xk+1) fn+1( xn+1 ) = 0边境条件边境条件ukDk47用函数根本方程逆推求解是常用的方法：用函数根本方程逆推求解是常用的方法： 首先要有效地建立首先要有效地建立动态规划模型，划模型， 然后再然后再递推求解，推求解， 最后得出最后得出结论。正确地建立一个正确地建立一个动态规划模型，是划模型，是处理理问题的关的关键。485.标号法只适用于一号法只适用于一类最最优道路道路问题的特殊解法的特殊解法 标号法是借助网号法是借助网络图经过分段分段标号来求出最号来求出最优道路的一种道路的一种简便、直便、直观的方法。通常的方法。通常标号法采取号法采取“逆序求解的方法来逆序求解的方法来寻觅问题的最的最优解，即从最后解，即从最后阶段开段开场，逐次向，逐次向阶段数小的方向推算，段数小的方向推算，最最终求得全局最求得全局最优解。解。行进方向行进方向动态规划寻优途径动态规划寻优途径EA标号法的普通步号法的普通步骤： 1给最后一段最后一段标号，号，该段各形状即各始点到段各形状即各始点到终点的距点的距离用数字分离用数字分别标在各点上方的方格内，并用粗箭在各点上方的方格内，并用粗箭线衔接各点和接各点和终点。点。 2向前向前递推，推，给前一前一阶段的各个形状段的各个形状标号。每个形状上方号。每个形状上方方格内的数字表示方格内的数字表示该形状到形状到终点的最短点的最短间隔。将隔。将刚标号的点沿着号的点沿着最短最短间隔用粗箭隔用粗箭线衔接起来，表示出各接起来，表示出各刚标号的点到号的点到终点的最短点的最短道路。道路。 3逐次向前逐次向前递推，直到将第一推，直到将第一阶段的形状即起点段的形状即起点标号，起点方格内的数字就是起点到号，起点方格内的数字就是起点到终点的最短点的最短间隔，从起点开隔，从起点开场衔接接终点的粗箭点的粗箭线就是最短道路。就是最短道路。50第第1步步 k=5 f5( x5 ) = f5( E ) = 0 这是是边境条件境条件0Efk( xk ) 表示从第表示从第 k 阶段形状阶段形状 xk 到到 E 点的的最短间隔点的的最短间隔51第第2步步 k=4形状形状变量量 x4 可取两种形状可取两种形状 D1、D2。 由由D1到到终点点E只需一条道路，路只需一条道路，路长为3，即，即 f4( D1 ) = 3。 同理，同理， f4( D2 ) = 4 。3表示由表示由D1点至点至E点的最短路点的最短路长为3。40D1第第3步步 k=3形状形状变量量 x3 可取三个可取三个值：C1、C2、C3。由由C1到到终点点E有有2条道路，分条道路，分别为经过D1、D2到达到达E点由点由D1、D2到达到达E点的最短路点的最短路长在第一步已在第一步已计算得出，需加以比算得出，需加以比较，取其中最，取其中最短的。短的。道路道路1 v3(C1, D1)+ f4(D1) = 1+3=4道路道路2 v3(C1, D2)+ f4(D2) = 4+4=834那么由那么由C1到到终点点E的最短的最短间隔隔 f3( C1 ) = minv3(C1, D1)+ f4(D1), v3(C1, D2)+ f4(D2) = 44C1第第3步步 k=3由由C2到到终点点E有有2条道路，分条道路，分别为经过D1、D2到达到达E点由点由D1、D2到达到达E点的最短路点的最短路长在第一步已在第一步已计算得出，需加以比算得出，需加以比较，取其中最短的。，取其中最短的。道路道路1 v3(C2, D1)+ f4(D1) = 6+3=9道路道路2 v3(C2, D2)+ f4(D2) = 3+4=734那么由那么由C2到到终点点E的最短的最短间隔隔 f3( C2 ) = minv3(C2, D1)+ f4(D1), v3(C2, D2)+ f4(D2) = 7C274第第3步步 k=3由由C3到到终点点E有有2条道路，分条道路，分别为经过D1、D2到达到达E点由点由D1、D2到达到达E点的最短路点的最短路长在第一步已在第一步已计算得出，需加以比算得出，需加以比较，取其中最短的。，取其中最短的。道路道路1 v3(C3, D1)+ f4(D1) = 3+3=6道路道路2 v3(C3, D2)+ f4(D2) = 3+4=734那么由那么由C3到到终点点E的最短的最短间隔隔 f3( C3 ) = minv3(C3, D1)+ f4(D1), v3(C3, D2)+ f4(D2) = 6C3746第第4步步 k=2形状形状变量量 x2 可取三个可取三个值：B1、B2、B3。由由B1到到终点点E，可分，可分别经过C1、C2、C3到达到达E点由点由C1、C2、C3到到E点点 的最短的最短间隔在第二步已隔在第二步已计算出，需加以比算出，需加以比较，取其中最短的。，取其中最短的。道路道路1 v2(B1, C1)+ f3(C1) = 7+4=11道路道路2 v2(B1, C2)+ f3(C2) = 5+7=12道路道路3 v2(B1, C3)+ f3(C3) = 6+6=1234那么由那么由B1到到终点点E的最短的最短间隔隔 f2( B1 ) = minv2(B1, C1)+ f3(C1), v2(B1, C2)+ f3(C2) v2(B1, C3)+ f3(C3) = 114B17611第第4步步 k=2由由B2到到终点点E，可分，可分别经过C1、C2、C3到达到达E点由点由C1、C2、C3到到E点点 的最短的最短间隔在第二步已隔在第二步已计算出，需加以比算出，需加以比较，取其中最短的。，取其中最短的。道路道路1 v2(B2, C1)+ f3(C1) = 3+4=7道路道路2 v2(B2, C2)+ f3(C2) = 2+7=9道路道路3 v2(B2, C3)+ f3(C3) = 4+6=1034那么由那么由B2到到终点点E的最短的最短间隔隔 f2( B2 ) = minv2(B2, C1)+ f3(C1), v2(B2, C2)+ f3(C2) v2(B2, C3)+ f3(C3) = 74B276117第第4步步 k=2由由B3到到终点点E，可分，可分别经过C1、C2、C3到达到达E点由点由C1、C2、C3到到E点点 的最短的最短间隔在第二步已隔在第二步已计算出，需加以比算出，需加以比较，取其中最短的。，取其中最短的。道路道路1 v2(B3, C1)+ f3(C1) = 5+4=9道路道路2 v2(B3, C2)+ f3(C2) = 1+7=8道路道路3 v2(B3, C3)+ f3(C3) = 5+6=1134那么由那么由B3到到终点点E的最短的最短间隔隔 f2( B3 ) = minv2(B3, C1)+ f3(C1), v2(B3, C2)+ f3(C2) v2(B3, C3)+ f3(C3) = 84B3761178第第5步步 k=1形状形状变量量 x1 只取一个只取一个值：A。 由由A到到终点点E，可分，可分别经过B1、B2、B3到达到达E点由点由B1、B2、B3到到E点点 的最短的最短间隔在第三步已隔在第三步已计算出，需加以比算出，需加以比较，取其中最短的。，取其中最短的。经过B1点点 v1(A, B1)+ f2(B1) = 2+11=13经过B2点点 v1(A, B2)+ f2(B2) = 5+7=12经过B3点点 v1(A, B3)+ f2(B3) = 3+8=1134那么由那么由A到到终点点E的最短的最短间隔隔 f1( A ) = minv1(A, B1)+ f2(B1), v1(A, B2)+ f2(B2) v1(A, B3)+ f2(B3) = 114A7611781159从以下从以下图反推可得到最反推可得到最优道路。道路。344A76117811因此，由因此，由A到到终点点E的最的最优解解为： AB3C2D2E由点由点A到到终点点E的最的最优值为11。60小小结：在求解的各：在求解的各阶段，都利用了第段，都利用了第k阶和第和第k+1段的如下关段的如下关 系：系： fk( xk ) = min vk( xk, uk ) + fk+1( xk+1 ) (1) f5( x5 = E ) = 0 (2)上述上述递推关系推关系称称为动态规划的划的根本方程。根本方程。其中其中2式称式称为边境条件。境条件。344A7611781161动态规划方法的划方法的优点点1.减少计算量减少计算量 动态规划方法减少了计算量，而且随着阶段数的添加，计动态规划方法减少了计算量，而且随着阶段数的添加，计算量将大大减少。算量将大大减少。2.丰富了计算结果丰富了计算结果 在动态规划的解法中，得到的不仅仅是由在动态规划的解法中，得到的不仅仅是由A点出发到点出发到E点的点的最短道路及相应间隔，而且得到了从一切中间点出发到最短道路及相应间隔，而且得到了从一切中间点出发到E点的最点的最短道路及相应间隔。这对于许多实践问题来说是很有用的，有短道路及相应间隔。这对于许多实践问题来说是很有用的，有利于协助分析所得的结果。利于协助分析所得的结果。62动态规划方法的根本思想划方法的根本思想1. 将多阶段决策过程划分阶段，恰当地选择形状变量、决策变将多阶段决策过程划分阶段，恰当地选择形状变量、决策变 量，定义最优目的函数，从而把问题化成一簇同类型的子问量，定义最优目的函数，从而把问题化成一簇同类型的子问 题，然后逐个求解。题，然后逐个求解。2. 求解时从边境条件开场，逆过程方向行进，逐段递推寻优，求解时从边境条件开场，逆过程方向行进，逐段递推寻优， 在每一个子问题求解时，都要运用它前面已求出的子问题的在每一个子问题求解时，都要运用它前面已求出的子问题的 最优结果，最后一个子问题的最优解，就是整个问题的最优最优结果，最后一个子问题的最优解，就是整个问题的最优 解。解。63学习目的：学习目的：1 1 了解顺序解法了解顺序解法4 逆序解法和顺序解法逆序解法和顺序解法64动态规划的求解有两种根本方法划的求解有两种根本方法 逆序解法后向逆序解法后向动态规划方法划方法 如例如例1所运用的方法，所运用的方法，寻优的方向与多的方向与多阶段决策段决策过程的程的实践践行行进方向相反，从最后一段开方向相反，从最后一段开场计算逐段前推，求得全算逐段前推，求得全过程的程的最最优战略。略。 顺序解法前向序解法前向动态规划方法划方法 与逆序解法相反，与逆序解法相反，顺序解法的序解法的寻优的方向与的方向与过程的行程的行进方向方向一一样，计算算时从第一段开从第一段开场逐段向后逐段向后递推，推，计算后一段要用到算后一段要用到前一段的求前一段的求优结果，最后一段果，最后一段计算的算的结果就是全果就是全过程的最程的最优结果。果。65我我们再次用例再次用例1来来阐明明顺序解法。序解法。由于此由于此问题的始点的始点A与与终点点E都是固定的，都是固定的，计算由算由A点到点到E点点的最短道路与由的最短道路与由E点到点到A点的最短道路没有什么不同。点的最短道路没有什么不同。假假设设 fk( xk+1 ) 表示从起点表示从起点A到第到第k阶段末形状点段末形状点xk+1的最短的最短间隔隔 就可以由前向后逐就可以由前向后逐渐求出起点求出起点A到各到各阶段末形状点的最短距段末形状点的最短距离，最后求出起点离，最后求出起点A到到E点的最短点的最短间隔及道路。隔及道路。动态规划的目的：最优目的动态规划的目的：最优目的 f4( E )66第一步第一步 k=0 f0( x1 ) = f0( A ) = 0 这是是边境条件境条件0Afk( xk+1 ) 表示从起点表示从起点A到第到第k阶段阶段末形状点末形状点xk+1的最短间隔的最短间隔第二步第二步 k=12350按按 f1( x2 ) 的定的定义有有 f1( B1 ) = v( B1, A ) + f0( A ) = 2 f1( B2 ) = v( B2, A ) + f0( A ) = 5 f1( B3 ) = v( B3, A ) + f0( A ) = 3 B1B2B3第三步第三步 k=22350按按 f2( x3 ) 的定的定义有有 v( C1, B1 ) + f1( B1 ) = 7+2 = 9 f2( C1 ) = min v( C1, B2 ) + f1( B2 ) = 3+5 = 8 v( C1, B3 ) + f1( B3 ) = 5+3 = 8 u2( C1 ) = B2 或或B38C1形状形状转移方程：移方程： xk=Tk( xk+1, uk )第三步第三步 k=22350按按 f2( x3 ) 的定的定义有有 v( C2, B1 ) + f1( B1 ) = 5+2 = 7 f2( C2 ) = min v( C2, B2 ) + f1( B2 ) = 2+5 = 7 v( C2, B3 ) + f1( B3 ) = 1+3 = 4 u2( C2 ) = B384C2第三步第三步 k=22350按按 f2( x3 ) 的定的定义有有 v( C3, B1 ) + f1( B1 ) = 6+2 = 8 f2( C3 ) = min v( C3, B2 ) + f1( B2 ) = 4+5 = 9 v( C3, B3 ) + f1( B3 ) = 5+3 = 8 84u2( C3 ) = B1 或或B38C3第四步第四步 k=32350按按 f3( x4 ) 的定的定义有有 v( D1, C1 ) + f2( C1 ) = 1+8 = 9 f3( D1 ) = min v( D1, C2 ) + f2( C2 ) = 6+4 = 10 v( D1, C3 ) + f2( C3 ) = 3+8 = 11 84u3( D1 ) = C189D1第四步第四步 k=32350按按 f3( x4 ) 的定的定义有有 v( D2, C1 ) + f2( C1 ) = 4+8 = 12 f3( D2 ) = min v( D2, C2 ) + f2( C2 ) = 3+4 = 7 v( D2, C3 ) + f2( C3 ) = 3+8 = 11 84u3( D2 ) = C2897D2第五步第五步 k=42350按按 f4( x5 ) 的定的定义有有 v( E, D1 ) + f3( D1 ) = 3+9 = 12 f4( E ) = min v( E, D2 ) + f3( D2 ) = 4+7 = 11 84u4( E ) = D289711E74235084897即可得到最即可得到最优道路。道路。因此，由因此，由A到到终点点E的最的最优解解为： AB3C2D2E由点由点A到到终点点E的最的最优值为11。1175课堂练习l从A 地到D 地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示间隔，如下图。问应该选择什么道路，使总间隔最短？AB1B2C1C2C3D2433332111476解：整个解：整个计算算过程分三个程分三个阶段，从最后一个段，从最后一个阶段开段开场第一第一阶段段C D： C 有三条道路到有三条道路到终点点D 。显然有然有 f3 (C1 ) = 1 ； f3(C2 ) = 3 ； f3 (C3 ) = 4AB1B2C1C2C3D2433321114C1C2C377l第二第二阶段段B C： B 到到C 有六条道路。有六条道路。l d( B1,C1 ) + f3 (C1 ) 3+1l f2 ( B1 ) = min d( B1,C2 ) + f3 (C2 ) = min 3+3 l d( B1,C3 ) + f3 (C3 ) 1+4l 4l = min 6 = 4 l 5AB1B2C1C2C3D24333321114B1B278l d( B2,C1 ) + f3 (C1 ) 2+1l f2 ( B2 ) = min d( B2,C2 ) + f3 (C2 ) = min 3+3 l d( B2,C3 ) + f3 (C3 ) 1+4l 3l = min 6 = 3l 5AB1B2C1C2C3D24333321114B1B279l第三第三阶段段 A B ： A 到到B 有二条道路。有二条道路。lf1 (A) = min = min6,7=6AB1B2C1C2C3D24333321114Ad(A, B1 ) f2 ( B1 )d(A, B2 ) f2 ( B2 )(最短道路最短道路为AB1C1 D)80l练习 P156 例例2 机器机器负荷分配荷分配问题时间阶段段问题l设有某种机器有某种机器设备，用于完成两，用于完成两类任任务A和和B。假。假设第第k年初完年初完好好l机器的数量机器的数量为 xk ，假，假设以数量以数量 uk 用于用于A，余下的，余下的xkuk用用于于l任任务B，那么，那么该年的年的预期收入期收入为 g( uk ) + h( xkuk )。其中。其中lg( uk ) 8uk ， h( xkuk ) = 5xkuk。l又机器又机器设备在运用中会有在运用中会有损坏，坏，设机器用于任机器用于任务A时，一年后，一年后l能能继续运用的完好机器数占年初投入量的运用的完好机器数占年初投入量的70%；假；假设用于任用于任务Bl时，一年后能，一年后能继续运用的完好机器数占年初投入量的运用的完好机器数占年初投入量的90%。那么。那么在在l下一年初能下一年初能继续用于用于A、B任任务的的设备数数为 xk+1=0.7uk+0.9(xkluk)。l设第第1年初完好的机器年初完好的机器总数数为1000台，台，问在延在延续5年内每年年内每年应如如l何分配用于何分配用于A、B两两项任任务的机器数，使的机器数，使5年的年的总收益收益为最大。最大。81l构造构造动态规划模型如下：划模型如下：阶段段k：运：运转年份年份k = 1,2,6, 其中其中k=1表示第一年表示第一年初，初， 依次依次类推；推；k=6表示第表示第5年末即第年末即第6年初。年初。形状形状变量量xk：第：第k年初完好的机器数年初完好的机器数k=1,2, ,4，其中其中x6表表 示第示第5年末即第年末即第6年初的完好机器数。年初的完好机器数。决策决策变量量uk：第：第k年度中分配于年度中分配于A任任务的机器数量，那的机器数量，那么么xkuk为 用于用于B任任务的机器数量。的机器数量。形状形状转移方程：移方程：xk+1=0.7uk + 0.9( xkuk )决策允决策允许集合：集合：Dk( xk ) = uk | 0ukxk 阶段目的：段目的：vk( xk , uk ) = 8uk + 5( xkuk )终端条件：端条件：f6( x6 ) = 082递推方程：推方程：fk( xk ) = max vk( xk, uk ) + fk+1( xk+1 ) dkDk(xk) =max 8uk+5(xk - uk)+fk+10.7uk+0.9(xk-uk) 0dkxk这里里xk和和uk均取延均取延续变量，它量，它们的非整数的非整数值可以可以这样理理解，如解，如xk=0.6，就表示一台机器在第，就表示一台机器在第k年度中正常任年度中正常任务时间只只占占6/10；uk=0.3，就表示一台机器在，就表示一台机器在该年度只需年度只需3/10的的时间能能正常用于正常用于A任任务。83f5(x5) = max 8u5+5(x5u5) + f6( x6 ) 0u5x5u5*=x5= max 3u5+5x5 0u5x5= 8x5f4(x4) = max 8u4+5(x4u4) + f5( x5 ) 0u4x4=max 8u4+5(x4u4)+8x5 0u4x4形状形状转移方程：移方程：xk+1=0.7uk + 0.9( xkuk )=max 8u4+5(x4u4)+80.7u4+0.9( x4u4 ) 0u4x4=max 1.4u4+12.2x4 0u4x4u4*=x4=13.6x484f3(x3) = max 8u3+5(x3u3) + f4( x4 ) 0u3x3=max 8u3+5(x3u3)+13.6x4 0u3x3形状形状转移方程：移方程：xk+1=0.7uk + 0.9( xkuk )=max 8u3+5(x3u3)+13.60.7u3+0.9( x3u3 ) 0u3x3=max 0.28u3+17.22x3 0u3x3u3*=x3=17.5x385f2(x2) = max 8u2+5(x2u2) + f3( x3 ) 0u2x2=max 8u2+5(x2u2)+17.5x3 0u2x2形状形状转移方程：移方程：xk+1=0.7uk + 0.9( xkuk )=max 8u2+5(x2u2)+17.50.7u2+0.9( x2u2 ) 0u2x2=max 0.504u2+20.8x2 0u2x2u2*= 0=20.8x286f1(x1) = max 8u1+5(x1u1) + f2( x2 ) 0u1x1=max 8u1+5(x1u1)+20.8x2 0u1x1形状形状转移方程：移方程：xk+1=0.7uk + 0.9( xkuk )=max 8u1+5(x1u1)+20.80.7u1+0.9( x1u1 ) 0u1x1=max 0.05u1+23.7x1 0u1x1u1*= 0=23.7x187由此可以得到：由此可以得到：f1(x1)=23.7x1,u1*=0f2(x2)=20.8x2,u2*=0f3(x3)=17.5x3,u3*=x3f4(x4)=13.6x4,u4*=x4f5(x5)=8x5 u5*=x5用用x1=1000代入，得到五年最大代入，得到五年最大总收入收入为 f1(x1)=f1(1000)=2370088年年度度年初完好机器数年初完好机器数用于工作用于工作A的数的数量量用于工作用于工作B的数的数量量1x1 = 1000u1*=02x2=0.7u1 + 0.9( x1u1 )u2*=03x3=0.7u2 + 0.9( x2u2 )u3*=x34x4=0.7u3 + 0.9( x3u3 )u4*=x45x5=0.7u4 + 0.9( x4u4 )u5*=x5x1u1 =1000x2 = 900x2u2 =900x3 = 810u3= 810x3u3 =0x4 = 567u4= 567x4u4 =0x5 = 397u5= 397x5u5 =089l例例4 某一警卫部门共有某一警卫部门共有12支巡查队，担任支巡查队，担任4个关键部位个关键部位A、B、C、Dde警卫巡查。对每个部位可分别派出警卫巡查。对每个部位可分别派出24支支巡查队，并且由于派出巡查队队数不同，各部位预期在巡查队，并且由于派出巡查队队数不同，各部位预期在一段时间内能够呵斥的损失由差别，详细数字见表。问一段时间内能够呵斥的损失由差别，详细数字见表。问该警卫部门分别派多少支巡查队，使总的预期损失为最该警卫部门分别派多少支巡查队，使总的预期损失为最小。小。ABCD21838243431435223141031212590l解解 把把12支巡查队伍往支巡查队伍往4部位看成依次分部位看成依次分4个阶段用个阶段用k表示，表示，k=1,2,3,4)l(1)逆序解法逆序解法l每个阶段初拥有的可派遣的巡查队数是前面阶段决策的结果，用每个阶段初拥有的可派遣的巡查队数是前面阶段决策的结果，用形状变量形状变量 来表示。各阶段的决策变量就是对各部位派出的巡查队来表示。各阶段的决策变量就是对各部位派出的巡查队数，用数，用 表示表示 ，显然个阶段允许的决策集合为，显然个阶段允许的决策集合为l英每阶段初拥有可派遣的巡查队数等于上阶段初拥有的数量减去英每阶段初拥有可派遣的巡查队数等于上阶段初拥有的数量减去上阶段排出的数，故形状转移律为上阶段排出的数，故形状转移律为l假设用假设用 表示阶段表示阶段 派出的巡查队数为派出的巡查队数为 时，该阶段的部位的时，该阶段的部位的预期损失值，因此目的函数可写为预期损失值，因此目的函数可写为91l设用设用 表示表示 阶段形状为阶段形状为 ，以此出发采用最优子战略到过程终，以此出发采用最优子战略到过程终了时的预期损失值，因此有了时的预期损失值，因此有l先思索给先思索给D部位派巡查队，即部位派巡查队，即 ，上式可写为，上式可写为 l因问题中只需因问题中只需4个关键部门，故第个关键部门，故第5阶段初拥有的未派出的巡查队数队前阶段初拥有的未派出的巡查队数队前4个部位的预期损失不再起影响，故边境条件个部位的预期损失不再起影响，故边境条件 ，因此有，因此有l因因 ，又，又 的能够值为的能够值为 ，故由表，故由表1的数的数据可得表据可得表2的结果。的结果。92 表表2 2 3 4 2 34 _ _ 34 2 3 34 31 _ 31 3 4 34 31 25 25 4 5 34 31 25 25 4 6 34 31 25 25 493再结合思索对再结合思索对C、D两个部位派巡查队，即两个部位派巡查队，即 ，这是有，这是有因有因有 ，又，又 ，故可得表，故可得表3的结果的结果 表表3 2 3 4 4 24+34 58 2 5 24+31 22+34 55 2 6 24+25 22+31 21+34 49 2 7 24+25 22+25 21+31 47 3 8 24+25 22+25 31+25 46 494l下面思索对下面思索对B、C、D三个部位派巡查队，即三个部位派巡查队，即 ，这时有，这时有l同样有同样有 又又 ，故计算得表，故计算得表4。 表表4 2 3 4 8 38+49 35+55 31+58 87 2 9 38+47 35+49 31+55 84 3 10 38+46 35+47 31+49 80 495l最后思索对最后思索对A、B、C、D四个部位派巡查队，即四个部位派巡查队，即 时，有时，有l因因 有有 故计算得表故计算得表5 2 3 4 12 18+80 14+84 10+87 97 496l由表由表5知，最优战略是：知，最优战略是：A部位部位4支，支，B部位部位2支，支，C部位部位2支，支，D部部位位4支，总预期损失为支，总预期损失为97单位。单位。97动态规划动态规划l动态规划问题实例动态规划问题实例l动态规划的根本概念与原理动态规划的根本概念与原理l动态规划运用举例动态规划运用举例98例 Wyndor Glass Company Problem运用动态规划进展求解9912一、动态规划问题建模一、动态规划问题建模这个问题需求对两个相关活动(activity)确定其活动程度(level of activity)，因此我们可以将这两个活动看作动态规划中的阶段。决策变量 ：第 k 个活动的活动程度 level ofactivity 形状变量 ：可用于第k阶段消费的资源量右端项。即100形状转移方程：阶段目的函数 ：第 k 阶段确定 时所产生的利润即最优目的函数 ：第 k 阶段形状为 且采取最正确投资战略，从第 k 个活动以及以后的最大总利润。 逆序法根本递推方程： 101二、动态规划问题求解二、动态规划问题求解1k=2 时由于故有k=2 时决策表1022k=1 时由于初时形状确定且103k=2 时决策表104在可行区间 上105由于和都在x1=2时获得最大值36 2k=1 时决策表所以10636 2k=1 时决策表k=2 时决策表107背背 包包 问 题 普通的提法为：一游览者携带背包去登山。知他所能接受 的背包分量的极限为a (千克)，现有n种物品可供他选择装入背包。第i种物品的单位分量为 (千克)，其价值可以是表明本物品对登山者的重要性目的是携带数量 的函数 i=1，2，n.问游览者应如何选择携带物品的件数，以使总价值最大？此模型处理的是运输工具包括卫星的最优装载问题。其数学模型为：108设 为第 i 种物品装入的件数，那么背包问题可归结为如下 方式的整数规划模型：下面从一个例子来分析动态规划建模。例例 有一有一辆最大最大货运量运量为10 t 的卡的卡车，用以装，用以装载3种种货物，每物，每种种货物的物的单位分量及相位分量及相应单位价位价值如表如表7-4 所示。所示。应如何装载可使总价值最大？109货物物编号号i 1 2 3单位重量（位重量（t） 3 4 5单位价位价值 ci 4 5 6表 7- 4 设第 种货物装载的件数为 那么问题可表为：阶段段k: 将可装入物品按将可装入物品按1，2，3的的顺序排序，每段装入一序排序，每段装入一种物品，共划分种物品，共划分3个个阶段，即段，即k=1,2,3.110形状形状变量量 ：在第：在第k段开段开场时，背包中允，背包中允许装入前装入前k种种物品的物品的总分量。分量。决策决策变量量 ：装入第：装入第k种物品的件数。种物品的件数。形状形状转移方程：移方程：最最优目的函数目的函数 ：在背包中允：在背包中允许装入物品的装入物品的总分量不超分量不超过 kg，采取最，采取最优战略只装前略只装前k种物品种物品时的最大运用价的最大运用价值货物1货物2货物3111由此可得动态规划的顺序递推方程为：K=1 时货物1货物2货物3112K=1 时留意到：例如：时，其它计算结果见表7-5：货物1货物2货物31130 1 2 3 0 1 2 3 4 5 6 7 8 9 104040 40 40 41 40 41 4240 41 42 430004812000123表 7- 5114K=2 时其中例如：时，货物1货物2货物3115表 7- 50 1 2 3 0 1 2 3 4 5 6 7 8 9 104040 40 40 41 40 41 4240 41 42 430004812000123116其它计算结果见表7-6： 0 1 2 0 1 2 3 4 5 6 7 8 9 10500 504 510 5012 518 520 0513011表 7- 6117K=3 时货物1货物2货物3118 0 1 2 0 1 2 3 4 5 6 7 8 9 10500 504 510 5012 518 520 0513011表 7- 6119从再由形状转移方程表 7- 6货物1货物2货物3 0 1 2 0 1 2 3 4 5 6 7 8 9 10500 504 510 5012 518 520 0513011120再由形状转移方程表 7- 5最大装载价值为 0 1 2 3 0 1 2 3 4 5 6 7 8 9 104040 40 40 41 40 41 4240 41 42 430004812000123121总结：今后解背包问题应先从k=3入手：k=3时 下面应有重点地从k=2中求解三个最优函数值： 122K=2 时123所以从第一阶段应有重点地求以下四个数： K=1 时124由此逐一逆推代回上式：125由此逐一逆推代回上式：126由此逐一逆推代回上式：127最后最优战略：再由形状转移方程再由形状转移方程最大装载价值为 1287.9/P-239 用动态规划方法求解：解：我们用背包问题顺序解的思绪：人为的划分三个阶段：k=1,2,3阶段目的函数及其他分配情况如以下图：123129123动态规划的顺序递推方程为：130123131132123133134135136137最优决策为所对应的最优解为138例二维背包 有一辆最大货运量为13t、最大容量为10件的卡车，用以装载3种货物，每种货物的单位分量及相应单位价值如下表所示。应如何装载可使总价值最大？货物编号货物编号i i 1 1 2 2 3 3单位重量（单位重量（t t） 1 1 3 3 6 6单位价值单位价值 c ci i 4 4 5 5 8 8解：设装载第i种货物的件数为 i=1,2,3，那么问题可表述为139123关于件数的约束:关于分量的约束:根本方程式：140123141问题就是求：123142143144123145同理可求得 146147所以最优决策方案为 ：最优装载价值为：148例 货郎担问题货郎担问题也叫推销商问题traveling salesman problem,其普通提法为：有n个城市，用1，2，n表示，城i, j之间的间隔为 ，有一个货郎从城1出发到其他城市一次且仅一次，最后回到城市1，怎样选择行走道路使总路程最短？123645789101112452368775845348435623113345149一。动态规划解阶段变量k：按所经过的城市个数划分阶段k, k=1,2,n-1.形状变量 ：设第k 阶段到达城市i 时途中所经过的k个城市集合为S，那么其中 123645789101112452368775845348435623113345150例如： ，表示推销商从城1出发途径城市2,3,4到达城市5时，须先途经城市2,4到达城市3，再奔城市5。决策变量 ：第k 阶段到达城市i 的最短道路上邻接i 的前一个城市 。123645789101112452368775845348435623113345151阶段目的函数 : 设从城市1出发，第k-1阶段到到达城市j,那么城市j与下一阶段第k阶段的目的地城市i之间的间隔为 最优目的函数 ：从城市1出发，经过S中k个城市,到达城市i的最短间隔.123645789101112452368775845348435623113345152那么动态规划的顺序递推关系为:最后算出 ,即为全程的最短间隔,同时可得最优战略,即最优行走道路.例1 知 4个城市间间隔如表1，求从城市1出发，经其与城市一次且仅一次最优回到城市1的最短路与间隔。12345153 城城城城 市市 市市 1 12 23 34 41 12 23 34 40 08 85 56 66 60 08 85 57 79 90 05 59 97 78 80 0解：由边境条件知：154 城城城城 市市 市市 1 12 23 34 41 12 23 34 40 08 85 56 66 60 08 85 57 79 90 05 59 97 78 80 0当k=1时，从城市1出发，经过1个城市到达城市i的最短间隔为： 即从城市1出发，途经1个城市奔城2，应先到4，再到2。155 城城城城 市市 市市 1 12 23 34 41 12 23 34 40 08 85 56 66 60 08 85 57 79 90 05 59 97 78 80 0即从城市1出发，途经1个城市奔城3，应先到4，再到3。156 城城城城 市市 市市 1 12 23 34 41 12 23 34 40 08 85 56 66 60 08 85 57 79 90 05 59 97 78 80 0即从城市1出发，途经1个城市奔城4，应先到2，再到4。157 城城城城 市市 市市 1 12 23 34 41 12 23 34 40 08 85 56 66 60 08 85 57 79 90 05 59 97 78 80 0当k=2时，从城市1出发，途经2个城市到达城市i的最短间隔为即从城市1出发，途经2个城市3，4奔城2，应先到4，再到2。158即从城市1出发，途经2个城市2，4奔城3，应先到4，再到3。 城城城城 市市 市市 1 12 23 34 41 12 23 34 40 08 85 56 66 60 08 85 57 79 90 05 59 97 78 80 0159 城城城城 市市 市市 1 12 23 34 41 12 23 34 40 08 85 56 66 60 08 85 57 79 90 05 59 97 78 80 0即从城市1出发，途经2个城市2，3奔城4，应先到2，再到4。160当k=3时，从城市1出发，途经3个城市到达城市1的最短间隔货郎担的最短道路是1 2431。 城城城城 市市 市市 1 12 23 34 41 12 23 34 40 08 85 56 66 60 08 85 57 79 90 05 59 97 78 80 0逆推回去行走间隔为23。161 第七讲：设备更新问题企业中经常会遇到一台设备应该运用多少年更新最合算的问题。普通来说，一台设备在比较新时，年运转量大，经济收入高，缺点少，维修费用少，但随着运用年限的添加，年运转量减少因此收入减少，缺点变多，维修费用添加。假设更新可提 高年净收入，但是当年要支出一笔数额较大的购买费。设备更新的普通提法为：在知一台设备的效益函数 ，维修费用函数 及更新费用函数 条件下，要求在n年内的每年年初作出决策，是继续运用旧设备还是改换一台新的，使使n年总效益最大。 162 例11 某台新设备的年效益及年均维修费、更新净费用如表7-15所示。试确定今后5年内的更新战略，使总收益最大。表 7-15 单位：万元 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5163解：以年限划分阶段k：1，2，3，4，512345决策变量 : 第k年初保管运用(keep)第k年初更新(replacement)形状变量 : 第k年初，设备已运用过的年数，称役龄。形状转移方程： 164在第k年设备已运用过t年或役龄为t年，再运用1年时的效益。 在第k年设备已运用过t年或役龄为t年，再运用1年时的维修费用。在第k年卖掉一台役龄为t年的设备，买进一台新的设备的更新净费用。 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5165 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5即： “买一部新机器的费用“卖一部t年役龄的旧机器的收益。 阶段目的函数：166最优目的函数 ：第k年初，运用一台已用了 年的设备，到第5年末的最大效益，有按逆序建立递推式：下面用逆序法求解： 167K=5时：此时， 的一切能够取值为：1，2，3，4。下分别求最优指标函数值：12345168 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 169 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 170 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 171 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 172 1 2 3 4 3.5 3 2.5 2.3 1.75 2 0.5 1.53.52.521.5173 1 2 3 43.52.521.5K=5时最优值表174K=4时：此时， 的一切能够取值为：1，2，3。下分别求最优指标函数值：12345175 1 2 3 43.52.521.5K=5时最优值表 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 176 1 2 3 43.52.521.5K=5时最优值表 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 177 1 2 3 43.52.521.5K=5时最优值表 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 178 1 2 36.55.85.5K=4时最优值表179K=3时：此时， 的一切能够取值为：1，2。下分别求最优指标函数值：12345180 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 1 2 36.55.85.5K=4时最优值表181 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 1 2 36.55.85.5K=4时最优值表182 1 2 9.58.8K=3时最优值表183K=2时：此时， 只能取1。所以12345184 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 1 2 9.58.8K=3时最优值表185K=1时：此时， 只能取0。所以12345186 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 18712345形状转移方程： 上述计算递推回去，当 时，由形状转移方程： 知 查得 18812345形状转移方程： 有知 1 2 9.58.8K=3时最优值表查 知18912345形状转移方程： 查 知 1 2 36.55.85.5K=4时最优值表19012345形状转移方程： 查 1 2 3 43.52.521.5K=5时最优值表191故此题最优战略为 ，即第一年初购买的设备到第二、三、四、年初各更新一次，用到第5年末，其总效益为17万元。