[數(shù)學(xué)]動(dòng)態(tài)規(guī)劃應(yīng)用

1、天津工業(yè)大學(xué)畢業(yè)設(shè)計(jì)（論文）題目：動(dòng)態(tài)規(guī)劃在學(xué)生選課中的應(yīng)用姓 名 學(xué) 院 專 業(yè) 指導(dǎo)教師 職 稱 2011年 5月 28日摘 要本文主要介紹了動(dòng)態(tài)規(guī)劃（dynamic programming）的基本內(nèi)容，詳細(xì)介紹了動(dòng)態(tài)規(guī)劃過程中的階段、狀態(tài)變量、決策變量的定義及其選取與詳細(xì)應(yīng)用。本文建立了大學(xué)生選修課選課的動(dòng)態(tài)規(guī)劃模型，并且研究了動(dòng)態(tài)規(guī)劃在求解選課過程最優(yōu)解的過程中的應(yīng)用。本論文在闡述了多階段動(dòng)態(tài)規(guī)劃模型的詳細(xì)求解過程的基礎(chǔ)上，主要解決了運(yùn)用最優(yōu)化方法中多階段動(dòng)態(tài)規(guī)劃模型求解多階段選課的問題。第二章是動(dòng)態(tài)規(guī)劃內(nèi)容的詳細(xì)介紹，第三章是多階段選修課選課動(dòng)態(tài)規(guī)劃模型的建立與最優(yōu)選課安排的得出過程

2、。本論文對(duì)于過程最優(yōu)解與全局最優(yōu)解的關(guān)系做出了直觀的描述。這有助于系統(tǒng)化人性化的選課系統(tǒng)的建立。關(guān)鍵詞：動(dòng)態(tài)規(guī)劃；最優(yōu)解；階段；決策變量；狀態(tài)變量。 abstractthis article mainly introduced the dynamic programming and introduced the process of dynamic planning stage or state variables, the definition and selection decision variables with detailed applications. this paper es

3、tablished the course of college students' elective dynamic programming model., and studied the dynamic programming in solving the optimal solution of course selection process in the process of application.this paper expounded the dynamic programming model in multi-stage detailed solving process,

4、 mainly solved the basis for the use of the optimization methods of dynamic programming model to solve multiple stage of course. the second chapter is dynamic programming content detailed introduction, and the third chapter is multi-stage elective courses of dynamic programming model is established

5、and arrange the optimal selection is obtained.this paper describes process optimal solution and the global optimal solution relationship intuitively. it helps to establish systematic humanistic elective course system.keywords: dynamic planning; the optimal solution; stage; the decision variables; st

6、age variables.目 錄 第一章 前言1第二章 動(dòng)態(tài)規(guī)劃的基本概念和基本原理22.1 動(dòng)態(tài)規(guī)劃的基本概念22.1.1 階段22.1.2 狀態(tài)22.1.3 決策和策略32.1.4 狀態(tài)轉(zhuǎn)移方程32.1.5 指標(biāo)函數(shù)42.2 動(dòng)態(tài)規(guī)劃的基本思想與基本原理42.2.1 動(dòng)態(tài)規(guī)劃方法的基本思想42.2.2動(dòng)態(tài)規(guī)劃算法的基本步驟52.2.3 動(dòng)態(tài)規(guī)劃的基本方程與基本原理62.2.4動(dòng)態(tài)規(guī)劃的適用條件6第三章 動(dòng)態(tài)規(guī)劃模型的建立與求解83.1 動(dòng)態(tài)規(guī)劃模型的建立83.2 狀態(tài)變量、決策變量的選擇93.3 求解動(dòng)態(tài)規(guī)劃的最優(yōu)解93.4 得出最優(yōu)解14第四章 問題與展望15參考文獻(xiàn)17附錄118附錄

