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

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

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

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

4、主要算法和實(shí)例, 并運(yùn)用delphi, excel和lingo方法解決資源分配問題.</p><p>　　關(guān)鍵詞: 動(dòng)態(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 動(dòng)態(tài)規(guī)劃的最優(yōu)定

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

35、<p><b>　　var</b></p><p>　　sb: integer; //總的設(shè)備臺(tái)數(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è)備臺(tái)數(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è)備臺(tái)數(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; //臨時(shí)循環(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>　　//對(duì)最后一個(gè)工廠, 即第一個(gè)階段進(jìn)行賦值</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>　　//對(duì)每個(gè)階段, 當(dāng)后續(xù)分配總量為0時(shí), 進(jìn)行賦值</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>　　//首先進(jìn)行初始化</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 //對(duì)后續(xù)分配總量一定時(shí)求其中最優(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>　　////////////////////////////////////////進(jìn)行最優(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是逆推時(shí)的1-j階段分配是之和</p><p>　　ky: =sb-su;</p><p>　　xs[i]: =d[i, ky]; //對(duì)對(duì)應(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])+’臺(tái)’+#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實(shí)現(xiàn)</p><p>　　使用上例用e

56、xcel求解</p><p>　　分析: 設(shè)表示是否分配臺(tái)機(jī)器給廠(1表示“是”, 0表示“否”). 根據(jù)條件得出下表示: </p><p><b>　　得到數(shù)學(xué)模型: </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>　　通過上面分析, 可以得出下圖所示的電子表格模型. 當(dāng)不分配給甲, 分給乙2臺(tái), 分給丙3臺(tái)時(shí), 得到的總收益最大, 為21.</p><p>　　3.5 逆推法的lingo實(shí)現(xiàn)</p><p>　　例: 設(shè)有一個(gè)旅行者從A點(diǎn)出發(fā), 途中要經(jīng)過B、C、D等處, 最后到達(dá)終點(diǎn)E. 從A到E有很多條路線可以選擇, 各點(diǎn)之間的距離如下圖所示, 問該旅行

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的值為集的屬性表達(dá)式的最小值, 一般形式為</p><p>　　@Min(集名(下標(biāo))｜條件: 屬性表達(dá)式)</p><p>　　注意, @Min與“Min=···

63、;”不同, 前者是一種循環(huán)設(shè)置函數(shù), 后者是最小化的目標(biāo)值. 與@Min相似的函數(shù)還有函數(shù)@Max.</p><p><b>　　計(jì)算結(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, 最短路長(zhǎng)為11. 同樣可得各頂點(diǎn)到E的最短路及最短路長(zhǎng).</p><p>　　以上幾個(gè)例子和算法都是運(yùn)用不同工具和算法把逆推法進(jìn)行自動(dòng)化計(jì)算, 在現(xiàn)今計(jì)算機(jī)飛速發(fā)展的時(shí)代, 越來越多的問題都將

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

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

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

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

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

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

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

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

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

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

92、 動(dòng)態(tài)規(guī)劃導(dǎo)論, 國(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>　　胡運(yùn)權(quán), 運(yùn)籌學(xué)(第三版), 清華大學(xué)出版社, 2005: 191-

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

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

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

97、碰碰, 但在自己的努力和老師、同學(xué)的幫助下都能克服. 同時(shí)也非常感謝所有的大學(xué)老師對(duì)我的諄諄教導(dǎo), 是你們給了我大學(xué)的知識(shí), 是你們讓我學(xué)會(huì)了以前從未學(xué)過的知識(shí), 這期間凝結(jié)了你們付出的心血, 我將終生不忘記這美好的大學(xué)生活.</p><p>　　我還要向我的同組同學(xué)表示感謝, 謝謝你們?cè)谡撐牡膶懽鬟^程中幫助我. 我也要感謝我的室友, 謝謝你們四年的朝夕相伴和鼓勵(lì). 我更要感謝身邊的所有同學(xué), 是你們的團(tuán)結(jié)友愛使