运筹与优化-动态规划课件.ppt

1、最短路径问题最短路径问题资源分配问题资源分配问题背包问题背包问题机器负荷分配问题机器负荷分配问题l动态规划是一种研究多阶段决策问题的理论和动态规划是一种研究多阶段决策问题的理论和 方方 法。动态规划又称为多阶段规划法。动态规划又称为多阶段规划.l多阶段决策问题多阶段决策问题:决策过程是一种在多个相互联决策过程是一种在多个相互联 系的阶段分别作出决策以形成序列决策的过程，系的阶段分别作出决策以形成序列决策的过程，而这些决策都是根据总体最优化这一共同目标而这些决策都是根据总体最优化这一共同目标 来选取的。来选取的。要点：阶段，状态，决策，状态转移方程，要点：阶段，状态，决策，状态转移方程，k-后部

2、子过程。后部子过程。状态状态 决策决策 状态状态 决策决策 状态状态 状态状态 决策决策 状态状态 阶段阶段1阶段阶段2阶段阶段n2511214106104131112396581052C1C3D1AB1B3B2D2EC2例例1 最短路径问题最短路径问题:求从求从A到到E的最短路径的最短路径.如果用枚举法，则从如果用枚举法，则从A到到E共有共有332 1=18条不同的路条不同的路径，逐个计算每条路径的长度，总共需作径，逐个计算每条路径的长度，总共需作418=72次加法次加法计算；对计算；对18条路径的长度做两两比较，找出其中最短的一条路径的长度做两两比较，找出其中最短的一条，总共要条，总共要

3、进行进行181=17次比较次比较.最短路径：最短路径：AB2C1D1E，最短距离，最短距离19。1.阶段与阶段变量阶段与阶段变量 把所给问题的过程把所给问题的过程,恰当地分为若干个相互联系恰当地分为若干个相互联系的阶段的阶段,以便能按一定的次序去求解以便能按一定的次序去求解.描述阶段的变量描述阶段的变量称为阶段变量称为阶段变量,用用k表示表示.(k=1,2,n)2.状态与状态变量状态与状态变量 状态是系统在变化过程中某个阶段的初始形态表状态是系统在变化过程中某个阶段的初始形态表征征.描述状态的变量称为状态变量描述状态的变量称为状态变量,用用sk表示第表示第k阶段的阶段的初始状态初始状态.第第k

4、阶段所有可能状态构成的集合称为该阶阶段所有可能状态构成的集合称为该阶段的段的(可达可达)状态集合状态集合,记为记为Sk.最短路问题中，各个节点就是状态最短路问题中，各个节点就是状态生产库存问题中，库存量是状态生产库存问题中，库存量是状态物资分配问题中，剩余的物资量是状态物资分配问题中，剩余的物资量是状态 无后效性：无后效性：如果某阶段状态给定后如果某阶段状态给定后,则在这阶段则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响以后过程的发展不受这阶段以前各阶段状态的影响.3.决策与决策变量决策与决策变量 决策是指在某个阶段状态给定以后决策是指在某个阶段状态给定以后,从该状态演从该状态演变至下

5、一阶段某状态的选择变至下一阶段某状态的选择.描述决策的变量称为决描述决策的变量称为决策变量策变量,用用uk(sk)表示第表示第k阶段处于状态阶段处于状态sk时的决策变时的决策变量量.用用Dk(sk)表示第表示第k阶段从状态阶段从状态sk出发的允许决策集出发的允许决策集合合.uk(sk)Dk(sk)最短路问题中，走哪条路最短路问题中，走哪条路生产库存问题中，各阶段的产品生产量生产库存问题中，各阶段的产品生产量物资分配问题中，分配给每个地区的物资量物资分配问题中，分配给每个地区的物资量 4.策略与策略与(后部后部)子策略子策略 策略是一个按顺序排列的决策组成的集合策略是一个按顺序排列的决策组成的集