7、227謝辭30 天津工業(yè)大學(xué)2007屆本科生畢業(yè)設(shè)計(jì)（論文）第一章 前言動(dòng)態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程(decision process)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國數(shù)學(xué)家bellman等人在研究多階段決策過程(multistep decision process)的優(yōu)化問題時(shí)，提出了著名的最優(yōu)化原理(principle of optimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個(gè)求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法動(dòng)態(tài)規(guī)劃。1957年出版了他的名著dynamic programming，這是

8、該領(lǐng)域的第一本著作。動(dòng)態(tài)規(guī)劃問世以來，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動(dòng)態(tài)規(guī)劃方法比用其他方法求解更為方便。雖然動(dòng)態(tài)規(guī)劃主要用于求解以時(shí)間劃分階段的動(dòng)態(tài)規(guī)劃過程的優(yōu)化問題，但是一些與時(shí)間無關(guān)的靜態(tài)規(guī)劃（如線性規(guī)劃、非線性規(guī)劃）只要認(rèn)為的引入時(shí)間因素，把它視為多階段決策過程，也可以用動(dòng)態(tài)規(guī)劃方法方便地求解。動(dòng)態(tài)規(guī)劃模型的分類：離散確定型；離散隨機(jī)型；連續(xù)確定型；連續(xù)隨機(jī)型。本文僅運(yùn)用離散確定型動(dòng)態(tài)規(guī)劃模型，初步解決動(dòng)態(tài)規(guī)劃在學(xué)生選修課選課過程中的應(yīng)用，并運(yùn)用數(shù)學(xué)軟件進(jìn)行模擬分析。第二章 動(dòng)態(tài)規(guī)劃的基本

9、概念和基本原理2.1 動(dòng)態(tài)規(guī)劃的基本概念是用動(dòng)態(tài)規(guī)劃方法解決多階段決策問題，首先要將實(shí)際問題寫成動(dòng)態(tài)規(guī)劃模型，此時(shí)我們要用到以下概念：1.階段；2狀態(tài)；3決策和策略；4狀態(tài)轉(zhuǎn)移；5指標(biāo)函數(shù)；2.1.1 階段將所給問題的過程，按照時(shí)間或空間特征分解成若干相互聯(lián)系的階段，以便按照次序去求每個(gè)階段的解，常用字母k表示階段變量。圖2.1圖2.1中，從a到f可以分成從a到b（b有兩種選擇b1，b2），從b到c（c有四種選擇c1，c2，c3，c4），從c到d（d有三種選擇d1，d2，d3），從d到e（e有兩種選擇e1，e2），再從e到f五個(gè)階段。k=1，2，3，4，5。2.1.2 狀態(tài)各階段開始時(shí)的客觀條

10、件叫做狀態(tài)。描述各階段狀態(tài)的變量成為狀態(tài)變量，常用表示第k階段的狀態(tài)變量，狀態(tài)變量sk的取值集合成為狀態(tài)集合，用sk表示。動(dòng)態(tài)規(guī)劃中的狀態(tài)應(yīng)居于如下性質(zhì)：當(dāng)某階段狀態(tài)給定以后，在這階段以后過程的發(fā)展不受這段以前各段狀態(tài)的影響。也就是說，當(dāng)前的狀態(tài)是過去歷史的一個(gè)完整總結(jié)，過程的過去歷史只能通過當(dāng)前狀態(tài)去影響它未來的發(fā)展，這稱為無后效性。如果所選定的變量不具備無后效性，就不能作為狀態(tài)變量來構(gòu)造動(dòng)態(tài)規(guī)劃模型。在例1中第一階段狀態(tài)為a，第二階段則有兩個(gè)狀態(tài)：b1，b2。狀態(tài)變量st的集合s1=a，后面各段的狀態(tài)集合分別是：s2=b1，b2s3=c1，c2 ,c3 ,c4s4=d1，d2 ,d3s5=

11、e1，e2 當(dāng)某段的初始狀態(tài)已選定某個(gè)點(diǎn)時(shí)，從這個(gè)點(diǎn)以后的路徑選擇只與該點(diǎn)有關(guān)，不受以前的路徑的影響，所以滿足狀態(tài)的無后效性。2.1.3 決策和策略當(dāng)各段的狀態(tài)去頂以后，就可以做出不同的決策（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策。表示決策的變量，稱為決策變量，產(chǎn)用uk(sk)表示第k階段當(dāng)狀態(tài)為sk時(shí)的決策變量。在實(shí)際問題中，決策變量的取值往往限制在一定范圍內(nèi)，我們稱此范圍為允許決策集合，常用dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合，顯然有uk(sk)dk(sk)。在例1中，從第二階段的狀態(tài)b1出發(fā)，可選擇下一段的c1，c2，c3，即其允許決策集合為：d2(b1)=c

12、1，c2，c3如我們選擇c3，則可表為：u2(b1)=c3各段決策確定后，整個(gè)問題的決策序列就構(gòu)成一個(gè)策略，用p1，n u1(s1)，u2(s2)，un(sn)表示。對(duì)每個(gè)實(shí)際問題，可供選擇的策略有一定范圍，稱為允許策略集合，記作p1，n，使整個(gè)問題達(dá)到最優(yōu)效果的策略就是最優(yōu)策略。2.1.4 狀態(tài)轉(zhuǎn)移方程 動(dòng)態(tài)規(guī)劃中本階段的狀態(tài)往往是上一階段狀態(tài)和上一階段的決策結(jié)果。如果給定了第k段的狀態(tài)sk，本階段決策為uk(sk)，則第k+1段的狀態(tài)sk+1也就完全確定，它們的關(guān)系可用下式表示：sk+1=tk(sk,uk)由于它表示了由k段到k+1段的狀態(tài)轉(zhuǎn)移規(guī)律，所以稱為狀態(tài)轉(zhuǎn)移方程。例1中，狀態(tài)轉(zhuǎn)移方

13、程為：sk+1= uk(sk)2.1.5 指標(biāo)函數(shù)用于衡量所選定策略優(yōu)劣的淑玲指標(biāo)稱為指標(biāo)函數(shù)。它分為階段指標(biāo)函數(shù)和過程指標(biāo)函數(shù)兩種。階段指標(biāo)函數(shù)是指第k段，從狀態(tài)sk出發(fā)；采取決策uk時(shí)的效益，用d（sk,uk）表示。而一個(gè)n段決策過程，從1到n叫做問題的原過程，對(duì)于任意一個(gè)給定的k（1kn），從第k段到第n段的過程稱為原過程的一個(gè)后部子過程。v1,n(s1,p1,n)表示初始狀態(tài)為s1采用策略p1，n時(shí)原過程的指標(biāo)函數(shù)值，而vk,n(sk,pk,n)表示在第k段，狀態(tài)為sk采用策略pk，n時(shí)，后部子過程的指標(biāo)函數(shù)值。最優(yōu)指標(biāo)函數(shù)記為fk(sk)，它表示從第k段狀態(tài)sk，采用最優(yōu)策略p*k，

14、n到過程中止是的最佳效益值。fk(sk)與vk,n(sk,pk,n)間的關(guān)系為：fksk=vk,nsk,pk,n*=optpk,npk,nvk,n(sk,pk,n)上式中opt表示最優(yōu)化，根據(jù)具體問題分別表示為max或min。在例1中，指標(biāo)函數(shù)是距離。如第二階段，狀態(tài)為b1是d(b1,c2)表示由b1出發(fā)。采用決策到下一段c2點(diǎn)的兩點(diǎn)間距離，v2,5(b1)表示從b1到f的距離，而f2(b1)則表示從b1到f的最短距離。本問題的總目標(biāo)是求f1(a)，即從a到終點(diǎn)f的最短距離。2.2 動(dòng)態(tài)規(guī)劃的基本思想與基本原理2.2.1 動(dòng)態(tài)規(guī)劃方法的基本思想一般來說，只要問題可以劃分成規(guī)模更小的子問題，并且

15、原問題的最優(yōu)解中包含了子問題的最優(yōu)解（即滿足最優(yōu)子化原理），則可以考慮用動(dòng)態(tài)規(guī)劃解決【1】。動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余，因此，動(dòng)態(tài)規(guī)劃是一種將問題實(shí)例分解為更小的、相似的子問題，并存儲(chǔ)子問題的解而避免計(jì)算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。由此可知，動(dòng)態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問題實(shí)例歸納為更小的、相似的子問題，并通過求解子問題產(chǎn)生一個(gè)全局最優(yōu)解。其中貪心法的當(dāng)前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個(gè)子問題是獨(dú)立的 (即不包含公共的子問題)，因此一旦遞歸地求出各子問題的解后，

16、便可自下而上地將子問題的解合并成問題的解。但不足的是，如果當(dāng)前選擇可能要依賴子問題的解時(shí)，則難以通過局部的貪心策略達(dá)到全局最優(yōu)解；如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題。解決上述問題的辦法是利用動(dòng)態(tài)規(guī)劃。該方法主要應(yīng)用于最優(yōu)化問題，這類問題會(huì)有多種可能的解，每個(gè)解都有一個(gè)值，而動(dòng)態(tài)規(guī)劃找出其中最優(yōu)(最大或最小)值的解。若存在若干個(gè)取最優(yōu)值的解的話，它只取其中的一個(gè)。在求解過程中，該方法也是通過求解局部子問題的解達(dá)到全局最優(yōu)解，但與分治法和貪心法不同的是，動(dòng)態(tài)規(guī)劃允許這些子問題不獨(dú)立，(亦即各子問題可包含公共的子子問題)也允許其通過自身子問題的解作出選擇，該方

17、法對(duì)每一個(gè)子問題只解一次，并將結(jié)果保存起來，避免每次碰到時(shí)都要重復(fù)計(jì)算。因此，動(dòng)態(tài)規(guī)劃法所針對(duì)的問題有一個(gè)顯著的特征，即它所對(duì)應(yīng)的子問題樹中的子問題呈現(xiàn)大量的重復(fù)。動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于，對(duì)于重復(fù)出現(xiàn)的子問題，只在第一次遇到時(shí)加以求解，并把答案保存起來，讓以后再遇到時(shí)直接引用，不必重新求解。2.2.2 動(dòng)態(tài)規(guī)劃算法的基本步驟設(shè)計(jì)一個(gè)標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃算法，通常可按以下幾個(gè)步驟進(jìn)行：1) 將多階段決策過程劃分階段，恰當(dāng)?shù)剡x取狀態(tài)變量、決策變量以及定義最優(yōu)指標(biāo)函數(shù)，從而把問題化成一族同類型的子問題，然后逐個(gè)求解。2) 求解時(shí)從邊界條件開始，逆（或順）過程行進(jìn)方向，逐段遞推尋優(yōu)。在每一個(gè)子問題求解時(shí)，都

