動態(tài)規(guī)劃方法及其在資源分配問題中的應(yīng)用【畢業(yè)論文】

1、<p>　　本科畢業(yè)設(shè)計(論文)</p><p>　題 目：動態(tài)規(guī)劃方法及其在資源分配問題中的應(yīng)用</p><p>　學 院：</p><p>　學生姓名：</p><p>　專 業(yè)：信息與計算科學</p><p>　班 級：</p><p>　指導教師：<

2、;/p><p>　起止日期：</p><p><b>　　摘要</b></p><p>　　動態(tài)規(guī)劃問題是一個應(yīng)用極為廣泛的問題, 它在工程技術(shù)、最優(yōu)控制和生產(chǎn)調(diào)度等方面的應(yīng)用也是相當廣泛的, 動態(tài)規(guī)劃也是計算機科學和運籌學的重要內(nèi)容. 20世紀50年代初, 美國數(shù)學家R. E. Bellman等人在對多階段決策過程(Multistep decis

3、ion process)的優(yōu)化問題研究過程中, 提出了著名的最優(yōu)性原理(Principle of optimality), 把一類多階段過程轉(zhuǎn)化為一系列相互聯(lián)系的單階段規(guī)劃問題. 而最近幾十年來關(guān)于動態(tài)規(guī)劃在資源分配方面的研究有很大進展, 研究成果也是層出不窮, 本文基于以往學者的研究成果上對資源分配問題進行了分析與總結(jié), 并給出了動態(tài)規(guī)劃及其在資源分配問題的算法的求解過程, 也涉及在實際生活中的應(yīng)用. 最后介紹了現(xiàn)在流行的一些動態(tài)規(guī)劃

4、主要算法和實例, 并運用delphi, excel和lingo方法解決資源分配問題.</p><p>　　關(guān)鍵詞: 動態(tài)規(guī)劃;逆推法;資源分配問題;最優(yōu)性原理</p><p>　　Dynamic programming and its application in resource allocation problems</p><p><b>　　Ab

5、stract</b></p><p>　　Dynamic programming is a very extensive application, which is widely used in production scheduling, engineering technology and optimal control. And the dynamic programming is the im

6、portant content of computer science and operational research. R. E. Bellman who is the United States mathematician, proposed the famous idea which is the optimum Principle. When he studyed the optimization problem of Mul

7、tistep decision process in the 1950s, he translated multistep decision process into a series of int</p><p>　　algorithm in the dynamic programming and the resource allocation problems, also involves in the ac

8、tual life application. At last, the paper introduces some mainly algorithm and practical examples which is often used in dynamic programming, and using Delphi, excel and lingo methods to solve resource allocation problem

9、s.</p><p>　　Keywords: Dynamic programming; Inverse push method; The method of Resource allocation problems; Principle of optimality</p><p><b>　　目錄</b></p><p><b>　

10、　摘要I</b></p><p>　　AbstractII</p><p>　　1 前言……………1</p><p>　　2 理論基礎(chǔ)……………………………………………………………………………...………..2</p><p>　　2.1 相關(guān)定義3</p><p>　　2.2 動態(tài)規(guī)劃的最優(yōu)定

11、理5</p><p><b>　　3逆推法6</b></p><p>　　3.1 逆推過程6</p><p>　　3.2 結(jié)果計算過程7</p><p>　　3.3 逆推法的delphi實現(xiàn)………………………………………………………………...7</p><p>　　3.4 逆推法

12、的excel實現(xiàn)………………………………………………………………….13</p><p>　　3.5 逆推法的lingo實現(xiàn)………………………………………………………………….14</p><p>　　4 資源分配問題的其他算法簡要介紹……………………………………………... ........20</p><p>　　5 小結(jié)…………………………………………………

13、………………………………………...22</p><p><b>　　參考文獻23</b></p><p><b>　　致謝24</b></p><p><b>　　1 前言</b></p><p>　　動態(tài)規(guī)劃應(yīng)用非常廣泛, 在生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制中的最優(yōu)問題.

14、 例如最短路線、生產(chǎn)調(diào)度問題、設(shè)備更新、排序、裝載等, 在資源分配問題中尤其重要.</p><p>　　動態(tài)規(guī)劃問題已經(jīng)有幾十年的研究歷史, 在這幾十年中, 人們已經(jīng)建立了動態(tài)規(guī)劃問題比較完善的理論, 從R. E. Bellman提出的最優(yōu)性原理至今, 很多學者都對其進行了研究和改進并提出了很多新的算法, 根據(jù)動態(tài)規(guī)劃問題的計算過程的特殊性, 其每一階段求出最優(yōu)值是都要把相應(yīng)的狀態(tài)集合存入內(nèi)存中去, 從而造成了計