6、合.由过程的第一阶段开始到终点为止的每阶段的由过程的第一阶段开始到终点为止的每阶段的决策所组成的决策序列称为全过程策略决策所组成的决策序列称为全过程策略,简称策略简称策略.记为记为 p1,n(s1)=u1(s1),u2(s2),un(sn)由过程的第由过程的第k阶段开始到终止状态为止的过程阶段开始到终止状态为止的过程,其相应的决策序列称为其相应的决策序列称为k子过程策略子过程策略,简称子策略简称子策略.记为记为 pk,n(sk)=uk(sk),uk+1(sk+1),un(sn)可供选择的策略范围称为允许策略集合可供选择的策略范围称为允许策略集合,用用P表表示示.从从P中找出达到最优效果的策略称

7、为最优策略中找出达到最优效果的策略称为最优策略.5.状态转移与状态转移方程状态转移与状态转移方程 过程由这一阶段的一个状态转变到下一阶段过程由这一阶段的一个状态转变到下一阶段的另一个状态称为状态转移的另一个状态称为状态转移.描述状态转移关系的描述状态转移关系的方程称为状态转移方程方程称为状态转移方程.由状态由状态sk转移到转移到sk+1的状态的状态转移方程转移方程.记为记为 sk+1=Tk(sk,uk)Tk称为状态转移函数称为状态转移函数.6.指标函数和最优值函数指标函数和最优值函数 用来衡量所实现过程优劣的一种数量指标用来衡量所实现过程优劣的一种数量指标,称称为指标函数为指标函数.表示为表示

8、为 Vk,n=Vk,n(sk,uk,sk+1,uk+1,sn+1)，k=1,2,n动态规划的指标函数应具有可分离性、递推关系，动态规划的指标函数应具有可分离性、递推关系，即即 Vk,n(sk,uk,sk+1,uk+1,sn+1)=ksk,uk,Vk+1,n(sk+1,uk+1,sn+1)常见的指标函数的形式是常见的指标函数的形式是:1).Vk,n(sk,uk,sn+1)=nj=k vj(sj,uj)=vk(sk,uk)+Vk+1,n(sk+1,uk+1,sn+1)2).Vk,n(sk,uk,sn+1)=nj=k vj(sj,uj)=vk(sk,uk)Vk+1,n(sk+1,uk+1,sn+1)

