第七章動態(tài)規(guī)劃動態(tài)規(guī)劃

(Dynamicprogramming)7.1多階段決策過程的最優(yōu)化7.2動態(tài)規(guī)劃的基本概念和基本原理7.4動態(tài)規(guī)劃在經(jīng)濟管理中的應用7.5馬氏決策規(guī)劃簡介7.3動態(tài)規(guī)劃模型的建立與求解動態(tài)規(guī)劃是解決多階段最優(yōu)決策的方法,由美國數(shù)學家貝爾曼(R.Bellman)于1951年首先提出;1957年貝爾曼發(fā)表動態(tài)規(guī)劃方面的第一部專著“動態(tài)規(guī)劃”,標志著運籌學的一個新分支的創(chuàng)立。動態(tài)規(guī)劃將復雜的多階段決策問題分解為一系列簡單的、離散的單階段決策問題,采用順序或逆序求解方法,通過解一系列小問題達到求解整個問題目的;動態(tài)規(guī)劃的各個決策階段不但要考慮本階段的決策目標,還要兼顧整個決策過程的整體目標,從而實現(xiàn)整體最優(yōu)決策.動態(tài)規(guī)劃的分類:離散確定型離散隨機型連續(xù)確定型連續(xù)隨機型動態(tài)規(guī)劃的特點: 動態(tài)規(guī)劃是研究多階段決策問題的一種運籌學方法。動態(tài)規(guī)劃與其他規(guī)劃方法的不同之處在于：動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種特定算法。因而，它不像線性規(guī)劃有一個標準的數(shù)學表達式和明確定義的一組（算法）規(guī)則，而必須對具體問題進行具體分析處理。因而學習動態(tài)規(guī)劃時，除了對基本概念和方法正確理解外，還應在一定經(jīng)驗積累基礎上，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。與運籌學其他方法有很好的互補關系,尤其在處理非線性、離散性問題時有其獨到的特點?！?.1多階段決策過程的最優(yōu)化每個階段都要進行決策,目的是使整個過程的決策達到最優(yōu)效果。多階段決策問題：在多階段決策過程中,系統(tǒng)的動態(tài)過程可以按照時間進程分為狀態(tài)相互聯(lián)系而又相互區(qū)別的各個階段；12n狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策多階段決策問題的典型例子：1.時間階段例子(機器負荷分配問題)：某種機器可以在高低兩種不同的負荷下進行生產(chǎn)。高負荷年產(chǎn)量8，年完好率0.7；低負荷年產(chǎn)量5，年完好率0.9.現(xiàn)有完好機器1000臺，需制定一個5年計劃，以決定每年安排多少臺機器投入高、低負荷下生產(chǎn)，使5年的總產(chǎn)量最大。125S1=1000決策x1S2輸出v1決策x2輸出v2S3S5決策x5輸出v52.(空間階段例子)最短路問題：給定一個交通網(wǎng)絡圖如下，其中兩點之間的數(shù)字表示距離（或花費），試求從A點到G點的最短距離（總費用最?。?。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643多階段決策問題的其他典型例子：1.生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季度地根據(jù)庫存和需求決定生產(chǎn)計劃。2.航天飛機飛行控制問題：由于航天飛機的運動的環(huán)境是不斷變化的，因此就要根據(jù)航天飛機飛行在不同環(huán)境中的情況，不斷地決定航天飛機的飛行方向和速度（狀態(tài)），使之能最省燃料和實現(xiàn)目的（如軟著落問題）。

