數(shù)學建模知識一

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

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

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

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

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

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

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

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

9、b,Aeq,beq,LB,UB,X0,OPTIONS)這里fval返回目標函數(shù)的值，Aeq和beq對應(yīng)等式約束，LB和UB分別是變量的下界和上界，是的初始值，OPTIONS是控制參數(shù)。 例2 求解下列線性規(guī)劃問題 解 （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即可得所求結(jié)果。此問題也可以通過線性規(guī)劃軟件Lindo求解max 2x1+3x2-

10、5x3s.t.x1+x2+x3=72x1-5x2+x3>=10x1>=0x2>=0x3>=0例3 求解線性規(guī)劃問題 解 編寫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 運輸問題(產(chǎn)銷平衡)例4 某商品有個產(chǎn)地、個銷地，各產(chǎn)地的產(chǎn)量分別為，各銷地的需求量分別為。若該商品由產(chǎn)地運到銷地的單位運價為，問應(yīng)該

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

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

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

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

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

16、矩陣再變換，第三行、第五行元素減去2，第一列元素加上2，得 現(xiàn)在已可看出，最優(yōu)指派為。§4 靈敏度分析4.1 靈敏度分析靈敏度分析是指對系統(tǒng)或周圍事物因周圍條件變化顯示出來的敏感程度的分析。目標函數(shù)：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來解這一優(yōu)化問題。輸入語句：max(不區(qū)分大小寫) x1+x2+x3+x4ST(大寫或?qū)憇ubject 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然后再按運算符鍵即可得結(jié)果。LINDO是規(guī)定j非負的，我們可發(fā)現(xiàn)輸入方式與我們的數(shù)學書寫的形式基本一致，運算后，計算機會問您是否需要靈敏度分析，我們選擇是，結(jié)果如下：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下面給出其結(jié)果的一般解釋：“LP OPTIMUM FOUND AT STEP 6”表示LINDO在（用單純形法）次迭代或旋轉(zhuǎn)后得到

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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