18、要使用它前面已求出的子問題的最優(yōu)結(jié)果，最后一個(gè)子問題的最優(yōu)解，就是整個(gè)問題的最優(yōu)解。3) 動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段與未來各段分開，又把當(dāng)前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法，因此每段的最優(yōu)策略選取是從全局考慮的，與該段的最優(yōu)選擇一般是不同的。【4】動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會(huì)非常簡(jiǎn)單。2.2.3 動(dòng)態(tài)規(guī)劃的基本方程與基本原理動(dòng)態(tài)規(guī)劃的基本方程為：fksk=optukdk(sk)vksk,uk+fk+1sk+1 k=n,n-1,1fn+1sn+1=0 動(dòng)態(tài)規(guī)劃方法基于貝爾曼等人提出的最優(yōu)化原理，它可表述為：一個(gè)過程的最優(yōu)策略具有這樣的性質(zhì)：即無論初始狀

19、態(tài)及初始決策如何，對(duì)于先前決策所形成的狀態(tài)而言，其以后的所有決策應(yīng)構(gòu)成最優(yōu)策略【3】。2.2.4 動(dòng)態(tài)規(guī)劃的適用條件任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同樣，動(dòng)態(tài)規(guī)劃也并不是萬能的。適用動(dòng)態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無后效性。1.最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)）最優(yōu)化原理可這樣闡述：一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡(jiǎn)而言之，一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。一個(gè)問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。最優(yōu)化原理是動(dòng)態(tài)規(guī)劃的基礎(chǔ)，任何問題，如果失去了最優(yōu)化原理的支持，就不可能用動(dòng)態(tài)規(guī)劃

