f第七章动态规划

1、 运筹学运筹学动态规划（动态规划（1 1） 运筹学运筹学定理：定理： 如果如果A到到F的最短路程是的最短路程是:ABCDEF 那么那么C到到F的最短路程一定是的最短路程一定是: CDEF (Bellman最优化原理）最优化原理）第六章 动态规划（1） 运筹学运筹学第六章 动态规划（1）动态规划在经济管理中应用：动态规划应用之一：最优路径问题最优路径问题动态规划应用之二：资源分配问题资源分配问题动态规划应用之三：生产计划调度问题生产计划调度问题动态规划应用之四：库存问题，采购问题库存问题，采购问题动态规划应用之五：设备更新问题设备更新问题动态规划应用之六： 生产过程最优控制问题生产过程最优控制问

2、题动态规划应用之七： . 运筹学运筹学动态规划应用之一：最优路径问题：最优路径问题：类似类似P201例题：例题： 某某工厂从国外进口一部精密设备，由机器制造厂到出口港有三个港口可供选择，工厂从国外进口一部精密设备，由机器制造厂到出口港有三个港口可供选择，而进口港又有三个港口可供选择，进口后可以经两个城市到达目的地，其运而进口港又有三个港口可供选择，进口后可以经两个城市到达目的地，其运输成本输成本 如图所示，求运费最低的路线如图所示，求运费最低的路线AB3B2B1D2D1C3C2C1E2040403020304010604070503030306040104030第六章 动态规划（1）运输成本运

3、输成本国外机器制造厂国外机器制造厂 出口港出口港 进口港进口港 国内城市国内城市 国内某工厂国内某工厂 运筹学运筹学AB3B2B1D2D1C3C2C1E2040403020304010604070503030306040104030400307040608070110110第六章 动态规划（1）从从C1到终点最短路到终点最短路两点间运输成本两点间运输成本国外机器制造厂国外机器制造厂 出口港出口港 进口港进口港 国内城市国内城市 国内某工厂国内某工厂 运筹学运筹学AB3B2B1D2D1C3C2C1E2040403020304010604070503030306040104030400307040

4、608070110国外机器制造厂国外机器制造厂 出口港出口港 进口港进口港 国内城市国内城市 国内某工厂国内某工厂1.阶段阶段 2.状态状态 3.决策决策 4.策略策略 5.状态转移方程状态转移方程 6.指标函数和最优值函指标函数和最优值函数数第六章 动态规划（1）110 运筹学运筹学动态规划的基本概念：动态规划的基本概念：1. 阶段：把问题分为互相联系有一定次序的阶段阶段：把问题分为互相联系有一定次序的阶段(上例，四个阶段上例，四个阶段)状态：每个阶段开始所处自然状况或客观条件，不可控制（第状态：每个阶段开始所处自然状况或客观条件，不可控制（第1阶阶段状态：段状态：A，第，第2阶段状态：阶段

5、状态：B1，B2，B3） 无后效性（马尔科夫性）无后效性（马尔科夫性）3. 决策：某个阶段的某个状态决定下一个阶段的状态（从决策：某个阶段的某个状态决定下一个阶段的状态（从A出发，三出发，三种不同决策：种不同决策： B1，B2，B3 ）4. 策略：按顺序排列的决策组成的集合（序列）策略：按顺序排列的决策组成的集合（序列）5. 状态转移方程：确定由一个状态转到另一个状态的过程状态转移方程：确定由一个状态转到另一个状态的过程指标函数和最优值函数：衡量过程优劣的数量指标指标函数和最优值函数：衡量过程优劣的数量指标2.阅读：阅读：P196-P198 基本概念基本概念第六章 动态规划（1） 运筹学运筹学

6、动态规划最优性原理与最优性定理：动态规划与静态规划的关系：动态规划非线性规划运输问题规划整数规划线性规划静态规划数字规划10第六章 动态规划（1） 运筹学运筹学1.资源分配问题资源分配问题引例：某种原料总数为引例：某种原料总数为a分配给分配给n种产品，分配数量种产品，分配数量Xi用于生产第用于生产第i种产品，种产品，效益为效益为gi(xi)0.)(.)()(212211innnxaxxxxgxgxgMaxZ种产品原料量第k种产品原料数量种产品到第第nk1种产品原料数量种产品到第第nk0)(1kkkkkkkkkkkSXUUSDXSUSS：允许决策集合：状态转移方程：第六章 动态规划（1） 运筹学

7、运筹学动态规划顺序解法：动态规划顺序解法：第一步：划分阶段第一步：划分阶段第二步：选择状态变量第二步：选择状态变量第三步：确定决策变量第三步：确定决策变量第四步：写状态转移方程第四步：写状态转移方程第五步：第五步： 指标函数指标函数第六章 动态规划（1） 运筹学运筹学第六章 动态规划（1）类似类似P 208例例4 顺推法求解非线性规划：顺推法求解非线性规划： maxZ=4x1+9x2+2x32 x1+x2+x3=10 xi=0 I=1,2,3分析：理解为分析：理解为 第一阶段投资第一阶段投资x1， 第二阶段投资第二阶段投资x2 第三阶段投资第三阶段投资x3 求最大利润求最大利润maxZ=4x1

8、+9x2+2x32 三阶段投资总额共有三阶段投资总额共有10单位单位 非线性规划问题求解非线性规划问题求解 第一阶段投资总额第一阶段投资总额S1（状态变量）（状态变量） 第一二阶段投资总额第一二阶段投资总额S2 （状态变量）（状态变量） 第一二三阶段投资总额第一二三阶段投资总额S3 （状态变量）（状态变量）x1x2x3S3S2S1S1 = X1 S2 = X1 +X2 S3 = X1+X2+X3动态规划应用之二：资源分配问题资源分配问题-P207 -P207 例例3 3 运筹学运筹学第六章 动态规划（1）解解:设状态变量设状态变量S1=X1 ,S2=S1+X2, S3=S2+X3F1(S1)=

9、4X1=4S1 ( 第一阶段投资第一阶段投资x1产生的效益产生的效益4X1 ）第一二阶段投资总量为第一二阶段投资总量为S2产生的效益产生的效益 第一阶段投资第一阶段投资x1产生的效益第二阶段投资产生的效益第二阶段投资X2产生的效益产生的效益S1=S2-X2 F2(S2)=9X2+F1(S1)= 9X2 + 4S2 -4X2 = 5X2 + 4S2 X2 S2当当X2=S2时时 maxF2(S2)=9S2第一二三阶段投资总量为第一二三阶段投资总量为S3产生的效益产生的效益 第一二阶段投资第一二阶段投资S2产生的效益第三阶段投资产生的效益第三阶段投资X3产生的效益产生的效益S2=S3-X3F3(S

10、3)= 2X32 +F2(S2)= 2X32 + 9(S3 -X3 ) = 2X32-9X3+9S3 =h3(S3,X3) 0=X3 =10d h3(S3,X3) /dX3=4X3-9=0 且且两阶导数大于零两阶导数大于零因此：因此：X3=9/4 在在X3=9/4, F3(S3)有最小值有最小值, F3(S3) 最大值最大值 X3 10max F3(S3)=2*102=200即即X3=10,则则 X1,X2为为0 max Z=200. 运筹学运筹学第六章 动态规划（1）X3H3(S3,X3)109/4在在X3=9/4, F3(S3)有最小值有最小值, F3(S3) 最大值最大值 X3 10 运

11、筹学运筹学背包问题背包问题：类似：类似P236 例例7： 用动态规划解下列问题：用动态规划解下列问题：Max Z= 8 X1 +7X2 S.T. 2X1 +X2 8 5X1 +2X2 15X1 , X2 为非负整数为非负整数 经济意义：经济意义： X1 , X2为物品数量，为物品数量，8，7为单位物品的价值，为单位物品的价值，2，1为单位物品的体积，为单位物品的体积，5，2为单为单位物品的重量位物品的重量. 8为背包的最大容积，为背包的最大容积，15为背包的最大承受重量为背包的最大承受重量第六章 动态规划（1） 运筹学运筹学第六章 动态规划（1）类似类似P207 例例3 用动态规划用动态规划逆

12、序算法逆序算法解下列问题（解下列问题（二维背包问题二维背包问题）：）：Max Z= 8 X1 +7X2 （最大效益，重量限制，体积限制）（最大效益，重量限制，体积限制） S.T. 2X1 + X2 8 (重量重量) 5X1 +2X2 15 (体积体积)X1 , X2 为非负整数为非负整数解：解：用逆序算法用逆序算法。设：。设： 阶段：分成两个阶段，分别对应第阶段：分成两个阶段，分别对应第1种物体的数量种物体的数量X1 ，第，第2种物体的数量种物体的数量X2 逆序算法先决定背包中第逆序算法先决定背包中第2种物体的数量种物体的数量决策变量：决策变量：X1 ，X2 为背包中两种物体的数量为背包中两种

13、物体的数量状态变量：状态变量：V1 为第为第1 阶段阶段 可供分配重量，可供分配重量， V1 8 W1 为第为第1 阶段可供分配体积，阶段可供分配体积， W1 15，V2 ，W2 对应第对应第2 阶段阶段于是，于是， F*2（V2 ，W2 ）= Max 7 X2 0X2 V2 (重量重量) 02X2 W2 (体积体积)x1x2V1 ， W1V2 ， W2V1 = 8 ， W1 = 15V2 = V1 -2X1 ( 重量重量)W2 = W1 - 5X1 (体积体积) 运筹学运筹学X2 为整数为整数 = 7min V2, W2/2(V是小于等于是小于等于V的最大整数的最大整数) F*1（V1 ，W

14、1 ）= Max 8 X1 + F*2（V1 -2X1 ，W1 - 5X1） 02X1 V1 (重量重量) 05X1 W1 (体积体积) X1 为整数为整数 而而V1 =8，W1=15 因此因此 F*1（8 ，15 ）= Max 8 X1 + 7min 8 -2X1, (15 - 5X1)/2 02X18 05X1 15 X1 为整数为整数由于由于 X1 min 8 /2, (15/5)=3 (X1 为为0，1，2，3，分别代入下式，分别代入下式) F*1（V1 ，W1 ）= Max 8 X1 + 7min 8 -2X1, (15 - 5X1)/2 第六章 动态规划（1） 运筹学运筹学X*1

15、=0 X*2 = min V2, W2/2 V2=V1 - 2X1=8， W2=W1 -5X1 =15 X*2 = 7因此因此, 最优解为最优解为X*1 =0, X*2 = 7 , 最优最优值值:Z*= 49第六章 动态规划（1） 运筹学运筹学第六章 动态规划（1）基本定理：基本定理： 如果如果A到到F的最短路程是的最短路程是ABCDEF，那么那么C到到F的最短路程一定是的最短路程一定是 CDEF (Bellman最优化原理）最优化原理）总结总结动态规划的基本概念：动态规划的基本概念：1。阶段：把问题分为互相联系有一定次序的阶段。阶段：把问题分为互相联系有一定次序的阶段2。状态：每个阶段开始所

16、处自然状况或客观条件，不可控制。状态：每个阶段开始所处自然状况或客观条件，不可控制3。决策：某个阶段的某个状态决定下一个阶段的状态。决策：某个阶段的某个状态决定下一个阶段的状态4。策略：某个阶段的某个状态所有可能的决策。策略：某个阶段的某个状态所有可能的决策5。状态转移方程：确定由一个状态转到另一个状态的过程。状态转移方程：确定由一个状态转到另一个状态的过程6。指标函数和最优值函数：衡量过程优劣的数量指标。指标函数和最优值函数：衡量过程优劣的数量指标 运筹学运筹学第六章 动态规划（3）知识要点知识要点 概念概念(1)多阶段决策问题是指这样的问题多阶段决策问题是指这样的问题,它可分为若干个互相联

17、系的它可分为若干个互相联系的阶段阶段,每一阶段都对应着一组可供选择的决策每一阶段都对应着一组可供选择的决策,每个阶段的决策选每个阶段的决策选定之后定之后,就构成一个决策序列就构成一个决策序列,称为一个策略称为一个策略,它对应一个确定的效它对应一个确定的效果。多阶段的决策问题果。多阶段的决策问题,就是要寻求使此效果最好的策略。就是要寻求使此效果最好的策略。(2)阶段是指总的需要作出决策的步数。阶段总数常记为阶段是指总的需要作出决策的步数。阶段总数常记为n，相应，相应的是的是n个阶段的决策问题。阶段的序号常记为个阶段的决策问题。阶段的序号常记为k,称为阶段变量，称为阶段变量，k=1,2, ，n。k

18、既可以顺序编号也可以逆序编号，常用顺序编号。既可以顺序编号也可以逆序编号，常用顺序编号。1.阶段阶段 2.状态状态 3.决策决策 4.策略策略 5.状态转移方程状态转移方程 6.指标函数和最优值函数指标函数和最优值函数 运筹学运筹学第六章 动态规划（3）知识要点知识要点(3)状态是某阶段决策的出发点，又是前个阶段决策的结果，因此它是阶段状态是某阶段决策的出发点，又是前个阶段决策的结果，因此它是阶段信息的传递点与结合点。第信息的传递点与结合点。第k阶段的状态常用状态变量阶段的状态常用状态变量xk表示，表示，xk应包含第应包含第k个阶段之前决策过程的全部信息，使该阶段后作出的决策同以前的状态和个阶

19、段之前决策过程的全部信息，使该阶段后作出的决策同以前的状态和决策相互独立。状态变量根据实际问题可以表述为一维或多维的向量，其决策相互独立。状态变量根据实际问题可以表述为一维或多维的向量，其取值可以是离散的，也可以是连续的。取值可以是离散的，也可以是连续的。（4）决策是指从某阶段的某个状态出发，在若干个不同方案中做出的选择。）决策是指从某阶段的某个状态出发，在若干个不同方案中做出的选择。第第k阶段状态为阶段状态为xk时的决策用决策变量时的决策用决策变量uk（xk）表示。决策变量允许的取值）表示。决策变量允许的取值范围称为允许决策集合，第范围称为允许决策集合，第k阶段状态为阶段状态为xk时的允许决

20、策集合记为时的允许决策集合记为Dk(xk)，它相当于线性规划中的约束条件。决策变量的取值可以是离散的，也可以它相当于线性规划中的约束条件。决策变量的取值可以是离散的，也可以是连续的。是连续的。（5）n个阶段的决策问题可看成是从第个阶段的决策问题可看成是从第1个阶段直到第个阶段直到第n个阶段决策的全过个阶段决策的全过程，而从第程，而从第k个阶段直到第个阶段直到第n个阶段可看作是子过程。动态规划问题各阶段个阶段可看作是子过程。动态规划问题各阶段决策组成的序列称为一个策略。决策组成的序列称为一个策略。1.阶段阶段 2.状态状态 3.决策决策 4.策略策略 5.状态转移方程状态转移方程 6.指标函数和

21、最优值函数指标函数和最优值函数 运筹学运筹学第六章 动态规划（3）知识要点知识要点(6)状态转移律是从上一阶段的某一状态值转变为下段某一状态值状态转移律是从上一阶段的某一状态值转变为下段某一状态值的转移规律的转移规律,常用数学等式描述。第常用数学等式描述。第k+1个阶段的状态变量个阶段的状态变量xk+1是第是第k个阶段状态变量个阶段状态变量xk和决策变量和决策变量uk(xk)的函数的函数.（7）指标函数可分为阶段的指标函数与过程的指标函数两种。阶）指标函数可分为阶段的指标函数与过程的指标函数两种。阶段的指标函数是指第段的指标函数是指第k个阶段从状态个阶段从状态xk出发采取决策出发采取决策uk时

22、的效益，时的效益，用用uk（xk，uk）表示。而过程的指标函数是指从第）表示。而过程的指标函数是指从第k个阶段的某个个阶段的某个状态状态xk出发，采取子策略出发，采取子策略uk ，uk+1,un时所得到的效益，它既与时所得到的效益，它既与xk有关，又与以后的子策略有关，是两者的函数有关，又与以后的子策略有关，是两者的函数.（8）最优指标函数是指从第）最优指标函数是指从第k个阶段的状态个阶段的状态xk出发采取最优子策出发采取最优子策略后得到的过程指标函数值，即对应最优子策略的效益值略后得到的过程指标函数值，即对应最优子策略的效益值.1.阶段阶段 2.状态状态 3.决策决策 4.策略策略 5.状态

23、转移方程状态转移方程 6.指标函数和最优值函数指标函数和最优值函数 运筹学运筹学动态规划在经济管理中应用：动态规划应用之一：最优路径问题（已讲）最优路径问题（已讲）动态规划应用之二：资源分配问题（已讲）资源分配问题（已讲）动态规划应用之三：生产计划调度问题（？）生产计划调度问题（？）动态规划应用之四：库存问题，采购问题（？）库存问题，采购问题（？）动态规划应用之五：设备更新问题（？）设备更新问题（？）动态规划应用之六： 生产过程最优控制问题（？）生产过程最优控制问题（？）动态规划应用之七： . 运筹学运筹学动态规划（动态规划（2 2） 运筹学运筹学第六章 动态规划（2）P216 例例1 一维资

24、源分配问题：一维资源分配问题：要把五台高效率的设备调配给自己的三家分厂，要把五台高效率的设备调配给自己的三家分厂，各个工厂得到这些设备所产生的利润如下表，各个工厂得到这些设备所产生的利润如下表，问如何调配可以获得最大利润？问如何调配可以获得最大利润？产生利润产生利润工厂工厂1工厂工厂2工厂工厂30台台0001台台3542台台71063台台911114台台1211125台台131112阶段、决策变量、阶段、决策变量、状态变量状态变量?动态规划应用之二：资源分配问题资源分配问题 运筹学运筹学第六章 动态规划（2）P216 例例1 一维资源分配问题：一维资源分配问题：阶段阶段,决策变量与状态变量决策

25、变量与状态变量分配到分配到k厂的设备台数厂的设备台数 Xk分配到分配到k厂到厂到3厂的设备总台厂的设备总台数数 Sk, 产生利润产生利润工厂工厂1工厂工厂2工厂工厂30台台0001台台3542台台71063台台911114台台1211125台台131112X1 X2 X3 S1S2S3S3 = X3 S2 = X2 +X3 S1 = X1+X2+X3 运筹学运筹学 P3(X3) F3(S3)X*3X3 =0X3 = 1X3 = 2X3 = 3X3 = 4X3 = 5S3 = 0000S3 = 1441S3 = 2662S3 = 311113S3 = 412124S3 = 512125 注意：分

26、配到注意：分配到3厂的设备总台数厂的设备总台数 S3 = 分配到分配到3厂的设备台数厂的设备台数 X3第六章 动态规划（2） 运筹学运筹学第六章 动态规划（2）分配到分配到2厂的设备厂的设备台数台数 X2 P2(X2) F3 ( S2 X2)F2 ( S2)X*2X2 =0X2 =1X2 =2X2 =3X2 =4X2 =5S2 = 0000S2 = 1045051S2 = 20654100102S2 = 301156104110142S2 = 4012511106114110161，2S2 = 50125121011116114110212分配到分配到2厂到厂到3厂的设备厂的设备总台数总台数

27、S2 = X2 X3由已知表：第由已知表：第2厂分配厂分配3台设备得效益台设备得效益11由上表：第由上表：第3厂分配厂分配2 台设备得效益台设备得效益6 运筹学运筹学第六章 动态规划（2）分配到分配到1厂的设备厂的设备台数台数 X1 P1(X1) F2(5 - X1)F1(5 )X*1X1 =0X1 = 1X1 = 2X1 = 3X1 = 4X1 = 5 S1 = 5021=21316=19714=21910=19125130=13210，2分配给分配给1厂到厂到3厂厂的设备总台数的设备总台数 S1 = 5由已知表：第由已知表：第1厂分配厂分配4台设备得效益台设备得效益12，由上表：第由上表：

28、第2，3厂分配厂分配 1台设备得效益台设备得效益5由第三表知：总利润由第三表知：总利润21万元万元X1 0，第，第1工厂不分配，工厂不分配， 第第2，3 工厂分配工厂分配 5 台，台， S2 = X2 +X3 5由第二表对应由第二表对应 S2 5知：知： X2 2，第，第2工厂分配工厂分配2台，台， 于是第于是第3工厂分配工厂分配 3台台 最优分配一：第最优分配一：第1厂厂 分配分配0台；台； 第第2厂厂 分配分配2台；第台；第3厂分配厂分配3台；台； 总利润总利润21万元万元 运筹学运筹学第六章 动态规划（2）另一个结果是，由第三表知：总利润也是另一个结果是，由第三表知：总利润也是21万元万

29、元X1 2，第，第1工厂分配工厂分配2台，台， 第第2，3 工厂分配工厂分配 3 台，台， S2 = X2 +X3 3由第二表由第二表 对应对应 S2 3 知：知： X2 2，第，第2工厂分配工厂分配2台，台，于是第于是第3工厂分配工厂分配 1台台最优分配二：第最优分配二：第1厂厂 分配分配2台；第台；第2厂厂 分配分配2台；第台；第3厂厂 分配分配1台；总利润台；总利润21万元万元 运筹学运筹学第六章 动态规划（3）基本要求基本要求 1.明确什么是多阶段的决策问题，特别要注意没有明显的时段明确什么是多阶段的决策问题，特别要注意没有明显的时段 背景的问题如何化归为多阶段的决策问题。背景的问题如

30、何化归为多阶段的决策问题。2 准确、熟练地掌握动态规划的基本概念，特别是状态变量、准确、熟练地掌握动态规划的基本概念，特别是状态变量、 决决 策变量、状态转移律、指标函数、基本方程等。策变量、状态转移律、指标函数、基本方程等。.3.掌握最优化原理的内容。掌握最优化原理的内容。4.掌握逆序解法与顺序解法，主要是逆序解法。掌握逆序解法与顺序解法，主要是逆序解法。5.会判定动态规划问题的类型。会判定动态规划问题的类型。1.阶段阶段 2.状态状态 3.决策决策 4.策略策略 5.状态转移方程状态转移方程 6.指标函数和最优值函数指标函数和最优值函数 运筹学运筹学第六章 动态规划（2）出租汽车高负荷运行

31、效果？出租汽车高负荷运行效果？出租汽车低负荷运行效果？出租汽车低负荷运行效果？动态规划应用之三：生产计划调度问题生产计划调度问题 运筹学运筹学P 219 例例2 动态规划应用举例动态规划应用举例 动态规划求解动态规划求解 机器负荷分配问题机器负荷分配问题 某种机器可以在高低两种不同的负荷下生产，高负荷生产产某种机器可以在高低两种不同的负荷下生产，高负荷生产产量函数为量函数为G= 8 U1 其中其中U1 表示投入生产的机器数量，表示投入生产的机器数量， 年完年完好率好率A=0.7低负荷生产产量函数为低负荷生产产量函数为H=5Y, 其中其中Y 表示投入生产的机器表示投入生产的机器数量，数量， 年完

32、好率年完好率 B = 0. 9, 如果初始投入生产的机器如果初始投入生产的机器1000台，台，问如何安排生产，使在问如何安排生产，使在5年内生产的产品总量达到最大？年内生产的产品总量达到最大？第六章 动态规划（2）高负荷生产高负荷生产低负荷生产低负荷生产 运筹学运筹学动态规划建模动态规划建模1 划分阶段：年度划分阶段：年度2 状态变量：状态变量： SK为为K 年度完好的机器数年度完好的机器数3 决策变量：决策变量： UK为为K 年度分配高负荷生产的机器数，年度分配高负荷生产的机器数， SK UK为为K 年度年度 低负荷生产的机器数低负荷生产的机器数4 状态转移方程：状态转移方程： SK1 0.

33、7 UK + 0. 9 ( SK UK )5 指标函数：指标函数： VK为为K 年度产量年度产量 ， VK8 UK + 5 ( SK UK ) MAXV1 + V2 + V3 + V4 + V5 6 递推公式：递推公式： F6 (S6) =0 F6 (S6)表示当表示当6年度完好的机器数年度完好的机器数S6时，从时，从6年到年到5年最大产量年最大产量 FK (SK) = MAX8 UK + 5 ( SK UK ) + FK+1 0.7 UK + 0. 9 ( SK UK ) 第六章 动态规划（2）FK (SK)表示当表示当K 年度完好的机器数年度完好的机器数SK时，从时，从k年到年到5年最大产

34、量年最大产量 运筹学运筹学K5F5 (S5) = MAX8 U5 + 5 ( S5 U5 ) + F60.7 U5 + 0. 9 ( S5 U5 ) 因为因为F60.7 U5 + 0. 9 ( S5 U5 ) 0F5 (S5) = MAX8 U5 + 5 ( S5 U5 ) MAX3 U5 + 5 S5 U5 = S5 , 当当U5 = S5 , F5 (S5) 8 S5K4F4 (S4) = MAX8 U4 + 5 ( S4 U4 ) + F50.7 U4 + 0. 9 ( S4 U4 ) = MAX8 U4 + 5 ( S4 U4 ) + 80.7 U4 + 0. 9 ( S4 U4 )

35、= MAX1. 4 U4 + 12 . 2 S4 U4 = S4 , 当当U4 = S4 , F4 (S4) 13 . 6 S4 同理，当同理，当U3 = S3 F3 (S3) 17 . 5 S3当当U2 =0 , F2 (S2) 20 . 8 S2 当当U1 = 0 , F1 (S1) 23 .7 S1第六章 动态规划（2） 运筹学运筹学最优解：前两年完好机器全部低负最优解：前两年完好机器全部低负荷生产，后三年完好机器全部高负荷生产，后三年完好机器全部高负荷生产，最优产量荷生产，最优产量23700台台第六章 动态规划（2） 运筹学运筹学动态规划（动态规划（3 3） 运筹学运筹学P226 应用

36、举例应用举例 固定资金分配固定资金分配有有N个企业，个企业， 都需要两种资源，对于第都需要两种资源，对于第K个企业，如果用第个企业，如果用第1种资种资源源 XK ，用第，用第2种资源种资源 YK ,可以得到利润可以得到利润 RK (XK , YK) , 第第1种资源种资源 的的单位价格为单位价格为A, 第第2种资源种资源 的单位价格为的单位价格为B, 现有资金现有资金Z, 问应该购买问应该购买第第1种资源（设为种资源（设为X） 和第和第2种资源（设为种资源（设为Y） 各多少单位分配到各多少单位分配到N个企业，可以使总利润达到最大？个企业，可以使总利润达到最大？第六章 动态规划（3）动态规划应用

37、之二：资源分配问题资源分配问题 运筹学运筹学有有N个企业，个企业， 都需要两种资源，对于第都需要两种资源，对于第K个企业，如果用第个企业，如果用第1种资种资源源 XK ，用第，用第2种资源种资源 YK ,可以得到利润可以得到利润 RK (XK , YK) , 第第1种资源种资源 的的单位价格为单位价格为A, 第第2种资源种资源 的单位价格为的单位价格为B, 现有资金现有资金Z, 问应该购买问应该购买第第1种资源（设为种资源（设为X） 和第和第2种资源（设为种资源（设为Y） 各多少单位分配到各多少单位分配到N个企业，可以使总利润达到最大？个企业，可以使总利润达到最大？建立模型：目标建立模型：目标

38、 MAXR1 (X1 , Y1)+ R2 (X2 , Y2) +RN (XN , YN) 约束约束 X1 + X2 +XN X Y1+ Y2 + +YN Y AX+BY =Z 第六章 动态规划（3）1.阶段阶段 2.状态状态 3.决策决策 4.策略策略 5.状态转移方程状态转移方程 6.指标函数和最优值函数指标函数和最优值函数动态规划求解动态规划求解（略）（略） 运筹学运筹学第六章 动态规划（3）公司要对某种产品制定一个生产计划或者采购计划，已知初始库存为零公司要对某种产品制定一个生产计划或者采购计划，已知初始库存为零每阶段生产数量有上限（生产能力限制），每阶段需求已知，在每阶段生产数量有上限

39、（生产能力限制），每阶段需求已知，在N阶段阶段末库存为零，问如何制定生产或者采购计划，使生产和库存成本最小？末库存为零，问如何制定生产或者采购计划，使生产和库存成本最小？企业企业阶段生产计划？阶段生产计划？阶段采购计划？阶段采购计划？已知阶段需求（定单）已知阶段需求（定单）已知内部库存已知内部库存动态规划应用之三：生产计划调度问题生产计划调度问题 运筹学运筹学动态规划应用举例动态规划应用举例 ( P229 例例3) 生产计划（采购计划）与存贮问题：生产计划（采购计划）与存贮问题： Min生产费用生产费用+存贮费用存贮费用 存贮量存贮量=生产量生产量 - 需求量需求量 生产量生产量= 最大生产量

40、最大生产量 决策变量决策变量? 状态变量状态变量? 状态转移方程状态转移方程?第六章 动态规划（3）1.阶段阶段 2.状态状态 3.决策决策 4.策略策略 5.状态转移方程状态转移方程 6.指标函数和最优值函数指标函数和最优值函数 运筹学运筹学动态规划应用举例动态规划应用举例 ( P229 例例3) 生产计划（采购计划）与存贮问题：生产计划（采购计划）与存贮问题： Min生产费用生产费用+存贮费用存贮费用 存贮量存贮量=生产量生产量 - 需求量需求量 生产量生产量 MHK (VK) 表示表示K 阶段结束时库存量为阶段结束时库存量为VK 时的库存成本时的库存成本K 阶段总成本阶段总成本 CK (

41、XK) HK (VK) 第六章 动态规划（3）1.阶段阶段 2.状态状态 3.决策决策 4.策略策略 5.状态转移方程状态转移方程 6.指标函数和最优值函数指标函数和最优值函数 运筹学运筹学动态规划模型为：动态规划模型为：MinG=C1 (X1) H1 (V1) +CN (XN) HN (VN) V0 = VN = 0 VK = X1 - D1+ XK - DK =0 0 =XK 6K=1F1 (V1) = Min C1 (X1) H1 (V1) + F0 (V0) 第六章 动态规划（3） 运筹学运筹学动态规划应用之四：库存问题，采购问题库存问题，采购问题 (P234 例例6)不确定性采购问题

42、（随机动态规划）：不确定性采购问题（随机动态规划）：特点特点价格是随机的，状态以一定的概率出现价格是随机的，状态以一定的概率出现购买决策特点购买决策特点市场价格低于最优价格时买市场价格低于最优价格时买 市场价格高于最优价格时不买市场价格高于最优价格时不买 最后期限如果还没购买，无论什么价格都要买最后期限如果还没购买，无论什么价格都要买第六章 动态规划（3）答案应该满足：开始几周时间充分，非最低价不买，到中间几周有点着急答案应该满足：开始几周时间充分，非最低价不买，到中间几周有点着急 中等价也买，最后时刻则没有谈判的余地。中等价也买，最后时刻则没有谈判的余地。1.阶段阶段 2.状态状态 3.决策

43、决策 4.策略策略 5.状态转移方程状态转移方程 6.指标函数和最优值函数指标函数和最优值函数 运筹学运筹学第六章 动态规划（3） 单单 价价 概概 率率 500 0.3 600 0.3 700 0.4P234 例例6 某工厂在最近五周内需要采购一批原料，估计五周内有价某工厂在最近五周内需要采购一批原料，估计五周内有价 格波动如下表，求那一周以什么价格购买最好格波动如下表，求那一周以什么价格购买最好YK为状态变量，表示第为状态变量，表示第K周实际价格周实际价格XK为决策变量，取为决策变量，取0或者或者1，表示第，表示第K周购买或者不买周购买或者不买1.阶段阶段 2.状态状态 3.决策决策 4.

44、策略策略 5.状态转移方程状态转移方程 6.指标函数和最优值函数指标函数和最优值函数 运筹学运筹学第六章 动态规划（3）分析：采购期分析：采购期5周分成周分成5个阶段：每周价格看成为状态变量个阶段：每周价格看成为状态变量 YK为状态变量，表示第为状态变量，表示第K周实际价格周实际价格 XK为决策变量，取为决策变量，取0或者或者1，表示第，表示第K周购买或者不买周购买或者不买 YKE表示第表示第K周实际价格为周实际价格为YK时，而在以后采取最优策略时，采购时，而在以后采取最优策略时，采购 价格的期望值（最可能的值）价格的期望值（最可能的值） FK(YK) 表示第表示第K周实际价格为周实际价格为Y

45、K时时,从第从第K周到第周到第5周采用最优策略周采用最优策略 时，价格的最小期望值。时，价格的最小期望值。从最后一周开始计算，对于最后一周如果还没有购买，按市场价格购买，从最后一周开始计算，对于最后一周如果还没有购买，按市场价格购买，K=5, F5(500) = 500, F5(600) = 600, F5(700) = 700根据根据YKE 和和FK(YK) 的定义，的定义，K=4, 期望价格期望价格Y4E = 0.3 F5(500)+0.3F5(600) +0.4 F5(700) = 610价格为价格为500的概率为的概率为0.3, 价格为价格为600的概率为的概率为0.3, 价格为价格为

46、700的概率为的概率为0.4, 1.阶段阶段 2.状态状态 3.决策决策 4.策略策略 5.状态转移方程状态转移方程 6.指标函数和最优值函数指标函数和最优值函数 运筹学运筹学 500 Y4 =500F4(Y4)Min Y4 , Y4E = Min Y4 , 610 = 600 Y4 =600 610 Y4=700 第四周最优策略为第四周最优策略为X4 = 1 采购采购 如如Y4 =500或者或者Y4 =6000 等待等待 如如Y4 =700同理同理 K=3, 期望价格期望价格Y3E = 0.3 F4(500)+0.3F4(600) +0.4 F4(700) = 0.3 500 + 0. 36

47、00 + 0.4 610574 Y3 =500574 Y3=600或者或者700第三周最优策略为第三周最优策略为X3 = 1 采购采购 如如Y3 =5000 等待等待 如如Y3 =600或者或者Y3 =700第六章 动态规划（3）F3(Y3)Min Y3 , Y3E = Min Y3 , 574 =F4(Y4)表示第表示第4周实际价格为周实际价格为Y4时时 , 从第从第4周到第周到第5周采用最优策略时，价格的最小期望值周采用最优策略时，价格的最小期望值实际价格实际价格Y4期望价格期望价格Y4E实际价格实际价格Y3期望价格期望价格Y3E 运筹学运筹学F2(Y2)Min Y2 , Y2E = Mi

48、n Y2 , 552 = Y2 =500552 Y2=600或者或者700第二周最优策略为第二周最优策略为X2 = 1 采购采购 如如Y3 =5000 等待等待 如如Y3 =600或者或者Y3 =700F1(Y1)Min Y1 , Y1E = Min Y1 , 536 = Y2 =500536 Y2=600或者或者700第一周最优策略为第一周最优策略为X2 = 1 采购采购 如如Y3 =5000 等待等待 如如Y3 =600或者或者Y3 =700第六章 动态规划（3）动态规划解动态规划解：开始一二三周时间充分，非最低价不买，第四周：开始一二三周时间充分，非最低价不买，第四周有点着急有点着急中等

49、价也买，中等价也买，第五第五 周则没有谈周则没有谈 判的余地。判的余地。实际价格实际价格Y2期望价格期望价格Y2E实际价格实际价格Y1期望价格期望价格Y1E答案的确满足：开始几周时间充分，非最低价不买，到中间几周有点着急答案的确满足：开始几周时间充分，非最低价不买，到中间几周有点着急 中等价也买，最后时刻则没有谈判的余地。中等价也买，最后时刻则没有谈判的余地。 运筹学运筹学期望价格价期望价格价500概率概率0.3第第1周出现周出现500第第2周出现周出现500第第3周出现周出现500第第4周周出现出现500第第5周出现周出现500 第第2周出现周出现500=（第（第1周出现周出现600或者或者

50、700）并且（第）并且（第2周出现周出现500 ） （ 0.3 + 0.4 ） 0.3 0.7 0.3 第第5周出现周出现500=（第（第1,2,3周出现周出现600或者或者700）并且（第）并且（第4周出现周出现700） 并且（第并且（第5周出现周出现500 ） 0.7 0.7 0.7 0.40.3期望价格期望价格5000.3 1+ 0.7+ 0.7 0.7 + 0.7 0.7 0.7 + 0.7 0.7 0.7 0.4 + 6000.30.7 0.7 0.7+ 0.7 0.7 0.7 0.4 + 700 0.7 0.7 0.7 0.4 0.4 = 525 第六章 动态规划（3）（第（第5周

51、出现周出现700第第1，2，3周出现周出现600和和700 ，第，第4周出现周出现 700，第，第5周出现周出现 700 700 0.7 0.7 0.7 0.4 0.4 ）动态规划解动态规划解-决策效果：期望价格决策效果：期望价格 525 元元 运筹学运筹学动态规划（动态规划（4 4） 运筹学运筹学第六章 动态规划（4）第第1阶段到第阶段到第K阶段阶段=第第1阶段到第阶段到第K-1阶段阶段 + 第第K阶段阶段第第k阶段到第阶段到第n阶段阶段=第第k+1阶段到第阶段到第n阶段阶段 + 第第K阶段阶段第第1阶段到第阶段到第4阶段阶段=第第1阶段到第阶段到第3阶段阶段 + 第第4阶段阶段第第3阶段到

52、第阶段到第5阶段阶段=第第4阶段到第阶段到第5阶段阶段 + 第第3阶段阶段 运筹学运筹学动态规划应用之五：设备更新问题设备更新问题举例举例： （P244 例例 10）第六章 动态规划（4）状态变量？状态变量？决策变量？决策变量？指标函数？指标函数？逆推关系？逆推关系？一台设备，使用到某年，是买新的，还是继续使用？一台设备，使用到某年，是买新的，还是继续使用？是买新的（更新费用）是买新的（更新费用） ，继续使用（维护费用），继续使用（维护费用） 运筹学运筹学动态规划应用之五：设备更新问题设备更新问题举例举例： （P244 例例 10）状态变量状态变量机龄机龄 t决策变量决策变量设备更新，保留设备

53、设备更新，保留设备第第i阶段阶段 收入收入 Ii(t)第第i阶段阶段 运行费用运行费用 Oi(t) 第第i阶段到第阶段到第n阶段收益阶段收益Gi (t) 第第i阶段到第阶段到第n阶段阶段 =第第i阶段阶段+ 第第i+1阶段到第阶段到第n阶段阶段指标函数指标函数收益收益 = 收入收入-运行费用运行费用-更新费用更新费用 Ii(t) - Oi(t) - Ci(t)逆推关系：逆推关系：第六章 动态规划（4） 运筹学运筹学动态规划应用举例动态规划应用举例设备更新问题设备更新问题： （P244 例例 10）逆推关系：逆推关系：第六章 动态规划（4）Gi(t)=Max更新收益收益: Ii(0)- Oi(0

54、)- Ci(t)+aGi+1(1)保留收益保留收益: Ii(t)- Oi(t) +a Gi+1(t+1)a表示折现因子表示折现因子机龄为机龄为t保留机器后，下一阶段机龄为保留机器后，下一阶段机龄为t1更换机器后，下一阶段机龄为更换机器后，下一阶段机龄为1年年 运筹学运筹学第六章 动态规划（4）机器第一年购买机器第一年购买机器第二年购买机器第二年购买第三年购买第三年购买四年购四年购买买五五年年买买几年前购买机器几年前购买机器t=01234012301201012345收收入入I2221201816272524222926243028321816161414运运行行费费66881056895564

55、54889910更更新新费费2729323437293134363132333233343234363638O5(3)=9 :表示第表示第5年开始机龄为年开始机龄为3年的机器，购买年年的机器，购买年5 3 =2 年年 , 运行费用运行费用 9 运行费用运行费用 Oj(t) 表示第表示第j年开始机龄为年开始机龄为t年的机器，购买年年的机器，购买年j t 运筹学运筹学第六章 动态规划（4） i= 机器第一年购买机器第一年购买 几年前购买的机器几年前购买的机器机龄机龄t=0123412345收入收入Ii(t)22I1(0)21I2(1)20I3(2)18I4(3)16I5(4)18I1(1)16I1

56、(2)16I1(3)14I1(4)14I1(5)运行运行费费Oi (t)6O1(0)6O2(1)8O3(2)8O4(3)10O5(4)8O1(1)8O1(2)9O1(3)9O1(4)10O1(5)更新更新费费Ci (t)27C1(0)29C2(1)32C3(2)34C4(3)37C5(4)32C1(1)34C1(2)36C1(3)36C1(4)38C1(5)说明符号对应：说明符号对应：I5(4)16 ： 机器已经使用了机器已经使用了4年，购买年为年，购买年为541年，在第年，在第5年的年的 收入为收入为16万元万元O1(5)10 ：机器已经使用了：机器已经使用了5年，购买年为年，购买年为514

57、年前，第年前，第1年使用机器运行费为年使用机器运行费为10万元万元 运筹学运筹学第六章 动态规划（4） j=5, 从第从第5年开始计算时，机器使用了年开始计算时，机器使用了t= 1，2，3，4，5年年 G5（t）表示从第表示从第5年开始计算时，机器使用了年开始计算时，机器使用了t年最佳总收入：年最佳总收入：G5（t）=Max更新更新收益收益：I5（0）- O5（0）- C5（0）+ G6（1）保持保持收益收益： I5（t）- O5（t）+ G6（t+1）G5（1）=Max更新：更新：I5（0）- O5（0）- C5（0）+ G6（1） =32 4 - 33 + 0 = -5保持：保持： I5（

58、1）- O5（1）+ G6（1+1） = 28-5+0=23I5（1）=第第5年开始，年开始，5-1=4年购买，机龄年购买，机龄1年年= 23X5（1）= 保持保持 运筹学运筹学第六章 动态规划（4）同理，同理， G5（3）=13 ， X5（3）= 保持保持 G5（4）=6 ， X5（4）= 保持保持 G5（5）=4 ， X5（5）= 保持：第保持：第5年使用机龄年使用机龄5年，最好不更新，年，最好不更新， 因为更新的当年利润为负，反正因为更新的当年利润为负，反正 最后一年了。最后一年了。G5（2）=Max更新：更新：I5（0）- O5（0）- C5（0）+ G6（1） =32 4 - 33 + 0 = -5保持：保持： I5（2）- O5（2）+ G6（2+1） = 24-6+0=18I5（2）=第第5年开始，年开始，5-2=3年购买，机龄年购买，机龄2年年=18X5（2）