【文章內(nèi)容簡介】 .,2,1,0,1)()(01201?????????????這里 評價(jià)函數(shù)的收斂性 ? 這是因?yàn)?，?F≤F39。，由于 F≥F0， F39?！軫0，故 0≤fjfj0≤fj39。fj0 j=1,2,…,p 且至少存在某個(gè) j0(1≤j0≤p)，有 fjfj0fj39。fj0 從而 λj0fj0λj0fj039。 故 U(F)U(F39。) 即 U(F)為 F的嚴(yán)格單調(diào)增函數(shù)。 評價(jià)函數(shù)的收斂性 ?3. 理想點(diǎn)法 式中 fj≥fj*， j=1,2,…,p 為 F的嚴(yán)格單調(diào)增函數(shù)。 可以仿照 2的證法類似證明。 1,]*)([)(11??? ??qffFU qpjqjj 評價(jià)函數(shù)的收斂性 ? 4. 極小極大法 U(F)=max λjfj 1≤j≤p 為 F的單調(diào)增函數(shù)。這里 λj0， j=1,2,…,p. 這是因?yàn)?，?FF39。，則對 j=1,2,…,p, 均有 fjfj39。 于是，若記 λj0fj0= max λjfj 1≤j≤p 則 U(F)=max λjfj =λj0fj0λj0fj039?！躮ax λjfj 39。=U(F39。) 1≤j≤p 1≤j≤p 評價(jià)函數(shù)的收斂性 ? 5. 乘除法 且 gj0, j=1,2,…,p 可證 U(G)為 G的嚴(yán)格單調(diào)增函數(shù)。 jpjjjjpkkgGUFUpjkfkjfgfffffFU1121)()(111......)(????????????????化為則評價(jià)函數(shù)當(dāng)當(dāng)令 評價(jià)函數(shù)的收斂性 ?這是因?yàn)椋?G≤G39。，則由 G0, G39。0及 gj≤gj39。 j=1,2,…,p 且至少存在某個(gè) j0(1≤j0≤p)使 gj0gj039。 則有 )39。(39。)(11GUggGU jpjjpj??????? 評價(jià)函數(shù)的收斂性 ?由上述討論知：由方法 1(λj0),2,3,5求得的最優(yōu)解 X*∈ Rpa* ?而由方法 1(λj≥0)， 4得到的最優(yōu)解 X*∈ Rwp* 逐步法 （交替式對話方法） ? 由于問題的復(fù)雜性，有時(shí)決策者所提供的信息不足以使分析者確定各目標(biāo)函數(shù)之間的關(guān)系，因此需要在決策者和分析者之間建立一種交互式的對話方法（如 Step Method, STEM, 逐步法），分析者根據(jù)決策者提供的信息（經(jīng)修改和補(bǔ)充后的）給出中間結(jié)果，決策者對中間結(jié)果發(fā)表意見，可根據(jù)中間結(jié)果進(jìn)一步提供信息，讓分析者重新計(jì)算，直到求得滿意解為止。 逐步法 ?下面介紹多目標(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è)不完全取等號。 逐步法 ? λ，分析者只好根據(jù)函數(shù) fi(X)和 R的性質(zhì)給出一種算法： ??????????????????????0)(10)(1,...,2,1*12*max**12max*max12121injijiiiinjijiiiipjjiifcffffcfffpi當(dāng)當(dāng)其中令???? 逐步法 ?3. 求線性規(guī)劃 的最優(yōu)解 (X(0), t(0)) ?????????RXpitfXftP iii ,...,2,1))((min)( *0 ? 逐步法 ? 4. 決策者對 F(X(0))與 F*=(f1*,…,f p*)T進(jìn)行比較，若對 X(0)比較滿意，則迭代停止；否則，對最滿意的fj0(X(0))提出允許變大的上限 Δfj0, 而對其它 fi(X)(i≠j0)則不允許變大，因此把 (P0)改成求 的最優(yōu)解 (X(1), t(1))。 ????????????????????RXjipiXfXffXfXfjipitfXftPiijjjiii0)0(0)0(000*1,...,2,1)()()()(,...,2,1))((min)(? 逐步法 ?若對 X(1)仍不滿意，則可用這種思想在(P1)中添加新的約束，或修改 Δfj的值，再求新的解，這種交互式對話進(jìn)行若干次，直到?jīng)Q策者滿意為止。 第六章 動態(tài)規(guī)劃 ? 動態(tài)規(guī)劃（ Dynamic Programming）是最優(yōu)化的一個(gè)分支。 1951年美國數(shù)學(xué)家 （貝爾曼）等人根據(jù)一類多階段決策問題的特性，提出了解決這類問題的“最優(yōu)性原理”，并研究了許多實(shí)際問題，從而建立了最優(yōu)化的一個(gè)分支 ——動態(tài)規(guī)劃。 動態(tài)規(guī)劃 ? 動態(tài)規(guī)劃把比較復(fù)雜的問題劃分成若干階段，通過逐段求解，最終求得全局最優(yōu)解。特別對于離散性問題，由于解析數(shù)學(xué)無法運(yùn)用，動態(tài)規(guī)劃就成為非常有效的工具。然而動態(tài)規(guī)劃目前還存在以下弱點(diǎn)： 1）動態(tài)規(guī)劃沒有一個(gè)統(tǒng)一的算法，它必須針對各種問題的性質(zhì)，利用最優(yōu)性原理得出函數(shù)方程后，再結(jié)合其它數(shù)學(xué)技巧來求解，而沒有一種統(tǒng)一的處理方法，從而我們稱動態(tài)規(guī)劃是一種方法。 2）當(dāng)變數(shù)的個(gè)數(shù)（維數(shù)）太大時(shí)，這類問題雖可以用動態(tài)規(guī)劃來描述，但由于計(jì)算機(jī)存貯容量和計(jì)算機(jī)速度的限制，使問題無法解決，此即所謂“維數(shù)障礙”。 動態(tài)規(guī)劃 ? 動態(tài)規(guī)劃根據(jù)多階段決策過程的時(shí)間參量是離散的還是連續(xù)的和其決策過程的演變是確定性的還是隨機(jī)的，可以分為離散確定性、離散隨機(jī)性、連續(xù)確定性、連續(xù)隨機(jī)性四種決策過程模型。 167。 1多階段決策問題及實(shí)例 ? 所謂多階段決策問題，是指一類活動過程，它可以分為互相聯(lián)系的若干個(gè)階段，在每一階段都需要作出決策，從而使整個(gè)過程達(dá)到最優(yōu)的活動效果。因此，各個(gè)階段決策的選取常依賴于當(dāng)前面臨的狀態(tài)，又影響下一個(gè)階段的決策，從而影響整個(gè)過程的活動路線，這種把一個(gè)問題看成一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為 多階段決策過程 ，也稱 序貫決策過程 。 多階段決策問題及實(shí)例 ? 各個(gè)階段的決策確定以后就構(gòu)成一個(gè)決策序列，稱為一個(gè)策略。由于每一個(gè)階段可供選擇的決策不止一個(gè)，因而對應(yīng)于整個(gè)活動過程就有許多策略選擇采用，從中選出一個(gè)效果最好的為最優(yōu)策略。在多階段決策問題中，既然引入了階段的概念，也就與時(shí)間密不可分，決策過程從一個(gè)狀態(tài)到另一個(gè)狀態(tài)，隨著時(shí)間的變化在變化，也就有了“動態(tài)”的含義。有一些問題表面上處來與時(shí)間無關(guān)，只要人為地引入“時(shí)間”因素，也可以變?yōu)橄聜€(gè)多階段決策問題，用動態(tài)規(guī)劃方法來處理。 多階段決策問題及實(shí)例 ?例 1 最短路線問題 A B1 B2 C1 C2 C3 C4 D1 E1 F1 G D2 D3 E2 E3 F2 5 3 1 3 6 8 7 6 6 8 3 5 3 3 8 4 2 2 1 2 3 3 3 5 5 2 6 6 4 3 4 3 7 5 9 7 6 8 13 10 9 12 13 16 18 多階段決策問題及實(shí)例 ? 例 2 多階段資源分配問題 ? 某工廠生產(chǎn) A, B和 C三種產(chǎn)品，都要使用某種原材料，原材料共有 4噸。將不同數(shù)量的這種原料分配給各種產(chǎn)品時(shí)產(chǎn)生收益如下表（單位：萬元），試確定使總收益最大的分配法。 原料的分配量 產(chǎn)品種類 （噸） A B C 0 0 0 0 1 10 6 8 2 17 17 11 3 20 18 167。 2動態(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)公式的形式。 解法二稱為逆推解法（逆序解法） 最短路線問題的解 ?上面的做法極其簡單，從中我們可以處到這樣一個(gè)規(guī)律，即最短路線必須且只能由最短子路線組成，在求 A到 G的最短路線時(shí)，附帶求得了從所有中間頂點(diǎn)到 G的最短路，它們是作為整個(gè)問題的子問題出現(xiàn)的，并且被嵌入較大問題之中，這常常是動態(tài)規(guī)劃方法的一個(gè)特點(diǎn)。 二、動態(tài)規(guī)劃的基本概念 ?(1)階段 (Stage) ? 對所給問題的過程，根據(jù)時(shí)間和空間的自然特征，恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)相互聯(lián)系的階段，以便能按一定的次序去求解。描述階段的變量稱為階段變量，用 k表示。 動態(tài)規(guī)劃的基本概念 ? (2)狀態(tài) (State) ? 狀態(tài)表示某階段開始所處的自然狀況（或條件），它既是本階段的起始位置，又是上一階段的終了位置，通常一個(gè)階段包含若干個(gè)狀態(tài)。描述狀態(tài)的變量稱為狀態(tài)變量，用 sk表示第 k個(gè)階段的狀態(tài)變量，用 Sk表示所有可能狀態(tài)的集合。 ? 狀態(tài)的選擇不是任意的，必須具有下列性質(zhì)：若某階段狀態(tài)給定后，則在這階段以后過程的發(fā)展不受這以前各階段狀態(tài)的影響，這個(gè)性質(zhì)稱為 無后效性 （即馬爾科夫性）。 動態(tài)規(guī)劃的基本概念 ? (3)決策 (Decision) ? 決策表示當(dāng)過程處于某一階段的某個(gè)狀態(tài)時(shí)，可以作出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策。在最優(yōu)控制中也稱為控制。描述決策的變量稱為決策變量，常用 uk(sk)表示第 k個(gè)階段當(dāng)狀態(tài)處于 sk時(shí)的決策變量，它是狀態(tài)變量的函數(shù)。決策變量的取值范圍稱為允許決策集合，常用 Dk(sk)表示第 k階段從狀態(tài) sk出發(fā)的允許決策集合，有 uk(sk)∈ Dk(sk)。 動態(tài)規(guī)劃的基本概念 ?(4)策略 (Policy) ?策略是一個(gè)按順序排列的決策序列，用 pk,n(sk)={uk(sk), u