20、方法計(jì)算。動(dòng)態(tài)規(guī)劃的最優(yōu)化理在其指標(biāo)函數(shù)的可分離性和單調(diào)性中得到體現(xiàn)。根據(jù)最優(yōu)化原理導(dǎo)出的動(dòng)態(tài)規(guī)劃基本方程是解決一切動(dòng)態(tài)規(guī)劃問題的基本方法。2.無后向性將各階段按照一定的次序排列好之后，對(duì)于某個(gè)給定的階段狀態(tài)，它以前各階段的狀態(tài)無法直接影響它未來的決策，而只能通過當(dāng)前的這個(gè)狀態(tài)。換句話說，每個(gè)狀態(tài)都是過去歷史的一個(gè)完整總結(jié)。這就是無后向性，又稱為無后效性。有些問題乍一看好像有后向性，但如果按照某種合理的方式重新劃分階段，就可以發(fā)現(xiàn)其本質(zhì)上是無后向性的，所以關(guān)鍵是階段的合理劃分，這一點(diǎn)將在動(dòng)態(tài)規(guī)劃的技巧中詳細(xì)闡述。3.子問題的重疊性動(dòng)態(tài)規(guī)劃可以將原來具有指數(shù)級(jí)復(fù)雜度的搜索算法改進(jìn)成具有多項(xiàng)式時(shí)間

21、的算法。其中的關(guān)鍵在于解決冗余，這是動(dòng)態(tài)規(guī)劃算法的根本目的。動(dòng)態(tài)規(guī)劃實(shí)質(zhì)上是一種以空間換時(shí)間的技術(shù)，它在實(shí)現(xiàn)的過程中，不得不存儲(chǔ)產(chǎn)生過程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其它的算法。以bitonic旅行路線問題為例，這個(gè)問題也可以用搜索算法來解決。動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度為o(n2)，搜索算法的時(shí)間復(fù)雜度為o(n!) ，但從空間復(fù)雜度來看，動(dòng)態(tài)規(guī)劃算法為o(n2)，而搜索算法為o(n)，搜索算法反而優(yōu)于動(dòng)態(tài)規(guī)劃算法。選擇動(dòng)態(tài)規(guī)劃算法是因?yàn)閯?dòng)態(tài)規(guī)劃算法在空間上可以承受，而搜索算法在時(shí)間上卻無法承受，所以我們舍空間而取時(shí)間。設(shè)原問題的規(guī)模為n，容易看出，當(dāng)子問題樹中的子問題總數(shù)是n的超多項(xiàng)式函數(shù)，

22、而不同的子問題數(shù)只是n的多項(xiàng)式函數(shù)時(shí)，動(dòng)態(tài)規(guī)劃法顯得特別有意義，此時(shí)動(dòng)態(tài)規(guī)劃法具有線性時(shí)間復(fù)雜性。所以，能夠用動(dòng)態(tài)規(guī)劃解決的問題還有一個(gè)顯著特征：子問題的重疊性。這個(gè)性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的必要條件，但是如果該性質(zhì)無法滿足，動(dòng)態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢(shì)。第三章 動(dòng)態(tài)規(guī)劃模型的建立與求解3.1 動(dòng)態(tài)規(guī)劃模型的建立建立動(dòng)態(tài)規(guī)劃的模型，就是分析問題并建立問題的動(dòng)態(tài)規(guī)劃基本方程。成功地應(yīng)用動(dòng)態(tài)規(guī)劃方法的關(guān)鍵，在于識(shí)別問題的多階段特征，將問題分解成為可用遞推關(guān)系式聯(lián)系起來的若干子問題，而正確建立基本遞推關(guān)系方程的關(guān)鍵又在于正確選擇狀態(tài)變量，保證各階段的狀態(tài)變量具有遞推的狀態(tài)轉(zhuǎn)移關(guān)系sk+1=t

