1、 贛南師院數學建模辦×數學建模協會目錄專題一.線性規劃.3專題二.動態規劃.13專題三.層次分析法.22專題四.馬爾可夫鏈.30專題五.排隊論理論.39專題六.簡單的圖論運用.48專題七.模糊數學.74專題八.對策論應用示例.88專題一 線性規劃§1 線性規劃在人們的生產實踐中，經常會遇到如何利用現有資源來安排生產，以取得最大經濟效益的問題。此類問題構成了運籌學的一個重要分支數學規劃，而線性規劃(Linear Programming 簡記LP)則是數學規劃的一個重要分支。自從1947年G. B. Dantzig 提出求解線性規劃的單純形方法以來，線性規劃在理論上趨向成熟，在

2、實用中日益廣泛與深入。特別是在計算機能處理成千上萬個約束條件和決策變量的線性規劃問題之后，線性規劃的適用領域更為廣泛了，已成為現代管理中經常采用的基本方法之一。1.1 線性規劃的實例與定義例1 某機床廠生產甲、乙兩種機床，每臺銷售后的利潤分別為4000元與3000元。生產甲機床需用機器加工，加工時間分別為每臺2小時和1小時；生產乙機床需用三種機器加工，加工時間為每臺各一小時。若每天可用于加工的機器時數分別為機器10小時、機器8小時和機器7小時，問該廠應該生產甲、乙機床各幾臺，才能使總利潤最大？上述問題的數學模型：設該廠生產臺甲種機床和乙機床時總利潤最大，則應滿足（目標函數） (1)s.t.（約

3、束條件） （2）這里變量稱之為決策變量，（1）被稱為問題的目標函數，（2）中的幾個不等式是問題的約束條件，記為s.t.(即subject to)。上述即為規劃問題數學模型的三個要素。由于上面的目標函數及約束條件均為線性函數，故被稱為線性規劃問題。總之，線性規劃問題是在一組線性約束條件的限制下，求線性目標函數最大或最小的問題。在解決實際問題時，把問題歸結成一個線性規劃數學模型是很重要的一步，但往往也是困難的一步，模型建立得是否恰當，直接影響到求解。而選取適當的決策變量，是我們建立有效模型的關鍵之一。1.2 線性規劃的Matlab標準形式線性規劃的目標函數可以是求解最大值，也可以是求最小值，約束條

4、件的不等號可以是小于號也可以是大于號。為了避免這種形式多樣性帶來的不便，Matlab中規定線性規劃的標準形式為：其中和為維列向量，為維列向量，為矩陣。例如線性規劃：的Matlab標準型式為：1.3 線性規劃問題的解的概念一般線性規劃問題的標準型為 (3) (4)可行解 滿足約束條件（4）的解，稱為線性規劃問題的可行解，而使目標函數（3）達到最小值的可行解叫最優解。可行域 所有可行解構成的集合稱為問題的可行域，記為。1.4 線性規劃的圖解法圖解法簡單直觀，有助于了解線性規劃問題求解的基本原理。我們先應用圖解法來求解例1。如上圖所示，陰影區域即為LP問題的可行域R。對于每一固定的值，使目標函數值等

5、于的點構成的直線稱為目標函數等位線，當變動時，我們得到一族平行直線。讓等位線沿目標函數值減小的方向移動，直到等位線與可行域有交點的最后位置，此時的交點（一個或多個）即為LP的最優解。對于例1，顯然等位線越趨于右上方，其上的點具有越大的目標函數值。不難看出，本例的最優解為，最優目標值。從上面的圖解過程可以看出并不難證明以下斷言：（1）可行域可能會出現多種情況。可能是空集也可能是非空集合，當非空時，它必定是若干個半平面的交集（除非遇到空間維數的退化）。既可能是有界區域，也可能是無界區域。（2）在非空時，線性規劃既可以存在有限最優解，也可以不存在有限最優解（其目標函數值無界）。（3）R非空且LP有有

6、限最優解時，最優解可以唯一或有無窮多個。（4）若線性規劃存在有限最優解，則必可找到具有最優目標函數值的可行域的“頂點”。上述論斷可以推廣到一般的線性規劃問題，區別只在于空間的維數。在一般的維空間中，滿足線性等式的點集被稱為一個超平面，而滿足一線性不等式（或）的點集被稱為一個半空間（其中為一維行向量，為一實數）。有限個半空間的交集被稱為多胞形，有界的多胞形又被稱為多面體。易見，線性規劃的可行域必為多胞形（為統一起見，空集也被視為多胞形）。在一般維空間中，要直接得出多胞形“頂點”概念還有一些困難。二維空間中的頂點可以看成為邊界直線的交點，但這一幾何概念的推廣在一般維空間中的幾何意義并不十分直觀。為

