运筹学研究生辅导-第二章动态规划ppt课件

1、第二章 动态规划 动态规划作为运筹学的一个重要分支是处理多动态规划作为运筹学的一个重要分支是处理多阶段决策过程最优化的一种非常有效的方法。阶段决策过程最优化的一种非常有效的方法。1951年，美国数学家贝尔曼年，美国数学家贝尔曼 R . Bellman 等人，根等人，根据一类多阶段决策问题的特点，把多阶段决策问题变据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联络的单阶段决策问题，然后分阶段换为一系列相互联络的单阶段决策问题，然后分阶段逐个加以处理。贝尔曼等人在研讨和处理了大量实践逐个加以处理。贝尔曼等人在研讨和处理了大量实践问题之后，提出理处理这类问题的问题之后，提出理处理这类问

2、题的所谓所谓“最优性最优性原理，通常称为原理，通常称为“贝尔曼最优化原理，从而创建贝尔曼最优化原理，从而创建理处理最优化问题的一种新的方法理处理最优化问题的一种新的方法 动态规划动态规划 Dynamic Programming 。2511214106104131112396581052C1C3D1AB1B3B2D2EC2 为了阐明动态规划的根本思想方法和特点，以以下图所示为例，讨论求最短路问题的方法。求从A到E的最短途径2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=02511214106104131112396581052C1C3D1A

3、B1B3B2D2EC2f4(D1)=5f5(E)=0505)E(f)ED(d)D(f51142511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5202)E(f)ED(d)D(f52242511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5112421141113DC8118min2953min)D(f)D,C()D(f)D,C(min)C(f最优决策2511214106104131112396581052C1C

4、3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8222422141223DC7711min2556min)D(f)D,C()D(f)D,C(min)C(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7232423141333DC121213min21058min)D(f)D,C()D(f)D,C(min)C(f最优决策2511214106104131112396581052C1C3D1A

5、B1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=81133312321131112CB20222120min1210714812min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=211233322322131222CB14161714min12471086min

6、)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=142333332323131332CB19231921min1211712813min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0