23、k(sk,uk)。本論文主要選取了某學(xué)生在大學(xué)四年期間所感興趣的選修課，要求其每學(xué)期只能選擇一門選修課，并且使其對(duì)所有選修課的滿意程度達(dá)到最大。圖3.1表3.1 平均喜好程度非常喜歡1喜歡0.7一般0.5不喜歡0.3完全不喜歡0.1且要求每一學(xué)年所修學(xué)分?jǐn)?shù)達(dá)到8個(gè)學(xué)分圖3.2圖3.2為圖3.1的關(guān)系圖，其中ai,bi,ci,di,ei,fi,gi,hi（i=1,2,3,4）分別代表對(duì)應(yīng)學(xué)期所選擇的對(duì)應(yīng)的選修課程，在課程名下方的紅色數(shù)字代表所選修課程的對(duì)應(yīng)學(xué)分?jǐn)?shù)；在課程之后的數(shù)字為對(duì)下一門課程的平局喜好程度（見表3.1），數(shù)字順序?qū)?yīng)下一學(xué)期可選修課程的順序，*代表在選擇本門課程時(shí)，不可選修*位

24、置所指示的課程。本文主要運(yùn)用動(dòng)態(tài)規(guī)劃算法解決該選課問題的最優(yōu)解，即最大喜好程度。3.2 狀態(tài)變量、決策變量的選擇階段k：在這里，k取1,2,3,4,5,6,7,8狀態(tài)變量sk：第k階段可以選擇的選修課決策變量xk：第k階段可選的選修課的滿意度3.3 求解動(dòng)態(tài)規(guī)劃的最優(yōu)解這是一個(gè)八階段的動(dòng)態(tài)規(guī)劃模型，在求解這個(gè)模型的最優(yōu)解時(shí)，采用逆序遞推方法求解，逐步求出各段各點(diǎn)到終點(diǎn)h的最短路線，最后求得o點(diǎn)到h點(diǎn)的最短路線。1. 第一步，從k=8開始，狀態(tài)變量s8可取兩種狀態(tài)g1，g2，它們到h點(diǎn)的平均喜好程度分別為0.3,0.7，即：f8g1=0.3 f8g2=0.7由于g(g2)+g(h)=7<8

25、，則只保留f8g1=0.3。2. 第二步，k=7，狀態(tài)變量s7可取三種狀態(tài)f1，f2，f3，它們到h點(diǎn)的平均喜好程度分別為：f7f1=0.1+0.3=0.4f7f2=0.5+0.3=0.8f7f3=0.5+0.3=0.83. 第三步，k=6，狀態(tài)變量s6可取四個(gè)值e1，e2，e3，e4 。從e1到h有兩條路線，需加以比較，取其中平均喜好程度最大的，即：f6e1=maxde1,f1+f6f1de1,f2+f6f2=max0.1+0.40.7+0.8=1.5這說明由e1到h的最大滿意度為1.5，其路徑為e1f2g1h，相應(yīng)決策為u6*e1=f2。從e2到h有兩條路線，需加以比較，取其中平均喜好程度

26、最大的，即：f6e2=maxde2,f1+f6f1de2,f2+f6f2=max0.3+0.40.7+0.8=1.5由于g(e2)+g(f2)=7<8，不符合第三學(xué)年的學(xué)分要求，則舍去此解。從而有f6(e2)=0.7。這說明由e2到h的最大滿意度為0.7，其路徑為e2f1g1h，相應(yīng)決策為u6*e2=f1。從e3到h有三條路線，需加以比較，取其中平均喜好程度最大的，即：f6e3=maxd(e3,f1)+f6(f1)d(e3,f2)+f6(f2)d(e3,f3)+f6(f3)=max0.3+0.41+0.80.7+0.8=1.8由于g(e3)+g(f2)=7<8，不符合第三學(xué)年的學(xué)分

27、要求，則舍去此解。從而有f6(e3)=1.5。這說明由e3到h的最大滿意度為1.5，其路徑為e3f3g1h，相應(yīng)決策為u6*e3=f3。從e4到h有兩條路線，需加以比較，取其中平均喜好程度最大的，即：f6e4=maxde4,f1+f6f1de4,f2+f6f2=max0.3+0.30.5+0.5=1由于g(e4)+g(f1)=7<8，不符合第三學(xué)年的學(xué)分要求，則舍去此解。由于g(e4)+g(f2)=6<8，不符合第三學(xué)年的學(xué)分要求，則舍去此解。從而舍去此決策。4. 第四步，k=5，狀態(tài)變量s5可取五個(gè)值d1，d2，d3，d4 ,d5。從d1到h有四條路線，需加以比較，取其中平均喜好

28、程度最大的，即：f5d1=maxdd1,e1+f5e1dd1,e2+f5e2dd1,e3+f5e3dd1,e4+f5e4=max0.3+1.50.5+1.50.7+1.80.5+1=2.5這說明由d1到h的最大滿意度為2.5，其路徑為d1e3f3g1h，相應(yīng)決策為u5*d1=e3。從d2到h有四條路線，需加以比較，取其中平均喜好程度最大的，即：f5d2=maxdd2,e1+f5e1dd2,e2+f5e2dd2,e3+f5e3dd2,e4+f5e4=max0.3+1.50.5+1.50.7+1.80.3+1=2.5這說明由d2到h的最大滿意度為2.5，其路徑為d2e3f3g1h，相應(yīng)決策為u5*