7、此，我們將采用另一途徑來定義它。定義1 稱維空間中的區域為一凸集，若及，有。定義2 設為維空間中的一個凸集，中的點被稱為的一個極點，若不存在及，使得。定義1 說明凸集中任意兩點的連線必在此凸集中；而定義2 說明，若是凸集的一個極點，則不能位于中任意兩點的連線上。不難證明，多胞形必為凸集。同樣也不難證明，二維空間中可行域的頂點均為的極點（也沒有其它的極點）。1.5 求解線性規劃的Matlab解法單純形法是求解線性規劃問題的最常用、最有效的算法之一。單純形法是首先由George Dantzig于1947年提出的，近60年來，雖有許多變形體已被開發，但卻保持著同樣的基本觀念。由于有如下結論：若線性規

8、劃問題有有限最優解，則一定有某個最優解是可行區域的一個極點。基于此，單純形法的基本思路是：先找出可行域的一個極點，據一定規則判斷其是否最優；若否，則轉換到與之相鄰的另一極點，并使目標函數值更優；如此下去，直到找到某一最優解為止。這里我們不再詳細介紹單純形法，有興趣的讀者可以參看其它線性規劃書籍。下面我們介紹線性規劃的Matlab解法。Matlab5.3中線性規劃的標準型式為：基本函數形式為linprog(c,A,b)，它的返回值是向量的值。還有其它的一些函數調用形式（在 Matlab 指令窗運行 help linprog 可以看到所有的函數調用形式），如：x,fval=linprog(c,A,

9、b,Aeq,beq,LB,UB,X0,OPTIONS)這里fval返回目標函數的值，Aeq和beq對應等式約束，LB和UB分別是變量的下界和上界，是的初始值，OPTIONS是控制參數。 例2 求解下列線性規劃問題 解 （i）編寫M文件c=2;3;-5;a=-2,5,-1; b=-10;aeq=1,1,1;beq=7;x=linprog(-c,a,b,aeq,beq,zeros(3,1)value=c'*x（ii）將M文件存盤，并命名為example1.m。（iii）在Matlab指令窗運行example1即可得所求結果。此問題也可以通過線性規劃軟件Lindo求解max 2x1+3x2-

10、5x3s.t.x1+x2+x3=72x1-5x2+x3>=10x1>=0x2>=0x3>=0例3 求解線性規劃問題 解 編寫Matlab程序如下：c=2;3;1;a=1,4,2;3,2,0;b=8;6;x,y=linprog(c,-a,-b,zeros(3,1)編寫Lindo程序為：min 2x1+3x2+x3s.t.x1+4x2+2x3>=83x1+2x2>=6x1>=0x2>=0x3>=0§2 運輸問題(產銷平衡)例4 某商品有個產地、個銷地，各產地的產量分別為，各銷地的需求量分別為。若該商品由產地運到銷地的單位運價為，問應該

11、如何調運才能使總運費最省？解：引入變量，其取值為由產地運往銷地的該商品數量，數學模型為 s.t. 顯然是一個線性規劃問題，當然可以用單純形法求解。對產銷平衡的運輸問題，由于有以下關系式存在：其約束條件的系數矩陣相當特殊，可用比較簡單的計算方法，習慣上稱為表上作業法（由康托洛維奇和希奇柯克兩人獨立地提出，簡稱康希表上作業法）。 表上作業法是單純形法在求解運輸問題時的一種簡化方法，其求解工作在運輸表上進行逐步迭代如下：先按某一規則找出一個初始解（初始調運方案）；再對現行解作最優性判斷；若這個解不是最優的，就在運輸表上對它進行調整改進，得一新解；再判斷，再改進，直到得到最優解。 有關供過于求和供不應

12、求的情況可以參見運用運籌學一書，書中有比較詳細的介紹。§3 指派問題（又稱分配問題Assignment Problem）3.1 指派問題的數學模型例5 擬分配人去干項工作，每人干且僅干一項工作，若分配第人去干第項工作，需花費單位時間，問應如何分配工作才能使工人花費的總時間最少？容易看出，要給出一個指派問題的實例，只需給出矩陣，被稱為指派問題的系數矩陣。引入變量，若分配干工作，則取，否則取。上述指派問題的數學模型為 s.t. (5)(5)的可行解既可以用一個矩陣(稱為解矩陣)表示，其每行每列均有且只有一個元素為1，其余元素均為0，也可以用中的一個置換表示。(5)的變量只能取0或1，從而

13、是一個0-1規劃問題。一般的0-1規劃問題求解極為困難。但指派問題并不難解，其約束方程組的系數矩陣十分特殊（被稱為全單位模矩陣，其各階非零子式均為），其非負可行解的分量只能取0或1，故約束可改寫為而不改變其解。此時，指派問題被轉化為一個特殊的運輸問題，其中，。3.2 求解指派問題的匈牙利算法由于指派問題的特殊性，又存在著由匈牙利數學家D.Konig提出的更為簡便的解法匈牙利算法。算法主要依據以下事實：如果系數矩陣一行（或一列）中每一元素都加上或減去同一個數，得到一個新矩陣 ，則以或為系數矩陣的指派問題具有相同的最優指派。利用上述性質，可將原系數陣C 變換為含零元素較多的新系數陣B，而

14、最優解不變。若能在B 中找出n個位于不同行不同列的零元素，令解矩陣中相應位置的元素取值為1，其它元素取值為零，則所得該解是以B為系數陣的指派問題的最優解，從而也是原問題的最優解。由C到B的轉換可通過先讓矩陣C的每行元素均減去其所在行的最小元素得矩陣D，D的每列元素再減去其所在列的最小元素得以實現。下面通過一例子來說明該算法。例6 求解指派問題，其系數矩陣為 解 將第一行元素減去此行中的最小元素15，同樣，第二行元素減去17，第三行元素減去17，最后一行的元素減去16，得 再將第3列元素各減去1，得 以為系數矩陣的指派問題有最優指派 由等價性，它也是例7的最優指派。例7 求解系數矩陣的指派問題

15、解：先作等價變換如下 容易看出，從變換后的矩陣中只能選出四個位于不同行不同列的零元素，但，最優指派還無法看出。此時等價變換還可進行下去。步驟如下：(1) 對未選出0元素的行打；(2) 對行中0元素所在列打；(3) 對列中選中的0元素所在行打；重復（2）、（3）直到無法再打為止。可以證明，若用直線劃沒有打的行與打的列，就得到了能夠覆蓋住矩陣中所有零元素的最少條數的直線集合，找出未覆蓋的元素中的最小者，令行元素減去此數，列元素加上此數，則原先選中的0元素不變，而未覆蓋元素中至少有一個已轉變為0，且新矩陣的指派問題與原問題也等價。上述過程可反復采用，直到能選取出足夠的0元素為止。例如，對例5變換后的

16、矩陣再變換，第三行、第五行元素減去2，第一列元素加上2，得 現在已可看出，最優指派為。§4 靈敏度分析4.1 靈敏度分析靈敏度分析是指對系統或周圍事物因周圍條件變化顯示出來的敏感程度的分析。目標函數：max z=x1+x2+x3+x4約束條件：x5+x6+x7+x8>=250000x1+x5<=380000x2+x6<=265200x3+x7<=408100x4+x8<=1301002.85x1-1.42x2+4.27x3-18.49x4>=02.85x5-1.42x6+4.27x7-18.49x8>=016.5x1+2.0x2-4.0x3+

17、17x4>=07.5x5-7.0x6-13.0x7+8.0x8>=0xj>=0(j=1,2.,8)下面我們就用LINDO來解這一優化問題。輸入語句：max(不區分大小寫) x1+x2+x3+x4ST(大寫或寫subject to)x5+x6+x7+x8>=250000x1+x5<=380000x2+x6<=265200x3+x7<=408100x4+x8<=1301002.85x1-1.42x2+4.27x3-18.49x4>=02.85x5-1.42x6+4.27x7-18.49x8>=016.5x1+2.0x2-4.0x3+17x

18、4>=07.5x5-7.0x6-13.0x7+8.0x8>=0end然后再按運算符鍵即可得結果。LINDO是規定j非負的，我們可發現輸入方式與我們的數學書寫的形式基本一致，運算后，計算機會問您是否需要靈敏度分析，我們選擇是，結果如下：LP OPTIMUM FOUND AT STEP      6        OBJECTIVE FUNCTION VALUE        1) 

19、60;    933400.0  VARIABLE        VALUE          REDUCED COST        X1    161351.734375          0.000000

20、        X2    265200.000000          0.000000        X3    408100.000000          0.000000    &

21、#160;   X4     98748.265625          0.000000        X5    218648.265625          0.000000X6     

22、60;   0.000000          0.000000        X7         0.000000          0.000000        X8

23、60;    31351.734375          0.000000       ROW   SLACK OR SURPLUS     DUAL PRICES        2)         0.00

