動(dòng)態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)系動(dòng)態(tài)規(guī)劃與靜態(tài)規(guī)劃（線性和非線性規(guī)劃等）研究的對(duì)象本質(zhì)上都是在若干約束條件下的函數(shù)極值問題。兩種規(guī)劃在很多情況下原則上可以相互轉(zhuǎn)換。動(dòng)態(tài)規(guī)劃可以看作求決策u1,u2，...,un，使指標(biāo)函數(shù)V1n（X],U],u2，...,un）達(dá)到最優(yōu)（最大或最小）的極值問題，狀態(tài)轉(zhuǎn)移方程、端點(diǎn)條件以及允許狀態(tài)集、允許決策集等是約束條件，原則上可以用非線性規(guī)劃方法求解。一些靜態(tài)規(guī)劃只要適當(dāng)引入階段變量、狀態(tài)、決策等就可以用動(dòng)態(tài)規(guī)劃方法求解。下面用例子說明：[例11]用動(dòng)態(tài)規(guī)劃解下列非線性規(guī)劃:max￡（虬）；上二1s.t.￡蜘二務(wù)虬乏。止二1其中g(shù)k（uk）為任意的已知函數(shù)。解:按變量uk的序號(hào)k劃分階段，看作n段決策過程；設(shè)狀態(tài)為x1,x2,..xn，取問題中的變量u1,u2,..,un為決策；狀態(tài)轉(zhuǎn)移方程為：取gk（uk）為階段指標(biāo)，最優(yōu)值函數(shù)的基本方程為（注意到xn+1=0）：兀(*)二懸碧［或(虬)+冗+i(知+1)L*=割)頊解此動(dòng)態(tài)規(guī)劃即可得到原靜態(tài)規(guī)劃的解。上面這個(gè)靜態(tài)規(guī)劃的模型有很多實(shí)際應(yīng)用，比如下面這個(gè)問題：［例12］InflateThemorepointsstudentsscoreinourcontests,thehappierwehereattheUSACOare.Wetrytodesignourcontestssothatpeoplecanscoreasmanypointsaspossible,andwouldlikeyourassistance.Wehaveseveralcategoriesfromwhichproblemscanbechosen,wherea"category"isanunlimitedsetofcontestproblemswhichallrequirethesameamountoftimetosolveanddeservethesamenumberofpointsforacorrectsolution.YourtaskiswriteaprogramwhichtellstheUSACOstaffhowmanyproblemsfromeachcategorytoincludeinacontestsoastomaximizethetotalnumberofpointsinthechosenproblemswhilekeepingthetotalsolutiontimewithinthelengthofthecontest.Theinputincludesthelengthofthecontest,M(1<=M<=10,000)(don'tworry,youwon'thavetocompeteinthelongercontestsuntiltrainingcamp)andN,thenumberofproblemcategories,where1<=N<=10,000.EachofthesubsequentNlinescontainstwointegersdescribingacategory:thefirstintegertellsthenumberofpointsaproblemfromthatcategoryisworth(1<=points<=10000);thesecondtellsthenumberofminutesaproblemfromthatcategorytakestosolve(1<=minutes<=10000).Yourprogramshoulddeterminethenumberofproblemsweshouldtakefromeachcategorytomakethehighest-scoringcontestsolvablewithinthelengthofthecontest.Remember,thenumberfromanycategorycanbeanynonnegativeinteger(0,one,ormany).Calculatethemaximumnumberofpossiblepoints.PROGRAMNAME:inflateINPUTFORMATLine1:M,N--contestminutesandnumberofproblemclassesLines2-N+1:Twointegers:thepointsandminutesforeachclassSAMPLEINPUT(fileinflate.in)3004100602501201201003520OUTPUTFORMATAsinglelinewiththemaximumnumberofpointspossiblegiventheconstraints.SAMPLEOUTPUT(fileinflate.out)605顯而易見，上面這個(gè)例題的數(shù)學(xué)模型就是也1的規(guī)劃模型。與靜態(tài)規(guī)劃相比，動(dòng)態(tài)規(guī)劃的優(yōu)越性在于：能夠得到全局最優(yōu)解。由于約束條件確定的約束集合往往很復(fù)雜，即使指標(biāo)函數(shù)較簡單，用非線性規(guī)劃方法也很難求出全局最優(yōu)解。而動(dòng)態(tài)規(guī)劃方法把全過程化為一系列結(jié)構(gòu)相似的子問題，每個(gè)子間題的變量個(gè)數(shù)大大減少，約束集合也簡單得多，易于得到全局最優(yōu)解。特別是對(duì)于約束集合、狀態(tài)轉(zhuǎn)移和指標(biāo)函數(shù)不能用分析形式給出的優(yōu)化問題，可以對(duì)每個(gè)子過程用枚舉法求解，而約束條件越多，決策的搜索范圍越小，求解也越容易。對(duì)于這類問題，動(dòng)態(tài)規(guī)劃通常是求全局最優(yōu)解的唯一方法。可以得到一族最優(yōu)解。與非線性規(guī)劃只能得到全過程的一個(gè)最優(yōu)解不同，動(dòng)態(tài)規(guī)劃得到的是全過程及所有后部子過程的各個(gè)狀態(tài)的一族最優(yōu)解。有些實(shí)際問題需要這樣的解族，即使不需要，它們在分析最優(yōu)策略和最優(yōu)值對(duì)于狀態(tài)的穩(wěn)定性時(shí)也是很有用的。當(dāng)最優(yōu)策略由于某些原因不能實(shí)現(xiàn)時(shí)，這樣的解族可以用來尋找次優(yōu)策略。能夠利用經(jīng)驗(yàn)提高求解效率。如果實(shí)際問題本身就是動(dòng)態(tài)的，由于動(dòng)態(tài)規(guī)劃方法反映了過程逐段演變的前后聯(lián)系和動(dòng)態(tài)特征，在計(jì)算中可以利用實(shí)際知識(shí)和經(jīng)驗(yàn)提高求解效率。比如在策略迭代法中，實(shí)際經(jīng)驗(yàn)?zāi)軌驇椭x擇較好的初始策略，提高收斂速度。動(dòng)態(tài)規(guī)劃的主要缺點(diǎn)是：沒有統(tǒng)一的標(biāo)準(zhǔn)模型，也沒有構(gòu)造模型的通用方法，甚至還沒有判斷一個(gè)問題能否構(gòu)造動(dòng)態(tài)規(guī)劃模型的具體準(zhǔn)則(大部分情況只能夠憑經(jīng)驗(yàn)判斷是否適用動(dòng)態(tài)規(guī)劃)。這樣就只能對(duì)每類問題進(jìn)行具體分析，構(gòu)造具體的模型。對(duì)于較復(fù)雜的問題在選擇狀態(tài)、決策、確定狀態(tài)轉(zhuǎn)移規(guī)律等方面需要豐富的想象力和靈活的技巧性，這就帶來了應(yīng)用上的局限