29、d2=e3。從d3到h有四條路線，需加以比較，取其中平均喜好程度最大的，即：f5d3=maxdd3,e1+f5e1dd3,e2+f5e2dd3,e3+f5e3dd3,e4+f5e4=max0.5+1.50.3+1.50.7+1.80.5+1=2.5這說明由d3到h的最大滿意度為2.5，其路徑為d3e3f3g1h，相應(yīng)決策為u5*d3=e3。從d4到h有四條路線，需加以比較，取其中平均喜好程度最大的，即：f5d4=maxdd4,e1+f5e1dd4,e2+f5e2dd4,e3+f5e3dd4,e4+f5e4=max0.5+1.50.5+1.51+1.80.5+1=2.8這說明由d4到h的最大滿意

30、度為2.8，其路徑為d4e3f3g1h，相應(yīng)決策為u5*d4=e3。從d5到h有四條路線，需加以比較，取其中平均喜好程度最大的，即：f5d5=maxdd5,e1+f5e1dd5,e2+f5e2dd5,e3+f5e3dd5,e4+f5e4=max0.5+1.50.7+1.51+1.80.7+1=2.8這說明由d5到h的最大滿意度為2.8，其路徑為d5e3f3g1h，相應(yīng)決策為u5*d5=e3。5. 第五步，k=4，狀態(tài)變量s4可取四個(gè)值c1，c2，c3，c4 。從c1到h有五條路線，需加以比較，取其中平均喜好程度最大的，即：f4c1=maxdc1,d1+f4d1dc1,d2+f4d2dc1,d3

31、+f4d3dc1,d4+f4d4dc1,d5+f4d5=max0.3+2.50.1+2.50.5+2.50.7+2.81+2.8=3.8由于g(c1)+g(d5)=7<8，不符合第二學(xué)年的學(xué)分要求，則舍去此解。從而有f4(c1)=3.5。這說明由c1到h的最大滿意度為3.5，其路徑為c1d4e3f3g1h，相應(yīng)決策為u4*c1=d4。從c2到h有四條路線，需加以比較，取其中平均喜好程度最大的，即：f4c2=maxdc2,d2+f4d2dc2,d3+f4d3dc2,d4+f4d4dc2,d5+f4d5=max0.5+2.50.5+2.50.3+2.80.7+2.8=3.5由于g(c2)+g

32、(d5)=7<8，不符合第二學(xué)年的學(xué)分要求，則舍去此解。這說明由c2到h的最大滿意度為3.0，其路徑為c2d4e3f3g1h，相應(yīng)決策為u4*c2=d4。從c3到h有四條路線，需加以比較，取其中平均喜好程度最大的，即：f4c3=maxdc3,d2+f4d2dc3,d3+f4d3dc3,d4+f4d4dc3,d5+f4d5=max0.1+2.50.5+2.50.5+2.80.7+2.8=3.5這說明由c3到h的最大滿意度為3.5，其路徑為c3d5e3f3g1h，相應(yīng)決策為u4*c3=d5。從c4到h有四條路線，需加以比較，取其中平均喜好程度最大的，即：f4c4=maxdc4,d2+f4d2

33、dc4,d3+f4d3dc4,d4+f4d4dc4,d5+f4d5=max0.7+2.51+2.50.7+2.80.5+2.8=3.5由于g(c4)+g(d2)=6<8，不符合第二學(xué)年的學(xué)分要求，則舍去此解。由于g(c4)+g(d4)=7<8，不符合第二學(xué)年的學(xué)分要求，則舍去此解。由于g(c4)+g(d5)=6<8，不符合第二學(xué)年的學(xué)分要求，則舍去此解。這說明由c4到h的最大滿意度為3.5，其路徑為c4d3e3f3g1h，相應(yīng)決策為u4*c4=d3。6. 第六步，k=3，狀態(tài)變量s3可取三個(gè)值b1，b2，b3 。從b1到h有四條路線，需加以比較，取其中平均喜好程度最大的，即：

34、f3b1=maxdb1,c1+f3c1db1,c2+f3c2db1,c3+f3c3db1,c4+f3c4=max0.3+3.80.3+3.50.3+3.50.7+3.5=4.2這說明由b1到h的最大滿意度為4.2，其路徑為b1c4d3e3f3g1h，相應(yīng)決策為u3*b1=c4。從b2到h有四條路線，需加以比較，取其中平均喜好程度最大的，即：f3b2=maxdb2,c1+f3c1db2,c2+f3c2db2,c3+f3c3db2,c4+f3c4=max0.7+3.80.3+3.50.3+3.51+3.5=4.5這說明由b2到h的最大滿意度為4.5，其路徑為b2c4d3e3f3g1h，相應(yīng)決策為u

35、3*b2=c4。從b3到h有四條路線，需加以比較，取其中平均喜好程度最大的，即：f3b3=maxdb3,c1+f3c1db3,c2+f3c2db3,c3+f3c3db3,c4+f3c4=max0.7+3.80.5+3.50.5+3.51+3.5=4.5這說明由b3到h的最大滿意度為4.5，其路徑為b3c4d3e3f3g1h，相應(yīng)決策為u3*b3=c4。7. 第七步，k=2，狀態(tài)變量s2可取三個(gè)值a1，a2，a3 。從a1到h有四條路線，需加以比較，取其中平均喜好程度最大的，即：f2a1=maxda1,b1+f2b1da1,b2+f2b2da1,b3+f2b3=max0.3+4.20.5+4.2