24、0000         -1.000000        3)         0.000000          1.000000        4)    

25、0;    0.000000          1.000000        5)         0.000000          1.000000       

26、6)         0.000000          1.000000        7)         0.000000          0.000000  &

27、#160;     8)     43454.000000          0.000000        9)   3239024.250000          0.000000     

28、60; 10)   1890675.875000          0.000000 NO. ITERATIONS=       6 RANGES IN WHICH THE BASIS IS UNCHANGED:                 &#

29、160;         OBJ COEFFICIENT RANGES VARIABLE         CURRENT        ALLOWABLE        ALLOWABLE       

30、0;           COEF          INCREASE         DECREASE       X1        1.000000    

31、;     0.000000         1.154137       X2        1.000000         INFINITY         0.000000 

32、;      X3        1.000000         INFINITY         0.000000       X4        1.000000  

33、;       0.000000         0.000000       X5        0.000000         1.154137         0

34、.000000       X6        0.000000         0.000000         INFINITY       X7        0.00000

35、0         0.000000         INFINITY       X8        0.000000         0.000000      &#

36、160;  0.000000                           RIGHTHAND SIDE RANGES      ROW         CURRENT  &

37、#160;     ALLOWABLE        ALLOWABLE                    RHS          INCREASE    

38、0;    DECREASE        2   250000.000000    186222.062500    234752.984375        3   380000.000000    234752.984375     15247.0175

