1、1，Yunchouxue，第七章動態(tài)規(guī)劃，2，最短路問題例如動態(tài)規(guī)劃概念，3，1，動態(tài)規(guī)劃基本概念：1，3360將要研究的問題、定時或空間特征分為幾個相互連接的階段。簡稱為“階段”。步驟就是決策做幾次。描述步驟的變量稱為步驟變量，k通常表示步驟變量。在上例中，k1、2、3、4、5。4，2，狀態(tài)和特性，每個階段開始的客觀條件稱為狀態(tài)。描述每個步驟狀態(tài)的變量稱為狀態(tài)變量，sk通常表示步驟的狀態(tài)變量，sk的值集稱為狀態(tài)集，Sk表示。階段的出發(fā)位置，即階段的起點。在上例中，第二階段有兩種茄子狀態(tài)。換句話說，Sk=B1，B2動態(tài)規(guī)劃期間的狀態(tài)具有以下屬性：確認(rèn)步驟：的狀態(tài)后，后續(xù)進程的狀態(tài)更改不受牙齒狀

2、態(tài)的先前影響。也就是說，處于特定狀態(tài)的后續(xù)進程與以前無關(guān)。僅與當(dāng)前狀態(tài)相關(guān)。我們把牙齒特性稱為“非后天性”。)P194，5，3，決策和策略，即表示從一個階段到下一個階段的狀態(tài)的選擇(決定)，稱為決策。表示決策變量的變量稱為決策變量，通常使用uk(sk)。k階段狀態(tài)為sk時表示決策變量。在實際問題中，決策變量的值通常限制在一定范圍內(nèi)。這稱為允許決策集，公用Dk(sk)表示k階段從狀態(tài)sk開始的允許決策集，因此uk(；步驟2中的狀態(tài)B1表示您可以選擇下一步驟中的C1、C2和C3。也就是說，允許的決策集為D2(B1)。如果我們選擇決策C3，則u2(B1)=C3。整個過程中每個步驟的決策配置順序統(tǒng)稱為

3、策略。在上例中，每條路線都稱為策略。使整個問題最優(yōu)的策略是最優(yōu)的策略。也就是說，在前面的例子中，最短的策略是最佳策略。7，狀態(tài)轉(zhuǎn)移方程，動態(tài)規(guī)劃中牙齒階段的狀態(tài)是上一階段的決策結(jié)果。如果給定了步驟k的狀態(tài)sk，則牙齒階段的決策狀態(tài)為uk(sk)，那么步驟k 1的狀態(tài)uk 1也完全確定，其關(guān)系為3360 SK1=TK (SK，)，8，指標(biāo)函數(shù)，衡量選定戰(zhàn)略優(yōu)劣的數(shù)量指標(biāo)函數(shù)。N段決策過程，從1到N的問題的整個過程，對于給定的所有內(nèi)容，通常使用的VK，N是Vk，N (sk，UK，SK1，SN1)，K=1，2，N指示符函數(shù)最佳值是最佳指示符函數(shù)，fk(sk如果K=1，則F1(s1)是從初始狀態(tài)到整個

4、流程的整體最佳函數(shù)、9、指標(biāo)函數(shù)、(1)流程和子流程的指標(biāo)是所包括的每個步驟的指標(biāo)總和。(2)流程及其子流程的指標(biāo)是所包含的每個步驟的指標(biāo)的乘積。指標(biāo)函數(shù)必須有可分離性牙齒，并滿足遞歸關(guān)系。Vj(sj，uj)表示階段j的指標(biāo)，1，2表達式分別表示vk、n (sk，uk，sk1，sn1) vk (sk，uk) vk1、n (Sk2，sn1)、n牙齒問題的總目標(biāo)是求出f1(A)，即從A到結(jié)束F的最短距離，11。階段可以將網(wǎng)絡(luò)圖中的問題分成k=5段。狀態(tài)從A-F分為5個段落。6茄子狀態(tài)允許集33666牙齒。D3、S5=E1、E2、S6=F、12、范例1的決策允許集D1 (a)=B1、B2 D2 (B

5、1)=，14，2，動態(tài)規(guī)劃基本思想和基本方程，最短路徑具有重要的特性，根據(jù)牙齒特性，找到最短段落的方法是從最后一段開始，從后面往前走，求出從各點到F點的最短段落，最后求出從A點到F點的最短段落。(阿爾伯特愛因斯坦，美國電視電視劇，藝術(shù))因此動態(tài)規(guī)劃方法是從終點到起點方向找出最短段落的方法。15，動態(tài)規(guī)劃最優(yōu)化路徑：尋找從終點到起點的最短路徑。范例1:從范例1衍生動態(tài)規(guī)劃基本方程式。16，17，動態(tài)規(guī)劃基本方程(1)，如上計算過程所示，在求解的各個階段，我們用了步驟K和步驟k 1的遞歸關(guān)系，18，動態(tài)規(guī)劃基本方程(2)，19，(2)在多階段決策過程中，動態(tài)規(guī)劃方法是將當(dāng)前段落和未來段落分開，將當(dāng)

6、前效果和未來效果相結(jié)合的最優(yōu)化方法。因此，各段的決策選擇是全局考慮的，與牙齒段的最佳選擇答案一般不同。(3)在查找整個問題的最優(yōu)策略時，初始狀態(tài)是已知的，每個段的決策段是該段的狀態(tài)函數(shù)，因此，可以通過逐個轉(zhuǎn)換最優(yōu)策略通過的每個段的狀態(tài)來確定最優(yōu)路徑。20，最短路問題地圖作業(yè)指示法，4，3，7，5，12，10，8，9，13，15，17，0整個過程的最佳策略具有以下特點：無論以前的狀態(tài)和是否決策了牙齒最優(yōu)策略的特定狀態(tài)，所有未來對牙齒狀態(tài)的決策之一都必須構(gòu)成最優(yōu)子策略。這意味著最佳策略的一個子策略是最佳策略。23、3、動態(tài)規(guī)劃和靜態(tài)計劃的關(guān)系、與時間無關(guān)的線性規(guī)劃問題或非線性計劃問題稱為靜態(tài)計劃。

7、動態(tài)規(guī)劃研究的問題是時間相關(guān)，它研究了多階段決策過程的問題，整個時間或空間的特點，多次分為前后連接的施工階段，找出了整個問題的最佳決策序列。因此，對于一些靜態(tài)問題，也可以人工引入時間因素，并根據(jù)階段被認(rèn)為是動態(tài)規(guī)劃問題，因此動態(tài)規(guī)劃可能是解決特定線性、非線性計劃的有效方法。(P203)，24，1，建立動態(tài)規(guī)劃模型，設(shè)置動態(tài)模型的6茄子元素：1)階段k 2)狀態(tài)SK 3)決策uk(sk) 4)狀態(tài)轉(zhuǎn)移方程5)階段指標(biāo)函數(shù)6)指標(biāo)迭代方程，25；順序解析(正向重復(fù))，1，從已知初始狀態(tài)S1反向解析： (反向重復(fù))，26，3，這兩種解決方案的區(qū)別如下表所示。27，順序解析示例1:28，29，4，例如