不包含時間因素的靜態(tài)決策問題（本質(zhì)上是一次決策問題）也可以適當?shù)匾腚A段的概念，作為多階段的決策問題用動態(tài)規(guī)劃方法來解決。3.線性規(guī)劃、非線性規(guī)劃等靜態(tài)的規(guī)劃問題也可以通過適當?shù)匾腚A段的概念，應用動態(tài)規(guī)劃方法加以解決。以上例子代表了這樣一種特殊的決策過程，該過程可以分為互相聯(lián)系的若干階段，每一階段都需作出決策，從而形成全過程的決策。這種把一個問題看作一個前后關聯(lián)具有鏈狀結構的多階段過程稱為多階段決策過程，也稱序貫決策過程，相應的問題稱為多階段決策問題?！?.2動態(tài)規(guī)劃的基本概念和基本原理1、階段2、狀態(tài)3、決策和策略4、狀態(tài)轉移方程5、指標函數(shù)動態(tài)規(guī)劃的基本概念1、階段：把一個問題的過程，恰當?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便于按一定的次序去求解。描述階段的變量稱為階段變量。階段的劃分，一般是根據(jù)時間和空間的自然特征來進行的，但要便于問題轉化為多階段決策。年、月、路段動態(tài)規(guī)劃的基本概念無后效性(馬爾可夫性)如果某階段狀態(tài)給定后，則在這個階段以后過程的發(fā)展不受這個階段以前各段狀態(tài)的影響；過程的過去歷史只能通過當前的狀態(tài)去影響它未來的發(fā)展；構造動態(tài)規(guī)劃模型時，要充分注意是否滿足無后效性的要求；狀態(tài)變量要滿足無后效性的要求；如果狀態(tài)變量不能滿足無后效性的要求，應適當?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。2、狀態(tài)：表示每個階段開始所處的自然狀況或客觀條件。通常一個階段有若干個狀態(tài)，描述過程狀態(tài)的變量sk稱為狀態(tài)變量。一個數(shù)、一組數(shù)、一個向量

狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為狀態(tài)允許集合Sk。3、決策：每階段狀態(tài)確定后的抉擇，即從該狀態(tài)演變到下階段某狀態(tài)的選擇，用決策變量uk(sk)

表示由k階段sk出發(fā)所作的決策。在實際問題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為允許決策集合，有。策略：在實際問題中，可供選擇的策略有一定的范圍，稱為允許策略集合，記作。從允許策略集合中找出達到最優(yōu)效果的策略稱為最優(yōu)策略。(空間階段例子)最短路問題：給定一個交通網(wǎng)絡圖如下，其中兩點之間的數(shù)字表示距離（或花費），試求從A點到G點的最短距離（總費用最?。?23456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643階段，狀態(tài)（及它的無后效性），狀態(tài)集合，決策，決策集合，策略圖示如下：狀態(tài)轉移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。如果第k階段狀態(tài)變量sk的值、該階段的決策變量一經(jīng)確定，第k+1階段狀態(tài)變量sk+1的值也就確定。其狀態(tài)轉移方程如下（一般形式）12ks1u1s2u2s3skuksk+1能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即具有無后效性的多階段決策過程。4、狀態(tài)轉移動態(tài)規(guī)劃中能處理的狀態(tài)轉移方程的形式。狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉移方程如下5、指標函數(shù)和最優(yōu)值函數(shù)：

用來衡量所選定策略優(yōu)劣的一種數(shù)量指標，稱為指標函數(shù)。在不同的問題中，指標函數(shù)的含義是不同的，它可能是距離、利潤、成本、產(chǎn)量或資源消耗等。

分為階段指標函數(shù)和過程指標函數(shù)。

階段指標函數(shù)：第k階段，從狀態(tài)sk出發(fā)，采取決策uk時的效益，記作d(sk,uk)

過程指標函數(shù)：表示初始狀態(tài)為s1采用策略p1,n時原過程的指標函數(shù)值;表示在第k階段，狀態(tài)為sk采用策略pk,n時，后部子過程的指標函數(shù)值。

效益最優(yōu)指標函數(shù):

問題：動態(tài)規(guī)劃的最優(yōu)解和最優(yōu)值是什么？

——最優(yōu)解：最優(yōu)策略p1,n

最優(yōu)值：最優(yōu)指標函數(shù)值f1(s1)解多階段決策過程問題，求出