39、78        4   265200.000000     30601.410156    265200.000000        5   408100.000000    156685.250000     10176.581055   &#

40、160;    6   130100.000000      2350.135254     36184.207031        7        0.000000     43454.000000    669046.000000 &

41、#160;      8        0.000000     43454.000000         INFINITY        9        0.000000   3239024.25

42、0000         INFINITY       10        0.000000   1890675.875000         INFINITY下面給出其結果的一般解釋：“LP OPTIMUM FOUND AT STEP 6”表示LINDO在（用單純形法）次迭代或旋轉后得到

43、最優解。“OBJECTIVE FUNCTION VALUE 1)933400.0”表示最優目標值為933400。“VALUE”給出最優解中各變量的值。“SLACK OR SURPLUS”給出松弛變量的值。上例中SLK 2= 第二行松弛變量（模型第一行表示目標函數，所以第二行對應第一個約束）“REDUCE COST”列出最優單純形表中判別數所在行的變量的系數，表示當變量有微小變動時，目標函數的變化率，其中基變量的reduce cost 值應為，對于非基變量j相應的reduce cost值表示j增加一個單位（此時假定其他非基變量保持不變）時目標函數減小的量（max 型問題）。上例中：X1 對應的

44、reduce cost 值為，表示當X1=1 時，目標函數值不變。“DUAL PRICE”（對偶價格）列出最優單純形表中判別數所在行的松弛變量的系數，表示當對應約束有微小變動時，目標函數的變化率，輸出結果中對應每一個約束有一個對偶價格。若其數值為，表示對應約束中不等式右端項若增加一個單位，目標函數將增加個單位（max 型問題）。上例中：第二行對應的對偶價格值應為-表示當約束）X5 + X6 + X7 + X8>250000變為）X5 + X6 + X7 + X8>250001時，目標函數值933400-1933399當REDUCE COST 或DUAL PRICE  的值

45、為。表示當微小擾動不影響目標函數。有時，通過分析DUAL PRICE，也可對產生不可行問題的原因有所了解。靈敏度分析：如果做敏感性分析，則系統報告當目標函數的費用系數和約束右端項在什么范圍變化（此時假定其他系數保持不變）時，最優基保持不變。報告中INFINITY表示正無窮，如上例：目標函數中的變量系數為，當它在1-1.154137,1-0=-0.154137,1 變化時，最優基保持不變 。第一個約束右端項為250000，當它在250000-234752.984375,250000+186222.0625=15247.015625,436222.0625 范圍變化時，最優基保持不變 。當您要判斷

46、表達式輸入是否有錯誤時，也可以使用菜單“Reports“的”Picture“選項。若想獲得靈敏度分析，可用“Reports“的”Rang“選項。若需顯示單純形表，可執行“Reports“的”Tab lean“選項。注意事項：） 目標函數及各約束條件之間一定要有“Subject to (ST) ”分開。） 變量名不能超過個字符。） 變量與其系數間可以有空格，單不能有任何運算符號（如乘號“”等）。） 要輸入<=或>=約束，相應以<或>代替即可。） 一般LINDO中不能接受括號“（）“和逗號“，“，例：400(X1+X2) 需寫成400X1+400X2；10,000需寫成10

