【正文】 一的處理方法，從而我們稱動(dòng)態(tài)規(guī)劃是一種方法。在多階段決策問題中，既然引入了階段的概念，也就與時(shí)間密不可分，決策過程從一個(gè)狀態(tài)到另一個(gè)狀態(tài)，隨著時(shí)間的變化在變化，也就有了“動(dòng)態(tài)”的含義。描述階段的變量稱為階段變量，用 k表示。 動(dòng)態(tài)規(guī)劃的基本概念 ?(4)策略 (Policy) ?策略是一個(gè)按順序排列的決策序列，用 pk,n(sk)={uk(sk), uk+1(sk+1), … u n(sn)} 表示從第 k階段 sk狀態(tài)開始到終止的決策序列，稱為 k子過程策略；當(dāng) k=1時(shí)，即為全過程的一個(gè)策略，簡稱策略。 ? 為了利用最優(yōu)性原理求解多階段決策問題，還要導(dǎo)出一些遞推公式，便于運(yùn)算。 下面用兩種迭代法來求解。選一無回路的初始策略 {u1(i), i=1,2,…,N 1}, u1(i)表示在此策略下由 i點(diǎn)到達(dá)的下一個(gè)點(diǎn)。 策略空間迭代法 ?可以證明：若初始策略 {u1(i)}不構(gòu)成回路，則以后迭代所得的策略 {uk(i)}也不構(gòu)成回路（即解是唯一的），且{fk(i)}一致收斂于泛函方程的解。 函數(shù)空間與策略空間迭代法 ?注意：在求解這類問題中，若網(wǎng)絡(luò)中出現(xiàn)負(fù)權(quán)邊，由于有可能出現(xiàn)負(fù)圈，故上述方法不太適用。 ? 設(shè) sk為狀態(tài)變量，表示在第 k階段（第 k年）可投入 A、 B兩種生產(chǎn)的資源量。 設(shè)狀態(tài)變量為 (Xk,Yk), Xk,Yk分別表示分配用于第 k種生產(chǎn)至 n種生產(chǎn)的兩種物資的數(shù)量 (資源剩余量 )。 ?? ?n i by1 * )(???nii by1* )(????ni iby1* )(? 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ?(2)逐次逼近法 ?這是另一種降維方法，先保持一個(gè)變量不變，對另一個(gè)變量實(shí)現(xiàn)最優(yōu)化，然后交替地固定變量，以迭代的形式反復(fù)進(jìn)行，直到獲得某種要求為止。 排序問題 ? X：表示在 A上等待加工的按取定順序排列。 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 令 hi(xi)=hi(xi,λ) = max[gi(xi,yi) –λyi] yi≥0 于是問題變?yōu)? max[h1(x1)+h1(x1)+…+h n(xn)] 滿足條件 x1+x2+…+x n=a xi≥0, i=1,2,…,n )0),(lim,( ??? iiiiy yyxgi可設(shè)為了使此式有意義 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ?這是一個(gè)一維分配問題，可用對一維的方法求解，這里由于 λ是參數(shù)，因此，最優(yōu)解 xi*是參數(shù) λ的函數(shù)，相應(yīng)的 yi*也是 λ的函數(shù)，即 xi=xi*(λ), yi=yi*(λ)為其解。 ?當(dāng) g(u), h(u)為凸函數(shù)，且 h(0)=g(0)=0時(shí)，可以證明：在每個(gè)階段上 u(i)的最優(yōu)決策總是取其上限或下限，因此，對于解的結(jié)構(gòu)來說，它與 g(u), h(u)是線性情況是類似的。 1中的例 2，將資源分配劃分為三個(gè)階段，分配給生產(chǎn)產(chǎn)品 A， B，C的數(shù)量設(shè)為 x1,x2,x3，其狀態(tài) (資源剩余量 )s1=4, s2=s1x1, s3=s2x2, sn+1=s4=0. ?現(xiàn)列表計(jì)算如下： 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ?由上述表知，最大總收益等于 35，最優(yōu)決策序列是 ?x1*=1, x2*=2, x3*=1 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 例 3 資源連續(xù)分配問題： ? 設(shè)有數(shù)量為 s1的某種資源，可投入生產(chǎn) A和 B兩種產(chǎn)品，第一年若以數(shù)量 u1投入生產(chǎn) A，剩下的s1u1投入生產(chǎn) B，其收入為 g(u1)+h(s1u1)，這里g(0)=h(0)=0，在 A、 B生產(chǎn)后，資源的回收率分別為 0a1, 0b1, 則在第一年生產(chǎn)后，回收的資源量合計(jì)為 s2=au1+b(s1u1)。 ,4176。 , 3176。直到 fk(i) = fk+1(i) = …=f(i) 為止， i=1,2,…,N 函數(shù)空間迭代法 ?可以證明： (1)由上述步驟確定的函數(shù)序列 {fk(i)} 不超過 N1步單調(diào)下降收斂于問題的最優(yōu)函數(shù) f(i) (2)若 0≤Cij+∞（ i,j=1,2,…,N ） ,則收斂步驟 P有下列估計(jì)： 12lg )1lg(2lg )1lg( ????? NPN 策略空間迭代法 ?策略空間的迭代就是先給出初始策略{u1(i)}，然后按某種方式求得新策略{u2(i)}, {u3(i)},… ，直至最終求出最優(yōu)策略。 ?設(shè)有 N個(gè)點(diǎn)，以 1, 2, …, N 記之，任兩點(diǎn) i, j之間的長度為 Cij, 當(dāng) i, j間有一弧直接連接時(shí)， 0≤Cij+∞, 當(dāng) i, j間不直接連接它們的弧時(shí)， Cij=+∞. 今設(shè) N為終點(diǎn)，求任一點(diǎn) i至終點(diǎn) N的最短距離。 動(dòng)態(tài)規(guī)劃的最優(yōu)性原理 ? 利用最優(yōu)性原理，可以把多階段決策問題的求解過程看成是一個(gè)連續(xù)的遞推過程，由后向前逐步推算（因條件不同，也可能由前向后推算）。描述決策的變量稱為決策變量，常用 uk(sk)表示第 k個(gè)階段當(dāng)狀態(tài)處于 sk時(shí)的決策變量，它是狀態(tài)變量的函數(shù)。 解法二稱為逆推解法（逆序解法） 最短路線問題的解 ?上面的做法極其簡單，從中我們可以處到這樣一個(gè)規(guī)律，即最短路線必須且只能由最短子路線組成，在求 A到 G的最短路線時(shí)，附帶求得了從所有中間頂點(diǎn)到 G的最短路，它們是作為整個(gè)問題的子問題出現(xiàn)的，并且被嵌入較大問題之中，這常常是動(dòng)態(tài)規(guī)劃方法的一個(gè)特點(diǎn)。 多階段決策問題及實(shí)例 ? 各個(gè)階段的決策確定以后就構(gòu)成一個(gè)決策序列，稱為一個(gè)策略。 動(dòng)態(tài)規(guī)劃 ? 動(dòng)態(tài)規(guī)劃把比較復(fù)雜的問題劃分成若干階段，通過逐段求解，最終求得全局最優(yōu)解。 則有 )39。 于是，若記 λj0fj0= max λjfj 1≤j≤p 則 U(F)=max λjfj =λj0fj0λj0fj039。fj0 從而 λj0fj0λj0fj039。 從而 λj0fj0λj0fj039。則 λjfj≤λjfj39。時(shí)，都有 U(F)U(F39。設(shè) (X, t)為 (Qt)的任一可行解，由 λjfj(X)≤t, j=1,2,…,p, X ∈ R 知 max λjfj(X)≤t 對任意 X∈ R 1≤j≤p 由此 t* = max λjfj(X*)≤max λjfj(X)≤t 1≤j≤p 1≤j≤p 即 t*為 (Qt)的最小值， (X*， t*）為 (Qt)的最優(yōu)解。 pjfXfXFUjpjjpjpjjj,...,2,1,0,1,...,))(())((11201??????????????數(shù)它們滿足為事先給定的一組權(quán)系其中 處理多目標(biāo)規(guī)劃的一些方法 ? 3. 理想點(diǎn)法（虛擬點(diǎn)法） 先求 p 個(gè)單目標(biāo)規(guī)劃問題的最優(yōu)解，記 fj*=fj(X(j))=min fj(X) j=1,2,…,p X∈ R 若所有 X(j)( j=1,2,…,p) 都相同，設(shè)為 X*，則X*為多目標(biāo)函數(shù)的絕對最優(yōu)解，但一般不易達(dá)到，因此向量 F*=(f1*,f2*,…,f p*) 只是一個(gè)理想點(diǎn)。 假設(shè) X*不 ∈ Rpa*，則必存在 Y∈ R，使 F(Y)≤F(X*) 下面分兩種情形討論： (1)若 f1(Y)f1(X*), 而 f1(X*)=f1*, 故得 (P1)的可行解 Y滿足 f1(Y)f1(X*)=f1* 此與 f1*=min f1(X)相矛盾。 ** wppa EE ? 多目標(biāo)規(guī)劃解的性質(zhì) ? 定理 4 在像集 F(R)上，若 Epa*已知，則在約束集合 R上，有 ? 定理 5 在像集 F(R)上，若 Ewp*已知，則在約束集合 R上，有 ? 另外通過對像集的研究，可以更直觀地認(rèn)識(shí)問題，并且可以提供一些處理多目標(biāo)規(guī)劃的方法。 *1*jpjab RR ??? 多目標(biāo)規(guī)劃解的性質(zhì) 多目標(biāo)規(guī)劃解的性質(zhì) ?定義 4 如果 f1(X), f2(X),…,f p(X)和 g1(X), g2(X),…,g m(X)均為凸函數(shù)，則稱多目標(biāo)數(shù)學(xué)規(guī)劃（ VP）為 凸多目標(biāo)數(shù)學(xué)規(guī)劃 。因此需要根據(jù)別的原則，權(quán)衡兩者之間的得失，從 R中找出滿意的方案來。 167。至今多目標(biāo)規(guī)劃已廣泛應(yīng)用于經(jīng)濟(jì)、管理、系統(tǒng)工程等科技的各個(gè)領(lǐng)域。 第五章 多目標(biāo)規(guī)劃 ?早在 1772年， Franklin就提出了多目標(biāo)問題矛盾如何協(xié)調(diào)的問題， 1896年，Pareto首次從數(shù)學(xué)角度提出了多目標(biāo)最優(yōu)決策問題，直到二十世紀(jì) 5070年代 Charnes, Karlin, Zadeh等人先后做了許多較有影響的工作，多目標(biāo)規(guī)劃受到人們的關(guān)注。 ?一般假設(shè)多目標(biāo)規(guī)劃中的目標(biāo)函數(shù)已經(jīng)是規(guī)范化了的。當(dāng)一目標(biāo)達(dá)到最優(yōu)時(shí)，另一目標(biāo)達(dá)不到最優(yōu)，兩目標(biāo)相互矛盾。并有下列定理。對此，有如下的定理。 ?定理 6 設(shè) X*是由分層序列法所得到的最優(yōu)解，則 X*∈ Rpa*. 處理多目標(biāo)規(guī)劃的一些方法 ? [證明 ]用反證法證明。 (1)“老手法” (2)α方法 處理多目標(biāo)規(guī)劃的一些方法 ?2. 平方和加權(quán)法 對單目標(biāo)規(guī)劃問題 (Pj) min fj(X) j=1,2,…,p X∈ R 求出一個(gè)盡可能好的下界 f10,…,f p0（可看成是規(guī)定值）， min fj(X)≥ fj0 j=1,2,…,p X∈ R 處理多目標(biāo)規(guī)劃的一些方法 ? 構(gòu)造評價(jià)函數(shù) ? 然后求 min U(F(X)) X∈ R 求得最優(yōu)解 X*作為多目標(biāo)規(guī)劃的解。 處理多目標(biāo)規(guī)劃的一些方法 ? 反之，設(shè) X*為 (Q)的最優(yōu)解，最小值為 max λjfj(X*)≡ t* 1≤j≤p 易見 (X*, t*)是 (Qt)的可行解?！?Ep, 當(dāng) FF39。 這是因?yàn)?，?λj≥0， j=1,2,…,p, 且 FF39。 則 至少存在某個(gè) j0(1≤j0≤p)，使 fj0fj039。fj0 j=1,2,…,p 且至少存在某個(gè) j0(1≤j0≤p)，有 fjfj0fj39。則對 j=1,2,…,p, 均有 fjfj39。 j=1,2,…,p 且至少存在某個(gè) j0(1≤j0≤p)使 gj0gj039。 1951年美國數(shù)學(xué)家 （貝爾曼）等人根據(jù)一類多階段決策問題的特性，提出了解決這類問題的“最優(yōu)性原理”，并研究了許多實(shí)際問題，從而建立了最優(yōu)化的一個(gè)分支 ——?jiǎng)討B(tài)規(guī)劃。因此，各個(gè)階段決策的選取常依賴于當(dāng)前面臨的狀態(tài)，又影響下一個(gè)階段的決策，從而影響整個(gè)過程的活動(dòng)路線，這種把一個(gè)問題看成一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為 多階段決策過程 ，也稱 序貫決策過程 。 2動(dòng)態(tài)規(guī)劃的基本概念 ?一、最短路線問題的解 首先討論最短路線問題的求解方法 [解法一 ]枚舉法 48條不同路線 48 6=288步加法 47次路線長度的比較 最短路長為 18 最短路線問題的解 ? [解法二 ]共有 6個(gè)階段 記 f1(A) ——A到 G的最短距離 則 f1(A)依賴于 f2(B1), f2(B2), ……… 而 f6(F1)=4, f6(F2)=3 故由后向前寫出相應(yīng)公式的形式。在最優(yōu)控制中也稱為控制。 動(dòng)態(tài)規(guī)劃的最優(yōu)性原理 ： 一個(gè)（整個(gè)過程的）最優(yōu)策略所具有的性質(zhì)是，不論過去的狀態(tài)和決策如何，其余下的諸決策必構(gòu)成一個(gè)最優(yōu)子策