15、算機使用的內(nèi)存要成倍增加. 雖然也有不少方法減少了這種障礙, 如多項式逼近法, 逐次逼近法, 狀態(tài)微增法, 拉格朗日乘數(shù)法等等. 所以動態(tài)規(guī)劃在未來的發(fā)展空間將會大大提升, 由于其實用性較強所以其在實際生活中應(yīng)用還是相當廣泛的.</p><p>　　最近也有很多關(guān)于動態(tài)規(guī)劃其他方面問題的研究, 而且發(fā)展迅速, 但是本文主要講述的是動態(tài)規(guī)劃方法和其在資源分配問題中的應(yīng)用, 并不涉及庫存等問題. 下面簡要介紹一下本文

16、的大概內(nèi)容: 本文第一部分介紹與動態(tài)規(guī)劃問題有關(guān)的定義及定理, 第二部分介紹最常見的逆推算法, 第三部分簡要介紹有關(guān)動態(tài)規(guī)劃問題幾種其他算法, 后面一部分對本文講述的方法及舉例進行總結(jié), 最后一部分是致謝.</p><p><b>　　2 理論基礎(chǔ)</b></p><p><b>　　2.1 相關(guān)定義</b></p><p&

17、gt;　　從文獻中我們可以得出所有動態(tài)規(guī)劃問題都必須涉及到以下定義: </p><p>　　定義2.1我們把在整個動態(tài)規(guī)劃過程的一個自然劃分我們稱為階段, 通?？梢愿鶕?jù)時間順序或空間特征來劃分階段, 以下是按階段的次序解優(yōu)化問題.一般用表示階段變量.</p><p>　　例如: 由出發(fā)為, 由出發(fā)為, 依次下去從出發(fā)為, 共有個階段.</p><p>　　定義2.2

18、每個階段開始時過程所處的自然狀況叫作一個狀態(tài). 它應(yīng)能描述過程的特征并且具有無后效性, 即當某階段狀態(tài)給定時, 這個階段以后過程的演變過程與該階段以前各階段的狀態(tài)沒有關(guān)聯(lián). 一般來說還要求狀態(tài)是可以間接或者直接觀測到的.</p><p>　　描述某個狀態(tài)的變量稱為狀態(tài)變量(State variable). 變量所允許取值的集合稱為允許狀態(tài)集合(Set of admissible states). 第階段的狀態(tài)變量

19、用表示, 它不但可以表示一個實數(shù)更可以表示一個向量. 第階段的允許狀態(tài)集合用表示. 其中階段的決策過程共有狀態(tài)變量個, 表示演變的結(jié)果.</p><p>　　我們根據(jù)每個過程演變的具體分析, 可以把狀態(tài)變量分為離散的和連續(xù)的. 在分析的過程中有時將離散的變量連續(xù)化; 有時在計算過程中把變量離散化. 有時我們把狀態(tài)變量簡單地叫做狀態(tài).</p><p>　　定義2.3當某個階段的狀態(tài)被確定后,

20、 可以作出多種選擇變成下一階段的某個狀態(tài), 這種選擇過程稱為決策, 在最優(yōu)控制問題中把這種選擇稱為控制(Control).</p><p>　　我們把描述某一決策的變量稱為決策變量(Dicision variable), 或叫做決策.同樣把變量允許的取值范圍稱為允許決策集合(Set of admissible decision). 第個階段處于第個狀態(tài)時的決策變量用表示, 它是的函數(shù), 的允許決策集合用表示.&l

21、t;/p><p>　　定義2.4所謂策略就是一連串決策共同組成的一個序列, 我們不妨記為從初始狀態(tài)開始的所有過程的策略, 即. 記為由第階段的所處的狀態(tài)開始到終止狀態(tài)的后部分子過程的策略, 即,類似的, 記為由第到第階段的子過程的策略. 我們把可供選擇的策略一定的范圍稱為允許策略集合(Set of admissible policies), 用, , 表示.</p><p>　　定義2.5在一