最優(yōu)策略，即最優(yōu)決策序列f1(s1)

最優(yōu)軌線，即執(zhí)行最優(yōu)策略時的狀態(tài)序列

最優(yōu)指標函數(shù)值從k到終點最優(yōu)策略子策略的最優(yōu)目標函數(shù)值(空間階段例子)最短路問題：給定一個交通網(wǎng)絡圖如下，其中兩點之間的數(shù)字表示距離（或花費），試求從A點到G點的最短距離（總費用最?。?。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643狀態(tài)轉移，階段指標函數(shù)，過程指標函數(shù)，最優(yōu)指標函數(shù)1、基本原理動態(tài)規(guī)劃的基本思想與最優(yōu)化原理D2E2F1F2G以最短路為例說明2、基本方程根據(jù)最優(yōu)性原理，可建立從后向前逆推求解的遞推公式——動態(tài)規(guī)劃基本方程。例從A

地到D

地要鋪設一條煤氣管道,其中需經(jīng)過兩級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。問應該選擇什么路線，使總距離最短？AB1B2C1C2C3D24333321114最短路徑問題s1s2s3s4

解：整個計算過程分三個階段，從最后一個階段開始（逆序解法）。

步驟1：C→D：C

有三條路線到終點D

。AB1B2C1C2C3D24333321114DC1C2C3顯然有f3(C1)

=1；

f3(C2)

=3；

f3(C3)

=4

u3(C1)

=D；u3(C2

)

=D；

u3(C3

)

=Ds1s2s3s4k=1k=2k=3

d(B1,C1)+f3(C1)

3+1f2(B1)=mind(B1,C2

)+f3(C2)

=min3+3

d(B1,C3)+f3(C3)1+44=min6=45步驟2：B→C：B到C有六條路線。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為B1→C1→D)s1s2s3s4u2(B1)

=C1

d(B2,C1)+f3(C1)

2+1f2(B2)=mind(B2,C2

)+f3(C2)

=min3+3

d(B2,C3)+f3(C3)1+43=min6=35AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為B2→C1→D)s1s2s3s4u2(B2)

=C1

步驟3：

A→B：A到B有二條路線。

f3(A)1=d(A,B1)＋f2(B1)＝2＋4＝6

f3(A)2=d(A,B2)＋f2(B2)＝4＋3＝7∴f1(A)

=min=min｛6,7｝=6d(A,B1)＋f2(B1)d(A,B2)＋f2(B2)(最短路線為A→B1→C1→D)AB1B2C1C2C3D24333321114DC1C2C3B1B2Au1(A)

=B1

AB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路線為A→B1→C1→D

路長為61、動態(tài)規(guī)劃方法的關鍵在于正確地寫出基本的遞推關系式和恰當?shù)倪吔鐥l件（簡稱基本方程）。要做到這一點，就必須將問題的過程分成幾個相互聯(lián)系的階段，恰當?shù)倪x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個大問題轉化成一組同類型的子問題，然后逐個求解。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結果，依次進行，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。動態(tài)規(guī)劃的基本思想總結2、在多階段決策過程中，動態(tài)規(guī)劃方法是既把當前一段和未來一段分開，又把當前效益和未來效益結合起來考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來考慮的，與該段的最優(yōu)選擇答案一般是不同的.

3、在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐段變換得到，從而確定了最優(yōu)路線。動態(tài)規(guī)劃的優(yōu)缺點動態(tài)規(guī)劃的優(yōu)點可以解決線性,非線性,整數(shù)規(guī)劃無法有效求解的復雜問題;容易找到全局最優(yōu)解;可以得到一組解;動態(tài)規(guī)劃的缺點：沒有標準的模型可供應用,構模依賴于個人的經(jīng)驗和技巧;狀態(tài)變量需滿足無后效性,有較大的局限性;動態(tài)規(guī)劃的維數(shù)災難限制了對規(guī)模較大問題的求解效率;§7.3動態(tài)規(guī)劃模型的建立與求解一、建立動態(tài)規(guī)劃模型的步驟

