多階段決策問題與動態(tài)規(guī)劃和科學(xué)決策與信息分析

4動態(tài)規(guī)劃

4.1多階段決策問題與動態(tài)規(guī)劃4.2動態(tài)規(guī)劃的基本概念4.3動態(tài)規(guī)劃的步驟4.4動態(tài)規(guī)劃的應(yīng)用

1求解靜態(tài)規(guī)劃問題2資源分配問題3不確定性采購問題4排序問題?

例2機器負(fù)荷分配問題某種機器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)．在高負(fù)荷下進(jìn)行生產(chǎn)時，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機器數(shù)量u的關(guān)系為g＝g(u),這時機器的年完好率為a（0<a<1)．在低負(fù)荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機器數(shù)量v的關(guān)系為h＝h(v),這時機器的年完好率為b（a<b<1）．假定開始生產(chǎn)時完好的機器數(shù)量為s1，要求制定一個五年計劃,在每年開始時決定機器在兩種不同負(fù)荷下生產(chǎn)的數(shù)量,使五年內(nèi)產(chǎn)品的總產(chǎn)量最高。4.1多階段決策問題與動態(tài)規(guī)劃?多階段決策問題和我們前面遇到的決策問題不同，它是和時間有關(guān)的。與時間有關(guān)的活動過程稱為動態(tài)過程，其優(yōu)化方法稱為動態(tài)規(guī)劃。而與時間無關(guān)的活動過程稱為靜態(tài)過程，相應(yīng)的的優(yōu)化方法稱為靜態(tài)規(guī)劃。?(1)階段（stage）把所研究的決策問題，按先后順序劃分為若干相互聯(lián)系的決策步驟，以便按一定的次序進(jìn)行求解。描述階段的變量稱階段變量，常用k表示。(2)狀態(tài)（state）狀態(tài)表示每個階段開始時所處的自然狀況或客觀條件，它描述了影響決策的因素隨決策進(jìn)程的變化情況，它既是前面階段所作決策的結(jié)果，又是本階段作出決策的出發(fā)點和依據(jù)。描述狀態(tài)的變量稱為狀態(tài)變量，第k階段的狀態(tài)變量常用sk表示。通常，在第一階段狀態(tài)變量s1是確定的，稱初始狀態(tài)。(3)決策（decision）決策表示在某一階段處于某種狀態(tài)時，決策者在若干種方案中作出的選擇決定。描述決策的變量稱決策變量，第k階段的決策變量常用uk表示。決策變量的取值會受到狀態(tài)變量的制約，被限制在某一范圍之內(nèi)。4.2動態(tài)規(guī)劃的基本概念（一）?(4)策略（policy）把從第一階段開始到最后階段終止的整個決策過程，稱為問題的全過程；而把從第k階段開始到最后階段終止的決策過程，或稱為k子過程。在全過程上，各階段的決策按順序排列組成的決策序列p1,n＝{u1,u2,……,un}稱為全過程策略，簡稱策略；而在k子過程上的決策序列pk,n＝{uk,uk+1,……,un}稱為k子過程策略，也簡稱子策略。(5)狀態(tài)轉(zhuǎn)移方程若第k階段的狀態(tài)變量值為sk，當(dāng)決策變量uk的取值決定后，下一階段狀態(tài)變量sk+1的值也就完全確定。即sk+1的值對應(yīng)于sk和uk的值。這種對應(yīng)關(guān)系記為sk+1＝Tk(sk,uk)，稱為狀態(tài)轉(zhuǎn)移方程。狀態(tài)轉(zhuǎn)移方程描述了由一個階段的狀態(tài)到下一階段的狀態(tài)的演變規(guī)律。?4.2動態(tài)規(guī)劃的基本概念（二）(6)指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)分為階段指標(biāo)函數(shù)和過程指標(biāo)函數(shù)。階段指標(biāo)函數(shù)是對某一階段的狀態(tài)和決策產(chǎn)生的效益值的度量，用vk(sk,uk)表示。過程指標(biāo)函數(shù)是指過程所包含的各階段的狀態(tài)和決策所產(chǎn)生的總的效益值，記為

Vk,n＝Vk,n(sk,uk,sk+1,uk+1,……,sn,un)