36、1+4.5=5.5由于g(a1)+g(b3)=7<8，不符合第二學(xué)年的學(xué)分要求，則舍去此解。這說明由a1到h的最大滿意度為4.7，其路徑為a1b2c4d3e3f3g1h，相應(yīng)決策為u2*a1=b2。從a2到h有四條路線，需加以比較，取其中平均喜好程度最大的，即：f2a2=maxda2,b1+f2b1da2,b2+f2b2da2,b3+f2b3=max0.5+4.20.5+4.20.7+4.5=5.2由于g(a2)+g(b3)=6<8，不符合第二學(xué)年的學(xué)分要求，則舍去此解。由于g(a2)+g(b2)=7<8，不符合第二學(xué)年的學(xué)分要求，則舍去此解。這說明由a2到h的最大滿意度為5

37、.2，其路徑為a2b1c4d3e3f3g1h，相應(yīng)決策為u2*a2=b1。從a3到h有四條路線，需加以比較，取其中平均喜好程度最大的，即：f2a3=maxda3,b1+f2b1da3,b2+f2b2da3,b3+f2b3=max1+4.20.7+4.20.5+4.5=5.2由于g(a3)+g(b3)=6<8，不符合第二學(xué)年的學(xué)分要求，則舍去此解。由于g(a3)+g(b2)=7<8，不符合第二學(xué)年的學(xué)分要求，則舍去此解。這說明由a3到h的最大滿意度為5.2，其路徑為a3b1c4d3e3f3g1h，相應(yīng)決策為u2*a3=b1。8. 第八步，k=1，只有一個(gè)狀態(tài)點(diǎn)o，則 f1o=maxd

38、o,a1+f2a1do,a2+f2a2do,a3+f2a3=max0.5+5.50.5+5.51+5.2=6.2即從o到h的最大滿意程度為6.2，本段決策為u1*o=a3。所以此動(dòng)態(tài)規(guī)劃的最優(yōu)路線為：oa3b1c4d3e3f3g1h。3.4 得出最優(yōu)解從而可以得出所可以選擇的最優(yōu)課程選擇為：第一學(xué)年：web應(yīng)用程序設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)第二學(xué)年：朋輩心理學(xué)，數(shù)學(xué)建模第三學(xué)年：運(yùn)籌學(xué)，最優(yōu)化方法第四學(xué)年：xml應(yīng)用程序設(shè)計(jì)，java web應(yīng)用程序設(shè)計(jì)第四章 問題與展望4.1 結(jié)果分析本文運(yùn)用動(dòng)態(tài)規(guī)劃原理解決了該大學(xué)生選修課的選擇問題，為其四年的選修課找到了一個(gè)最優(yōu)選擇。同時(shí)也說明了動(dòng)態(tài)規(guī)劃在解決選課問

39、題方面具有的可行性。在本論文中，創(chuàng)新的使用了平均喜好程度這一概念作為選修課選擇的標(biāo)準(zhǔn)，既將對(duì)于某課程的喜好程度進(jìn)行了量化，又成為解決選修課的選擇的重要標(biāo)準(zhǔn)。4.2 本文的不足與尚可改進(jìn)之處本文所建立的動(dòng)態(tài)規(guī)劃模型具有一定的局限性，只考慮了具體某一個(gè)同學(xué)的選課問題。而且在選課過程中，默認(rèn)的認(rèn)為一定能選到所要選擇的課程，不考慮抽簽過程。在本論文基礎(chǔ)上，可以通過matlab編程實(shí)現(xiàn)最優(yōu)解的求解過程，從而建立新型選課系統(tǒng)程序。4.3 matlab 簡(jiǎn)介與程序?qū)崿F(xiàn)4.3.1 matlab軟件簡(jiǎn)介matlab是由美國mathworks公司發(fā)布的主要面對(duì)科學(xué)計(jì)算、可視化以及交互式程序設(shè)計(jì)的高科技計(jì)算環(huán)境。它

