【正文】 略。 4 函數(shù)空間與策略空間迭代法 ?多階段決策問(wèn)題其階段數(shù)有可能是固定的，也有可能不是固定的，此時(shí)可用泛函方程來(lái)求解。反復(fù)迭代 2176。按 2176。 , 3176。 原料分配量 產(chǎn)品種類 （噸） A B C 0 0 0 0 1 10 6 8 2 17 17 11 3 20 18 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ?下面求167。 先計(jì)算 f3(s3),得 f3(s3)=max { + (s3u3)} 0≤u3≤s3 = max { + }= 0≤u3≤s3 u3*=s3 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 而 f2(s2)=max {g(u2) + h(s2u2) + f3(au2+b(s2u2))} 0≤u2≤s2 = max { + }= 0≤u2≤s2 u2*=s2 f1(s1)=max {g(u1) + h(s1u1) + f2(au1+b(s1u1))} 0≤u1≤s1 = max { }= 0≤u1≤s1 u1*=0 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 上述結(jié)果可列表如下： 實(shí)際階段 投入 A的量 投入 B的量 收入 剩余量 1 0 s1 2 s1 0 3 0 總收入 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ?上面的例子較簡(jiǎn)單，但當(dāng) n很大時(shí)，且g(u), h(u)是復(fù)雜函數(shù)時(shí)，問(wèn)題的求解也是不容易的。 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ? (1)Lagrange乘子法 引入 Lagrange乘子 λ，將上述問(wèn)題化為 max{g1(x1,y1) +g2(x2,y2) +…+g n(xn,yn) –λ(y1+y2+…+y n)} 滿足條件 x1+x2+…+x n=a xi≥0, yi≥0 i=1,2,…,n 其中 λ作為一個(gè)固定的參數(shù)。 排序問(wèn)題 ?當(dāng)加工順序取定之后，工件在 A上加工時(shí)沒(méi)有等待時(shí)間，而在 B上常常等待，且第 i個(gè)工件在 A上加工完畢以后，在 B上要經(jīng)過(guò)若干時(shí)間才能加工完，因此對(duì)同一個(gè)工件來(lái)說(shuō)，在 A、 B上總是出現(xiàn)加工完畢的時(shí)間差。 逐次逼近法 ? 先設(shè) x(0)={x1(0), x2(0),…,x n(0)}為滿足x1(0)+x2(0)+…+x n(0)=a的一個(gè)可行解，固定 x在 x(0)，求 max{g1(x1(0),y1) +g2(x2(0),y2) +…+g n(xn(0),yn)} 滿足條件 y1+y2+…+y n=b yi≥0 i=1,2,…,n 的解，設(shè)這個(gè)解為 y(0)={y1(0), y2(0),…,y n(0)} 逐次逼近法 ?然后再固定 y為 y(0), 求 max{g1(x1,y1(0)) +g2(x2,y2(0)) +…+g n(xn,yn(0))} 滿足條件 x1+x2+…+x n=a xi≥0 i=1,2,…,n 的解，設(shè)其解為 x(1)={x1(1), x2(1),…,x n(1)}， 逐次逼近法 ?再固定 x為 x(1),對(duì) y求解，這樣依次輪換下去得到一系列的解 {x(k)},{y(k)}，(k=0,1,2,…), 顯然，函數(shù)值 g1(x1(k),y1(k)) +g2(x2(k),y2(k)) +…+g n(xn(k),yn(k))是單調(diào)上升的，通常它收斂到一個(gè)局部最優(yōu)解，因此，在實(shí)際計(jì)算中，可選擇幾個(gè)初始點(diǎn) x(0)進(jìn)行計(jì)算，從中選出一個(gè)最好的解作為近似最優(yōu)解。 決策變量為 (xk,yk), xk,yk分別表示分配用于第 k種生產(chǎn)的兩種物資的數(shù)量。 ? uk為決策變量，它表示在第 k階段用于 A生產(chǎn)的資源量，則 skuk表示用于 B生產(chǎn)的資源量。 167。 函數(shù)空間與策略空間迭代法 ?例 3 下圖為一街區(qū)的單行道交通網(wǎng)絡(luò)，分別用函數(shù)空間迭代法和策略空間迭代法求各點(diǎn)到頂點(diǎn) 5的最短路線。令 k=1 策略空間迭代法 2176。 函數(shù)空間迭代法 ? 設(shè) fk(i)表示由 i點(diǎn)出發(fā)向 N走 k步所構(gòu)成的所有路線中的最短距離。 二、泛函方程 ?在最短路的計(jì)算中，若記 fk(sk)表示第 k階段處于狀態(tài) sk時(shí)到終點(diǎn)的最短距離， dk(sk, uk(sk)表示從狀態(tài) sk到由決策 uk(sk)所決定的狀態(tài) sk+1之間的距離，則有下列遞推關(guān)系式 fn+1(sn+1)=0 fk(sk)=min{dk(sk, uk(sk)) + fk+1(sk+1)} k=n,n1,…,2,1 uk∈ Dk(sk) 泛函方程 ? 一般地，所有動(dòng)態(tài)規(guī)劃過(guò)程之間的相似性在于，構(gòu)造一組特殊類型泛函方程，稱為遞推關(guān)系，這些遞推關(guān)系使得我們能夠以簡(jiǎn)單的方式從 fk+1(sk+1)算出 fk(sk)，典型的指標(biāo)函數(shù)可以為“和”的形式或“積”的形式。 動(dòng)態(tài)規(guī)劃的基本概念 ?(5)狀態(tài)轉(zhuǎn)移方程 ?狀態(tài)轉(zhuǎn)移方程是確定過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程。 動(dòng)態(tài)規(guī)劃的基本概念 ? (2)狀態(tài) (State) ? 狀態(tài)表示某階段開(kāi)始所處的自然狀況（或條件），它既是本階段的起始位置，又是上一階段的終了位置，通常一個(gè)階段包含若干個(gè)狀態(tài)。有一些問(wèn)題表面上處來(lái)與時(shí)間無(wú)關(guān)，只要人為地引入“時(shí)間”因素，也可以變?yōu)橄聜€(gè)多階段決策問(wèn)題，用動(dòng)態(tài)規(guī)劃方法來(lái)處理。 2）當(dāng)變數(shù)的個(gè)數(shù)（維數(shù)）太大時(shí)，這類問(wèn)題雖可以用動(dòng)態(tài)規(guī)劃來(lái)描述，但由于計(jì)算機(jī)存貯容量和計(jì)算機(jī)速度的限制，使問(wèn)題無(wú)法解決，此即所謂“維數(shù)障礙”。 逐步法 ?下面介紹多目標(biāo)線性規(guī)劃中的 STEM步驟 : 求 Vmin F(X)=(f1(X), f2(X),…,f p(X))T X∈ R }0,|{,...,2,1,)(1????? ??XbAXXRpixcXfnjjiji設(shè) 逐步法 ? p個(gè)線性規(guī)劃的最優(yōu)解 min fi(X) = fi(X(i)) = fi* i=1,2,…,p X∈ R 令 fimax≡ max {fi(X(j)) } i=1,2,…,p 1≤j≤p 顯然 fimax≥fi* i=1,2,…,p 不妨設(shè)不完全取等號(hào)。) 1≤j≤p 1≤j≤p 評(píng)價(jià)函數(shù)的收斂性 ? 5. 乘除法 且 gj0, j=1,2,…,p 可證 U(G)為 G的嚴(yán)格單調(diào)增函數(shù)。 評(píng)價(jià)函數(shù)的收斂性 ?3. 理想點(diǎn)法 式中 fj≥fj*， j=1,2,…,p 為 F的嚴(yán)格單調(diào)增函數(shù)。)(11FUffFUpjjjpjjj ??? ?????? 評(píng)價(jià)函數(shù)的收斂性 ?2. 平方和加權(quán)法 U(F)為 F的嚴(yán)格單調(diào)增函數(shù)。(39。 若 X*不 ∈ Rpa*，即存在 Y∈ R，使 F(Y)≤F(X*) 由 U(F)的嚴(yán)格單調(diào)性，有 U(F(Y))U(F(X*)) 此與 X*是 min U(F(X))的最優(yōu)解矛盾?！?Ep, 當(dāng) F≤F39。 處理多目標(biāo)規(guī)劃的一些方法 ? 對(duì)于極小極大問(wèn)題，可以用增加一個(gè)變量 t及 p個(gè)約束的方法將其化為通常的數(shù)學(xué)規(guī)劃模型。 處理多目標(biāo)規(guī)劃的一些方法 ? 評(píng)價(jià)函數(shù)法 直接求解多目標(biāo)規(guī)劃問(wèn)題是比較困難的，有一類方法是通過(guò)構(gòu)造一個(gè)評(píng)價(jià)函數(shù)（或效用函數(shù)） U(F(X))將多目標(biāo)規(guī)劃問(wèn)題 (VP)轉(zhuǎn)化為單目標(biāo)規(guī)劃問(wèn)題 min U(F(X)) X∈ R 然后求解該問(wèn)題，并將其最優(yōu)解 X*作為 (VP)的最優(yōu)解。 2中，注意到，要使多目標(biāo)規(guī)劃（ VP）中所有子目標(biāo)同時(shí)實(shí)現(xiàn)最優(yōu)經(jīng)常是不可解的，那么如何制定比較標(biāo)準(zhǔn)在（弱）有效解集中找到滿意解呢？ 處理多目標(biāo)規(guī)劃的一些方法 ? 約束法（主要目標(biāo)法） 在目標(biāo)函數(shù) f1(X), f2(X),…,f p(X)中，選出其中的一個(gè)作為主要目標(biāo)，如 f1(X), 而其它的目標(biāo) f2(X),…,f p(X)只要滿足一定的條件即可。 多目標(biāo)規(guī)劃解的性質(zhì) ?一般來(lái)說(shuō)，即使（ VP）是凸多目標(biāo)規(guī)劃，像集 F(R)也不一定為凸集（見(jiàn)例 3）。 多目標(biāo)規(guī)劃解的概念 對(duì)于一般的多目標(biāo)規(guī)劃問(wèn)題： (VP) Vmin F(X)=(f1(X), f2(X),…,f p(X))T . gi(X)≤0, i=1,2,…,m 其中 X=(x1,x2,…,x n)T, p≥2 設(shè) R={X| gi(X)≤0, i=1,2,…,m} 定義 1 設(shè) X*∈ R，若對(duì)任意 j=1,2,…,p, 以及任意X∈ R均有 fj(X)≥fj(X*), j=1,2,…,p 則稱 X*為問(wèn)題 (VP)的 絕對(duì)最優(yōu)解 。 RxxFVRxxxxxfxxxf???????????????)(min],2,0[213210)(,42)( 221求設(shè) 多目標(biāo)規(guī)劃解的概念 ? 下面考察例 1中生產(chǎn)計(jì)劃問(wèn)題。決策者希望制定一個(gè)日生產(chǎn)方案，不僅能得到最大的利潤(rùn)，且能最大地滿足市場(chǎng)需求。第五章 多目標(biāo)規(guī)劃 ? 在實(shí)際問(wèn)題中，衡量一個(gè)設(shè)計(jì)方案的好壞往往不止一個(gè)。 生產(chǎn)計(jì)劃問(wèn)題 ? [問(wèn)題分析 ] 設(shè)每日生產(chǎn)甲、乙的數(shù)量分別為 x1, x2, 令 X=(x1, x2), 則其目標(biāo)函數(shù)為利潤(rùn) f1(X)=4x1 + 3x2 甲的產(chǎn)量 f2(X)=x1 都取最大值 滿足約束條件 x1 + x2≤400（原料供應(yīng)約束） 2x1 + x2≤500（加工時(shí)間約束） x1≥0， x2≥0 多目標(biāo)規(guī)劃問(wèn)題舉例 ?例 2投資問(wèn)題 ?假設(shè)在一段時(shí)間內(nèi)有 a（億元）的資金可用于建廠投資，若可供選擇的項(xiàng)目記為 1,2,…,m, 而且一旦對(duì)第 i個(gè)項(xiàng)目投資，則必須用掉 ai（億元） 。問(wèn)：是否能找到一個(gè)可行解 X*=(x1*, x2*)T使之同時(shí)為 f1(X)與 f2(X)的最大解？ ? 在可行域內(nèi)容易求解 max f1(X)的唯一最優(yōu)解為 (100, 300), 見(jiàn)圖中 B點(diǎn)。最優(yōu)解的全體記為 Rab* 多目標(biāo)規(guī)劃解的概念 對(duì)于無(wú)絕對(duì)最優(yōu)解的情況，引進(jìn)下面的偏好關(guān)系 ： 設(shè) F1=(f11, f21, …,f p1)T, F2=(f12, f22, …,f p2)T (1)F1F2意味著 F1每個(gè)分量都嚴(yán)格小于 F2的相應(yīng)分量，即 fj1fj2, j=1,2,…,p (2)F1≤F2等價(jià)于 fj1≤fj2, j