数学建模(动态规划)

动态规划教学内容：™动态规划问题实例™动态规划的基本概念与原理™动态规划的基本概念与原理™动态规划应用举例引言动态规划是解决多阶段决策过程最优化的一种方法。该方法是由美国数学家贝尔曼（R.E.Bellman)等人在20世该方法是由美国数学家贝尔曼（..e)等人在0世纪50年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多问题，从而建立了运筹学的一个新的分支，即动态规划。Bellman在1957年出版了《DynamicProgramming》一书，是动态规划领域中的第一本著作。动态规划问题及实例动态规划是解决多阶段决策问题的一种方法，是现代企业管理中的一种重要决策方法，可用于最优路径问题、资源分配问题生产计划和库存问题投资问题装载问题排分配问题、生产计划和库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。动态规划模型的分类动态规划模型的分类：以“时间”角度可分成：离散型和连续型。从信息确定与否可分成：确定型和随机型。从目标函数的个数可分成单目标型和多目标型从目标函数的个数可分成：单目标型和多目标型。动态规划问题及实例动态规划问题及实例一、多阶段决策过程多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策过程也称为序贯决策过程。这种问题就称为多阶段决策问题。二、多阶段决策问题的特点过程可分为若干个相互联系的阶段；每一阶段都对应过程可分为若干个相互联系的阶段；每阶段都对应着一组可供选择的决策；每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。动态规划问题及实例三具体实例三、具体实例1、最短路线问题给定一个线路网络，要从A向F铺设一条输油管道，各点间连线上的数字表示距离问应选择什么路线可使总距离最短？线上的数字表示距离，问应选择什么路线，可使总距离最短？动态规划问题及实例2生产与存储问题：2、生产与存储问题：某工厂每月需供应市场一定数量的产品。供应需求所某厂每月需供应市场定数量的产品供应需求所剩余产品应存入仓库，一般地说，某月适当增加产量可降低生产成本但超产部分存入仓库会增加库存费用降低生产成本，但超产部分存入仓库会增加库存费用，要确定一个每月的生产计划，在满足需求条件下，使一年的生产与存储费用之和最小。动态规划的基本概念与原理动态规划的基本概念阶段；状态；决策和策略；状态转移方程；指标数指标函数。动态规划的基本概念与原理动态规划的基本概念与原理一基本概念。基本概念阶段：是指问题需要做出决策的步数。阶段总数常记为n，相应的是n个阶段的决策问题。阶段的序号常记为k，称为阶段变量，k=12nk即可以是顺序编号也可以是逆序编号，变量，k=1,2,…,n.k即可以是顺序编号也可以是逆序编号，常用顺序编号。状态：各阶段开始时的客观条件，第k阶段的状态常用状态变量表示，状态变量取值的集合成为状态集合，用kskS变量表示，状态变量取值的集合成为状态集合，用表示。kk例如案例1中}{}{BBSAS例如，案例1中，}.,{},{2121BBSAS==状状状状状状状态状态状态状态状态状态C125B1C2D1E142368453564AB2C3D2DE2F5873486213B2C4D3743第1阶段第2阶段第3阶段第4阶段第5阶段决策是指从某阶段的某个状态出发在若干个不同方案中决策：是指从某阶段的某个状态出发，在若干个不同方案中做出的选择。表示决策的变量，称为决策变量，用表示。)(kksu表示第k阶段当状态处于sk时的决策变量。kk)(kksu例如：表示走到C阶段,当处于C2路口时，下一步到D123)(DCu=步到D1.决策变量允许的取值范围称为允许决策集合，第k阶段状态为时的允许决策集合记为，例如：)(kksD},,{)(32112CCCBD=ks策略：一个按顺序排列的决策组成的集合。由每段的决策按顺序排列组成的决策函数序列称为k子过程策略。简称子策略，记为。即当k=1时，此决策函数序列成为全过程的一个策略，简称策略记为策略，记为：在实际问题中，可供选择的策略有一定的范围，此范围称状态转移方程：是从上一阶段的某一状态值转变为下一阶段为允许策略集合，用P表示。某一状态值的转移规律，用)(usTs=表示),(1kkkkusTs=+表示。指标函数：分阶段指标函数和过程指标函数。阶段指标函数指标函数：分阶段指标函数和过程指标函数。阶段指标函数是指第k阶段从状态出发，采取决策时的效益，用ksku),(kkkusv表示。而过程指标函数是从第k阶段的某状态出发，采取子策略采取子策略效益之和时所得到的阶段效益之和：最优指标函数：表示从第k阶段状态为时采用最佳策略ks到过程终止时的最佳效益记为到过程终止时的最佳效益。记为其中opt可根据具体情况取max或min其中opt可根据具体情况取max或min。基本方程：此为逐段递推求和的依据，一般为：1()()opt{(,())(())},1,,2,1()0kkkkkkkkkkkkuDsfsvsusfusknnf+∈⎧=+=−⎪⎪⎪⎨⎪⎪式中opt可根据题意取max或min.11()0nnfs++⎪=⎪⎪⎩p例如，案例1的基本方程为：1()()min{(,())(())}5,4,3,2,1kkkkkkkkkkkkuDsfsdsusfusk+∈⎧=+=⎪⎪⎪⎨⎪66()0fs⎪=⎪⎪⎩最优性原理：最优策略的子策略必为最优不管过去的状态最优性原理：最优策略的子策略必为最优。不管过去的状态和决策如何，从眼下直到最后的诸决策必构成最优子策略。动态规划的优点：•可把一个N维优化问题化成N个一维优化问题求解。•函数方程中附加某些约束条件，可使求解更加容易。函数方程中附加某些约束条件，可使求解更加容易•求得最优解以后，可得所有子问题的最优解。动态规划的缺点动态规划的缺点：•“一个”问题，“一个”模型，“一个”求解方法。且求解技巧要求比较高，没有统一处理方法。动态规划应用举例动态规划应用举例例最短路线问题例1最短路线问题基本思想如果起点经过而到终点则由出基本思想：如果起点A经过B1,C1,D1,E1而到终点F，则由C1出发经D1,E1到F点这条子路线，是从C1到F的最短路线。所以，寻找最短路线应该从最后一段开始找然后往前递推寻找最短路线，应该从最后段开始找，然后往前递推。状态变量：各路线的位置s状态变量：各路线的位置决策变量：第k阶段当状态处于时，决定下一个ksks)(kksu决策变量：第k阶段当状态处于时，决定下个状态的位置状态转移方程上一阶段到下一阶段的转移规则kkk)(su状态转移方程：上一阶段到下一阶段的转移规则指标函数：从状态出发，采取决策时的路程距)(kksu指标函数：从状态出发，采取决策时的路程距离最优指标函数：第k阶段状态为时且采用最s最优指标函数：第k阶段状态为时且采用最佳走线策略，使从k位置及以后的路线最短。ksC1258AB1C2D1DE14368453564AB2C3D2D3E2F58773482313逆序递推方程：C437431()()min{(,())(())}5,4,3,2,1()0kkkkkkkkkkkkuDsfsdsusfuskfs+∈⎧=+=⎪⎪⎪⎨⎪=⎪⎪（1）k=5时，状态},{215EES=它们到F点的距离即为66()0fs=⎪⎪⎩最短路。,4)(15=Ef;3)(25=Ef,)(1*5FEu=.)(2*5FEu=C1258,)(1*5FEu=AB1C2D1DE14368453564.)(2*5FEu=AB2C3D2D3E2F58773482313C43743（2）k=4时，状态},,{3214DDDS=它们到F点需经过中途点E，需一一分析从D到F的最短路：先说从D1到F的最短路有两种选择：经过E1,E2,比较最短。C1258,)(1*5FEu=AB1C2D1DE14368453564.)(2*5FEu=AB2C3D2D3E2F58773482313C43743)}(),(),(),(min{)(252141511414EfEDdEfEDdDf++=7}3543i{.7}35,43min{=++=这说明由D1到F的最短距离为7，其路径为.11FED→→这说明由D1到F的最短距离为7，其路径为11相应的决策为：.)(11*4EDu=C1258,)(1*5FEu=AB1C2D1DE14368453564.)(2*5FEu=AB2C3D2D3E2F58773482313)(*EDu=C43743.)(114EDu=)}(),(),(),(min{)(252241512424EfEDdEfEDdDf++=5}3246min{++.5}32,46min{=++=这说明由D2到F的最短距离为5，其路径为.22FED→→这说明由D2到F的最短距离为5，其路径为22相应的决策为：)(*EDu=相应的决策为：.)(224EDu=C1258,)(1*5FEu=AB1C2D1DE14368453564.)(2*5FEu=AB2C3D2D3E2F58773482313)(*EDu=C43743.)(114EDu=.)(22*4EDu=)}(),(),(),(min{)(252341513434EfEDdEfEDdDf++=.5}33,41min{=++=即D到F的最短距离为5其路径为FED→→即D3到F的最短距离为5，其路径为.13FED→→相应的决策为：.)(13*4EDu=相应的决策为)(134C1258,)(1*5FEu=.)(13*4EDu=7)(=DfAB1C2D1DE14368453564.)(2*5FEu=7)(14=DfAB2C3D2D3E2F58773482313)(*EDu=5)(24=DfC43743.)(114EDu=.)(22*4EDu=5)(24Df5)(34=Df（3）k=3时，状态},,,{43214CCCCS=)}()()()(min{)(DfDCdDfDCdCf++)}(),(),(),(min{)(242131411313DfDCdDfDCdCf++=.12}58,75min{=++=},{这说明由C1到F的最短距离为12，相应的决策为.)(11*3DCu=C1258,)(1*5FEu=.)(13*4EDu=.)(11*3DCu=AB1C2D1DE14368453564.)(2*5FEu=.)(113DCu7)(14=DfAB2C3D2D3E2F58773482313)(*EDu=5)(24=DfC43743.)(114EDu=.)(22*4EDu=5)(34=Df)}(),(),(),(min{)(242231412323DfDCdDfDCdCf++=.10}55,74min{=++=.},7{即由C2到F的最短距离为10，相应的决策为.)(22*3DCu=)}(),(),(),(min{)(343332423333DfDCdDfDCdCf++=.8}54,53min{=++=C1258,)(1*5FEu=.)(13*4EDu=.)(11*3DCu=*AB1C2D1DE14368453564.)(2*5FEu=.)(22*3DCu=AB2C3D2D3E2F58773482313)(*EDu=5)(=DfC43743.)(114EDu=.)(22*4EDu=5)(24=Df5)(34=Df即由C3到F的最短距离为8，相应的决策为.)(23*3DCu=)}(),(),(),(min{)(343432424343DfDCdDfDCdCf++=9}5458min{=++=.9}54,58min{=++=即由C4到F的最短距离为9，相应的决策为.)(34*3DCu=C1258,)(1*5FEu=.)(13*4EDu=.)(11*3DCu=*AB1C2D1DE14368453564.)(2*5FEu=.)(22*3DCu=AB2C3D2D3E2F58773482313)(*EDu=.)(