动态规划与静态规划的关系

《动态规划与静态规划的关系》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、动态规划与静态规划的关系动态规划与静态规划(线性和非线性规划等)研究的对象本质上都是在若干约束条件下的函数极值问题。两种规划在很多情况下原则上可以相互转换。动态规划可以看作求决策u1,u2,...,un ，使指标函数V1n(xl,u1,u2,...,un)达到最优(最大或最小)的极值问题，状态转移方程、端点条件以及允许状态集、允许决策集等是约束条件，原则上可以用非线性规划方法求解。一些静态规划只要适当引入阶段变量、状态、决策等就可以用动态规划方法求解。下面用例子说明：[例11] 用动态规划解下列非线性规划:其中gk(uk)为任意的已知函

2、数。解：按变量uk的序号k划分阶段，看作n段决策过程；设状态为x1,x2,..xn，取问题中的变量u1,u2,..,un为决策；状态转移方程为：取gk(uk)为阶段指标，最优值函数的基本方程为(注意到xn+1=0)：解此动态规划即可得到原静态规划的解。上面这个静态规划的模型有很多实际应用，比如下面这个问题：[例12]InflateThemorepointsstudentsscoreinourcontests,thehappierwehereattheUSACOare.Wetrytodesignourcontestssothatpeopl

3、ecanscoreasmanypointsaspossible,andwouldlikeyourassistance.Wehaveseveralcategoriesfromwhichproblemscanbechosen,wherea"category"isanunlimitedsetofcontestproblemswhichallrequirethesameamountoftimetosolveanddeservethesamenumberofpointsforacorrectsolution.Yourtaskiswriteapro

4、gramwhichtellstheUSACOstaffhowmanyproblemsfromeachcategorytoincludeinacontestsoastomaximizethetotalnumberofpointsinthechosenproblemswhilekeepingthetotalsolutiontimewithinthelengthofthecontest.Theinputincludesthelengthofthecontest,M(1<=M<=10,000)(don'tworry,youwon'thaveto

5、competeinthelongercontestsuntiltrainingcamp)andN,thenumberofproblemcategories,where1<=N<=10,000.EachofthesubsequentNlinescontainstwointegersdescribingacategory:thefirstintegertellsthenumberofpointsaproblemfromthatcategoryisworth(1<=points<=10000);thesecondtellsthenumbero

6、fminutesaproblemfromthatcategorytakestosolve(1<=minutes<=10000).Yourprogramshoulddeterminethenumberofproblemsweshouldtakefromeachcategorytomakethehighest-scoringcontestsolvablewithinthelengthofthecontest.Remember,thenumberfromanycategorycanbeanynonnegativeinteger(0,one,o

7、rmany).Calculatethemaximumnumberofpossiblepoints.PROGRAMNAME:inflateINPUTFORMATLine1:M,N--contestminutesandnumberofproblemclassesLines2-N+1:Twointegers:thepointsandminutesforeachclassSAMPLEINPUT(fileinflate.in)3004100602501201201003520OUTPUTFORMATAsinglelinewiththemaximu

8、mnumberofpointspossiblegiventheconstraints.SAMPLEOUTPUT(fileinflate.out)605显而易见，上面这个例题的数学模型就是例11的规划模型。与