数学建模动态规划

数学(shùxué)建模

动态规划动态规划问题(wèntí)实例动态规划的根本概念与原理动态规划应用举例第一页，共70页。1动态规划是解决多阶段(jiēduàn)决策过程最优化的一种方法。该方法是由美国数学家贝尔曼〔R.E.Bellman)等人在20世纪50年代初提出的。他们针对多阶段(jiēduàn)决策问题的特点，提出了解决这类问题的“最优化原理〞，并成功地解决了生产管理、工程技术等方面的许多问题，从而建立了运筹学的一个新的分支，即动态规划。Bellman在1957年出版了?DynamicProgramming?一书，是动态规划领域中的第一本著作。第二页，共70页。2动态规划(guīhuà)问题及实例动态规划是解决多阶段决策问题的一种方法，是现代企业管理中的一种重要决策方法，可用于最优路径问题、资源分配问题、生产方案和库存问题、投资(tóuzī)问题、装载问题、排序问题及生产过程的最优控制等。动态规划模型的分类：以“时间〞角度可分成：离散型和连续型。从信息确定与否可分成：确定型和随机型。从目标函数的个数可分成：单目标型和多目标型。第三页，共70页。3一、多阶段决策(juécè)过程多阶段决策(juécè)过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成假设干相互联系的阶段，在每个阶段都要做出决策(juécè)，全部过程的决策(juécè)是一个决策(juécè)序列，所以多阶段决策(juécè)过程也称为序贯决策(juécè)过程。这种问题就称为多阶段决策(juécè)问题。

