【正文】 j=1,2,…,p X∈ R 處理多目標規(guī)劃的一些方法 ? 構(gòu)造評價函數(shù) ? 然后求 min U(F(X)) X∈ R 求得最優(yōu)解 X*作為多目標規(guī)劃的解。 處理多目標規(guī)劃的一些方法 ?Cа л у к в а л з е （ 1975）提出的理想點，其中心思想是定義一個模，在這個模的意義下，找一個點盡量接近理想點 F*，即求 ?min U(F(X))= min ||F(X)F*|| X∈ R X∈ R 處理多目標規(guī)劃的一些方法 ? 一般定義 |*)(|max)(*))(()(1]*))(([)(,2,),1[)(]*))(([||*)(||1112112211jjpjpjjjpjjjqqpjqjjfXfXLqfXfXLqfXfXLqqXLfXfFXF????????????????????????時當時當點之間的距離的模即為歐氏空間中兩上述定義時當取區(qū)間的取值一般在 處理多目標規(guī)劃的一些方法 ? 例 4 設 f1(X)=3x12x2, f2(X)= 4x13x2, 約束集R={X|2x1+3x2≤18, 2x1+x2≤10, x1 ≥0, x2 ≥0} 試用理想點法求解 Vmin F(X)=(f1(X), f2(X))T X∈ R [解 ]先分別對單目標求出最優(yōu)解 X(1)=(0, 6)T, X(2)=(3, 4)T, 對應的目標函數(shù)值為 f1(X(1))=f1*= 12, f2(X(2))=f2*= 24, 故理想點為 F*=(f1*, f2*)T = (12, 24)T 處理多目標規(guī)劃的一些方法 ?取 q=2, 此時要求 ?可解得最優(yōu)解 X*=(, )T, 對應的目標函數(shù)值分別為 f1*= , f2*= , 其解空間、像空間如圖。 處理多目標規(guī)劃的一些方法 ? 對于極小極大問題，可以用增加一個變量 t及 p個約束的方法將其化為通常的數(shù)學規(guī)劃模型。 ? 定理 7 設（ X*， t*）為 的最優(yōu)解，則 X*必為 (Q)的最優(yōu)解；反之，設 X*為 (Q)的最優(yōu)解，令 t*= max λjfj(X*)，則 (X*， t*）必為 (Qt)的最優(yōu)解。 處理多目標規(guī)劃的一些方法 ? 反之，設 X*為 (Q)的最優(yōu)解，最小值為 max λjfj(X*)≡ t* 1≤j≤p 易見 (X*, t*)是 (Qt)的可行解。 處理多目標規(guī)劃的一些方法 ? 5. 乘除法（幾何平均法） ? 在 (VP)中，設各目標函數(shù)值均有 ? fj(X)0, j=1,2,…,p ? 不妨設其中 k個 f1(X), f2(X),…,f k(X)要求實現(xiàn)最小，其余 fk+1(X), …,f p(X)要求實現(xiàn)最大，則可構(gòu)造評價函數(shù) ? 然后求 min U(F(X)) ? X∈ R )()...()()...()())((121XfXfXfXfXfXFUpkk?? 評價函數(shù)的收斂性 ?上節(jié)中，用不同的評價函數(shù) U(F(X))將多目標規(guī)劃 (VP)轉(zhuǎn)化為單目標問題 min U(F(X)) X∈ R 來處理，并將其解 X*作為 (VP)的解?！?Ep, 當 F≤F39。) 成立，則稱 U(F)是 F的 嚴格單調(diào)增函數(shù) 。∈ Ep, 當 FF39。) 成立，則稱 U(F)是 F的 單調(diào)增函數(shù) 。 若 X*不 ∈ Rpa*，即存在 Y∈ R，使 F(Y)≤F(X*) 由 U(F)的嚴格單調(diào)性，有 U(F(Y))U(F(X*)) 此與 X*是 min U(F(X))的最優(yōu)解矛盾。 ?定理 9 若對 F∈ Ep， U(F)是單調(diào)增函數(shù)，則單目標問題 ? min U(F(X)) ? X∈ R ?的最優(yōu)解 X*∈ Rwp* 評價函數(shù)的收斂性 ?針對 ，由分析知均為嚴格單調(diào)函數(shù)或單調(diào)函數(shù)，從而由定理 8和定理 9知，求得的 X*∈ Rpa*或 X*∈ Rwp* 評價函數(shù)的收斂性 ? 1. 線性加權和法 λj≥0， j=1,2,…,p, 且 ∑ λj=1，此時 U(F)為單調(diào)增函數(shù)。 這是因為，若 λj≥0， j=1,2,…,p, 且 FF39。 j=1,2,…,p 又由 ∑ λj=1可知，至少存在某個 j0(1≤j0≤p)，使 λj00，于是 λj0fj0λj0fj039。(39。則 λjfj≤λjfj39。 則 至少存在某個 j0(1≤j0≤p)，使 fj0fj039。 相加得 )39。)(11FUffFUpjjjpjjj ??? ?????? 評價函數(shù)的收斂性 ?2. 平方和加權法 U(F)為 F的嚴格單調(diào)增函數(shù)。由于 F≥F0， F39。fj0 j=1,2,…,p 且至少存在某個 j0(1≤j0≤p)，有 fjfj0fj39。 故 U(F)U(F39。 評價函數(shù)的收斂性 ?3. 理想點法 式中 fj≥fj*， j=1,2,…,p 為 F的嚴格單調(diào)增函數(shù)。 1,]*)([)(11??? ??qffFU qpjqjj 評價函數(shù)的收斂性 ? 4. 極小極大法 U(F)=max λjfj 1≤j≤p 為 F的單調(diào)增函數(shù)。則對 j=1,2,…,p, 均有 fjfj39。≤max λjfj 39。) 1≤j≤p 1≤j≤p 評價函數(shù)的收斂性 ? 5. 乘除法 且 gj0, j=1,2,…,p 可證 U(G)為 G的嚴格單調(diào)增函數(shù)。則由 G0, G39。 j=1,2,…,p 且至少存在某個 j0(1≤j0≤p)使 gj0gj039。(39。 逐步法 ?下面介紹多目標線性規(guī)劃中的 STEM步驟 : 求 Vmin F(X)=(f1(X), f2(X),…,f p(X))T X∈ R }0,|{,...,2,1,)(1????? ??XbAXXRpixcXfnjjiji設 逐步法 ? p個線性規(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 不妨設不完全取等號。 ????????????????????RXjipiXfXffXfXfjipitfXftPiijjjiii0)0(0)0(000*1,...,2,1)()()()(,...,2,1))((min)(? 逐步法 ?若對 X(1)仍不滿意，則可用這種思想在(P1)中添加新的約束，或修改 Δfj的值，再求新的解，這種交互式對話進行若干次，直到?jīng)Q策者滿意為止。 1951年美國數(shù)學家 （貝爾曼）等人根據(jù)一類多階段決策問題的特性，提出了解決這類問題的“最優(yōu)性原理”，并研究了許多實際問題，從而建立了最優(yōu)化的一個分支 ——動態(tài)規(guī)劃。特別對于離散性問題，由于解析數(shù)學無法運用，動態(tài)規(guī)劃就成為非常有效的工具。 2）當變數(shù)的個數(shù)（維數(shù)）太大時，這類問題雖可以用動態(tài)規(guī)劃來描述，但由于計算機存貯容量和計算機速度的限制，使問題無法解決，此即所謂“維數(shù)障礙”。 167。因此，各個階段決策的選取常依賴于當前面臨的狀態(tài)，又影響下一個階段的決策，從而影響整個過程的活動路線，這種把一個問題看成一個前后關聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為 多階段決策過程 ，也稱 序貫決策過程 。由于每一個階段可供選擇的決策不止一個，因而對應于整個活動過程就有許多策略選擇采用，從中選出一個效果最好的為最優(yōu)策略。有一些問題表面上處來與時間無關，只要人為地引入“時間”因素，也可以變?yōu)橄聜€多階段決策問題，用動態(tài)規(guī)劃方法來處理。將不同數(shù)量的這種原料分配給各種產(chǎn)品時產(chǎn)生收益如下表（單位：萬元），試確定使總收益最大的分配法。 2動態(tài)規(guī)劃的基本概念 ?一、最短路線問題的解 首先討論最短路線問題的求解方法 [解法一 ]枚舉法 48條不同路線 48 6=288步加法 47次路線長度的比較 最短路長為 18 最短路線問題的解 ? [解法二 ]共有 6個階段 記 f1(A) ——A到 G的最短距離 則 f1(A)依賴于 f2(B1), f2(B2), ……… 而 f6(F1)=4, f6(F2)=3 故由后向前寫出相應公式的形式。 二、動態(tài)規(guī)劃的基本概念 ?(1)階段 (Stage) ? 對所給問題的過程，根據(jù)時間和空間的自然特征，恰當?shù)貏澐譃槿舾蓚€相互聯(lián)系的階段，以便能按一定的次序去求解。 動態(tài)規(guī)劃的基本概念 ? (2)狀態(tài) (State) ? 狀態(tài)表示某階段開始所處的自然狀況（或條件），它既是本階段的起始位置，又是上一階段的終了位置，通常一個階段包含若干個狀態(tài)。 ? 狀態(tài)的選擇不是任意的，必須具有下列性質(zhì)：若某階段狀態(tài)給定后，則在這階段以后過程的發(fā)展不受這以前各階段狀態(tài)的影響，這個性質(zhì)稱為 無后效性 （即馬爾科夫性）。在最優(yōu)控制中也稱為控制。決策變量的取值范圍稱為允許決策集合，常用 Dk(sk)表示第 k階段從狀態(tài) sk出發(fā)的允許決策集合，有 uk(sk)∈ Dk(sk)。 動態(tài)規(guī)劃的基本概念 ?(5)狀態(tài)轉(zhuǎn)移方程 ?狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。 動態(tài)規(guī)劃的基本概念 ? (6)指標函數(shù)和最優(yōu)值函數(shù) 指標函數(shù)是用以衡量多階段決策過程實現(xiàn)效果的一種數(shù)量指標，用 Vk, n表示，即 Vk, n=Vk, n(sk, uk, sk+1,…s n+1)， k=1,2,…,n 指標函數(shù)應具有可分離性，并滿足遞推關系 Vk, n(sk, uk, sk+1,…s n+1)=φk(sk, uk,Vk+1, n(sk+1,…s n+1)) ? 指標函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)，記為 fk(sk)，即 fk(sk)=OptimizationVk, n(sk, uk, sk+1,…s n+1) {uk, …, u n} 167。 動態(tài)規(guī)劃的最優(yōu)性原理 ： 一個（整個過程的）最優(yōu)策略所具有的性質(zhì)是，不論過去的狀態(tài)和決策如何，其余下的諸決策必構(gòu)成一個最優(yōu)子策略。在求解時，各狀態(tài)前面的狀態(tài)和決策對其后面的子問題來說，只不過相當于其初始條件而已，并不影響后面過程的最優(yōu)策略。 二、泛函方程 ?在最短路的計算中，若記 fk(sk)表示第 k階段處于狀態(tài) sk時到終點的最短距離， dk(sk, uk(sk)表示從狀態(tài) sk到由決策 uk(sk)所決定的狀態(tài) sk+1之間的距離，則有下列遞推關系式 fn+1(sn+1)=0 fk(sk)=min{dk(sk, uk(sk)) + fk+1(sk+1)} k=n,n1,…,2,1 uk∈ Dk(sk)