1、劃分階段劃分階段是運用動態(tài)規(guī)劃求解多階段決策問題的第一步，在確定多階段特性后，按時間或空間先后順序，將過程劃分為若干相互聯(lián)系的階段。對于靜態(tài)問題要人為地賦予“時間”概念，以便劃分階段。2、正確選擇狀態(tài)變量選擇變量既要能確切描述過程演變又要滿足無后效性，而且各階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)變量的選擇是從過程演變的特點中尋找。3、確定決策變量及允許決策集合通常選擇所求解問題的關鍵變量作為決策變量，同時要給出決策變量的取值范圍，即確定允許決策集合。4、確定狀態(tài)轉移方程根據(jù)k階段狀態(tài)變量和決策變量，寫出k+1階段狀態(tài)變量，狀態(tài)轉移方程應當具有遞推關系。5、確定階段指標函數(shù)和最優(yōu)指標函數(shù)，建立動態(tài)規(guī)劃基本方程階段指標函數(shù)是指第k階段的收益，最優(yōu)指標函數(shù)是指從第k階段狀態(tài)出發(fā)到第n階段末所獲得收益的最優(yōu)值，最后寫出動態(tài)規(guī)劃基本方程。以上五步是建立動態(tài)規(guī)劃數(shù)學模型的一般步驟。由于動態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動態(tài)規(guī)劃模型沒有統(tǒng)一的模式，建模時必須根據(jù)具體問題具體分析，只有通過不斷實踐總結，才能較好掌握建模方法與技巧。例AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664求從A到G的最短路徑（逆序解法）3s1s2s3s4s5s6s7k=5，出發(fā)點E1、E2、E3u5(E1)=F1E1F1GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u5(E2)=F2E2F2Gu5(E3)=F2E3F2Gk=6,F1Gf6(F1)=4F2G

,f6(F2)=3k=4，f4(D1)=7

u4(D1)=E2f4(D2)=6

u4(D2)=E2f4(D3)=8

u4(D3)=E2k=2,f2(B1)=13

u2(B1)=C2f2(B2)=16u2(B2)=C3f3(C1)=13

u3(C1)=D1f3(C2)=10

u3(C2)=D1f3(C3)=9

u3(C3)=D1f3(C4)=12

u3(C4)=D3k=3,=minf1(A)=mind1(A,B1)+f2(B1)d1(A,B2)+f2(B2)5+133+16=18k=1,u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2u5(E1)=F1E1F1Gu5(E2)=F2E2F2Gu5(E3)=F2E3F2G759

u5(E2)=F2u6(F2)=G最優(yōu)策略AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643例AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最優(yōu)路線為：A→B1→C2→D1→E2→F2→G

路長＝18求從A到G的最短路徑（逆序解法）3s1s2s3s4s5s6s7例AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664求從A到G的最短路徑（順序解法）3s1s2s3s4s5s6s7例AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最優(yōu)路線為：A→B1→C2→D1→E2→F2→G路長＝18求從A到G的最短路徑（順序解法）3s1s2s3s4s5s6s7二、順序解法與逆序解法的區(qū)別1、狀態(tài)轉移方式不同12ns1u1s2u2s3snunsn+1V1(s1,u1)V2(s2,u2)Vn(sn,un)12ns1u1s2u2s3snunsn+1V1(s2,u1)V2(s3,u2)Vn(sn+1,un)順序解法與逆序解法的區(qū)別2、指標函數(shù)的定義不同順序解法與逆序解法的區(qū)別3、基本方程形式不同當指標函數(shù)為階段指標和形式順序解法與逆序解法的區(qū)別3、基本方程形式不同當指標函數(shù)為階段指標積形式求從A到E的最短路徑（順序法）路線為A→B2→C1→D1→E

，最短路徑為19AB2B1B3C1C3D1D2EC25214112610104312111396581052課堂練習1三、基本方程分段求解的幾種常用算法