22、個確定的過程中, 如果某階段的狀態(tài)和決策已經(jīng)知道, 那么下階段的狀態(tài)便完全可以由上階段的狀態(tài)和決策確定. 我們這種演變規(guī)律為狀態(tài)轉(zhuǎn)移方程, 記作.</p><p>　　定義2.6指標函數(shù)是衡量某一過程好壞的數(shù)量上的指標, 它是定義在整個全過程和后部子過程上的數(shù)量函數(shù), 用表示, . 指標函數(shù)是可分離的, 即可表示為的函數(shù), 記為</p><p>　　并且函數(shù)關(guān)于變量的嚴格的單調(diào)函數(shù).<

23、;/p><p>　　狀態(tài)和決策決定了第階段的階段指標, 用表示, 指標函數(shù)由組成, 最常見的有以下幾種形式: </p><p>　　所有階段指標之和: </p><p>　　所有階段指標之積: </p><p>　　在這些形式下稱為第到第階段的子過程的指標函數(shù).</p><p>　　由其中的狀態(tài)轉(zhuǎn)移方程, 我們還可以把指標

24、函數(shù)表示為狀態(tài)和策略的函數(shù), 即.</p><p>　　在狀態(tài)給定的指標函數(shù)對的最優(yōu)的值稱為最優(yōu)值函數(shù), 記作, 即</p><p>　　其中可依據(jù)具體情況取或. 因此在不同的問題中, 指標函數(shù)的含義是不同的, 它可能是距離、時間、利潤、成本等.</p><p>　　定義2.7從開始的后部子過程的最優(yōu)策略就能讓指標函數(shù)達到最優(yōu)值, 記作</p><

25、;p>　　表示全過程當中的最優(yōu)策略, 簡稱最優(yōu)策略.</p><p>　　從初始狀態(tài)出發(fā), 過程按照和狀態(tài)轉(zhuǎn)移方程演變所經(jīng)歷的狀態(tài)序列稱為最優(yōu)軌線.</p><p>　　2.2 動態(tài)規(guī)劃的最優(yōu)定理</p><p>　　最優(yōu)定理是由R. E. Bellman等提出的, 有時我們也把它叫做最優(yōu)性原理. 它在動態(tài)規(guī)劃中是一個非常重要的定理, 也是所有動態(tài)規(guī)劃問題中

26、的理論基礎(chǔ). 以下是對最優(yōu)定理的介紹: </p><p>　　設(shè)階段數(shù)為的多階段決策過程, 其階段編號為允許策略 為最優(yōu)策略的充要條件是對任意一個 有</p><p>　　式中, , 它是由給定的初始狀態(tài)和子策略所確定的段狀態(tài). 當是有效函數(shù)時, 取;當是損失函數(shù)時, 取.</p><p>　　根據(jù)動態(tài)規(guī)劃的前后關(guān)聯(lián)性, 通過分解成一系列的單階段決策過程, 然后逐個

27、加以解決, 從而求出了整個問題的最優(yōu)決策序列. 最為常用的兩種方法為逆推法和順推法. 由于兩種方法計算方法相似, 故我們就拿逆推法來說明舉例.</p><p><b>　　3 逆推法</b></p><p>　　逆推法顧名思義就是利用一些關(guān)系對整個過程進行逆向推算, 從而得出最終結(jié)果.它是動態(tài)規(guī)劃最基礎(chǔ)的方法, 后來的方法都是基于此方法改進的. 下面就介紹整個逆推法過

28、程.</p><p><b>　　3.1 逆推過程 </b></p><p>　　下面就以逆推法為例解決動態(tài)規(guī)劃問題: </p><p>　　設(shè)初始狀態(tài)為是已知, 并假設(shè)最優(yōu)值函數(shù)表示第階段的初始狀態(tài), 從階段到階段所得到的最大效益, 上圖為階段的決策過程.</p><p>　　從第階段開始, 則有</p>

29、<p>　　其中是由狀態(tài)所確定的第階段的允許決策集合. 求解這個極值問題, 就能得到最優(yōu)的解和最優(yōu)值, 需要我們著重注意的是, 若集合有且只有唯一一個決策, 則就應(yīng)寫成.</p><p><b>　　在第階段, 有</b></p><p>　　其中;解這個極值問題, 就能得到此階段的最優(yōu)解和對應(yīng)的最優(yōu)值.</p><p><b

30、>　　在第階段, 有</b></p><p>　　其中;求解得到此階段的最優(yōu)解為和對應(yīng)的最優(yōu)值為.</p><p>　　由此類推到第一個階段, 有</p><p>　　其中;解得最后的最優(yōu)解為和最優(yōu)值為.</p><p>　　3.2 結(jié)果計算過程</p><p>　　因初始的狀態(tài)已知, 故和是確定的,