二、多阶段决策(juécè)问题的特点过程可分为假设干个相互联系的阶段；每一阶段都对应着一组可供选择的决策(juécè)；每一决策(juécè)的选定即依赖于当前面临的状态，又影响以后总体的效果。第四页，共70页。4三、具体(jùtǐ)实例1、最短路线问题给定(ɡěidìnɡ)一个线路网络，要从A向F铺设(pūshè)一条输油管道，各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短？第五页，共70页。52、生产与存储(cúnchǔ)问题：某工厂每月需供给市场一定数量的产品。供给需求所剩余产品应存入仓库，一般地说，某月适当(shìdàng)增加产量可降低生产本钱，但超产局部存入仓库会增加库存费用，要确定一个每月的生产方案，在满足需求条件下，使一年的生产与存储费用之和最小。第六页，共70页。6动态规划(guīhuà)的根本概念与原理动态规划的根本概念阶段；状态(zhuàngtài)；决策和策略；状态(zhuàngtài)转移方程；指标函数。第七页，共70页。7一、根本(gēnběn)概念阶段：是指问题需要做出决策(juécè)的步数。阶段总数常记为n，相应的是n个阶段的决策(juécè)问题。阶段的序号常记为k，称为阶段变量，k=1,2,…,n.k即可以是顺序编号也可以是逆序编号，常用顺序编号。状态：各阶段开始时的客观条件，第k阶段的状态常用(chánɡyònɡ)状态变量表示，状态变量取值的集合成为状态集合，用表示。例如，案例1中，第八页，共70页。8AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段(jiēduàn)第2阶段(jiēduàn)第3阶段(jiēduàn)第4阶段第5阶段状态1状态2状态3状态4状态5状态6第九页，共70页。9决策：是指从某阶段(jiēduàn)的某个状态出发，在假设干个不同方案中做出的选择(xuǎnzé)。表示决策的变量，称为决策变量，用表示。表示第k阶段当状态处于sk时的决策变量。例如(lìrú)：表示走到C阶段,当处于C2路口时，下一步奔D1.时的允许决策集合记为，例如：决策变量允许的取值范围称为允许决策集合，第k阶段状态为第十页，共70页。10状态转移(zhuǎnyí)方程：是从上一阶段的某一状态值转变为下一阶段某一状态值的转移(zhuǎnyí)规律，用表示(biǎoshì)。策略：一个按顺序排列的决策组成的集合(jíhé)。由每段的决策按顺序排列组成的决策函数序列称为k子过程策略。简称子策略，记为。即当k=1时，此决策函数序列成为全过程的一个策略，简称策略，记为：在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合，用P表示。第十一页，共70页。11指标函数(hánshù)：阶段指标函数(hánshù)和过程指标函数(hánshù)。阶段指标函数(hánshù)是指第k阶段(jiēduàn)从状态出发，采取决策时的效益，用表示。而过程指标(zhǐbiāo)函数是从第k阶段的某状态出发，采取子策略效益之和：最优指标函数：表示从第k阶段状态为时采用最正确策略到过程终止时的最正确效益。记为时所得到的阶段第十二页，共70页。12其中(qízhōng)opt可根据具体情况取max或min。根本方程(fāngchéng)：此为逐段递推求和的依据，一般为：式中opt可根据(gēnjù)题意取max或min.例如，案例1的根本方程为：第十三页，共70页。13最优性原理(yuánlǐ)：最优策略的子策略必为最优。不管过去的状态和决策如何，从眼下直到(zhídào)最后的诸决策必构成最优子策略。动态规划(guīhuà)的优点：可把一个N维优化问题化成N个一维优化问题求解。求得最优解以后，可得所有子问题的最优解。动态规划的缺点：“一个〞问题，“一个〞模型，“一个〞求解方法。且求解技巧要求比较高，没有统一处理方法。状态变量维数不能太高，一般要求小于6。第十四页，共70页。14动态(dòngtài)规划应用举例例1最短路线问题(wèntí)根本思想：如果起点A经过B1,C1,D1,E1而到终点F，那么由C1出发经D1,E1到F点这条子路线，是从C1到F的最短路线。所以，寻找(xúnzhǎo)最短路线，应该从最后一段开始找，然后往前递推。第十五页，共70页。15状态变量：各路线(lùxiàn)的位置决策变量(biànliàng)：第k阶段当状态处于时，决定下一个状态的位置状态(zhuàngtài)转移方程：上一阶段到下一阶段的转移规那么指标函数：从状态出发，采取决策时的路程距离最优指标函数：第k阶段状态为时且采用最正确走线策略，使从k位置及以后的路线最短。第十六页，共70页。16逆序递推方程(fāngchéng)：〔1〕k=5时，状态(zhuàngtài)它们(tāmen)到F点的距离即为最短路。AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第十七页，共70页。17AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143〔2〕k=4时，状态(zhuàngtài)它们到F点需经过(jīngguò)中途点E，需一一分析(fēnxī)从E到F的最短路：先说从D1到F的最短路有两种选择：经过E1,E2,比较最短。第十八页，共70页。18AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143这说明(shuōmíng)由D1到F的最短距离为7，其路径为相应(xiāngyīng)的决策为：第十九页，共70页。19这说明(shuōmíng)由D2到F的最短距离为5，其路径为相应(xiāngyīng)的决策为：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第二十页，共70页。20AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即D3到F的最短距离为5，其路径(lùjìng)为相应(xiāngyīng)的决策为：第二十一页，共70页。21〔3〕k=3时，状态(zhuàngtài)这说明(shuōmíng)由C1到F的最短距离为12，相应的决策为AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第二十二页，共70页。22AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即由C2到F的最短距离为10，相应(xiāngyīng)的决策为第二十三页，共70页。23即由C3到F的最短距离为8，相应(xiāngyīng)的决策为即由C4到F的最短距离为9，相应(xiāngyīng)的决策为AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第二十四页，共70页。24AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143〔4〕k=2时，状态(zhuàngtài)这说明由B1到F的最短距离为13，相应(xiāngyīng)的决策为第二十五页，共70页。25即由B2到F的最短距离为15，相应(xiāngyīng)的决策为AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第二十六页，共70页。26AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143〔1〕k=1时，只有一个(yīɡè)状态点A,那么即由A到F的最短距离为17，相应(xiāngyīng)的决策为第二十七页，共70页。27所以(suǒyǐ)最优路线为：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143再按计算(jìsuàn)顺序反推可得最优决策序列：第二十八页，共70页。28顺序(shùnxù)递推方程：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143例1：1阶段(jiēduàn)2阶段(jiēduàn)3阶段4阶段5阶段行走方向第二十九页，共70页。29AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143K=1时注意(zhùyì)到：所以(suǒyǐ)第三十页，共70页。30K=2时AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第三十一页，共70页。31K=3时AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第三十二页，共70页。32AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143或类似(lèisì)地，可算出：第三十三页，共70页。33最优策略(cèlüè)：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143或第三十四页，共70页。34最短路径(lùjìng)：最短路(duǎnlù)长：注：顺序解法与逆序解法无本质区别，一般来说，当初始(chūshǐ)状态给定时用逆序解法，当终止状态给定时用顺序解法。假设问题给定了一个初始(chūshǐ)状态与一个终止状态，那么两种方法均可使用。第三十五页，共70页。35例2资源分配问题(wèntí)〔离散型〕例：设有6万元资金(zījīn)用于4个工厂的扩建，每个工厂的利润增长额同投资额的大小有关，见下表。问应如何确定对这四个工厂的投资额，使总利润增长额最大？投资额(j)工厂(i)010020030040050060010204260758590202545576570733018396178909540284765748085表1利润(lìrùn)增长额〔百元〕第三十六页，共70页。36解：把对四个工厂的投资依次看成4个阶段的决策(juécè)过程，确定对第k个工厂的投资额看成第k个阶段(jiēduàn)的决策，k=1,2,3,4。图示如下：状态变量：可用于第k,k+1,…n个工厂(gōngchǎng)的投资额。决策变量：第k阶段对第k个工厂的投资额。允许决策集：工厂1工厂2工厂3工厂4投资x1投资x2投资x3投资x4状态状态状态第三十七页，共70页。37状态转移(zhuǎnyí)方程：其中(qízhōng)阶段指标函数(hánshù)：第k阶段投资元时所产生的利润。〔见上表〕最优指标函数：第k阶段状态为且采取最正确投资策略，从第k个工厂以及以后的最大总利润。逆序法根本递推方程：第三十八页，共70页。38工厂(gōngchǎng)1工厂(gōngchǎng)2工厂(gōngchǎng)3工厂4投资x1投资x2投资x3投资x4状态状态状态投资额(j)工厂(i)010020030040050060040284765748085