1、離散變量的分段窮舉算法狀態(tài)變量與決策變量只能取離散值，且取值個數(shù)較少時，可以用分段窮舉算法，如最短路徑問題。2、連續(xù)變量的解法狀態(tài)變量與決策變量為連續(xù)變量，可采用經(jīng)典解析方法、線性規(guī)劃方法、非線性規(guī)劃方法或其他數(shù)值計算方法等。例

分配投資問題

問題的一般描述如下：設有某種資源，總數(shù)量為a，用于生產(chǎn)n種產(chǎn)品；若分配數(shù)量xi用于生產(chǎn)第i種產(chǎn)品，其收益為gi(xi)。問應如何分配，使得使總收益最大？該類問題可用動態(tài)規(guī)劃進行求解：

問題分n個階段，即k=1，2，…，nsk

：第k階段初擁有的資金總量xk

：項目k

的投資額，0≤xk≤sk

uk=xksk+1=sk-xk

Vk(sk,xk)=gk(xk)最優(yōu)指標函數(shù)fk(sk)：當可投資金額為時sk，投資第k-n項所得的最大收益。（逆序）基本方程為：例

（投資決策問題，逆序解法）某公司有資金10萬元，擬投資于3個項目，已知對第i個項目投資xi萬元，收益為gi(xi)，問應如何分配資金可使總收益最大？其中，解：現(xiàn)人為地給它賦予“時段”的概念，將投資項目排序，首先考慮項目1的投資，然后考慮項目2的投資，……，問題分為3個階段，每個階段只決定一個項目的投資金額。階段k=1,2,3決策變量uk：第k個項目的投資額狀態(tài)變量sk：在第k階段時可以用于投資第k到第3個項目的資金數(shù)指標函數(shù)Vk,n：第k階段可分配的資金數(shù)為sk時，第k至第3個

項目的最大總收益狀態(tài)轉移方程：sk+1=sk-uk邊界條件：資源分配問題的動態(tài)規(guī)劃基本方程：建立遞推公式：k=3,2,1：第k階段可分配的資金數(shù)為sk時，第k至第3個

項目的最大總收益用逆序解法解k=3時k=2時令由解得極大值只可能在[0,s2]端點取得，最優(yōu)投資方案為全部資金投于第三個項目，可得最大收益200萬元。sk+1=sk-uk例

（投資決策問題，順序解法）某公司有資金10萬元，擬投資于3個項目，已知對第i個項目投資xi萬元，收益為gi(xi)，問應如何分配資金可使總收益最大？其中，解：現(xiàn)人為地給它賦予“時段”的概念，將投資項目排序，首先考慮項目1的投資，然后考慮項目2的投資，……，問題分為3個階段，每個階段只決定一個項目的投資金額。階段k=1,2,3決策變量uk：第k個項目的投資額狀態(tài)變量sk+1：在第k階段，可用于投資第1到第k個項目的資金數(shù)，s4=10指標函數(shù)V1,k：第k階段可分配的資金數(shù)為sk+1時，第1至第k個

項目的最大總收益狀態(tài)轉移方程：sk=sk+1-xk邊界條件：資源分配問題的動態(tài)規(guī)劃基本方程：建立遞推公式：k=3,2,1：第k階段可分配的資金數(shù)為sk+1時，第1至第k個

項目的最大總收益用順序解法解K=1時k=2時k=3時最優(yōu)投資方案為全部資金投于第三個項目，可得最大收益200萬元。sk=sk+1-xk三、基本方程分段求解的幾種常用算法

1、離散變量的分段窮舉算法狀態(tài)變量與決策變量只能取離散值，且取值個數(shù)較少時，可以用分段窮舉算法，如最短路徑問題。2、連續(xù)變量的解法狀態(tài)變量與決策變量為連續(xù)變量，可采用經(jīng)典解析方法、線性規(guī)劃方法、非線性規(guī)劃方法或其他數(shù)值計算方法等。3、連續(xù)變量的離散化解法