47、000。在以前討論線性規劃問題時，假定都是常數。但實際上這些系數往往是估計值和預測值。如市場條件一變，值就會變化；往往是因工藝條件的改變而改變；是根據資源投入后的經濟效果決定的一種決策選擇。因此提出這樣兩個問題：當這些參數有一個或幾個發生變化時，已求得的線性規劃問題的最優解會有什么變化；或者這些參數在什么范圍內變化時，線性規劃問題的最優解不變。這里我們就不討論了。4.2 參數線性規劃參數線性規劃是研究這些參數中某一參數連續變化時，使最優解發生變化的各臨界點的值。即把某一參數作為參變量，而目標函數在某區間內是這參變量的線性函數，含這參變量的約束條件是線性等式或不等式。因此仍可用單純形法和對偶單純

48、形法進行分析參數線性規劃問題。專題二 動態規劃§1 引言1.1 動態規劃的發展及研究內容動態規劃（dynamic programming）是運籌學的一個分支，是求解多階段決策問題的最優化方法。20世紀50年代初R. E. Bellman等人在研究多階段決策過程(multistep decision process)的優化問題時，提出了著名的最優性原理（principle of optimality），把多階段過程轉化為一系列單階段問題，逐個求解，創立了解決這類過程優化問題的新方法動態規劃。1957年出版了他的名著Dynamic Programming，這是該領域的第一本著作。動態規劃

49、問世以來，在經濟管理、生產調度、工程技術和最優控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題，用動態規劃方法比用其它方法求解更為方便。雖然動態規劃主要用于求解以時間劃分階段的動態過程的優化問題，但是一些與時間無關的靜態規劃（如線性規劃、非線性規劃），只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態規劃方法方便地求解。應指出，動態規劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種特殊算法（如線性規劃是一種算法）。因而，它不象線性規劃那樣有一個標準的數學表達式和明確定義的一組規則，而必須對具體問題進行具體分析處理。因此，在學習時，除

50、了要對基本概念和方法正確理解外，應以豐富的想象力去建立模型，用創造性的技巧去求解。例1 最短路線問題 下面是一個線路網，連線上的數字表示兩點之間的距離（或費用）。試尋求一條由到距離最短（或費用最省）的路線。例2 生產計劃問題工廠生產某種產品，每單位（千件）的成本為1（千元），每次開工的固定成本為3（千元），工廠每季度的最大生產能力為6（千件）。經調查，市場對該產品的需求量第一、二、三、四季度分別為2，3，2，4（千件）。如果工廠在第一、二季度將全年的需求都生產出來，自然可以降低成本（少付固定成本費），但是對于第三、四季度才能上市的產品需付存儲費，每季每千件的存儲費為0.5（千元）。還規定年初和

51、年末這種產品均無庫存。試制定一個生產計劃，即安排每個季度的產量，使一年的總費用（生產成本和存儲費）最少。1.2 決策過程的分類 根據過程的時間變量是離散的還是連續的，分為離散時間決策過程（discrete-time decision process）和連續時間決策過程（continuous-time decision process）；根據過程的演變是確定的還是隨機的，分為確定性決策過程（deterministic decision process）和隨機性決策過程（stochastic decision process），其中應用最廣的是確定性多階段決策過程。§2 基本概念、基本方

52、程和計算方法2.1 動態規劃的基本概念和基本方程一個多階段決策過程最優化問題的動態規劃模型通常包含以下要素。2.1.1 階段階段(step)是對整個過程的自然劃分。通常根據時間順序或空間順序特征來劃分階段，以便按階段的次序解優化問題。階段變量一般用表示。在例1中由出發為，由出發為，依此下去從出發為，共個階段。在例2中按照第一、二、三、四季度分為，共四個階段。2.1.2 狀態狀態（state）表示每個階段開始時過程所處的自然狀況。它應能描述過程的特征并且無后效性，即當某階段的狀態變量給定時，這個階段以后過程的演變與該階段以前各階段的狀態無關。通常還要求狀態是直接或間接可以觀測的。描述狀態的變量稱

53、狀態變量（state variable）。變量允許取值的范圍稱允許狀態集合(set of admissible states)。用表示第階段的狀態變量，它可以是一個數或一個向量。用表示第階段的允許狀態集合。在例1中可取，或將定義為，則或，而。個階段的決策過程有個狀態變量，表示演變的結果。在例1中取，或定義為，即。根據過程演變的具體情況，狀態變量可以是離散的或連續的。為了計算的方便有時將連續變量離散化；為了分析的方便有時又將離散變量視為連續的。狀態變量簡稱為狀態。2.1.3 決策當一個階段的狀態確定后，可以作出各種選擇從而演變到下一階段的某個狀態，這種選擇手段稱為決策（decision），在最優