表1利润增长额

〔百元〕解：〔1〕k=4时考虑：假设到最后一个，第4个工厂投资时，还有资金，假设投资于第4个工厂的资金为，那么最大利润为第三十九页，共70页。39工厂(gōngchǎng)1工厂(gōngchǎng)2工厂(gōngchǎng)3工厂4投资x1投资x2投资x3投资x4状态状态状态投资额(j)工厂(i)010020030040050060040284765748085

表1利润增长额

〔百元〕〔注意到此时=0〕第四十页，共70页。40自然(zìrán)问：现在还有多少钱？即=？=0，100，200，300，400，500，600都有可能(kěnéng)。下面分情况(qíngkuàng)讨论：工厂1工厂2工厂3工厂4投资x1投资x2投资x3投资x4状态状态状态投资额(j)工厂(i)010020030040050060040284765748085

表1利润增长额

〔百元〕第四十一页，共70页。41时，时，其他种情况类似讨论(tǎolùn)，我们把所有的结果汇总成一个表2。投资额(j)工厂(i)010020030040050060040284765748085表1利润(lìrùn)增长额〔百元〕第四十二页，共70页。4201002003004005006000100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600表2

k=4时决策表投资额(j)工厂(i)010020030040050060010204260758590202545576570733018396178909540284765748085表1利润(lìrùn)增长额〔百元〕第四十三页，共70页。43〔2〕k=3时到第三个工厂投资(tóuzī)时，可利用的资金还有，假设向第三个工厂投资〔万元〕，那么(nàme)自此即以后最大利润为：表1利润(lìrùn)增长额〔百元〕投资额(j)工厂(i)010020030040050060030183961789095同样问：=？，即现在还有多少钱？它是允许决策集上界。同理第四十四页，共70页。44仅举一例(yīlì)：投资额(j)工厂(i)010020030040050060030183961789095表1利润(lìrùn)增长额〔百元〕第四十五页，共70页。4501002003004005006000100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600表2