s110x10246810g1+f220013688605040f12000最優(yōu)投資方案為全部資金投于第三個項目，可得最大收益200萬元。三、基本方程分段求解的幾種常用算法

1、離散變量的分段窮舉算法狀態(tài)變量與決策變量只能取離散值，且取值個數(shù)較少時，可以用分段窮舉算法，如最短路徑問題。2、連續(xù)變量的解法狀態(tài)變量與決策變量為連續(xù)變量，可采用經(jīng)典解析方法、線性規(guī)劃方法、非線性規(guī)劃方法或其他數(shù)值計算方法等。3、連續(xù)變量的離散化解法4、高維問題的降維法及疏密格子點法以二維分配問題為例研究高維問題的處理方法。

§7.4動態(tài)規(guī)劃在經(jīng)濟管理中的應用有一個徒步旅行者，其可攜帶物品重量的限度為a公斤，設有n

種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（作用），問此人應如何選擇攜帶的物品（各幾件），使所起作用（使用價值）最大？物品

12…j…n重量（公斤/件）a1a2…

aj…

an每件使用價值c1c2…cj…

cn這就是背包問題。類似的還有工廠里的下料問題、運輸中的貨物裝載問題、人造衛(wèi)星內(nèi)的物品裝載問題等。1、

背包問題設xj為第j種物品的裝件數(shù)（非負整數(shù)）則問題的數(shù)學模型如下：用動態(tài)規(guī)劃方法求解

例：求下面背包問題的最優(yōu)解(a=10)物品123aj重量（公斤）345cj使用價值456解：a＝10，問題是求f3(10)S2012345678910f1(s2)000444888121200011122233例：求下面背包問題的最優(yōu)解(a=5)物品123重量（公斤）345使用價值456S3012345678910x20000010101010120120120004454585898910129101213100004558910121300001101201對于k=3最大值為13練習：某廠生產(chǎn)三種產(chǎn)品，各種產(chǎn)品重量與利潤的關系如表所示。現(xiàn)將此三種產(chǎn)品運往市場出售，運輸能力總重量不超過6噸，問如何安排運輸，使總利潤最大？種類123重量（噸/公斤）234單件利潤（元）80130180最優(yōu)方案：X1

=（0,2,0）X2=（1,0,1）Z=260（1）庫存問題2、

生產(chǎn)經(jīng)營問題例某工廠生產(chǎn)并銷售某種產(chǎn)品，已知今后四個月市場需求預測如表7-7，又每月生產(chǎn)j單位產(chǎn)品費用為：每月庫存j單位產(chǎn)品的費用為E(j)=0.5j(千元)，該廠最大庫存容量為3單位，每月最大生產(chǎn)能力為6單位，計劃開始和計劃期末庫存量都是零。試制定四個月的生產(chǎn)計劃，在滿足用戶需求條件下總費用最小。假設第i+1個月的庫存量是第i個月可銷售量與該月用戶需求量之差；而第i個月的可銷售量是本月初庫存量與產(chǎn)量之和。階段k狀態(tài)變量sk決策變量uk狀態(tài)轉移方程階段指標終端條件月份，k=1,2,3,4；第k個月初（發(fā)貨以前）的庫存量；第k個月的生產(chǎn)量xk；sk+1=sk+uk-gk；gk(sk

,dk)=ckuk；f5(s5)=0,x5=0；最優(yōu)指標函數(shù)fk(sk)第k月初庫存量為sk時，采取最佳策略生產(chǎn)，從本月到4月底的生產(chǎn)與庫存最低費用遞推方程4月底庫存要求為0，本月需求gk=4，從而有最大庫存量為3，對于K=4s40123f4(s4)76.565.5u4(s4)4321遞推方程對于u3max(0,2-s3)≤u3≤min(6,5-s3,6-s3),其中s3的取值范圍為0,1,2,3當s3=0時對于K=3遞推方程對于u2，max(0,3-s2)≤u2≤min(6,6-s2,9-s2),其中s2的取值范圍為0,1,2,3當s2=0時對于K=2u*3(s3)f3(

s3)C+E+f4u3(s3)00128811.5121211.5812.51211.581312.51211.513.51312.5122103210432154323210s3對于K=2u*2(s2)f2(

s2)C+E+f3u2(s2)