31、 從而也就可以通過和確定了, 于是和也就可以確定. 這樣, 按照上面的遞推步驟往回推算下去, 就可一步一步得出每個階段的決策及效益.</p><p>　　3.3 逆推法的delphi實現(xiàn)</p><p>　　例: 設(shè)備平行分配問題 某公司根據(jù)國家的安排擬將某種設(shè)備5臺分配給所屬的甲、乙、丙三個工廠, 各廠獲得這種設(shè)備每年可以向國家提供的利潤如表所示.</p><p>

32、;<b>　　設(shè)備利潤關(guān)系表</b></p><p>　　問應(yīng)如何分配這些設(shè)備, 才能使公司得到的利潤最大？</p><p><b>　　結(jié)果計算圖為: </b></p><p>　　(1)輸入工廠數(shù)3和設(shè)備總臺數(shù)5如下圖所示</p><p>　　(2)按確定后生成下圖: </p>&

33、lt;p>　　(3)輸入設(shè)備利潤關(guān)系圖按確定如下圖: </p><p>　　(4)單擊計算得出最終結(jié)果如下圖: </p><p>　　本程序存在一點不足, 就是未能列出所有的情況.</p><p><b>　　部分代碼: </b></p><p>　　unit Unit1;</p><p>

34、　　type array2=array[1..99, 0..99] of real;//聲明的二維實型數(shù)組類型</p><p>　　type array2i=array[1..99, 0..99] of integer;//聲明的二維整數(shù)型數(shù)組類型</p><p>　　type array1=array[1..99] of integer;//聲明的一維實型數(shù)組類型</p>

35、<p><b>　　var</b></p><p>　　sb: integer; //總的設(shè)備臺數(shù)</p><p>　　gb: integer; //總的工廠數(shù)</p><p>　　g: array2; //存放盈利矩陣</p><p>　　f: array2; //方案的盈利<

36、/p><p>　　d: array2i; //在某一階段某五后續(xù)總分配量下的該階段的最優(yōu)分配置值值</p><p>　　xs: array2; //最終得到的各階段的最優(yōu)分配值</p><p>　　implementation</p><p>　　{$ R * .dfm}</p><p>　　procedure

37、 TForml.Button2Click(Sender: TObject);</p><p><b>　　begin</b></p><p>　　edit1.text: =’ ’;</p><p>　　edit2.text: =’’;</p><p><b>　　end;</b></p>

38、<p><b>　　//清除輸入框</b></p><p>　　procedure TForml.Button3Click(Sender: TObject);</p><p><b>　　var</b></p><p>　　i, j: integer;</p><p><b>

39、;　　begin</b></p><p>　　for i: =1 to gc do</p><p>　　for j: =1 to sb do</p><p>　　g[I, j]: =strtofloat(stringgrid1.cells[j+1, i]);</p><p><b>　　end;</b><

40、;/p><p>　　//讀取輸入的工廠與設(shè)備臺數(shù)之間盈利關(guān)系表</p><p>　　procedure TForml.ButtonClick(Sender: TObject);</p><p><b>　　var</b></p><p>　　i, j: integer;</p><p><b&g

41、t;　　begin</b></p><p>　　sb: =strtoint(edit1.text); //總的設(shè)備臺數(shù)</p><p>　　gc: =strtoint(edit2.text); //總的工廠數(shù)</p><p>　　stringgrid1.RowCount: =gc+1;</p><p>　　stringgr

42、id1.ColCount: =sb+2;</p><p>　　for j: =1 to sb+1 do</p><p>　　stringgrid1.cells[j, 0]: =inttostr(j-1);</p><p>　　for i: =1 to gc do</p><p>　　stringgrid1.cells[0, i]: =’A’+

43、inttostr(i);</p><p>　　//填寫輸入框的提示邊框</p><p><b>　　end;</b></p><p>　　procedure TForml.ButtonClick(Sender: TObject);</p><p><b>　　var</b></p>&

44、lt;p>　　i, j, x, z, kx: integer;</p><p>　　su: integer; //逆推后從第1到第是j階段總的最優(yōu)分配值之和</p><p>　　im: integer; //臨時循環(huán)變量</p><p>　　ky: integer; //逆推后, 從第j到第gc階段總的最優(yōu)分配值之和</p>&

45、lt;p>　　xs: array1; //逆推后, 第j階段最優(yōu)分配值</p><p><b>　　begin</b></p><p>　　for x: =0 to sb do</p><p><b>　　begin</b></p><p>　　f[gc, x]: =g[gc, x];