k=4时决策表投资额(j)工厂(i)010020030040050060030183961789095表1利润(lìrùn)增长额〔百元〕第四十六页，共70页。46所有(suǒyǒu)情况讨论结果汇总成下表：010020030040050060001002003004005006000+00+2818+00+4718+2839+00+6518+4739+2861+00+7418+6539+4761+2878+00+8018+7439+6561+7478+2890+00+8518+8039+7461+6578+4790+2895+0028476789108126000200300300300表3

k=3时决策表第四十七页，共70页。47〔3〕k=2时仅举一例(yīlì)：第四十八页，共70页。48投资额(j)工厂(i)010020030040050060020254557657073表1利润(lìrùn)增长额〔百元〕第四十九页，共70页。49010020030040050060001002003004005006000+00+2818+00+4718+2839+00+6518+4739+2861+00+7418+6539+4761+2878+00+8018+7439+6561+7478+2890+00+8518+8039+7461+6578+4790+2895+0028476789108126000200300300300表3

k=3时决策表第五十页，共70页。50关于(guānyú)的其它取值情况及相应的最优决策列于下表010020030040050060001002003004005006000+00+2825+00+4725+2845+00+6725+4745+2857+00+8925+6745+4757+2865+00+10825+8945+6757+4765+2870+00+12625+10845+8957+6765+4770+2873+002853739211413400100200100或200100200

表4k=2时决策表第五十一页，共70页。51〔4〕k=1时，此时(cǐshí)第五十二页，共70页。52投资额(j)工厂(i)010020030040050060010204260758590表1利润(lìrùn)增长额〔百元〕第五十三页，共70页。53010020030040050060001002003004005006000+00+2825+00+4725+2845+00+6725+4745+2857+00+8925+6745+4757+2865+00+10825+8945+6757+4765+2870+00+12625+10845+8957+6765+4770+2873+002853739211413400100200100或200100200表4k=2时决策表第五十四页，共70页。54汇一表格(biǎogé)：0100200300400500600600134134134133138113901340或100或200表5k=1时决策表此时(cǐshí)对应最大值134的有三个值：所对应(duìyìng)的最优策略分别为：时，由状态转移方程知：所对应的第五十五页，共70页。55010020030040050060001002003004005006000+00+2825+00+4725+2845+00+6725+4745+2857+00+8925+6745+4757+2865+00+10825+8945+6757+4765+2870+00+12625+10845+8957+6765+4770+2873+002853739211413400100200100或200100200表4k=2时决策表对应(duìyìng)的再由状态(zhuàngtài)转移方程对应(duìyìng)的第五十六页，共70页。56010020030040050060001002003004005006000+00+2818+00+4718+2839+00+6518+4739+2861+00+7418+6539+4761+2878+00+8018+7439+6561+7478+2890+00+8518+8039+7461+6578+4790+2895+0028476789108126000200300300300表3

k=3时决策表所对应(duìyìng)的再由状态转移(zhuǎnyí)方程对应(duìyìng)的第五十七页，共70页。5701002003004005006000100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600表2

k=4时决策表对应(duìyìng)的从而(cóngér)得一最优策略第五十八页，共70页。58同理