40、將數(shù)值分析、矩陣計(jì)算、科學(xué)數(shù)據(jù)可視化以及非線性動(dòng)態(tài)系統(tǒng)的建模和仿真等諸多強(qiáng)大功能集成在一個(gè)易于使用的視窗環(huán)境中，為科學(xué)研究、工程設(shè)計(jì)以及必須進(jìn)行有效數(shù)值計(jì)算的眾多科學(xué)領(lǐng)域提供了一種全面的解決方案，并在很大程度上擺脫了傳統(tǒng)非交互式程序設(shè)計(jì)語言（如c、fortran）的編輯模式，代表了當(dāng)今國際科學(xué)計(jì)算軟件的先進(jìn)水平 【6】。matlab所具有的優(yōu)點(diǎn)：1. 高效的數(shù)值計(jì)算及符號(hào)計(jì)算功能,能使用戶從繁雜的數(shù)學(xué)運(yùn)算分析中解脫出來；2. 具有完備的圖形處理功能,實(shí)現(xiàn)計(jì)算結(jié)果和編程的可視化；3. 友好的用戶界面及接近數(shù)學(xué)表達(dá)式的自然化語言,使學(xué)者易于學(xué)習(xí)和掌握；4. 功能豐富的應(yīng)用工具箱(如信號(hào)處理工具箱、

41、通信工具箱等) ,為用戶提供了大量方便實(shí)用的處理工具【7】。4.3.2 動(dòng)態(tài)規(guī)劃的matlab程序本文中的動(dòng)態(tài)規(guī)劃模型可以用matlab程序編程實(shí)現(xiàn)，由于時(shí)間問題以及8階段的動(dòng)態(tài)規(guī)劃模型程序過于復(fù)雜，所以在此僅附一個(gè)四階段的動(dòng)態(tài)規(guī)劃模型的matlab實(shí)現(xiàn)程序見附錄2。參考文獻(xiàn)1 徐光輝. 運(yùn)籌學(xué)基礎(chǔ)手冊(cè).北京：科學(xué)出版社，1999 2 胡運(yùn)權(quán). 運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用（第4版）.北京：高等教育出版社，20043 郭耀煌. 運(yùn)籌學(xué)原理與方法.程度：西南交通大學(xué)出版社，19944 弗雷德里克·s. 任建標(biāo)譯.數(shù)據(jù)、模型與決策.北京：中國財(cái)政經(jīng)濟(jì)出版社，20015 王日爽. 應(yīng)用動(dòng)態(tài)規(guī)劃.北京：

42、國防工業(yè)出版社,19876 劉則毅. 科學(xué)計(jì)算技術(shù)與matlab. 北京：科學(xué)出版社，2001.7 張志涌. 精通matlab 6. 5 版m . 北京:北京航空航天大學(xué)出版社,2003.8 bellman r e. dynamic programming. princeton university press,19579 peterman m l. markov decision process-stochastic dp. john wileysons,1994附錄附錄1：參考英文及譯文：原文dynamic programming: from novice to advancedan im

43、portant part of given problems can be solved with the help of dynamic programming (dp for short). being able to tackle problems of this type would greatly increase your skill. i will try to help you in understanding how to solve problems using dp. the article is based on examples, because a raw theo

44、ry is very hard to understand. note: if you're bored reading one section and you already know what's being discussed in it - skip it and go to the next one. introduction (beginner)what is a dynamic programming, how can it be described? a dp is an algorithmic technique which is usually based

45、on a recurrent formula and one (or some) starting states. a sub-solution of the problem is constructed from previously found ones. dp solutions have a polynomial complexity which assures a much faster running time than other techniques like backtracking, brute-force etc. now let's see the base o

46、f dp with the help of an example: given a list of n coins, their values (v1, v2, . , vn), and the total sum s. find the minimum number of coins the sum of which is s (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up

47、 to s. now let's start constructing a dp solution: first of all we need to find a state for which an optimal solution is found and with the help of which we can find the optimal solution for the next state. what does a "state" stand for? it's a way to describe a situation, a sub-so

48、lution for the problem. for example a state would be the solution for sum i, where is. a smaller state than state i would be the solution for any sum j, where j<i. for finding a state i, we need to first find all smaller states j (j<i) . having found the minimum number of coins which sum up to

49、 i, we can easily find the next state - the solution for i+1. how can we find it? it is simple - for each coin j, vji, look at the minimum number of coins found for the i-vjsum (we have already found it previously). let this number be m. if m+1 is less than the minimum number of coins already found

50、for current sum i, then we write the new result for it. for a better understanding let's take this example:given coins with values 1, 3, and 5.and the sum s is set to be 11. first of all we mark that for state 0 (sum 0) we have found a solution with a minimum number of 0 coins. we then go to sum

51、 1. first, we mark that we haven't yet found a solution for this one (a value of infinity would be fine). then we see that only coin 1 is less than or equal to the current sum. analyzing it, we see that for sum 1-v1= 0 we have a solution with 0 coins. because we add one coin to this solution, we

52、'll have a solution with 1 coin for sum 1. it's the only solution yet found for this sum. we write (save) it. then we proceed to the next state - sum 2. we again see that the only coin which is less or equal to this sum is the first coin, having a value of 1. the optimal solution found for s

53、um (2-1) = 1 is coin 1. this coin 1 plus the first coin will sum up to 2, and thus make a sum of 2 with the help of only 2 coins. this is the best and only solution for sum 2. now we proceed to sum 3. we now have 2 coins which are to be analyzed - first and second one, having values of 1 and 3. let&

54、#39;s see the first one. there exists a solution for sum 2 (3 - 1) and therefore we can construct from it a solution for sum 3 by adding the first coin to it. because the best solution for sum 2 that we found has 2 coins, the new solution for sum 3 will have 3 coins. now let's take the second co

55、in with value equal to 3. the sum for which this coin needs to be added to make 3 , is 0. we know that sum 0 is made up of 0 coins. thus we can make a sum of 3 with only one coin - 3. we see that it's better than the previous found solution for sum 3 , which was composed of 3 coins. we update it and mark it as having o