46、</p><p>　　d[gc, x]: =x;</p><p><b>　　end;</b></p><p>　　//對最后一個工廠, 即第一個階段進行賦值</p><p>　　for i: =gc-1 downto 1 do</p><p><b>　　begin</b>

47、</p><p><b>　　x: =0;</b></p><p>　　f[I, x]: =g[I, 0]+f[i+1, 0];</p><p>　　d[gc, x]: =x;</p><p>　　//對每個階段, 當后續(xù)分配總量為0時, 進行賦值</p><p>　　for x: =1 to s

48、b do</p><p><b>　　begin</b></p><p>　　f[i, x]: =g[i, 0]+f[i+1, x];</p><p>　　d[i, x]: =0;</p><p><b>　　//首先進行初始化</b></p><p>　　for z: =1

49、 to x do</p><p><b>　　begin</b></p><p><b>　　kx: =x-z;</b></p><p>　　if g[i, x]+f[i+1, kx]>f[i, x] then //對后續(xù)分配總量一定時求其中最優(yōu)的該階段分配量</p><p><b>

50、;　　begin</b></p><p>　　f[i, x]: =g[i, z]+f[i+1, kx];</p><p>　　d[i, x]: =z;</p><p><b>　　end;</b></p><p><b>　　end;</b></p><p>&l

51、t;b>　　end;</b></p><p><b>　　end;</b></p><p><b>　　//求解完畢</b></p><p>　　////////////////////////////////////////進行最優(yōu)方案確定</p><p>　　xs[1]=ds[

52、1, sb];</p><p>　　for i: =1 to gc do</p><p><b>　　begin</b></p><p><b>　　su: =0;</b></p><p><b>　　im: =i-1;</b></p><p>　　fo

53、r j: =1 to im do</p><p>　　su: =su+xs[j]; //su是逆推時的1-j階段分配是之和</p><p>　　ky: =sb-su;</p><p>　　xs[i]: =d[i, ky]; //對對應(yīng)求出該階段的最優(yōu)分配量</p><p>　　label4.caption: =’最大盈利為: ’+

54、floattostr(f[1, sb])+#13+’設(shè)備的最佳分配方案是: ’+#13;</p><p>　　for j: =1 to gc do</p><p>　　label4.caption=label4.caption+’工廠A’+inttostr(j)+’分配’+inttostr(xs[j])+’臺’+#13;</p><p><b>　　//輸

55、出最優(yōu)方案</b></p><p><b>　　end;</b></p><p><b>　　end;</b></p><p><b>　　end;</b></p><p>　　3.4 逆推法的excel實現(xiàn)</p><p>　　使用上例用e

56、xcel求解</p><p>　　分析: 設(shè)表示是否分配臺機器給廠(1表示“是”, 0表示“否”). 根據(jù)條件得出下表示: </p><p><b>　　得到數(shù)學模型: </b></p><p>　　Max z=(3+7+9+12+13)+(5+10+11+11+11)+</p><p>　　(4+6+11+12+12)

57、</p><p>　　通過上面分析, 可以得出下圖所示的電子表格模型. 當不分配給甲, 分給乙2臺, 分給丙3臺時, 得到的總收益最大, 為21.</p><p>　　3.5 逆推法的lingo實現(xiàn)</p><p>　　例: 設(shè)有一個旅行者從A點出發(fā), 途中要經(jīng)過B、C、D等處, 最后到達終點E. 從A到E有很多條路線可以選擇, 各點之間的距離如下圖所示, 問該旅行

58、者應(yīng)該選擇哪條路線, 使從A到E的總的路程最短.</p><p>　　從而可得出如下的lingo程序如下:</p><p><b>　　Model:</b></p><p><b>　　Sets:</b></p><p>　　Nodes/a, b1, b2, b3, c1, c2, c3, d1,

59、d2, e/: d;</p><p>　　Arcs(nodes, nodes)/a, b1 a, b2 a, b3 b1, c1 b1, c1 b1, c2 b1, c3 b2, c1 b2, c2 b2, c3 b3, c1 b3, c2 b3, c3</p><p>　　C1, d1 c1, d2 c2, d1 c2, d2 c3, d1 c3, d2 d1, 3 d2, e/: w,