54、控制問題中也稱為控制（control）。描述決策的變量稱決策變量（decision variable），變量允許取值的范圍稱允許決策集合（set of admissible decisions）。用表示第階段處于狀態時的決策變量，它是的函數，用表示的允許決策集合。在例1中可取或，可記作，而。決策變量簡稱決策。2.1.4 策略決策組成的序列稱為策略（policy）。由初始狀態開始的全過程的策略記作，即.由第階段的狀態開始到終止狀態的后部子過程的策略記作，即，.類似地，由第到第階段的子過程的策略記作.可供選擇的策略有一定的范圍，稱為允許策略集合(set of admissible policies

55、)，用表示。2.1.5. 狀態轉移方程在確定性過程中，一旦某階段的狀態和決策為已知，下階段的狀態便完全確定。用狀態轉移方程（equation of state transition）表示這種演變規律，寫作 （1）在例1中狀態轉移方程為。2.1.6. 指標函數和最優值函數指標函數(objective function)是衡量過程優劣的數量指標，它是定義在全過程和所有后部子過程上的數量函數，用表示，。指標函數應具有可分離性，即可表為的函數，記為并且函數對于變量是嚴格單調的。過程在第階段的階段指標取決于狀態和決策，用表示。指標函數由組成，常見的形式有：階段指標之和，即，階段指標之積，即，階段指標之極

56、大（或極小），即.這些形式下第到第階段子過程的指標函數為。根據狀態轉移方程指標函數還可以表示為狀態和策略的函數，即。在給定時指標函數對的最優值稱為最優值函數（optimal value function），記為，即，其中可根據具體情況取或。 最優策略和最優軌線使指標函數達到最優值的策略是從開始的后部子過程的最優策略，記作。是全過程的最優策略，簡稱最優策略（optimal policy）。從初始狀態出發，過程按照和狀態轉移方程演變所經歷的狀態序列稱最優軌線（optimal trajectory）。2.1.8 遞歸方程如下方程稱為遞歸方程 （2）在上述方程中，當為加法時取；當為乘法時，取。動態規劃

57、遞歸方程是動態規劃的最優性原理的基礎，即：最優策略的子策略，構成最優子策略。用狀態轉移方程（1）和遞歸方程（2）求解動態規劃的過程，是由逆推至，故這種解法稱為逆序解法。當然，對某些動態規劃問題，也可采用順序解法。這時，狀態轉移方程和遞歸方程分別為：， 縱上所述，如果一個問題能用動態規劃方法求解，那么，我們可以按下列步驟，首先建立起動態規劃的數學模型：（i）將過程劃分成恰當的階段。（ii）正確選擇狀態變量，使它既能描述過程的狀態，又滿足無后效性，同時確定允許狀態集合。 （iii）選擇決策變量，確定允許決策集合。（iv）寫出狀態轉移方程。（v）確定階段指標及指標函數的形式（階段指標之和，階段指標之

58、積，階段指標之極大或極小等）。（vi）寫出基本方程即最優值函數滿足的遞歸方程，以及端點條件。§3 逆序解法的計算框圖以自由終端、固定始端、指標函數取和的形式的逆序解法為例給出計算框圖，其它情況容易在這個基礎上修改得到。一般化的自由終端條件為 (3)其中為已知。固定始端條件可表示為。如果狀態和決策是連續變量，用數值方法求解時需按照精度要求進行離散化。設狀態的允許集合為.決策的允許集合為.狀態轉移方程和階段指標應對的每個取值和的每個取值計算，即，。最優值函數應對的每個取值計算。基本方程可以表為 （4）按照（3），（4）逆向計算出，為全過程的最優值。記狀態的最優決策為，由和按照狀態轉移方程

59、計算出最優狀態，記作。并得到相應的最優決策，記作。于是最優策略為。算法程序的框圖如下。圖的左邊部分是函數序列的遞推計算，可輸出全過程最優值，如果需要還可以輸出后部子過程最優值函數序列和最優決策序列。計算過程中存是備計算之用，在算完后可用將替換掉；存是備右邊部分讀之用。圖的右邊部分是最優狀態和最優決策序列的正向計算，可輸出最優策略和最優軌線。§4 動態規劃與靜態規劃的關系動態規劃與靜態規劃（線性和非線性規劃等）研究的對象本質上都是在若干約束條件下的函數極值問題。兩種規劃在很多情況下原則上可以相互轉換。動態規劃可以看作求決策使指標函數達到最優（最大或最小）的極值問題，狀態轉移方程、端點條