9、其中其中vj(sj,uj)表示第表示第j阶段的指标阶段的指标.指标函数指标函数1),2)可统一表示为可统一表示为:其中记号其中记号“*”可都表示为可都表示为“+”或都表示为或都表示为“”.指标函数的最优值指标函数的最优值,称为最优值函数称为最优值函数,记为记为fk(sk).它表示从第它表示从第k阶段的状态阶段的状态sk开始到第开始到第n阶段的终止状阶段的终止状态的过程态的过程,采取最优策略所得到的指标函数值采取最优策略所得到的指标函数值.即即其中其中“opt”是最优化是最优化(optimization)的缩写的缩写,可依题意取可依题意取min或或max.),()(1,),(nkknkuukks

10、usVoptsfnk),(),(),(111,nnnkkkkkknkusvusvusvV 最短路线有一个重要特性：如果最短路线有一个重要特性：如果L是允许策略集是允许策略集合合P中从始点中从始点A到终点到终点E的最短路线的最短路线,M是是L中的一点中的一点,则则从从M沿沿L到到E的路是从的路是从M到到E的最短路线的最短路线.寻找最短路线的方法寻找最短路线的方法,可以从最后一段开始可以从最后一段开始,由后由后向前逐步递推向前逐步递推,求出各点到后一点的最短路线求出各点到后一点的最短路线,最后求最后求得始点到终点的最短路线得始点到终点的最短路线.所以所以,动态规划的方法是从动态规划的方法是从终点逐

11、段向始点方向寻找最短路线的一种方法终点逐段向始点方向寻找最短路线的一种方法.如图如图所示所示:行进方向行进方向 始点始点 1 2 3 n 终点终点 寻优途径寻优途径2511214106104131112396581052C1C3D1AB1B3B2D2EC2例例1、最短路径问题、最短路径问题求从求从A到到E的最短路径的最短路径2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0505)E(f)ED(d)D(f5114EDu

12、)(:14最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5202)()()(5224EfEDdDfEDu)(:24最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5.:;)(:82953min)(),()(),(min)(111132421141113EDCDCuDfDCDfDCCf最短路线最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC

13、2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8.:;)(:72556min)(),()(),(min)(222232422141223EDCDCuDfDCDfDCCf最短路线最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7.:;)(:1221058min)(),()(),(min)(232332423141333EDCDCuDfDCDfDCCf最短路线最优决策2511214106104131112396581052

14、C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=8.:201210714812min)(),()(),()(),(min)(11133312321131112EDCBCfCBCfCBCfCBBf最短路线112)(:CBu最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=211233322322131222:1412471

15、086min)(),()(),()(),(min)(CBCfCBCfCBCfCBBf最优决策122)(CBu即2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=142333332323131332:191211712813min)(),()(),()(),(min)(CBCfCBCfCBCfCBBf最优决策232)(CBu即2511214106104131112396581052C1C3D1AB1B3B2D2

16、EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=2123232221211:19191145212min)(),()(),()(),(min)(BABfBABfBABfBAAf最优决策21)(BAu即2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态状态 最优决策最优

17、决策 状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态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）C12511214106104131112396581052C1C3

18、D1AB1B3B2D2EC2f4(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）D12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2

19、(B2)=14f2(B1)=21状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态A （A，B2）B2 （B2，C1）C1 （C1，D1）D1 （D1，E）E从从A到到E的最短路径为的最短路径为19，最短路线为，最短路线为AB 2C1 D1 E k阶段与阶段与k+1阶段之间的递推关系阶段之间的递推关系:称为动态规划的基本方程称为动态规划的基本方程.例例1中中opt=min，vk(sk,uk(sk)=dk(sk,uk(sk).用动态规划解题的基本思路用动态规划解题的基本思路,是将一个是将一个n阶段的决阶段的决策问题化为依次求解

20、策问题化为依次求解n个具有递推关系的单阶段决策个具有递推关系的单阶段决策问题问题,从而简化计算过程从而简化计算过程.这一思路体现了动态规划方这一思路体现了动态规划方法的如下基本特征法的如下基本特征:多阶段性，无后效性，递归性，总体优化性多阶段性，无后效性，递归性，总体优化性.)1.8(.1,2,1,0)(:)()(,()(1111)(nnksfsfsusvoptsfnnkkkkkksDukkkkk边界条件 逆序解法逆序解法:从问题的最后一个阶段开始从问题的最后一个阶段开始,逆多阶段逆多阶段决策的实际过程反向寻优决策的实际过程反向寻优.如图所示如图所示:行进方向行进方向 始点始点 1 2 3 n

21、 终点终点 寻优途径寻优途径 顺序解法顺序解法:从问题的最初阶段开始从问题的最初阶段开始,顺多阶段决策顺多阶段决策的实际过程同向寻优的实际过程同向寻优.如图所示如图所示:行进方向行进方向 始点始点 1 2 3 n 终点终点 寻优途径寻优途径(两种解法可表示行进方向的不同或对始点终点看法的颠倒两种解法可表示行进方向的不同或对始点终点看法的颠倒)给实际问题建立动态规划模型的基本步骤给实际问题建立动态规划模型的基本步骤:(1).将问题的过程恰当地划分为若干个阶段将问题的过程恰当地划分为若干个阶段;(2).正确选择状态变量正确选择状态变量sk(第第k阶段的初始状态阶段的初始状态),使它既使它既 能描述

22、过程的演变能描述过程的演变,又能满足无后效性又能满足无后效性;(3).确定决策变量确定决策变量uk及每阶段的允许决策集合及每阶段的允许决策集合Dk(sk);(4).正确写出状态转移方程正确写出状态转移方程;(5).正确写出指标函数正确写出指标函数Vk,n，它应满足下面三个性质，它应满足下面三个性质:a)是定义在全过程和所有后部子过程上的函数是定义在全过程和所有后部子过程上的函数;b)要具有可分离性要具有可分离性,且满足递推关系且满足递推关系,即即 Vk,n(sk,uk,sn+1)=ksk,uk,Vk+1,n(sk+1,uk+1,sn+1)c)函数函数k(sk,uk,Vk+1,n)对于变量对于变

23、量Vk+1,n 要严格单调要严格单调.指标函数指标函数:动态规划逆序解法的基本方程为动态规划逆序解法的基本方程为:式中状态转移方程式中状态转移方程sk+1=Tk(sk,uk).(8.2)中通常中通常“*”取取“+”时时=0；取；取“”时时=1.),(*),(),(),(),(111,1111,nkknkkkknnnkkkkkknksusVusvusvusvusvV)2.8(.1,2,1,)()(),()(1111)(nnksfsfusvoptsfnnkkkkksDukkkkk 动态规划顺序解法的基本方程为动态规划顺序解法的基本方程为:式中状态转移方程式中状态转移方程sk=Tk(sk+1,uk)

24、.(8.3)中通常中通常“*”取取“+”时时=0；取；取“”时时=1.)3.8(.,2,1,)()(),()(1011)(11nksfsfusvoptsfkkkkksDukkkkk 附注：附注：若将状态变量若将状态变量sk表示表示k阶段末的结束状阶段末的结束状态，则态，则 动态规划顺序解法的基本方程为动态规划顺序解法的基本方程为:)3.8(.,2,1,)()(),()(0011)(nksfsfusvoptsfkkkkksDukkkkk作为整个过程的最优策作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何略具有这样的性质，无论过去的状态和决策如何,对对前面决策所形成的状态而言前面决策

25、所形成的状态而言,余下的诸决策必构成最余下的诸决策必构成最优策略优策略.(简言之简言之,一个最优策略的子策略总是最优的一个最优策略的子策略总是最优的)设阶段数为设阶段数为n的多阶段的多阶段决策过程决策过程,其阶段编号为其阶段编号为k=0,1,2,。允许策略允许策略 是最优策略的充要是最优策略的充要条件是对任一个条件是对任一个k，0kn-1和和s0S0有有),(110*1,0nnuuup式式(8.4)中中 ,它是由给它是由给定的初始状态定的初始状态s0和子策略和子策略p0，k-1所确定的所确定的k段状态段状态.允许策略允许策略p*0,n-1 是最优策略是最优策略,则对任意的则对任意的k，0kn-

26、1，它的子策略，它的子策略p*k，n-1对于以对于以 s*k=Tk-1(s*k-1,u*k-1)为起点的为起点的k到到n-1子过程来说子过程来说,必是必是最优策略最优策略.(注意注意:k段状态段状态s*k是由是由s0和和p*0,k-1所确定的所确定的)此推论就是动态规划的此推论就是动态规划的“最优性原理最优性原理”,它仅仅它仅仅是是最优策略的必要性最优策略的必要性.),(),(1111,1,01,0kkkknkknusTsppp)4.8(),(),(),(1,1,)(1,001,0)(1,001,01,1,01,01,0nkknksppkksppnnpsVoptpsVoptpsVknknkkk

27、l动态规划的四大要素、一个重点动态规划的四大要素、一个重点(方程方程)状态变量及其可达状态集合状态变量及其可达状态集合 sk Sk 决策变量及其允许决策集合决策变量及其允许决策集合 uk Dk 状态转移方程状态转移方程 sk+1=Tk(sk,uk)阶段指标函数阶段指标函数 vk(sk,uk)动态规划基本方程动态规划基本方程(8.2)或或(8.3)l多阶段决策过程特点多阶段决策过程特点:要点：阶段，状态，决策，状态转移方程，要点：阶段，状态，决策，状态转移方程，k子过程子过程.逆推解法逆推解法:决策决策uk使状态使状态sk(输入输入)转移为状态转移为状态sk+1(输出输出).状态转移方程状态转移

28、方程 sk+1=Tk(sk,uk)，k=n,n-1,1.顺推解法顺推解法:决策决策uk使状态使状态sk+1(输入输入)转移为状态转移为状态sk(输出输出).状态转移方程状态转移方程 sk=Tk(sk+1,uk)，k=1,2,n.初始状态给定时初始状态给定时,宜用逆推法宜用逆推法;终止状态给定时终止状态给定时,宜用顺推法宜用顺推法.例例1、设备负荷分配问题、设备负荷分配问题 某种机器可在高低两种不同的负荷下进行生产某种机器可在高低两种不同的负荷下进行生产.设机器在高负荷下生产的产量函数为设机器在高负荷下生产的产量函数为g=cu=8u，其，其中中u为投入生产的机器数量为投入生产的机器数量,年终机器

29、的完好率为年终机器的完好率为a=0.7；在低负荷下生产的产量函数为在低负荷下生产的产量函数为h=dx=5x，其，其中中x为投入生产的机器数量为投入生产的机器数量,年终机器的完好率为年终机器的完好率为b=0.9.假定开始生产时完好的机器数量为假定开始生产时完好的机器数量为s1=1000台台.试问企业每年年初应如何分配机器在高、低两种负试问企业每年年初应如何分配机器在高、低两种负荷下的生产荷下的生产,使在第使在第5年年末完好的机器数量为年年末完好的机器数量为s6=500台台,并且并且5年内生产的产品总产量最高年内生产的产品总产量最高.例例1、设备负荷分配问题、设备负荷分配问题 解解.设阶段序号设阶

30、段序号k表示年度表示年度.状态变量状态变量sk为第为第k年年初拥有的完好机器数量年年初拥有的完好机器数量,同同时也是第时也是第k-1年年末的完好机器数量年年末的完好机器数量.决策变量决策变量uk为第为第k年度投入高负荷下生产的机器年度投入高负荷下生产的机器数量数量,于是于是 xk=sk-uk 为该年度中分配在低负荷下生产为该年度中分配在低负荷下生产的机器数量的机器数量.状态转移方程为状态转移方程为 sk+1=auk+bxk=0.7uk+0.9(sk-uk)第第k年度的允许决策集合为年度的允许决策集合为 Dk(sk)=uk0uksk第第k年度的产量为年度的产量为 vk=8uk+5(sk-uk),

31、k=1,2,5指标函数指标函数 V1,5=5k=1vk.令最优值函数令最优值函数fk(sk)表示从第表示从第k年开始到第年开始到第5年年末年年末所生产的产品的最大总产量所生产的产品的最大总产量,则有逆推法的基本方程则有逆推法的基本方程:从第从第5年度开始年度开始,向前递推计算向前递推计算.1,4,5,0)()(9.07.0)(58max)(661ksfusufususfkkkkkkkDukkkk75005.18)(58max)(555525005.45555sususfsu0,750065.21)75007.065.21(max)2.09.0(53max)(*44440445440444444

32、usususfsusfsusu0),7500897.10635.27(max)(*22202222uussfsu0,7500485.24)750033.1485.24(max)2.09.0(53max)(*33330334330333333usususfsusfsusu0),75004073.23329.29(max)(*11101111uussfsu.218339.21832)1000(11sf 最优策略为：最优策略为：u1*=u2*=u3*=u4*=0，u5*=4.5s5-2500452.这表明这表明,从第从第1年到第年到第4年应把年初全部完好的机器投年应把年初全部完好的机器投入低负荷生产

33、入低负荷生产,则在第则在第5年初完好机器数为年初完好机器数为656台台,第第5年分配年分配452台机器高负荷生产台机器高负荷生产,204 台机器低负荷生产台机器低负荷生产,可以保证在第可以保证在第5年年末完好的机器数量为年年末完好的机器数量为500台台,且且5年年内生产的产品总产量最高内生产的产品总产量最高,最高产量为最高产量为21833单位单位.注注1.sk=0.5表示一台机器在表示一台机器在k年内只有半年正常年内只有半年正常工作时间；工作时间；uk=0.3表示一台机器在表示一台机器在k年内只有年内只有3/10时时间高负荷生产。间高负荷生产。.218339.21832)1000(11sf 注

34、注2.如果第如果第n年年末完好的机器数量没有限制，年年末完好的机器数量没有限制，则可以确定从低负荷转为高负荷生产的第则可以确定从低负荷转为高负荷生产的第t年。由年。由intaiabcdabcdcnt1/1)(,11，知从知从1至至t-1年在低负荷下生产，年在低负荷下生产，t至至n年在高负荷下年在高负荷下生产，使生产，使n年内生产的产品总产量最高。年内生产的产品总产量最高。当当g(x)、h(x)为凸函数，且为凸函数，且g(0)=h(0)=0，则则在每个阶段上的最优策略总是取其上限或下限。在每个阶段上的最优策略总是取其上限或下限。例例1中，若第中，若第5年年末完好的机器数量没有限年年末完好的机器数

35、量没有限制，则制，则t=5-1-1=3，即从第即从第3年年初将完好的机器全年年初将完好的机器全部投入高负荷生产，部投入高负荷生产，5年内生产的产品总产量最高。年内生产的产品总产量最高。例例2、生产与存储问题、生产与存储问题 某厂在未来某厂在未来3个月连续生产某种产品个月连续生产某种产品.每月初开始每月初开始生产生产.月生产量为月生产量为x,生产成本为生产成本为x2,库存费为每月每单库存费为每月每单位位1元元.假如假如3个月的需求量预测为个月的需求量预测为 b1=100,b2=110，b3=120，且初始存货，且初始存货s0=0，第三个月的期末存货，第三个月的期末存货s3=0.问应如何安排生产问

36、应如何安排生产,使总成本最小使总成本最小.解解.以月为阶段以月为阶段.设设uk为第为第k月的产量，月的产量，sk为第为第k月月末的库存量末的库存量,vk(sk,uk)为第为第k月的成本，月的成本，fk(sk)为从第为从第1月月到第到第k月按最优策略安排生产的总成本月按最优策略安排生产的总成本.状态转移方程为状态转移方程为 sk-1=sk-uk+bk，sk0，uk0，k=1,2,3 建立顺推法的基本方程建立顺推法的基本方程:.3,2,1,0)()(1min)(001120ksfsfsusfkkkkukkk111121112111,)()(min)(111sbussbsusfsbu12222122

37、221222222221222012112220224/12/1)(2/1)(,04/1)(2/1)()(min)(1min)(22bssbbsfsbbubusbusbsussbsusfuu 将将b1,b2,b3代入上式代入上式,并依次回代并依次回代,得得 u3=110.5，s2=9.5，u2=110，s1=9.5,u1=109.5 全期的最小总成本为全期的最小总成本为 f3(s3)=36319.5.2/1)(3/1)4/1)2/1)(2/1min)(min)(3213133233212302232303333bbbubububbbusfsusfuu n个阶段的生产与存储问题个阶段的生产与存储

38、问题 设第设第k阶段对产品的需求量阶段对产品的需求量dk，生产量生产量uk，库存库存费费hk(uk)。初始库存量初始库存量s0=0，第，第n阶段末存货阶段末存货sn=0。在在保证供应下，问如何安排生产保证供应下，问如何安排生产,使总成本最小使总成本最小.sk为第为第k阶段末的库存量，则有阶段末的库存量，则有sk-1=sk-uk+bk，ck(uk)为第为第k阶段生产产品阶段生产产品uk时的成本，即时的成本，即mumuauKuuckkkkkk,3,2,100)(其中其中K为生产准备成本，为生产准备成本，a为单位产品成本，为单位产品成本，m为每阶段最多能生产该产品的上限为每阶段最多能生产该产品的上限

39、.fk(sk)表示从第表示从第1阶段到第阶段到第k阶段按最优策略阶段按最优策略安排生产的最小总成本安排生产的最小总成本.则顺序递推式为则顺序递推式为:).,min(.,2,1),()(min)(0)()()()(min)(1111110011011mdunkshscsfsfsfshucsfkkkukkkkkkukkkk其中或.)0(,min0)(,1即为最小总费用之间的值，最后求得至在中的，计算出对每个nnkjkjkkkfdmdssfk 注注1.若每阶段生产产品的数量无上限的限制，若每阶段生产产品的数量无上限的限制，则只要改变则只要改变ck(uk)，即即kkkkkkkkdsuauKuuc,3,

40、2,100)(.0)(,1之间的值至在中的，需计算对每个nkjjkkkdssfk 例例3.书书P225例例3.注注2.如果对每个如果对每个i，都有都有si-1ui=0，则称该点的生则称该点的生产产决策决策(或称一个策略或称一个策略u=u1,u2un)具有再生产点性质。具有再生产点性质。如果如果si=0，则称阶段则称阶段i为再生产点。为再生产点。若库存问题的目标函数若库存问题的目标函数g(x)在凸集在凸集S上是凹（或凸）上是凹（或凸）函数，则函数，则g(x)在在S的顶点上具有再生产点性质的最优的顶点上具有再生产点性质的最优策略。策略。设设c(j,i)(ji)为阶段为阶段j到阶段到阶段i的总成本，

41、给定的总成本，给定j-1和和i是再生产点，并且阶段是再生产点，并且阶段j和阶段和阶段i期间的产品全部由期间的产品全部由阶段阶段j供给。则供给。则）（5.8)()0()(),(111ijrirttrijrrijrrjdhcdcijc 设最优值函数设最优值函数fi表示在阶段表示在阶段i末库存量末库存量si=0时，时，从阶段从阶段1到阶段到阶段i的最小成本的最小成本.则递推式为则递推式为:)7.8(0)6.8(.,2,1),(min011fniijcffjiji个阶段的最小总成本。为则，逐个计算nffffnn)0(,21设设j(n)为计算为计算fn时，使（时，使（8.6）式右边最小的）式右边最小的j

42、 值，即值，即),(),(min1)(11nnjcfnjcffnjjnjn 则从阶段则从阶段j(n)到阶段到阶段n的最优生产决策为的最优生产决策为:.0,2)(,1)(;)()(rnnjrrnjxnnjnjrdx时当故故j(n)-1为再生产点。为再生产点。记记 m=j(n)-1，而而j(m)是在计算是在计算fm时，使（时，使（8.6）式右边最小的式右边最小的j 值，则从阶段值，则从阶段j(m)到阶段到阶段j(n)的最优的最优生产决策为：生产决策为：.0,2)(,1)(;)()(rmmjrrmjxmmjmjrdx时当故故j(m)-1为再生产点为再生产点,其余依此类推。其余依此类推。例例4.利用再

43、生产点性质解例利用再生产点性质解例3。再生产点性质计算。都是凹函数，故可利用、解kkkkkkkkksshuuuuuc5.0)(66,3,2,1300)(.4,3,2,1,1)()0()(),(.1111iijdhcdcijcijrirttrijrrijrrj计算）（505.023)0()2()1,1(hcc5.935.053)3()5()2,1(hcc25.055.0)2()5()7()3,1(hhcc)4()6()9()11()4,1(hhhcc9)2()5()3,2(6)0()3()2,2(hcchcc，5)0()2()3,3(,)4()6()9()4,2(hcchhcc7)4()4,4(

44、,11)4()6()4,3(cchcc0.,2,1),(min.2011fnifijcfjiji计算）（1)1(,550)1,1(,0010jcfff1)2(,5.965,5.90min)2,2(),2,1(min102jcfcff2)3(,1455.9,95,0min)3,3()3,2(),3,1(min2103jcfcfcff，3)4(,5.20714,115.9,5,0min)4,4()4,3()4,2(),4,1(min32104jcfcfcfcff，0,3)4(.34433udduj由找出最优生产决策）（千元。最小总成本为所以最优生产决策为：5.200,6,0,50,51)2()(2

45、1)4(43212211uuuuuddujmjjm 例例5、设备更新问题、设备更新问题 某企业在今后某企业在今后4年内需使用一辆卡车年内需使用一辆卡车.现有一现有一辆已使用辆已使用2年的旧车年的旧车,根据统计资料分析根据统计资料分析,预计卡车预计卡车的年收入、年维修费的年收入、年维修费(包括油料等费包括油料等费)、一次更新、一次更新重置费及重置费及4年后年后残值如下表所示，残值如下表所示，表中表中k=1,2,3,4.试确定试确定4年中的年中的最优更新计划最优更新计划,以使总利润最大以使总利润最大.i 0 1 2 3 4 5 6 rk(i)yk(i)ck(i)t5(i)16 14 11 8 5

46、2 -1 2 2 3 4 4 -18 21 25 29 34 -15 12 8 3 0 0 解解.设状态变量设状态变量sk表示第表示第k年初机器的役龄年初机器的役龄;决策变量决策变量uk表示第表示第k年初对役龄年初对役龄sk的机器采用的的机器采用的决策决策,则则 ukDk=(更新更新)R，(继续使用继续使用)K.状态转移方程：状态转移方程：RuKusskkkk当当111 t5(s5)表示第表示第5年初役龄为年初役龄为s5的机器残值的机器残值;rk(sk)为第为第k年初役龄为年初役龄为sk的机器继续使用一年的的机器继续使用一年的年收入年收入;yk(sk)表示第表示第k年初役龄为年初役龄为sk的机

47、器继续使用一年的机器继续使用一年的年维修费的年维修费(包括因维修而减少生产所引起的损失包括因维修而减少生产所引起的损失);ck(sk)表示第表示第k年初对役龄为年初对役龄为sk的机器进行更新时的机器进行更新时一次性以旧换新的费用一次性以旧换新的费用(购买和安装新机器费用与旧购买和安装新机器费用与旧机器残值之差机器残值之差).第第k年的年利润为年的年利润为:设设fk(sk)表示第表示第k年至第年至第4年内年内,期初有一台役龄为期初有一台役龄为sk的机器的机器,采用最优更新策略所能获得的最大利润采用最优更新策略所能获得的最大利润,则有则有RuscyrKusysrusvkkkkkkkkkkkkk当当

48、)()0()0()()(),(.1,3,4),()()1(),()(),(max)(5555111kstsfRufusvKusfusvsfkkkkkkkkkkkDukkkk 计算结果计算结果:表表1 表表2(k=4)s51 2 3 4 5 6f5(s5)15 12 8 3 0 0 s41 2 3 4 5 f4(s4)u4*24 17 8 -2K K K -K s31 2 3 4f3(s3)u3*29 18 -8 K R -R s21 2 3 f2(s2)u2*30 -19K -R 表表3(k=3)表表4(k=2)k=1时时f1(s1=2)=28,u*1=s1.最优策略为最优策略为 K,R,K,

49、K,最大年利润最大年利润28个单位个单位.例例6、资源分配问题、资源分配问题 设有某种原料设有某种原料,总数量为总数量为a,用于生产用于生产n种产品种产品.若分若分配数量配数量xi用于生产第用于生产第i种产品种产品.其收益为其收益为gi(xi).问应如何问应如何分配分配,才能使生产才能使生产n种产品总收益最大种产品总收益最大?此问题可写成静态规划此问题可写成静态规划)1(,2,1,0.)()()(max212211nixaxxxtsxgxgxgzinnn 对某些静态问题可用动态规划来求解对某些静态问题可用动态规划来求解,把依次决把依次决定各个变量的取值看成是一个多阶段的决策过程定各个变量的取值

50、看成是一个多阶段的决策过程,因因而模型中有多少个变量而模型中有多少个变量,求解就分多少个阶段求解就分多少个阶段.约束条约束条件的右端项表明可分配的资源量件的右端项表明可分配的资源量,用状态变量表示用状态变量表示,而而约束条件的个数则是状态变量的维数约束条件的个数则是状态变量的维数.解解.设状态变量设状态变量sk表示分配用于生产第表示分配用于生产第k种产品至种产品至第第n种产品的原料数量种产品的原料数量;决策变量决策变量uk表示分配给生产第表示分配给生产第k种产品的原料数，种产品的原料数，即即uk=xk.允许决策集合为允许决策集合为Dk：0uksk.状态转移方程为状态转移方程为 sk+1=sk-