60、 p;</p><p><b>　　Endsets</b></p><p>　　N=@size(nodes);</p><p><b>　　d(n)=0;</b></p><p>　　@for(nodes(i)|i#LT#n: d(i)=@min(arcs(i, j): w(i, j)+d(j)))

61、;</p><p>　　@for(arcs(i, j): p(i, j)=@if(d(i)#eq#w(i, j)+d(j), 1, 0));</p><p><b>　　Data:</b></p><p>　　W=2 5 3 7 5 6 3 2 4 5 1 5 1 4 6 3 3 3 3 4;</p><p><b

62、>　　Enddata</b></p><p><b>　　End</b></p><p>　　程序中函數(shù)@Min的值為集的屬性表達式的最小值, 一般形式為</p><p>　　@Min(集名(下標)｜條件: 屬性表達式)</p><p>　　注意, @Min與“Min=···

63、;”不同, 前者是一種循環(huán)設(shè)置函數(shù), 后者是最小化的目標值. 與@Min相似的函數(shù)還有函數(shù)@Max.</p><p><b>　　計算結(jié)果如下: </b></p><p>　　Feasible solution found at iteration: 0</p><p>　　Variable Value</p&g

64、t;<p>　　N 10.00000</p><p>　　D(A) 11.00000</p><p>　　D(B1) 11.00000</p><p>　　D(B2) 7.00000</p><p>　　D(B3) 8.00000</p>

65、;<p>　　D(C1) 4.00000</p><p>　　D(C2) 7.00000</p><p>　　D(C3) 6.00000</p><p>　　D(D1) 3.00000</p><p>　　D(D2) 4.00000</p>

66、;<p>　　D(E) 0.00000</p><p>　　W(A, B1) 2.00000</p><p>　　W(A, B2) 5.00000</p><p>　　W(A, B13) 3.00000</p><p>　　W(B1, C1) 7.00000&l

67、t;/p><p>　　W(B1, C2) 5.00000</p><p>　　W(B1, C3) 6.00000</p><p>　　W(B2, C1) 3.00000</p><p>　　W(B2, C2) 2.00000</p><p>　　W(B2, C3)

68、 4.00000</p><p>　　W(B3, C1) 5.00000</p><p>　　W(B3, C2) 1.00000</p><p>　　W(B3, C3) 5.00000</p><p>　　W(C1, D1) 1.00000</p><p>　　W(C1,

69、 D2) 4.00000</p><p>　　W(C2, D1) 6.00000</p><p>　　W(C2, D2) 3.00000</p><p>　　W(C3, D1) 3.00000</p><p>　　W(C3, D2) 3.00000</p><

70、p>　　W(D1, E) 3.00000</p><p>　　W(D2, E) 4.00000</p><p>　　P(A, B1) 0.00000</p><p>　　P(A, B1) 0.00000</p><p>　　P(A, B1)

71、1.00000</p><p>　　P(B1, C1) 1.00000</p><p>　　P(B1, C2) 0.00000</p><p>　　P(B1, C3) 0.00000</p><p>　　P(B2, C1) 1.00000</p><p

72、>　　P(B2, C2) 0.00000</p><p>　　P(B2, C3) 0.00000</p><p>　　P(B3, C1) 0.00000</p><p>　　P(B3, C2) 1.00000</p><p>　　P(B3, C3)

73、 0.00000</p><p>　　P(C1, D1) 1.00000</p><p>　　P(C1, D2) 0.00000</p><p>　　P(C2, D1) 0.00000</p><p>　　P(C2, D2) 1.00000</p><

74、p>　　P(C3, D1) 1.00000</p><p>　　P(C3, D2) 0.00000</p><p>　　P(D1, E) 1.00000</p><p>　　P(D2, E) 1.00000</p><p>　　Row Slac

75、k or surplus</p><p>　　1 0.00000</p><p>　　2 0.00000</p><p>　　3 0.00000</p><p>　　4 0.00000</p><p>　　5 0.000

76、00</p><p>　　6 0.00000</p><p>　　7 0.00000</p><p>　　8 0.00000</p><p>　　9 0.00000</p><p>　　10 0.00000</p&

77、gt;<p>　　11 0.00000</p><p>　　12 0.00000</p><p>　　13 0.00000</p><p>　　14 0.00000</p><p>　　15 0.00000</p>

78、<p>　　16 0.00000</p><p>　　17 0.00000</p><p>　　18 0.00000</p><p>　　19 0.00000</p><p>　　20 0.00000</p><p

79、>　　21 0.00000</p><p>　　22 0.00000</p><p>　　23 0.00000</p><p>　　24 0.00000</p><p>　　25 0.00000</p><p>　

80、　26 0.00000</p><p>　　27 0.00000</p><p>　　28 0.00000</p><p>　　29 0.00000</p><p>　　30 0.00000</p><p>　　31

81、 0.00000</p><p>　　20 0.00000</p><p>　　最短路為A B3 C2 D2 E, 最短路長為11. 同樣可得各頂點到E的最短路及最短路長.</p><p>　　以上幾個例子和算法都是運用不同工具和算法把逆推法進行自動化計算, 在現(xiàn)今計算機飛速發(fā)展的時代, 越來越多的問題都將

82、用計算機編程來實現(xiàn), 因此, 從上述算法可以看出同一問題不同電腦工具有其獨特的解題思路. 動態(tài)規(guī)劃問題運用非常廣泛, 更多的簡單易行又方便的解法也需要我們慢慢去發(fā)掘. </p><p>　　4 資源分配問題其他算法簡要介紹</p><p>　　上面提到的逆推算法是現(xiàn)在運籌學教科書中主要介紹的方法, 也是現(xiàn)在計算動態(tài)規(guī)劃的重要算法, 而當我們有時會遇到一些二維資源分配問題, 逆推法就行不通了

83、, 我們這時就要借助其他方法解決, 其中包括拉格朗日乘數(shù)法、逐次逼近法和粗格子點法(疏密法)等.下面我們就來簡單介紹下這幾種算法. </p><p>　　拉格朗日乘數(shù)法是引入拉格朗日乘數(shù), 將二維分配問題化為</p><p><b>　　滿足條件</b></p><p>　　其中作為一個固定的參數(shù). </p><p>　

84、　令 </p><p><b>　　于是問題變?yōu)?lt;/b></p><p><b>　　滿足</b></p><p>　　這是一個一維問題, 可用對一維問題的求解方法求解. 從而用這樣的降維方法在理論上保證了在計算上是可行, 故對于高維的問題可以用上述拉格朗日乘數(shù)降維法的思想來降低

85、維數(shù).</p><p>　　逐次逼近法是另一種降維方法, 我們先保持一個變量不變, 再對另一個變量實現(xiàn)最優(yōu)化, 然后交替地固定, 以迭代的形式反復進行, 直到獲得能滿足一定程度的要示為止.</p><p>　　先設(shè)為滿足的一個可行解, 固定在, 先對求解, 則二維分配問題變成一維問題: </p><p>　　可用對一維的方法來求解. 設(shè)這解為, 然后固定為, 對求解

86、, 即</p><p>　　設(shè)其解為, 再固定為, 對求解, 這樣交替下去可以得到一系列的解.</p><p><b>　　因為</b></p><p>　　因此得到的函數(shù)值序列是單調(diào)增的, 但不一定就能收斂到絕對的最優(yōu)解, 一般情況只能收斂到某一局部的最優(yōu)解. 因此, 在實際計算過程中, 我們可以選擇多個初始點進行計算, 然后在求出的所有的幾

87、個局部最優(yōu)解中挑選出一個最好的.</p><p>　　粗格子點法(疏密法) 在用離散化的方法來計算時, 先把矩形定義域: 分成一系列的網(wǎng)格, 然后在這些格子點上逐個進行計算. 如將、各分為和等份, 則總共有個. 因此, 對于和很大時這里的格子點就很驚人, 所以這樣的計算量也是很驚人的. 考慮到計算的可行性, 我們往往根據(jù)問題要求的精度, 采用格子點法逐步縮小計算區(qū)域來減少計算量.</p><p

88、>　　在使用粗格子點法時, 我們要先用少數(shù)的格子點對結(jié)果進行粗糙的計算, 在求出相應(yīng)的最優(yōu)解之后, 再在最優(yōu)解周邊的小區(qū)域內(nèi)進一步細分, 并求解在細分區(qū)域格子點上的最優(yōu)解, 如此反復繼續(xù)細分下去直到達到要求為止. 但是運用這種方法也可能會發(fā)生最優(yōu)解“漏網(wǎng)”的情況, 因此, 應(yīng)用此法時我們要結(jié)合指標函數(shù)的特征進行具體分析.</p><p>　　綜上所述, 粗格子點法和逐次逼近法雖然都有各自的缺點, 但在實際生

89、活問題中, 這兩種方法的應(yīng)用還是比較廣泛的.</p><p><b>　　5小結(jié)</b></p><p>　　本文重點放在了現(xiàn)有的一些求動態(tài)規(guī)劃問題的算法進行介紹, 以及運用幾種計算工具對算法的舉例的計算和編程. 當然, 最重要的還是能把這些算法運用到實際生活中, 不但是理論的計算, 而且要能在滿足實際條件和允許的范圍. 眾所周知, 一種算法的運用好壞取決于他計算的精

90、度和復雜度, 不同的問題對于不同的算法有著不同的適合程度. 因此, 在實際計算中我們要針對不同的問題選用合適的算法. 但不論怎樣逆推法仍是所有動態(tài)規(guī)劃求解算法的基礎(chǔ). 本文介紹持的算法也可借助編譯程序計算出他們的復雜度, 然后將它們進行對比, 就能發(fā)現(xiàn)各自的優(yōu)點. 同時由于很多生活中的問題都能轉(zhuǎn)換成動態(tài)規(guī)劃問題來解決, 因此, 它在我們生活中的應(yīng)用越來越廣泛, 所以也得到了很多的專業(yè)人士的重視. 如今計算機的發(fā)展也達到一定程度, 但不論

91、怎樣只要我們計算能力在不斷提升那么新的算法也就自然誕生了. 相信不久將來一種種簡單易行的算法也會出現(xiàn), 不但被高層知識分子所了解熟悉, 更能在廣大人民群眾中實際應(yīng)用.</p><p><b>　　參考文獻</b></p><p>　　楊敦悌、陳斌著, 動態(tài)規(guī)劃簡介, 遼寧教育出版社, 1990: 221-278</p><p>　　張有為譯,

92、 動態(tài)規(guī)劃導論, 國防工業(yè)出版社, 1985: 5-156</p><p>　　G.K.Hortom, A.A.Mardudin. Dynamical Propertics of solids, Northholland Publishing Company, 1974,1: 365-369</p><p>　　J.Browne, etal. Classification of flexi

93、ble manufacturing systems. The FMS Magazine, 1984, 22: 114-117</p><p>　　K.A Dowsland, W.B Dowslan, European Journal of Operational Reserch, 1992: 2-14</p><p>　　胡運權(quán), 運籌學(第三版), 清華大學出版社, 2005: 191-

94、250</p><p>　　張宏偉, 數(shù)學建模中的動態(tài)規(guī)劃問題, 東北師范大學學位評定委員會, 2008: 23-35</p><p>　　胡名雨, 李順新, 逐次逼近動態(tài)的規(guī)劃法在水庫優(yōu)化調(diào)度中的應(yīng)用[J], 計算機與現(xiàn)代化, 2008: 8-10</p><p>　　張之坯等, 動態(tài)規(guī)劃及其應(yīng)用[M] , 北京國防工業(yè)出版社, 1993: 3-10</p&

95、gt;<p>　　魏國華、傅家良、周仲良實用運籌學, 上海:復旦大學出版社, 1987: 254-290</p><p><b>　　致謝</b></p><p>　　在撰寫論文的過程中, 得到了老師和同學的熱心幫助, 雖然自己的知識還沒達到一定的高度, 不能完全自我創(chuàng)新, 但在我的指導老師金老師的指導和細心幫助下, 我完成了大學里最有價值的一件事, 就

96、是能獨立的撰寫出有自我見解的論文. 指導老師詳盡的審閱了論文初稿, 給我提出了寶貴的修改意見, 對英文翻譯也進行了逐字逐句的修改與校正. 金老師嚴謹?shù)闹螌W態(tài)度和誨人不倦的師者作風使我受益終身, 其淡淡的笑容更給予我很大的鼓舞, 再次向金麗老師表示衷心的感謝. 寫作過程中, 我閱讀了很多學者發(fā)表的論文, 也看了大量的文章, 其中很多人的科研成果和寫作思路都給我很大啟發(fā), 在此也向這些學者們表示由衷的感謝. 雖然在撰寫過程中遇到了許多磕磕

97、碰碰, 但在自己的努力和老師、同學的幫助下都能克服. 同時也非常感謝所有的大學老師對我的諄諄教導, 是你們給了我大學的知識, 是你們讓我學會了以前從未學過的知識, 這期間凝結(jié)了你們付出的心血, 我將終生不忘記這美好的大學生活.</p><p>　　我還要向我的同組同學表示感謝, 謝謝你們在論文的寫作過程中幫助我. 我也要感謝我的室友, 謝謝你們四年的朝夕相伴和鼓勵. 我更要感謝身邊的所有同學, 是你們的團結(jié)友愛使