動態(tài)規(guī)劃所要求的過程指標(biāo)函數(shù)應(yīng)具有可分離性，即可表達(dá)為它所包含的各階段指標(biāo)函數(shù)的函數(shù)形式。常見的兩種過程指標(biāo)函數(shù)形式是：①各階段指標(biāo)函數(shù)的和Vk,n＝∑vj(sj,uj)；②各階段指標(biāo)函數(shù)的積Vk,n＝∏vj(sj,uj)。

把過程指標(biāo)函數(shù)Vk,n對k子過程策略pk,n求最優(yōu)，得到一個關(guān)于狀態(tài)sk的函數(shù)，稱為最優(yōu)值函數(shù)，記為fk(sk)。即

fk(sk)＝optVk,n(sk,uk,……,sn,un)uk,…,un式中的“opt”（optimization）可根據(jù)具體問題而取min或max。?(7)基本方程通常動態(tài)規(guī)劃問題的最優(yōu)值函數(shù)滿足遞推關(guān)系式。設(shè)過程指標(biāo)函數(shù)為各階段指標(biāo)函數(shù)的和的形式，即Vk,n＝∑vj(sj,uj)，則有fk(sk)＝opt{vk(sk,uk)+fk+1(sk+1)}

uk∈Dk(sk)(k＝n,n-1,…,1)

遞推方程

fn+1(sn+1)＝0邊界條件遞推方程和邊界條件一起稱為動態(tài)規(guī)劃的基本方程?？筛鶕?jù)邊界條件，從k=n開始，由后向前逆推，逐步求得各階段的最優(yōu)決策和相應(yīng)的最優(yōu)值，最后求出f1(s1)時，就得到整個問題的最優(yōu)解。?此問題的基本方程為fk(sk)＝Min{dk(uk)+fk+1(sk+1)}

uk∈Dk(sk)

k＝6,5,4,3,2,1f7(s7)＝04.3動態(tài)規(guī)劃的步驟（一）當(dāng)k=6時?按基本方程由后向前繼續(xù)遞推有:當(dāng)k=5時當(dāng)k=4時?當(dāng)k=3時當(dāng)k=2時當(dāng)k=1時由此可以看出，A到G的最短路長為18，路徑為：A→B1→C2→D1→E2→F2→G?現(xiàn)在把動態(tài)規(guī)劃法的步驟歸納如下：(1)將所研究問題的過程劃分為n個恰當(dāng)?shù)碾A段，

k＝1,2,…,n；(2)正確地選擇狀態(tài)變量Sk，并確定初始狀態(tài)S1的值；(3)確定決策變量uk以及各階段的允許決策集Dk(Sk)；(4)給出狀態(tài)轉(zhuǎn)移方程；(5)給出滿足要求的過程指標(biāo)函數(shù)Vk,n及相應(yīng)的最優(yōu)值函數(shù)；(6)寫出遞推方程和邊界條件，建立基本方程；(7)按照基本方程遞推求解。以上步驟是動態(tài)規(guī)劃法處理問題的基本步驟，其中的前六步是建立動態(tài)規(guī)劃模型的步驟。4.3動態(tài)規(guī)劃的步驟（二）?例：機器負(fù)荷問題某種機器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)．在高負(fù)荷下進(jìn)行生產(chǎn)時，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機器數(shù)量u的關(guān)系為g＝8u,這時機器的年完好率為a=0.7．在低負(fù)荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機器數(shù)量v的關(guān)系為h＝5v,這時機器的年完好率為b=0.9．假定開始生產(chǎn)時完好的機器數(shù)量為s1，要求制定一個五年計劃,在每年開始時決定機器在兩種不同負(fù)荷下生產(chǎn)的數(shù)量,使五年內(nèi)產(chǎn)品的總產(chǎn)量最高。?(1)按年數(shù)劃分為5個階段，k=1,2,3,4,5(2)取第k年初完好的機器數(shù)sk為狀態(tài)變量,s1=1000(3)取第k年投入高負(fù)荷的機器數(shù)xk為決策變量,0≤xk≤sk(4)狀態(tài)轉(zhuǎn)移方程為sk+1=0.7xk+0.9(sk-xk)=0.9sk-0.2xk(5)指標(biāo)函數(shù)為Vk,5=∑[8xj+5(sj-xj)]=∑(5sj+3xj)(6)基本方程為

fk(sk)＝max{5sj+3xj+fk+1(sk+1)}k=5,4,3,2,1

0≤xk≤sk