34

513.5

1515.5

1614.51713.5161517.51716.515.51817.5171618.5182104321543265433210s2315.50u*1(s1)f1(

s1)C+f2u1(s1)221.52221.52154320s121對于K=1得出最佳生產(chǎn)計劃為，第一個月生產(chǎn)2單位，第二個月生產(chǎn)5單位，第三個月不生產(chǎn)，第四個月生產(chǎn)4個單位?？偨Y此類生產(chǎn)存貯問題的基本方程為：若最大庫存量為q,每月最大生產(chǎn)能力為p.則狀態(tài)集合為：允許決策集合為：（2）采購與銷售問題2、

生產(chǎn)經(jīng)營問題某商店在未來的四個月里，準備利用商店的一個倉庫來專門經(jīng)銷某種商品，倉庫最大容量為這種商品1000單位。假定商店每月只能賣出倉庫現(xiàn)有的貨物。當商店在某月購貨時，下月初才能到貨。預測該商店未來四個月的買賣價格如下表，假定商店在1月開始經(jīng)銷時，倉庫貯有該商品500單位，試問，如何制定這四個月的訂購與銷售計劃，使獲利最大（不計庫存費）。110122983111341517月份（k）購買單價（ck）銷售單價（pk）已知：倉庫最大容量為1000單位。商店每月只賣出倉庫現(xiàn)有的貨物。當商店在某月購貨時，下月初才能到貨。第k月的購買單價ck，銷售單價pk，1月開始經(jīng)銷時，倉庫貯有該商品500單位，如何制定四個月的訂購與銷售計劃，使獲利最大（不計庫存費）。解：k=1，2，3，4狀態(tài)變量skxk—第k月賣出的貨物數(shù)量,0≤xk≤sk

yk—第k月訂購的貨物數(shù)量，0≤yk≤1000-(sk-xk)求f1（500）決策變量：s1=500,0≤sk≤1000k=2，3，4—第k個月的庫存量（含上月的定貨）x3+x1=s3

-x3+y3+x2=1000-s3

maxZ=-4x3+6y3

+17s3

x1,x2,x3,y3≥0x3y3x1x2-4600Z-17s3

x11010s3x2-11011000-s3x3y3x1x2200-6Z-6000-11s3

x11010s3y3-11011000-s3x3y3x1x200-2-6Z-6000-13s3

x31010s3y301111000x*3=s3y*3=1000最優(yōu)值Z=6000+13s3x3≤s3

-x3+y3≤1000-s3

x3,y3≥0求maxZ=-4x3+6y3

+17s3標準型：最優(yōu)解：f1（500）=17000x*1=500，y*1=0f2（s2）=x*2=011000+8s2，y*2=1000-s2f3（s3）=x*3=s3，y*3=10006000+13s3f4（s4）=17s4x*4=s4，y*4=0xk—第k月賣出的貨物數(shù)量yk—第k月訂購的貨物數(shù)量sk+1=sk+yk-xkfk（sk）=第k月初庫存為時sk

，從第k月到第4月末所獲得的最大利潤結論：當?shù)?個月初庫存為時500時，

