《運(yùn)籌學(xué)-動(dòng)態(tài)規(guī)劃》PPT課件.ppt

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

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

3、策略。在上例中，每條路線都稱為策略。使整個(gè)問題最優(yōu)的策略是最優(yōu)的策略。也就是說，在前面的例子中，最短的策略是最佳策略。7，狀態(tài)轉(zhuǎn)移方程，動(dòng)態(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的問題的整個(gè)過程，對于給定的所有內(nèi)容，通常使用的VK，N是Vk，N (sk，UK，SK1，SN1)，K=1，2，N指示符函數(shù)最佳值是最佳指示符函數(shù)，fk(sk如果K=1，則F1(s1)是從初始狀態(tài)到整個(gè)

4、流程的整體最佳函數(shù)、9、指標(biāo)函數(shù)、(1)流程和子流程的指標(biāo)是所包括的每個(gè)步驟的指標(biāo)總和。(2)流程及其子流程的指標(biāo)是所包含的每個(gè)步驟的指標(biāo)的乘積。指標(biāo)函數(shù)必須有可分離性牙齒，并滿足遞歸關(guān)系。Vj(sj，uj)表示階段j的指標(biāo)，1，2表達(dá)式分別表示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個(gè)段落。6茄子狀態(tài)允許集33666牙齒。D3、S5=E1、E2、S6=F、12、范例1的決策允許集D1 (a)=B1、B2 D2 (B

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

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

7、動(dòng)態(tài)規(guī)劃研究的問題是時(shí)間相關(guān)，它研究了多階段決策過程的問題，整個(gè)時(shí)間或空間的特點(diǎn)，多次分為前后連接的施工階段，找出了整個(gè)問題的最佳決策序列。因此，對于一些靜態(tài)問題，也可以人工引入時(shí)間因素，并根據(jù)階段被認(rèn)為是動(dòng)態(tài)規(guī)劃問題，因此動(dòng)態(tài)規(guī)劃可能是解決特定線性、非線性計(jì)劃的有效方法。(P203)，24，1，建立動(dòng)態(tài)規(guī)劃模型，設(shè)置動(dòng)態(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)計(jì)劃模型如下：maxz=G1(x1)G2(x2)gn(xn)x1 x2 xn=axi 0(I=1，2，n)，31；n如果將茄子產(chǎn)品作為一個(gè)互連的整體生產(chǎn)，則一個(gè)產(chǎn)品的資源分配將由階段組成，每個(gè)階段確定一個(gè)產(chǎn)品的資源投入量。牙齒問題成為多層次的決策問題。狀態(tài)變量sk的選擇原則是據(jù)此確定滿足決策變量uk和狀態(tài)切換方程要求的

9、非滯后性。在資源分配問題中，決策變量被選擇為產(chǎn)品K的資源投入量，因此狀態(tài)變量可以選擇步驟K最初擁有的資源量，即在K種和第N種產(chǎn)品之間分配的資源量。牙齒問題的靜態(tài)計(jì)劃模型是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)分析集團(tuán)提出要求：如何分配50萬元給三家工廠，實(shí)現(xiàn)最大總收益？35，解決：首先分配工廠1牙齒，分配其余工廠2，最后分配給工廠3。設(shè)置動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的過程如下：1)步驟變量k=1，2，3，2)狀態(tài)變量sk表示從第k個(gè)工廠到第n個(gè)工廠分配的資金數(shù)。3)決策變量xk表示為分配給第K個(gè)工廠的資金數(shù)。4)狀態(tài)轉(zhuǎn)移方程sk 1=sk-xk是從k 1工廠到第N個(gè)工廠分配的資金數(shù)。5)階段指標(biāo)函數(shù)gk(xk)表示分配給資金xk的第K個(gè)工廠的收入。，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，計(jì)算方法如下：39，示例3。投資項(xiàng)目i(i=1，2，3)的投資額可以列出它的靜態(tài)模型：分析：這是表面和時(shí)間無關(guān)的問題，但要用動(dòng)態(tài)規(guī)劃方法解決，必須將其分為“期間”。牙齒問題可以分為三個(gè)時(shí)期，每一段只決定一個(gè)投資項(xiàng)目投資額。這樣的問題是三級決策問題。當(dāng)40，解析K