60、件以及允許狀態集、允許決策集等是約束條件，原則上可以用非線性規劃方法求解。一些靜態規劃只要適當引入階段變量、狀態、決策等就可以用動態規劃方法求解。下面用例子說明。例3 用動態規劃解下列非線性規劃 ； s.t. .其中為任意的已知函數。解 按變量的序號劃分階段，看作段決策過程。設狀態為，取問題中的變量為決策。狀態轉移方程為取為階段指標，最優值函數的基本方程為（注意到）；.按照逆序解法求出對應于每個取值的最優決策，計算至后即可利用狀態轉移方程得到最優狀態序列和最優決策序列。與靜態規劃相比，動態規劃的優越性在于：（i）能夠得到全局最優解。由于約束條件確定的約束集合往往很復雜，即使指標函數較簡單，用非

61、線性規劃方法也很難求出全局最優解。而動態規劃方法把全過程化為一系列結構相似的子問題，每個子問題的變量個數大大減少，約束集合也簡單得多，易于得到全局最優解。特別是對于約束集合、狀態轉移和指標函數不能用分析形式給出的優化問題，可以對每個子過程用枚舉法求解，而約束條件越多，決策的搜索范圍越小，求解也越容易。對于這類問題，動態規劃通常是求全局最優解的唯一方法。 （ii）可以得到一族最優解。與非線性規劃只能得到全過程的一個最優解不同，動態規劃得到的是全過程及所有后部子過程的各個狀態的一族最優解。有些實際問題需要這樣的解族，即使不需要，它們在分析最優策略和最優值對于狀態的穩定性時也是很有用的。當最優策略由

62、于某些原因不能實現時，這樣的解族可以用來尋找次優策略。（iii）能夠利用經驗提高求解效率。如果實際問題本身就是動態的，由于動態規劃方法反映了過程逐段演變的前后聯系和動態特征，在計算中可以利用實際知識和經驗提高求解效率。如在策略迭代法中，實際經驗能夠幫助選擇較好的初始策略，提高收斂速度速度。動態規劃的主要缺點是： （i）沒有統一的標準模型，也沒有構造模型的通用方法，甚至還沒有判斷一個問題能否構造動態規劃模型的準則。這樣就只能對每類問題進行具體分析，構造具體的模型。對于較復雜的問題在選擇狀態、決策、確定狀態轉移規律等方面需要豐富的想象力和靈活的技巧性，這就帶來了應用上的局限性。 （ii）用數值方法

63、求解時存在維數災（curse of dimensionality）。若一維狀態變量有個取值，那么對于維問題，狀態就有個值，對于每個狀態值都要計算、存儲函數，對于稍大（即使）的實際問題的計算往往是不現實的。目前還沒有克服維數災的有效的一般方法。§5 若干典型問題的動態規劃模型5.1 最短路線問題 對于例1一類最短路線問題（shortest Path Problem），階段按過程的演變劃分，狀態由各段的初始位置確定，決策為從各個狀態出發的走向，即有，階段指標為相鄰兩段狀態間的距離，指標函數為階段指標之和，最優值函數是由出發到終點的最短距離（或最小費用），基本方程為利用這個模型可以算出例l

64、的最短路線為， 相應的最短距離為18。5.2 生產計劃問題對于例 2一類生產計劃問題（Production planning problem），階段按計劃時間自然劃分，狀態定義為每階段開始時的儲存量，決策為每個階段的產量，記每個階段的需求量（已知量）為，則狀態轉移方程為 (5)設每階段開工的固定成本費為，生產單位數量產品的成本費為，每階段單位數量產品的儲存費為，階段指標為階段的生產成本和儲存費之和，即 (6)指標函數為之和。最優值函數為從第段的狀態出發到過程終結的最小費用，滿足其中允許決策集合由每階段的最大生產能力決定。若設過程終結時允許存儲量為，則終端條件是 （7）（5）（7）構成該問題的動

65、態規劃模型。5.3 資源分配問題一種或幾種資源（包括資金）分配給若干用戶，或投資于幾家企業，以獲得最大的效益。資源分配問題（resource allocating Problem）可以是多階段決策過程，也可以是靜態規劃問題，都能構造動態規劃模型求解。下面舉例說明。例4 機器可以在高、低兩種負荷下生產。臺機器在高負荷下的年產量是，在低負荷下的年產量是，高、低負荷下機器的年損耗率分別是和（）。現有臺機器，要安排一個年的負荷分配計劃，即 每年初決定多少臺機器投入高、低負荷運行，使年的總產量最大。如果進一步假設，（），即高、低負荷下每臺機器的年產量分別為和，結果將有什么特點。解 年度為階段變量。狀態為