7、f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=2123232221211BA19201923min191145212min)B(f)B,A()B(f)B,A()B(f)B,A(min)A(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21形状 最优决策 形状 最优决策 形状 最优决策 形状 最优

8、决策 形状A A，B2 B22511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21形状 最优决策 形状 最优决策 形状 最优决策 形状 最优决策 形状A A，B2 B2 B2，C1 C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1

9、(A)=19f2(B2)=14f2(B1)=21形状 最优决策 形状 最优决策 形状 最优决策 形状 最优决策 形状A A，B2 B2 B2，C1 C1 C1，D1 D12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21形状 最优决策 形状 最优决策 形状 最优决策 形状 最优决策 形状A A，B2 B2 B2，C1 C1 C1，D1 D1 D1，E E从A到E的最短途径为19，道路为AB

10、 2C1 D1 E 1、阶段、阶段stage 为了便于求解和表示决策过程的开展顺序，为了便于求解和表示决策过程的开展顺序，而把所给问题恰当地划分为假设干个相互联络又有而把所给问题恰当地划分为假设干个相互联络又有区别的子问题，称之为多段决策问题的阶段。一个区别的子问题，称之为多段决策问题的阶段。一个阶段，就是需求作出一个决策的子问题，通常，阶阶段，就是需求作出一个决策的子问题，通常，阶段是按决策进展的时间顺序或空间特征上先后顺序段是按决策进展的时间顺序或空间特征上先后顺序划分的。用以描画阶段的变量叫作阶段变量，普通划分的。用以描画阶段的变量叫作阶段变量，普通以以k表示阶段变量阶段数等于多段决策过

11、程从开表示阶段变量阶段数等于多段决策过程从开场到终了所需作出决策的数目，例如上面的最短路场到终了所需作出决策的数目，例如上面的最短路问题就是一个四阶段决策过程。问题就是一个四阶段决策过程。动态规划的根本概念和根本原理动态规划的根本概念和根本原理2、形状、形状state 每个阶段开场时过程所处的自然情况或客观每个阶段开场时过程所处的自然情况或客观条件。反映形状变化的量叫做形状变量，它可以条件。反映形状变化的量叫做形状变量，它可以用一个数，一组数或一向量来描画，用一个数，一组数或一向量来描画， 。形状变量。形状变量必需包含在给定的阶段上确定全部允许决策所需必需包含在给定的阶段上确定全部允许决策所需

12、求的信息。它应能描画过程的特征并具有求的信息。它应能描画过程的特征并具有“无后无后效性，即当前阶段形状给定时，这个阶段以后效性，即当前阶段形状给定时，这个阶段以后过程的演化与该阶段以前各阶段的形状无关。用过程的演化与该阶段以前各阶段的形状无关。用sk表示形状变量表示形状变量 state variable。 普通形状变量的取值有一定的范围或允许集普通形状变量的取值有一定的范围或允许集合，称为能够形状集合，称为能够形状集set of admissible set of admissible statesstates 。能够形状集实践上是关于形状的约。能够形状集实践上是关于形状的约束条件。通常能够形

13、状集用相应阶段形状束条件。通常能够形状集用相应阶段形状sksk的大的大写字母写字母SkSk表示，能够形状集可以是一离散取值的表示，能够形状集可以是一离散取值的集合，也可以为一延续的取值区间，视详细问题集合，也可以为一延续的取值区间，视详细问题而定例如上面的最短路问题中，第一阶段形状而定例如上面的最短路问题中，第一阶段形状为为A A，形状变量，形状变量s1s1的形状集合的形状集合S1=AS1=A；第二阶段；第二阶段那么有三个形状：那么有三个形状：B1 ,B2 ,B3 ,B1 ,B2 ,B3 ,形状变量形状变量s2s2的形的形状集合状集合S2=B1 ,B2 ,B3 .S2=B1 ,B2 ,B3 .

14、3、决策、决策decision 当一个阶段的形状确定后，可以作出不同的决议当一个阶段的形状确定后，可以作出不同的决议或选择，从而演化到下一阶段的某个形状，这种决议或选择，从而演化到下一阶段的某个形状，这种决议或选择称为决策。或选择称为决策。 用以描画决策变化的量称之决策变量用以描画决策变化的量称之决策变量decision variable 。和形状变量一样，决策变量可以用一个。和形状变量一样，决策变量可以用一个数，一组数或一向量来描画，由于各阶段的决策取决数，一组数或一向量来描画，由于各阶段的决策取决于形状变量于形状变量sk，所以用，所以用 uk(sk)，表示阶段，表示阶段k的形状为的形状为s

15、k时的决策变量。时的决策变量。 决策变量的取值往往也有一定的允许范围，称之决策变量的取值往往也有一定的允许范围，称之允许决策集合允许决策集合set of admissible decision。决。决策变量策变量uk(sk)的允许决策集用的允许决策集用Uk(sk)表示表示, 允许决策允许决策集合实践是决策的约束条件。集合实践是决策的约束条件。 4、战略、战略policy 一组有序的决策序列构成一个战略，从第一组有序的决策序列构成一个战略，从第k阶阶段至第段至第n阶段的一个战略称为阶段的一个战略称为k部子战略记为部子战略记为 pk,n (sk)=uk，uk+1，un，当，当k=1时的时的k部部子

16、战略称为全过程战略，简称战略，记为子战略称为全过程战略，简称战略，记为p1,n (s1) 。 在实践问题中，由于在各个阶段可供选择的在实践问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许决策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列多可供选择的决策序列(战略战略)，由它们组成的集合，由它们组成的集合，称之允许战略集合，记作称之允许战略集合，记作P1,n ，从允许战略集中，从允许战略集中，找出具有最优效果的战略称为最优战略。找出具有最优效果的战略称为最优战略。5、形状转移方程、形状转移方程equation of state transition 反映

17、前后阶段形状之间关系的方程称为形反映前后阶段形状之间关系的方程称为形状转移方程。在确定型多阶段决策过程中，状转移方程。在确定型多阶段决策过程中，一旦某阶段的形状和决策为知，下一阶段的一旦某阶段的形状和决策为知，下一阶段的 形状便完全确定，用形状转移方程反映这种形状便完全确定，用形状转移方程反映这种形状间的演化规律，记作：形状间的演化规律，记作：)(,(1kkkkksusTs 有些问题的形状转移方程不一定存在数学有些问题的形状转移方程不一定存在数学表达式，但是它们的形状转移，还是有一定规表达式，但是它们的形状转移，还是有一定规律可循的。律可循的。6、阶段目的值、阶段目的值objective va

18、lue in a stage 阶段目的值是第阶段目的值是第k阶段的形状为阶段的形状为sk和采取决策和采取决策uk时的效益，通常表示为时的效益，通常表示为 dksk，uk。 对不同问题，阶段目的值可以是诸如费用、对不同问题，阶段目的值可以是诸如费用、本钱、产值、利润、产量、耗量、间隔、时间，本钱、产值、利润、产量、耗量、间隔、时间，等等。例如上面的最短路问题中，假设第二阶段等等。例如上面的最短路问题中，假设第二阶段地形状为地形状为B2,采取决策是由采取决策是由B2到达到达C1,那么阶段目那么阶段目的值为的值为6。7、目的函数、目的函数objective function 衡量在选定某战略时，其优

19、劣的数量目的。衡量在选定某战略时，其优劣的数量目的。 定义在整个过程定义在整个过程1到到n阶段上的目的函数阶段上的目的函数记为：记为：V1,ns1，u1，s2，sn，un， 定义在后部子过程定义在后部子过程k到到n阶段上的目的函阶段上的目的函数记为：数记为： Vk,nsk，uk，sn，un。 Vk,nsk，uk，sn，un 表示第表示第k阶段阶段处于处于sk形状且所作决策为形状且所作决策为uk, uk+1, , un时的决时的决策效果。策效果。 由此可见，由此可见， Vk,nsk，uk，sn，un不仅跟当前形状不仅跟当前形状sk有关，还跟该子过程战略有关，还跟该子过程战略pk,n(sk)有关，

20、因此它是有关，因此它是sk和和pk,n(sk)的函数，的函数，因此它可简记为：因此它可简记为：Vk,nsk， pk,n 目的函数目的函数Vk,nVk,nsksk， pk,n pk,n 通常通常是描画所实现的全过程或是描画所实现的全过程或k k后部子过程效后部子过程效果优劣的数量目的，它是由各阶段的阶段果优劣的数量目的，它是由各阶段的阶段目的函数目的函数dkdksksk，ukuk累积构成的，适于累积构成的，适于用动态规划求解的问题的目的函数，必需用动态规划求解的问题的目的函数，必需具有关于阶段目的的可分别方式对于后具有关于阶段目的的可分别方式对于后部子过程的目的函数可以表示为：部子过程的目的函数

21、可以表示为： ,11111( ,)(,)(,)( ,)k nk nkkkknnkkkkkknnnVVs u sus ud sudsud s u式中，式中，表示某种运算，可以是加、乘等。表示某种运算，可以是加、乘等。 总之，详细问题的目的函数表达方式需求视总之，详细问题的目的函数表达方式需求视详细问题而定。详细问题而定。.(,)nk niiiikVdsu,(,)nk niiiikVdsu多阶段决策问题中，常见的目的函数方式之一多阶段决策问题中，常见的目的函数方式之一是取各阶段效应之和的方式，即是取各阶段效应之和的方式，即:有些问题，如系统可靠性问题，其目的函数是有些问题，如系统可靠性问题，其目的

22、函数是取各阶段效应的连乘积方式，如：取各阶段效应的连乘积方式，如：8、最优目的函数、最优目的函数optimal value function 目的函数的最优值称为最优目的函数，记目的函数的最优值称为最优目的函数，记为为fk(sk)，它表示从第，它表示从第k阶段形状阶段形状 sk 出发，采出发，采用最优战略到终止形状时的后部子过程目的函用最优战略到终止形状时的后部子过程目的函数值，即数值，即式中式中opt即即optimization，根据详细问题可取，根据详细问题可取max或或min。与它相应的子战略称为在。与它相应的子战略称为在sk形状形状下的最优子战略，记为下的最优子战略，记为pk*(sk)

23、 ；而构成该子战；而构成该子战略的各段决策称为该过程上的最优决策，记为略的各段决策称为该过程上的最优决策，记为 ,()( )( ,( ),1,2,k nk nkkkk nkk nkpPsf soptVs pskn)(,),(),(11nnkkkksususu即即 )(,(kkkkspsR,11( ) ( ),(), , ( ),1,2, ,k nkkkkknnpsu s usu skn,1,1,2,k nkknpuuukn简记为简记为特别当特别当k=1时，时，f1(s1)就是问题的最优值，而就是问题的最优值，而p1*就是最优战略。例如上面的最短路问题就是最优战略。例如上面的最短路问题中，有独一

24、最优值中，有独一最优值f1(s1)=18，而，而1211, pB C D E就是其最优战略。就是其最优战略。 多阶段决策问题的数学模型多阶段决策问题的数学模型 综上所述，适于运用动态规划方法求综上所述，适于运用动态规划方法求解的一类多阶段决策问题，亦即具有无后效性的解的一类多阶段决策问题，亦即具有无后效性的多阶段决策问题的数学模型呈以下方式多阶段决策问题的数学模型呈以下方式: :1,1,1111,11,1()1()(,()(,). .1,2,nnnnpPskkkkkkkkfsoptVspssTsusSs tuUkn 最优化原理最优化原理 贝尔曼最优化原理贝尔曼最优化原理 作为一个全过程的最优战

25、略具有这样的性质：作为一个全过程的最优战略具有这样的性质：对于最优战略过程中的恣意形状而言，无论其对于最优战略过程中的恣意形状而言，无论其过去的形状和决策如何，余下的诸决策必构成过去的形状和决策如何，余下的诸决策必构成一个最优子战略。该原理的详细解释是，假设一个最优子战略。该原理的详细解释是，假设某一全过程最优战略为：某一全过程最优战略为：1,11122( )( ),( ),( ),( )nkknnpsu su su su s 那么对上述战略中所隐含的任一形状而言，那么对上述战略中所隐含的任一形状而言， 第第k k子过程上对应于该形状的最优战略必然子过程上对应于该形状的最优战略必然 包含在上述

26、全过程最优战略包含在上述全过程最优战略p1p1* *中，即为中，即为,11()(),(),()k nkkkkknnpsususus 动态规划的根本方程动态规划的根本方程 在上面最短路问题的求解过程中，在求解的在上面最短路问题的求解过程中，在求解的各阶段利用了第各阶段利用了第k阶段和第阶段和第k+1阶段的如下递推阶段的如下递推关系：关系：11( )55( )min ( , ( )(),4,3,2,1( ) 0kkkkkkkkkkku U sf sd s u sfskf s(,() )kkkkdsus其中，其中，表示从形状表示从形状sk到由决策到由决策uk(sk)所决议的形状所决议的形状sk+1之

27、间的间隔。之间的间隔。 普通地，对于普通地，对于n n个阶段的决策过程，假设只个阶段的决策过程，假设只思索目的函数是思索目的函数是“和与和与“积的方式，第积的方式，第k k阶段阶段和第和第k+1k+1阶段间的递推公式可表示如下：阶段间的递推公式可表示如下： (1) (1)当目的函数为以下当目的函数为以下“和的方式时，其相和的方式时，其相应的根本方程为应的根本方程为1111( )( ,( )(),1,2,1()0kkkkkkkkkkuUnnf sopt d s u sfskn nfs0)(55sf是边境条件。是边境条件。 (2) 当过程目的函数为以下当过程目的函数为以下“积的方式时积的方式时,其

28、其相应的根本方程为相应的根本方程为1111( ) ( ,( )(),1,2,1() 1kkkkkkkkkku Unnf sopt d s u sfskn nfs 普通来说普通来说,要用函数根本方程逆推求解要用函数根本方程逆推求解,首先要有效地建立动态规划模型首先要有效地建立动态规划模型,然后再递推然后再递推求解求解,最后得出结论最后得出结论.然而然而,要把一个实践问题要把一个实践问题用动态规划方法来求解用动态规划方法来求解,还必需首先根据问题还必需首先根据问题的要求。把它构呵斥动态规划模型的要求。把它构呵斥动态规划模型,这是非常这是非常重要的一步。正确地建立一个动态规划模型重要的一步。正确地建

29、立一个动态规划模型,往往问题也就处理了一大半往往问题也就处理了一大半,而一个正确的动而一个正确的动态规划模型态规划模型,应该满足哪些条件呢应该满足哪些条件呢?动态规划求解的普通步骤： - 确定过程的分段，构造形状变量； - 设置决策变量，写出形状转移； - 列出阶段目的和目的函数； - 写出根本方程，由此逐段递推求解。机器负荷问题例1 有某种机床,可以在高低两种不同的负荷下进展消费,在高负荷下消费时,产品的年产量为g,与年初投入消费的机床数量u1的关系为g=g(u1)=8u1,这时,年终机床完好台数将为au1,(a为机床完好率，0a1,设a=0.7).在低负荷下消费时,产品的年产量为h,和投入

30、消费的机床数量u2的关系为h=h(u2)=5u2,相应的机床完好率为b(0b1,设b=0,9),普通情况下a0所以 d2(x2)=d2|13-x2d217-x2由此 f2(x2)=5(13-x2)-13x2+377 =-18x2+442, d2*=13-x2生生 产产 库库 存存 问问 题题对于k=1f1(x1)=minc1d1+f2(x2) d1D1(x1) =min11d1+442-18x2 d1D1(x1) =min11d1+442-18(x1-r1+d1) d1D1(x1) =min11d1+442-18(x1-0+d1) d1D1(x1) =min-7d1-18x1+442 d1D1

31、(x1) D1(x1)=d1|d1D1(x1)=d1|d10,r20,r2x1-r1+d1x1-r1+d1HH =d1|d1 =d1|d10,r2+r1-x10,r2+r1-x1d1d1H+r1-x1H+r1-x1 =d1|d1 =d1|d10,8-x10,8-x1d1d19-x19-x1生生 产产 库库 存存 问问 题题根据题意 x1=2所以 D1(x1)=d1| 6d17由此 d1=7f1(x1)=-7d1-18x1+442 =-77182442 =357将以上结果总结成下表：k 1 2 3 4 5 6 7 ck 11 18 13 17 20 10 15 rk 0 8 5 3 2 7 4

32、xk 2 9 5 9 9 7 4 dk 7 13-x2=4 14-x3=9 12-x4=3 9-x5=0 11-x6=4 0 生生 产产 库库 存存 问问 题题三、设备更新问题例4 某运输公司购进一批卡车投入运营，公司每年初需对卡车作出更新或继续运用的决议。假设第k年中，rk(tk)表示车龄为tk的车运用一年的收入，uk(tk)表示车龄为tk的车运用一年的维修费用，ck(tk)表示车龄为tk的车更新成新车的费用。现公司需制定一个10年方案，以决议如何安排使10年的总收入最大。12S1=？x1x2 10 x10s10v1v2v10s2问题：形状和决策怎样设置？ 决策是更新与否，可用0-1变量表示

33、；形状可设为车龄。阶段k形状sk决策xk= 1,10表示第k年的决策过程；= tk表示第k年的车龄；年不更新，第年更新第kk0 1, 形状转移tk+1= tk +1(1-xk)阶段目的vk目的函数vkn = rktk - uktk - ck(tk)(1-xk)(1-xk)xk；10kiiv,110,0,111kffvMaxfkkxkk1 ,M基本方程例例9 消费消费库存问题库存问题 某工厂要对一种产品制定今后四个时期的某工厂要对一种产品制定今后四个时期的消费方案，据估计在今后四个时期内，市场对该消费方案，据估计在今后四个时期内，市场对该产品的需求量分别为产品的需求量分别为2，3，2，4单位，假

34、设每单位，假设每批产品固定本钱为批产品固定本钱为3千元，假设不消费为千元，假设不消费为0，每，每单位产品本钱为单位产品本钱为1千元，每个时期最大消费才干千元，每个时期最大消费才干不超越不超越6个单位，每期期末未出卖产品，每单位个单位，每期期末未出卖产品，每单位需付存贮费需付存贮费0.5千元，假定第千元，假定第1期初和第期初和第4期末库期末库存量均为存量均为0，问该厂如何安排消费与库存，可在，问该厂如何安排消费与库存，可在满足市场需求的前提下总本钱最小。满足市场需求的前提下总本钱最小。解解: 以每个时期作为一个阶段，该问题分为以每个时期作为一个阶段，该问题分为4个个阶段，阶段，k=1，2，3，4

35、；决策变量决策变量xk表示第表示第k阶段消费的产品数；阶段消费的产品数；形状变量形状变量sk表示第表示第k阶段初的库存量；阶段初的库存量；kkjjsd 4kkjjsd 4kkjjsd 4以以dk表示第表示第k阶段的需求，那么形状转移方程：阶段的需求，那么形状转移方程：sk+1=sk+xkdk；k=4，3，2，1由于期初及期末库存为由于期初及期末库存为0，所以，所以s1=0，s5=0；允许决策集合允许决策集合Dksk确实定：当确实定：当skdk时，时，xk可以为可以为0，当，当skdk时，至少应消费时，至少应消费dksk，故，故xk的下限为的下限为max0，dksk每期最大消费才干为每期最大消费

36、才干为6，xk最大不超越最大不超越6，由于期末库存为，由于期末库存为0，xk还应小还应小于本期至于本期至4期需求之和减去本期的库存量，期需求之和减去本期的库存量，所以所以xk的上限为的上限为min ，6，故有：，故有：Dksk=xk| max0，dkskxkmin，66 , 5 , 4 , 3 , 2 , 1 5 . 030 5 . 0),(kkkkkkkkxsxxsxsr0)(1 , 2 , 3 , 4 )(),(min)(5511)(sfksfxsrsfkkkkksDxkkkkk阶段目的函数阶段目的函数rksk，xk表示第表示第k期的消费费用期的消费费用与存贮费用之和：与存贮费用之和：最优

37、目的函数最优目的函数fksk表示第表示第k期库存为期库存为sk到第到第4期末的消费与存贮最低费用，动态规划根本方程为：期末的消费与存贮最低费用，动态规划根本方程为：例例10 库存库存销售问题销售问题设某公司方案在设某公司方案在1至至4月份从事某种商品运营。月份从事某种商品运营。知仓库最多可存储知仓库最多可存储600件这种商品，知件这种商品，知1月初存货月初存货200件，根据预测知件，根据预测知1至至4月份各月的单位购货本钱月份各月的单位购货本钱及销售价钱如表及销售价钱如表6.13所示，每月只能销售本月初所示，每月只能销售本月初的库存，当月进货供以后各月销售，问如何安排的库存，当月进货供以后各月

38、销售，问如何安排进货量和销售量，使该公司四个月获得利润最大进货量和销售量，使该公司四个月获得利润最大假设四月底库存为零。假设四月底库存为零。表表6.13 单位购货本钱及销售价钱单位购货本钱及销售价钱月份月份购货成本购货成本C销售价格销售价格P12344038404245423944解解: 按月份划分阶段，按月份划分阶段，k=1，2，3，4；形状变量形状变量sk表示第表示第k月初的库存量，月初的库存量，s1=200，s5=0；决策变量：决策变量： xk表示第表示第k月售出的货物数量，月售出的货物数量，yk表表示第示第k月购进的货物数量；月购进的货物数量；形状转移方程：形状转移方程：sk+1=sk

39、+yk-xk；允许决策集合：允许决策集合：0 xksk，0yk600-sk-xk；阶段目的函数为：阶段目的函数为：pkxkckyk表示表示k月份的利润，月份的利润，其中其中pk为第为第k月份的单位销售价钱，月份的单位销售价钱，ck为第为第k月份的月份的单位购货本钱；单位购货本钱；最优目的函数最优目的函数fksk表示第表示第k月初库存为月初库存为sk时从时从第第k月至第月至第4月末的最大利润，那么动态规划根本方月末的最大利润，那么动态规划根本方程为：程为：0)(1 , 2 , 3 , 4 )(max)(5511)(60000sfksfycxpsfkkkkkkxsysxkkkkkkk444)(60

40、0004444)4244(max)(44444syxsfxsysx)4544(max )(444039max )(4039max)(333)(6000033333)(600004433)(6000033333333333333333yxsxysyxsfyxsfxsysxxsysxxsysxk=4时，时，x4*=s4y4*=0k=3时，时，为求出使为求出使44s35x3+4y3最大的最大的x3，y3，须求解，须求解线性规划问题：线性规划问题：0,600 4544 max3333333333yxsyxsxyxsz只需两个变量只需两个变量x3，y3，可用图解法也可用单纯，可用图解法也可用单纯形法求解

41、，获得最优解，形法求解，获得最优解，x3*=0，y3*=600s3，f3s3=40s3+2400例例 某部门欲采购一批原料，原料价钱在五周内能够某部门欲采购一批原料，原料价钱在五周内能够有所变动，已预测得该种原料今后五周内取不同单价有所变动，已预测得该种原料今后五周内取不同单价的概率如下表所示。试确定该部门在五周内购进这批的概率如下表所示。试确定该部门在五周内购进这批原料的最优战略，使采购价钱的期望值最小。原料的最优战略，使采购价钱的期望值最小。原料价格（元）原料价格（元）概率概率5006007000.30.30.4解解 这里价钱是一个随机变量，是按某种知的概率这里价钱是一个随机变量，是按某种

42、知的概率分布取值的。用动态规划方法处置，按采购期限分布取值的。用动态规划方法处置，按采购期限5周周分分5个阶段，将每周的价钱看作该阶段的形状，设个阶段，将每周的价钱看作该阶段的形状，设sk为形状变量，表示第为形状变量，表示第k周的实践价钱周的实践价钱xk为决策变量，当为决策变量，当xk=1，表示第，表示第k周决议采购；周决议采购；当当xk=0，表示第，表示第k周决议等待。周决议等待。SkE表示第表示第k周决议等待，而在以后采用最优决策周决议等待，而在以后采用最优决策时采购价钱的期望值。时采购价钱的期望值。fk(sk)表示第表示第k周实践价钱为周实践价钱为sk时，从第时，从第k周至周至第五周采用最优决策所得的最小期望值。因此可第五周采用最优决策所得