4個月能獲得的最大利潤為17000四個月的訂購與銷售計劃：第1個月：賣出500個，訂購0個第2個月：賣出0個，訂購1000個第3個月：賣出1000個，訂購1000個第4個月：賣出1000個，訂購0個3、設備更新問題已知一臺設備已使用了t年，再使用一年的效益為r(t)，維修費為u(t),若在第t+1年更新，則更新費為c(t)，α為折扣因子，表示一年以后的單位收入價值相當于現(xiàn)年的α單位。現(xiàn)要做一個n年的設備更新計劃：每年年初做出決策，是繼續(xù)使用舊機器還是更換一臺新機器，使n年的總收益最大。建模：階段k=1,2,…,n，表示計劃使用該設備的年限數(shù)決策變量uk狀態(tài)變量sk=第k年初,機器已使用過的年限狀態(tài)轉移方程：第k年的收益：基本方程：基本方程：例：設某臺新設備的年效益及年均維修費、更新凈費用如下表所示。試確定今后5年內(nèi)的更新策略，使總收益最大。（設α=1）役齡t012345效益rk(t)54.543.7532.5維修費uk(t)0.511.522.53更新費ck(t)-1.52.22.533.5當K=5當K=4當K=3當K=2當K=1上述計算遞推回去，當u1*(0)=K,知s2=1得u2*=R,u3*=R,u4*=R,u5*=K;4、復合系統(tǒng)工作可靠性問題

該問題為整數(shù)非線性規(guī)劃，可以用動態(tài)規(guī)劃求解，設關鍵器件數(shù)n=3，總費用為120萬元。器件的單價與可靠性如下表：1 30 0.1 2 15 0.2 3 20 0.5 器件號i

單價(萬元)失效概率pi建立動態(tài)規(guī)劃模型：k=3器件號單價失效概率1300.12150.23200.5k=2:s3=s2–c2x2器件號單價失效概率1300.12150.23200.5k=1:s2=s1–c1x1

因此得到：x1=1,s2=120-30=90,x2=2,s3=90-2*15=60,x3=3

即：p={1，2，3}可靠性為0.756器件號單價失效概率1300.12150.23200.5§7.5馬氏決策規(guī)劃簡介

馬氏決策規(guī)劃的基本概念于20世紀60年代建立，幾十年來，無論是理論上還是應用方面都有很大進展。根據(jù)其報酬函數(shù)和目標函數(shù)的不同，建立了不同類型的優(yōu)化模型，如有限階段模型、折扣模型、平均模型、無界報酬模型等。對這些模型的理論研究已取得了較好的成果。另外，馬氏決策規(guī)劃也被成功地應用于許多實際問題，如機器的最優(yōu)更換、維修問題、質(zhì)量控制問題、水庫最優(yōu)調(diào)度問題、隨機旅行售貨點問題、電話網(wǎng)絡中的最優(yōu)線路問題、最優(yōu)投資與消費問題等等。

一、馬爾可夫過程馬爾可夫過程是一類特殊的隨機過程，它因偉大的俄國數(shù)學家馬爾可夫而得名。這種過程的特點是存在著確定的轉移概率，與系統(tǒng)先前的歷史無關，有一個很形象的比喻來形容這個過程：池塘里的青蛙在荷葉上跳來跳去，如果將它在某一時刻所在的荷葉稱為狀態(tài)，則青蛙未來處于什么狀態(tài)只有它現(xiàn)在所在的狀態(tài)有關，與它以前所處的狀態(tài)無關。這種性質(zhì)就是所謂的“一階Markov性”或“無后效性”★★★★★基本概念

1.狀態(tài)轉移概率

假定系統(tǒng)有n個可能的狀態(tài)，處于這些狀態(tài)的概率分別為p1,p2…pi,…pn。例如，有1000名顧客在每周只到A和B購物，設定時間階段為一周。在某一周，有900名顧客到A購物，我們稱為狀態(tài)1，有100名顧客到B，成為狀態(tài)2，因此，系統(tǒng)的兩個狀態(tài)和概率分別為狀態(tài)1：顧客到A購物，0.9

狀態(tài)2：顧客到B購物，0.1

假定市場調(diào)查數(shù)據(jù)顯示，在隨后的一周內(nèi)，上周去A購物的顧客有90％仍然在A購物，有10％的顧客則流向了B，去B購物的