8、，提出東江流域水資源分配問題，東江流域水資源首次分配方案。公共資源、教育資源、衛(wèi)生資源等都包括資源分配問題。30，1，一維資源分配問題，某些資源總量為A，用于生產(chǎn)N茄子產(chǎn)品。分配數(shù)量Xi用于生產(chǎn)我的I產(chǎn)品，我的I產(chǎn)品的收入是gi(Xi)。問：如何分配以最大化總利潤？牙齒問題的靜態(tài)計劃模型如下：maxz=G1(x1)G2(x2)gn(xn)x1 x2 xn=axi 0(I=1，2，n)，31；n如果將茄子產(chǎn)品作為一個互連的整體生產(chǎn)，則一個產(chǎn)品的資源分配將由階段組成，每個階段確定一個產(chǎn)品的資源投入量。牙齒問題成為多層次的決策問題。狀態(tài)變量sk的選擇原則是據(jù)此確定滿足決策變量uk和狀態(tài)切換方程要求的

9、非滯后性。在資源分配問題中，決策變量被選擇為產(chǎn)品K的資源投入量，因此狀態(tài)變量可以選擇步驟K最初擁有的資源量，即在K種和第N種產(chǎn)品之間分配的資源量。牙齒問題的靜態(tài)計劃模型是maxz=G1(x1)G2(x2)gn(xn)x1 x2 xn=axi 0(I=1，2，n)，33，1維資源分配范圍是0ska決策變量uu范圍為0uksk。狀態(tài)轉(zhuǎn)移方程式是sk 1=sk-uk階段指標(biāo)。資源分配uk用于生產(chǎn)K產(chǎn)品的收入。指標(biāo)包括函數(shù)、Vk(sk，uk)=gk(uk)=gk(xk)。重復(fù)方程式為，34，范例2: 1。如果用10萬元作為最小分割單位，工廠收益和投資之間的關(guān)系如下：從數(shù)量決策的需要，向公司經(jīng)理、公司系

10、統(tǒng)分析集團提出要求：如何分配50萬元給三家工廠，實現(xiàn)最大總收益？35，解決：首先分配工廠1牙齒，分配其余工廠2，最后分配給工廠3。設(shè)置動態(tài)規(guī)劃數(shù)學(xué)模型的過程如下：1)步驟變量k=1，2，3，2)狀態(tài)變量sk表示從第k個工廠到第n個工廠分配的資金數(shù)。3)決策變量xk表示為分配給第K個工廠的資金數(shù)。4)狀態(tài)轉(zhuǎn)移方程sk 1=sk-xk是從k 1工廠到第N個工廠分配的資金數(shù)。5)階段指標(biāo)函數(shù)gk(xk)表示分配給資金xk的第K個工廠的收入。，6)指標(biāo)遞歸方程：36，最大收益：F3 (S3)=G3 (X3) F4 (S4)，S3，X3，G3 (X3)，0 S3萬韓元全部出廠，38，最大收益為f1 (S1)=，016 16，4.5 12.5=17，7 9.5。如果S2=s1- x1*=5-1=4，則x2*3 s3=s2- x2*。x1=0，1，2，3，4，5，計算方法如下：39，示例3。投資項目i(i=1，2，3)的投資額可以列出它的靜態(tài)模型：分析：這是表面和時間無關(guān)的問題，但要用動態(tài)規(guī)劃方法解決，必須將其分為“期間”。牙齒問題可以分為三個時期，每一段只決定一個投資項目投資額。這樣的問題是三級決策問題。當(dāng)40，解析K