66、第年初完好的機器數，決策為第年投入高負荷運行的臺數。當或不是整數時，將小數部分理解為一年中正常工作時間或投入高負荷運行時間的比例。機器在高、低負荷下的年完好率分別記為和，則，有。因為第年投入低負荷運行的機器臺數為，所以狀態轉移方程是 （8）階段指標是第年的產量，有 （9）指標函數是階段指標之和，最優值函數滿足 (10)及自由終端條件 （11）當中的用較簡單的函數表達式給出時，對于每個可以用解析方法求解極值問題。特別，若，（10）中的 將是的線性函數，最大值點必在區間的左端點或右端點取得，即每年初將完好的機器全部投入低負荷或高負荷運行。專題三.層次分析法層次分析法（Analytic Hierar

67、chy Process，簡稱AHP）是對一些較為復雜、較為模糊的問題作出決策的簡易方法，它特別適用于那些難于完全定量分析的問題。它是美國運籌學家T. L. Saaty 教授于70年代初期提出的一種簡便、靈活而又實用的多準則決策方法。§1 層次分析法的基本原理與步驟人們在進行社會的、經濟的以及科學管理領域問題的系統分析中，面臨的常常是一個由相互關聯、相互制約的眾多因素構成的復雜而往往缺少定量數據的系統。層次分析法為這類問題的決策和排序提供了一種新的、簡潔而實用的建模方法。運用層次分析法建模，大體上可按下面四個步驟進行：（i）建立遞階層次結構模型；（ii）構造出各層次中的所有判斷矩陣；（

68、iii）層次單排序及一致性檢驗；（iv）層次總排序及一致性檢驗。下面分別說明這四個步驟的實現過程。1.1 遞階層次結構的建立與特點應用AHP分析決策問題時，首先要把問題條理化、層次化，構造出一個有層次的結構模型。在這個模型下，復雜問題被分解為元素的組成部分。這些元素又按其屬性及關系形成若干層次。上一層次的元素作為準則對下一層次有關元素起支配作用。這些層次可以分為三類：（i）最高層：這一層次中只有一個元素，一般它是分析問題的預定目標或理想結果，因此也稱為目標層。（ii）中間層：這一層次中包含了為實現目標所涉及的中間環節，它可以由若干個層次組成，包括所需考慮的準則、子準則，因此也稱為準則層。（ii

69、i）最底層：這一層次包括了為實現目標可供選擇的各種措施、決策方案等，因此也稱為措施層或方案層。遞階層次結構中的層次數與問題的復雜程度及需要分析的詳盡程度有關，一般地層次數不受限制。每一層次中各元素所支配的元素一般不要超過9個。這是因為支配的元素過多會給兩兩比較判斷帶來困難。下面結合一個實例來說明遞階層次結構的建立。例1 假期旅游有、 3個旅游勝地供你選擇，試確定一個最佳地點。在此問題中，你會根據諸如景色、費用、居住、飲食和旅途條件等一些準則去反復比較3個侯選地點。可以建立如下的層次結構模型。目標層 選擇旅游地 準則層 景色 費用 居住 飲食 旅途 措施層 1.2 構造判斷矩陣層次結構反映了因素

70、之間的關系，但準則層中的各準則在目標衡量中所占的比重并不一定相同，在決策者的心目中，它們各占有一定的比例。在確定影響某因素的諸因子在該因素中所占的比重時，遇到的主要困難是這些比重常常不易定量化。此外，當影響某因素的因子較多時，直接考慮各因子對該因素有多大程度的影響時，常常會因考慮不周全、顧此失彼而使決策者提出與他實際認為的重要性程度不相一致的數據，甚至有可能提出一組隱含矛盾的數據。為看清這一點，可作如下假設：將一塊重為1千克的石塊砸成小塊，你可以精確稱出它們的重量，設為，現在，請人估計這小塊的重量占總重量的比例（不能讓他知道各小石塊的重量），此人不僅很難給出精確的比值，而且完全可能因顧此失彼而提供彼此矛盾的數據。設現在要比較個因子對某因素的影響大小，怎樣比較才能提供可信的數據呢？Saaty等人建議可以采取對因子進行兩兩比較建立成對比較矩陣的辦法。