运筹学第七章 动态规划课件.ppt

《运筹学第七章 动态规划课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章动态规划一、多阶段决策问题优点：适用范围比较广泛；L·P、I·P、D·P缺点：a、维数障碍；b、无规范化的解题方法；例1：求最短路线问题某工厂从国外引进一台设备，有许多种运输方式AD3D1D2C3C1C2B2B1E1234例2、甲乙两方合资建厂，建厂初期，由乙方提供完好机器1000台，其它义务由甲方负责承担（如人员招聘、培训、管理），利润双方共享，共同经营5年，5年后，整个工厂归甲方所有，问应如何安排年度计划？已知：高负荷生产时，年产量S1=8u1(机器数，完好率为70%，折损率为30%)低负荷生产时，年产量S2=5u2(机器数，完好率为

2、90%）乙方：追求5年内产量达到最高甲方：5年后还有500台完好机器的条件下的最高产量分析：按年度划分为5个阶段，xi为决策变量即第I阶段投入高负荷生产时的机器数；yi为状态变量，即I阶段或I+1阶段的输入或输出机器数。12345最优化原理可叙述为：“一个过程的最优决策具有这样的性质，无论其初始状态或初始决策如何，从目前决策所导致的新状态开始，以后的一系列决策必须是最优决策。”三、基本术语：1、阶段：把一个庞大的项目体系，划分为若干子问题（划分的目的：是把后面一个最优阶段加到前一个里面，形成最优中干部分，依次向前逆序求解）2、状态：系数处于不同

3、阶段所具有的不同属性，用yk或xk表示。3、决策：本阶段做出的选择，作为状态变量的函数，用xk或uk表示。4、传递函数：是状态变量，决策变量的函数。5、阶段收益：是本阶段状态变量，决策变量的函数。6、策略：每阶段所做的选择构成一个序列，称策略。7、指标函数：从k阶段到k+1阶段最优的目标函数值（max,min），它是决策变量，状态变量的函数。8、边界条件：7-2D·P模型和求解一、D·P模型1、阶段划分：k=1,2…..n(按时间顺序和空间部位划分)2、状态变量：yk或xk(必须满足：a、描述受控阶段；b、无后效性；c、可知性)3、决策变量：x

4、k或uk4、状态转移方程：5、指标函数：6、边界条件：二、计算实例：例3、题目同例1：解：1、阶段划分：按年度划分为5个阶段，即k=1,2..52、状态变量：yk(表示k年初的完好机器数）3、决策变量：uk（表示第k年分配在高负荷下生产的机器数）123454、状态转移方程式：5、最优指标函数：6、边界条件：（1）从乙方考虑，五年内达到最高产量？回溯过程：（2）从甲方考虑：即五年后还有500台完好机器的条件下的最高产量？解：根据题意知：回溯过程：7-3D·P程序及应用举例项目基金1230000404520508070457012090758016

5、0105110100200120150130例1、某部拟将200万元建设基金分配给三个水利工程，它们获得不同的资金后，产生的收益也不同，如何分配，使总收益最大？解：建模：1、阶段划分：以3个水利工程为3个阶段；2、状态变量yk:(0≤yk≤200)3、决策变量xk；4、状态转移方程：5、vk—查表可得；6、指标函数：7、边界条件：f4=0123解：k=3时04080120160200040801201602000507080100130f2(y2)x2y204080120160200004050*208070*70*45120809095*75

6、160100100115125*110200130120125145160*150K=2时X1*(y1)04080120160200y1=200200200200200200200f1(y1)160170*165160155120K=1时回溯过程：312解：建模：1、阶段划分：以x1，x2，x3分别划分为3个阶段；2、状态变量yk；3、决策变量xk；4、状态转移方程：5、指标函数：6、阶段收益:7、边界条件：回溯过程：12解：建模1、阶段划分：按x1，x2划分为两个阶段；2、状态变量yk，zk；3、决策变量xk；4、状态转移方程：5、6、7、边

7、界条件：回溯过程：例4、某住宅公司拟建甲、乙、丙三类住宅出售；该公司目前拥有350万资金，三类住宅耗资以及建好后售价如下，求该公司最大售房收入，每类住宅最多不超过3幢。类型耗资售价（单位：10万元）甲1025乙611丙37解：设甲、乙、丙三类住宅的数量为x1，x2，x3套：建模：1、阶段划分：以x1，x2，x3划分为三个阶段；2、状态变量：yk3、决策变量：xk4、状态转移方程:5、6、指标函数：7、边界条件：123y3x3V3=C3·x3y4=y3－a3x3f4f3=v3+f40000001001002002003~5170~2076~821

8、40~20149~353212~26021K=3时k=2时y2x2v2=c2·x2y3=y2－a2x2f3=v3+f4f2=v2+f3500577*1