f6(s6)＝0解:當(dāng)k=5時f5(s5)＝max{5s5+3x5+f6(s6)}=max{5s5+3x5}=8s5(x5*=s5)0≤x5≤s50≤x5≤s5?當(dāng)k=4時f4(s4)＝max{5s4+3x4+8s5}=max{5s4+3x4+8(0.9s4-0.2x4)}0≤x4≤s40≤x4≤s4=max{12.2s4+1.4x4}=13.6s4(x4*=s4)0≤x4≤s4當(dāng)k=3時f3(s3)＝max{5s3+3x3+13.6s4}=max{5s3+3x3+13.6(0.9s3-0.2x3)}0≤x3≤s30≤x3≤s3=max{17.24s3+0.28x3}=17.5s3(x3*=s3)0≤x3≤s3當(dāng)k=2時f2(s2)=max{5s2+3x2+17.52s3}=max{5s2+3x2+17.52(0.9s2-0.2x2)}0≤x2≤s20≤x2≤s2=max{20.77s2-0.504x2}=20.7s4(x2*=0)0≤x2≤s2當(dāng)k=1時f1(s1)=23.7s1(x1*=0)f1(1000)=23700s1=1000,x1*=0s2=900,x2*=0s3=810,x3*=810s4=576,x4*=576s5=397,x5*=397?某些靜態(tài)規(guī)劃問題可用動態(tài)規(guī)劃法來求解。

例用動態(tài)規(guī)劃法求解maxz=x12.x22.x3x1+x2+x3=cxi≥0i=1,2,34.4動態(tài)規(guī)劃的應(yīng)用(一)1求解靜態(tài)規(guī)劃問題?資源分配問題可描述如下：設(shè)有某種原料，總數(shù)量為a，分配給n個使用者。已知第i個使用者得到數(shù)量xi的資源，可創(chuàng)造的收益為gi（xi）。問應(yīng)如何分配該資源，才能使總收益最大。4.4動態(tài)規(guī)劃的應(yīng)用(二)用動態(tài)規(guī)劃法處理這種問題時，通常把給一個使用者分配資源的過程看成一個階段，按n個使用者分成先后n個決策階段。即先給第1個使用者分配資源，為第一階段；再給第2個使用者分配，為第2階段；依此類推，最后給第n個使用者分配，為第n階段。2資源分配問題?例某工業(yè)部門根據(jù)國家計劃安排，擬將五臺某種高效率的機器分配給所屬的甲、乙、丙三個工廠，各工廠得到不同數(shù)量的機器可獲得的收益如下表。問應(yīng)如何分配機器，才能使各廠的總效益最大。?某單位準(zhǔn)備在以后的n個時期內(nèi)采購一批物資。各時期的價格不是確定的，而是按照某種已知的概率分布取值。試制定采購策略，確定在哪一時期以什么價格采購，能使采購價的數(shù)學(xué)期望值最低。這類問題也適合用動態(tài)規(guī)劃法進(jìn)行處理。下面通過實例加以說明。例7某廠生產(chǎn)上需要在近五周內(nèi)采購一批原料，而估計在未來五周的價格有波動，其浮動價格和概率策得如下表。試確定該廠應(yīng)在哪一周以什么價格購入，能使其采購價的數(shù)學(xué)期望值最小，并求出期望值。4.4動態(tài)規(guī)劃的應(yīng)用(三)3不確定性采購問題?設(shè)有n個工件需要在機床A、B上加工，每個工件都必須先經(jīng)過A而后B兩道加工工序。以ai、bi分別表示工件i(1≤i≤n)在A、B上的加工時間。問應(yīng)如何在兩機床上安排各工件的加工順序，使在機床A上加工第一個工件開始到在機床B上加工完最后一個工件為止，所用的加工總時間最少？加工工件在機床A上有加工順序問題，在機床B上也有加工順序問題?？梢宰C明：最優(yōu)加工順序在兩臺機床上可同時實現(xiàn)。因此，最優(yōu)排序方案可以只在機床A、B上加工順序相同的排序中尋找。即使如此，所有可能的方案仍有n!個，這是一個不小的數(shù)，用窮舉法是不現(xiàn)實的。4.4動態(tài)規(guī)劃的應(yīng)用(四)4排序問題?用動態(tài)規(guī)劃法可以推出，工件i應(yīng)該排在工件j之前的條件為min(ai,bj)≤min(aj,bi)。根據(jù)這個條件，構(gòu)造下列排序方法：

