《运筹学动态规划新a管理资料课件》由会员分享，可在线阅读，更多相关《运筹学动态规划新a管理资料课件（86页珍藏版）》请在金锄头文库上搜索。
1、作业：作业：P215 8.1 8.2第八章第八章 动态规划动态规划第一节第一节 多阶段决策问题多阶段决策问题 动态规划是用来求解多阶段决策问题的。动态规划是用来求解多阶段决策问题的。运筹学动态规划(新)a管理资料课件多阶段决策问题：可将问题分为若干个相互联系多阶段决策问题：可将问题分为若干个相互联系的阶段，在每一阶段分别对应着若干个可以选择的阶段，在每一阶段分别对应着若干个可以选择的决策，当每个阶段的决策选定之后，也就确定的决策，当每个阶段的决策选定之后，也就确定了问题的一个决策过程。将各阶段的决策综合起了问题的一个决策过程。将各阶段的决策综合起来，就构成了一个决策序列，称为问题的一个策来，就
2、构成了一个决策序列，称为问题的一个策略。略。 显然，决策不同，过程的策略也不同。对应显然，决策不同，过程的策略也不同。对应于每一个策略，都有一个确定的效果（值）。一于每一个策略，都有一个确定的效果（值）。一般情况下，策略不同，效果也不同。般情况下，策略不同，效果也不同。 多阶段决策的目的就是在所有可采取的策略多阶段决策的目的就是在所有可采取的策略中选取一个最优策略，使在一定条件下取得最优中选取一个最优策略，使在一定条件下取得最优的效果。的效果。运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件例三：将一个数c（ c0）分为n个部分c1,c2,
3、cn 之和 ，且ci0（i=1，2，n）,问如何分割使其乘积 最大？运筹学动态规划(新)a管理资料课件第二节第二节 最优化原理与动态规划数学模型最优化原理与动态规划数学模型2.1 基本思想 将多阶段问题转化为单阶段问题，按着目标要求和递推关系求出最优结果。（用逆序解法解例1）运筹学动态规划(新)a管理资料课件 例例1 最短路线问题。最短路线问题。 设有一个旅行者从图设有一个旅行者从图8-1中的中的A点出发，点出发，途中要经过途中要经过B、C、D等处，最后到达终点等处，最后到达终点E。从从A到到E有很多条路线可以选择，各点之间的有很多条路线可以选择，各点之间的距离如图中所示，问该旅行者应选择哪一
4、条距离如图中所示，问该旅行者应选择哪一条路线，使从路线，使从A到达到达E的总路程为最短。的总路程为最短。运筹学动态规划(新)a管理资料课件25375632455114633334C1C3D1AB1B3B2D2EC2运筹学动态规划(新)a管理资料课件25375632455114633334C1C3D1AB1B3B2D2EC2f5(E)=0f4(D1)=3f4(D2)=4f3(C1)=4f3(C2)=7f3(C3)=6f2(B1)=11f2(B2)=7f2(B3)=8f1(A)=11状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态
5、状态 A，（，（ A，B3）, B3 ,（B3，C2），），C2,（C2，D2）, D2，（，（D2，E）, E从从A到到E的最短路径为的最短路径为11，路线为，路线为AB3C2 D2 E 。运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件2.2 动态规划的基本概念动态规划的基本概念 阶段：阶段： 问题需要做出决策的步数。阶段用问题需要做出决策的步数。阶段用k表示。通常，表示。通常， k=1，2，n。（逆序编号与顺序编号顺序编号）。运筹学动态规划(新)a管理资料课件2. 状
6、态：系统某阶段的出发位置或特征、状况。状态：系统某阶段的出发位置或特征、状况。 通常一个阶段包含有若干个（设r个）状态。每一阶段所有状态的集合称为状态变量集合。用Sk= ski i=1,2,r表示。 第第k阶段的状态变量阶段的状态变量Sk应包含该阶段之前决应包含该阶段之前决策过程的全部信息，做到从该阶段后做出的决策策过程的全部信息，做到从该阶段后做出的决策只与该状态有关，与这之前的状态和决策相互独只与该状态有关，与这之前的状态和决策相互独立。（无后效性）立。（无后效性） 状态可以是一个数或一组数，也可能不是数；可以使离散的，也可以是连续的；可以是确定的，也可以是随机的。（维数障碍）（维数障碍）
7、运筹学动态规划(新)a管理资料课件3. 决策：决策： 当某阶段的状态给定以后，从该当某阶段的状态给定以后，从该状态演变到下一阶段某种状态的选择。状态演变到下一阶段某种状态的选择。 决策变量xk(sk)表示第k阶段状态为sk时对方案的选择。显然，它是状态的函数。 决策变量的取值要受到一定的限制（约束条件），用Dk(sk)表示k阶段状态为sk时的决策变量允许取值范围，称为允许决策集合，因而有 xk(sk) Dk(sk) 。运筹学动态规划(新)a管理资料课件4. 策略和子策略：策略和子策略：策略：动态规划问题各阶段决策组成的序策略：动态规划问题各阶段决策组成的序列总体。列总体。子策略：从某一阶段开始
8、到过程最终的决子策略：从某一阶段开始到过程最终的决策序列称为问题的子过程策略。策序列称为问题的子过程策略。 使问题达到最优效果最优效果的策略称为最优策略。运筹学动态规划(新)a管理资料课件25375632455114633334C1C3D1AB1B3B2D2EC2f5(E)=0f4(D1)=3f4(D2)=4f3(C1)=4f3(C2)=7f3(C3)=6f2(B1)=11f2(B2)=7f2(B3)=8f1(A)=11状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态 A，（，（ A，B3）, B3 ,（B3，C2），），
9、C2,（C2，D2）, D2，（，（D2，E）, E从从A到到E的最短路径为的最短路径为11，路线为，路线为AB3C2 D2 E 。运筹学动态规划(新)a管理资料课件5. 状态转移方程：状态转移方程： 从从sk的某一状态（值）的某一状态（值）出发，当决策变量出发，当决策变量xk(sk)的取值决定后，下的取值决定后，下一阶段状态变量一阶段状态变量sk+1 （的取值）也就随之确（的取值）也就随之确定。这种从上一阶段的某一状态（值）到下定。这种从上一阶段的某一状态（值）到下一阶段某一状态（值）的转移规律称为状态一阶段某一状态（值）的转移规律称为状态转移率，也称状态转移方程。记为：转移率，也称状态转移
10、方程。记为：运筹学动态规划(新)a管理资料课件6. 指标函数：指标函数：（1）阶段指标函数：对应某一阶段状态和）阶段指标函数：对应某一阶段状态和从该状态出发的一个决策的某种效益的度量。从该状态出发的一个决策的某种效益的度量。用用 v k= (sk，xk）表示。）表示。运筹学动态规划(新)a管理资料课件（2）过程指标函数）过程指标函数Vk,n ： 从状态从状态sk（k=1，2，n）出发至过程）出发至过程最终，当采取某种子策略时，按预定标准得到最终，当采取某种子策略时，按预定标准得到的效益值。它既与的效益值。它既与sk有关，也与有关，也与sk以后所选取以后所选取的策略有关。记作：的策略有关。记作：
11、运筹学动态规划(新)a管理资料课件（3）最优指标函数：指对某一确定状态）最优指标函数：指对某一确定状态sk选选取最优策略后得到的指标函数值。记作：取最优策略后得到的指标函数值。记作： f k(sk） =optVk,noptmax或或min。运筹学动态规划(新)a管理资料课件 上述基本概念在多阶段决策过程中的上述基本概念在多阶段决策过程中的关系见图关系见图8-2。运筹学动态规划(新)a管理资料课件2-3 最优化原理与动态规划的数学模型最优化原理最优化原理: (R.Bellman) 作为整个过程的最优策略具有这样的性质，作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对先前决策所无
12、论过去的状态和决策如何，对先前决策所形成的状态而言，余下的诸决策必构成最优形成的状态而言，余下的诸决策必构成最优策略。策略。即：最优策略的子策略都是最优的。即：最优策略的子策略都是最优的。运筹学动态规划(新)a管理资料课件动态规划的基本方程（逆序）动态规划的基本方程（逆序）：（递推关系式）：（递推关系式）运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件2-4 顺序解法状态转移率：运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件2-5 动态规划模型的分类1.确定性，随机性2.离散性，连续性3.阶段数固定定期决策过程；阶段数不固定或无限不定期或无期决策过程注
13、意事项：1.阶段2.状态变量3.决策变量4.状态转移率5.过程指标函数运筹学动态规划(新)a管理资料课件用动态规划解决实际问题的基本过程是：用动态规划解决实际问题的基本过程是：1.正确划分阶段，选择阶段变量正确划分阶段，选择阶段变量k；2.对每个阶段，正确选择状态变量对每个阶段，正确选择状态变量sk， 选择状态变选择状态变量时应当注意两点：一是要能够正确描述受控过程量时应当注意两点：一是要能够正确描述受控过程的演变特性，二是要满足无后效性；的演变特性，二是要满足无后效性；3.对每个阶段，正确选择决策变量对每个阶段，正确选择决策变量xk ； 4.列出相邻阶段的状态转移方程列出相邻阶段的状态转移方
14、程: sk+1= Tk(sk, xk (sk) )； 5. .列出按阶段可分的准则函数列出按阶段可分的准则函数V1,n ；6.写出递推方程和边界条件，建立基本方程；写出递推方程和边界条件，建立基本方程；7. .按照基本方程递推求解。按照基本方程递推求解。 以上步骤是动态规划法处理问题的基本步骤，以上步骤是动态规划法处理问题的基本步骤，其中的前六步是建立动态规划模型的步骤。其中的前六步是建立动态规划模型的步骤。运筹学动态规划(新)a管理资料课件第三节第三节 离散确定性动态规划模型的求解离散确定性动态规划模型的求解一、一、一维资源分配问题 假定有一种资源，其数量为a，现须将它分配给n个使用者，而使
15、总收益最大。若分配给第i个使用者的数量为xi(i=1,2,n)，且由此产生的收益(或损失）为gi(xi)(gi(xi)是xi的单调递增(或递减)函数)，则该问题的数学模型为：运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件 例4 某一警卫部门共有9支巡逻队，负责3个要害部位A、B、C的警卫巡逻。对每个部位可分别派出24支巡逻队，并且由于派出巡逻队数的不同，各部位预期在一段时期内可能造成的损失有差别，具体数字见表8-1。问该警卫部门应往各部位分别派多少支巡逻队，使总的预期损失为最小。运筹学动态规划(新)a管理资料课件(1)逆序解法：阶段k：要害部位（k=1，2，3） 。状态变
16、量sk：每个阶段初拥有的可派遣的巡逻队数（s1=a=9） 。决策变量xk：对每个部位派遣的巡逻队数 。 Dk(sk) = xk(sk) 2 xk(sk) 4 （k=1,2,3）。s1 s2 s3 s4 运筹学动态规划(新)a管理资料课件状态转移方程： sk+1= sk xk (k=1,2,3)指标函数（递推方程） fk(sk) ： s1 s2 s3 s4运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件X3* =2运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资
17、料课件作业：作业：P218 8.15二、设备负荷问题运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件例：某种机器可在高低两种不同的负荷下运转，高负荷运转时，年损坏率为30%，每台机器的年收益为8万元；低负荷运转时，年损坏率为10%，每台机器的年收益为5万元。若第一年初有1000台设备，问每年如何安排生产，可使得5年内的总收益最大。运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件第四节第四节 离散随机性动态规划模型的求解离
18、散随机性动态规划模型的求解作业：作业：P216 8.4运筹学动态规划(新)a管理资料课件N第k+1个阶段可能的状态数；pi（i=1,2,.N）给定状态sk和决策xk的情况下，下一个可能到达状态的概率；ci（或vi ）（i=1,2,.N）从k阶段状态sk转移到k+1阶段状态为i时的指标函数值。基本方程：运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件作业：作业：P216 8.8第五节第五节 一般问题的动态规划解法一般问题的动态规划解法一一、用动态规划求解非线性规划问题运筹学动
19、态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件0R220，2)内一阶导数大于零，故为增函数。内一阶导数大于零，故为增函数。运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件作业：P217 8.9(a) 选作二、用动态规划求解线性规划问题补例：运筹学动态规划(新)a管理资料课件R11=4, R21=12, R31=18R13=R12 - 0R23=R22 - 2X2R33=R32 - 2X2运筹学
20、动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件三、背包问题运筹学动态规划(新)a管理资料课件作业：P215 8.3运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件离散离散运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件四、生产计划问题运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件0x44=d运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件五、二维资源分配问题运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件运筹学动态规划(新)a管理资料课件