a1a2…an1)建立工時矩陣M=b1b2…bn2)在工時矩陣M中找出最小元素（若不止一個可任選其一），若它在上行，則相應(yīng)的工件排在最前位置；若它在下行，則相應(yīng)的工件排在最后位置。3)將排定位置的工件所對應(yīng)的列從M中劃去，然后對余下的工件再按2)進(jìn)行排序。如此進(jìn)行下去，直到把所有工件都排完為止。當(dāng)加工順序排定之后，工件在A上沒有等待時間，而在B上則常常需要等待。因此，尋求最優(yōu)排序方案只有盡量減少在B上等待加工的時間，才能使總加工時間最短。?

例設(shè)有5個工件需在機床A、B上加工，加工的次序為先A后B，每個工件需要的加工時間如下表。試安排加工順序，使總加工時間最少，并求出總加工時間。?第3章科學(xué)決策與信息分析主要內(nèi)容：信息分析在決策中的作用；各類型決策中的信息保障；信息分析的工作流程?；疽螅毫私飧黝悰Q策中信息利用的重要性；了解不同決策階段信息服務(wù)的特點；理解決策對信息的基本要求；掌握信息分析工作的基本流程。3.1信息分析在決策中的作用3.1.1決策活動中的信息利用信息分析:是對情報進(jìn)行定向濃集和科學(xué)抽象的一種科學(xué)勞動.信息在軍事戰(zhàn)略制定中的作用；信息在制定地區(qū)經(jīng)濟發(fā)展規(guī)劃中的作用；信息在科學(xué)管理中的作用；信息在對外貿(mào)易中的作用；信息在制定生產(chǎn)計劃中的作用；信息在提高產(chǎn)品質(zhì)量、發(fā)展花色品種中的作用。3.1信息分析在決策中的作用3.1.2不同決策階段的信息服務(wù)決策階段信息服務(wù)的內(nèi)容與特點決策前（超前服務(wù)）促成決策及早完成（快）；有助于決策者掌握預(yù)測性信息（準(zhǔn)）；有助于決策者更新知識、增強判斷力（增）決策中（跟蹤服務(wù)）確立目標(biāo)階段；決策方案準(zhǔn)備階段；選定決策方案階段。決策后（反饋服務(wù)）跟蹤反饋；循環(huán)反饋；同步追蹤反饋。3.1信息分析在決策中的作用3.1.3決策對信息的基本要求可靠性（可信度）——信息的真實性和準(zhǔn)確性。信息源；信息獲取手段；信息獲取的條件。完整性（完全度）——包括決策對象全部的信息全面收集歷史的、現(xiàn)實的和未來的信息；兼顧反映正面的和反面問題的信息。精確性（精確度）——反映事物特征的細(xì)微化程度。不同決策對信息的精確度要求不同；劃定范圍，確定上限和下限。3.2各類型決策中的信息保障3.2.1新產(chǎn)品研制的信息保障創(chuàng)意產(chǎn)生與篩選階段的信息保障創(chuàng)意產(chǎn)生于對信息的收集、吸收和理解；創(chuàng)意孕育著新產(chǎn)品，要盡可能多的收集；篩選是從多個創(chuàng)意中選擇出具有開發(fā)價值項目的過程，其要求是：新意；可行；實用；有效。3.2各類型決策中的信息保障3.2.1新產(chǎn)品研制的信息保障開發(fā)決策階段的信息保障主要任務(wù)是針對經(jīng)過初步篩選出的幾個創(chuàng)意中的每一個新產(chǎn)品開發(fā)構(gòu)想收集信息；主要目的是從若干初步入選的新產(chǎn)品開發(fā)設(shè)想中挑選一個，作為本企業(yè)的新產(chǎn)品研制項目。新產(chǎn)品設(shè)計階段的信息保障方案設(shè)計：正確選型，確定新產(chǎn)品的基本結(jié)構(gòu)和基本參數(shù)。技術(shù)設(shè)計：確定產(chǎn)品的具體結(jié)構(gòu)和形式，進(jìn)行各部分、各部件的設(shè)計和組裝設(shè)計。施工設(shè)計：繪制新產(chǎn)品試制所需的全套圖紙，編制有關(guān)制造工藝的全部文件。3.2各類型決策