【正文】 17 17 11 3 20 18 167。 多階段決策問題及實例 ?例 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 多階段決策問題及實例 ? 例 2 多階段資源分配問題 ? 某工廠生產(chǎn) A, B和 C三種產(chǎn)品，都要使用某種原材料，原材料共有 4噸。在多階段決策問題中，既然引入了階段的概念，也就與時間密不可分，決策過程從一個狀態(tài)到另一個狀態(tài)，隨著時間的變化在變化，也就有了“動態(tài)”的含義。 多階段決策問題及實例 ? 各個階段的決策確定以后就構成一個決策序列，稱為一個策略。 1多階段決策問題及實例 ? 所謂多階段決策問題，是指一類活動過程，它可以分為互相聯(lián)系的若干個階段，在每一階段都需要作出決策，從而使整個過程達到最優(yōu)的活動效果。 動態(tài)規(guī)劃 ? 動態(tài)規(guī)劃根據(jù)多階段決策過程的時間參量是離散的還是連續(xù)的和其決策過程的演變是確定性的還是隨機的，可以分為離散確定性、離散隨機性、連續(xù)確定性、連續(xù)隨機性四種決策過程模型。然而動態(tài)規(guī)劃目前還存在以下弱點： 1）動態(tài)規(guī)劃沒有一個統(tǒng)一的算法，它必須針對各種問題的性質，利用最優(yōu)性原理得出函數(shù)方程后，再結合其它數(shù)學技巧來求解，而沒有一種統(tǒng)一的處理方法，從而我們稱動態(tài)規(guī)劃是一種方法。 動態(tài)規(guī)劃 ? 動態(tài)規(guī)劃把比較復雜的問題劃分成若干階段，通過逐段求解，最終求得全局最優(yōu)解。 第六章 動態(tài)規(guī)劃 ? 動態(tài)規(guī)劃（ Dynamic Programming）是最優(yōu)化的一個分支。 逐步法 ? λ，分析者只好根據(jù)函數(shù) fi(X)和 R的性質給出一種算法： ??????????????????????0)(10)(1,...,2,1*12*max**12max*max12121injijiiiinjijiiiipjjiifcffffcfffpi當當其中令???? 逐步法 ?3. 求線性規(guī)劃 的最優(yōu)解 (X(0), t(0)) ?????????RXpitfXftP iii ,...,2,1))((min)( *0 ? 逐步法 ? 4. 決策者對 F(X(0))與 F*=(f1*,…,f p*)T進行比較，若對 X(0)比較滿意，則迭代停止；否則，對最滿意的fj0(X(0))提出允許變大的上限 Δfj0, 而對其它 fi(X)(i≠j0)則不允許變大，因此把 (P0)改成求 的最優(yōu)解 (X(1), t(1))。)(11GUggGU jpjjpj??????? 評價函數(shù)的收斂性 ?由上述討論知：由方法 1(λj0),2,3,5求得的最優(yōu)解 X*∈ Rpa* ?而由方法 1(λj≥0)， 4得到的最優(yōu)解 X*∈ Rwp* 逐步法 （交替式對話方法） ? 由于問題的復雜性，有時決策者所提供的信息不足以使分析者確定各目標函數(shù)之間的關系，因此需要在決策者和分析者之間建立一種交互式的對話方法（如 Step Method, STEM, 逐步法），分析者根據(jù)決策者提供的信息（經(jīng)修改和補充后的）給出中間結果，決策者對中間結果發(fā)表意見，可根據(jù)中間結果進一步提供信息，讓分析者重新計算，直到求得滿意解為止。 則有 )39。0及 gj≤gj39。 jpjjjjpkkgGUFUpjkfkjfgfffffFU1121)()(111......)(????????????????化為則評價函數(shù)當當令 評價函數(shù)的收斂性 ?這是因為，若 G≤G39。=U(F39。 于是，若記 λj0fj0= max λjfj 1≤j≤p 則 U(F)=max λjfj =λj0fj0λj0fj039。這里 λj0， j=1,2,…,p. 這是因為，若 FF39。 可以仿照 2的證法類似證明。) 即 U(F)為 F的嚴格單調增函數(shù)。fj0 從而 λj0fj0λj0fj039?！軫0，故 0≤fjfj0≤fj39。 pjffffFUjjjpjjjpjjj,...,2,1,0,1)()(01201?????????????這里 評價函數(shù)的收斂性 ? 這是因為，若 F≤F39。(39。 從而 λj0fj0λj0fj039。 j=1,2,…,p 由 F≤F39。)(11FUffFUpjjjpjjj ??? ?????? 評價函數(shù)的收斂性 特別當 λj0， j=1,2,…,p 時，對 F≤F39。 相加得 ???pjjj fFU1)( ? )39。則 λjfj≤λjfj39。 特別當 λj0， j=1,2,…,p 時， U(F)為嚴格單調增函數(shù)。 X∈ R 評價函數(shù)的收斂性 ?類似地可證得下面的定理。 評價函數(shù)的收斂性 ? 定理 8 若對 F∈ Ep， U(F)是嚴格單調增函數(shù)，則單目標問題 min U(F(X)) X∈ R 的最優(yōu)解 X*∈ Rpa* ? [證明 ]用反證法。時，都有 U(F)U(F39。 ?定義 8 若對任意 F, F39。時，都有 U(F)U(F39。 而 X*是否為 (VP)的有效解或弱有效解呢？ 評價函數(shù)的收斂性 ?定義 7 若對任意 F, F39。設 (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)解。 1≤j≤p ????????RXpjtXftQ jjt ,...,2,1,)(min)( ? 處理多目標規(guī)劃的一些方法 ? [證明 ]設 (X*， t*）為 (Qt)的最優(yōu)解，則對 (Qt)的任意可行解 (X, t)有 λjfj(X*)≤t*≤t, (j=1,2,…,p) ，由此 max λjfj(X*)≤t*≤t 1≤j≤p 若取 X∈ R， t = max λjfj(X), 易見 (X, t)也是 (Qt)的 1≤j≤p 可行解，將此 t代入上式右端，得 max λjfj(X*)≤max λjfj(X) 對任意 X∈ R 1≤j≤p 1≤j≤p 即 X*為 (Q)的最優(yōu)解。有下面等價的定理。 212122 ]*))(([)(min ?????jjjRX fXfXL 處理多目標規(guī)劃的一些方法 ? 4. 極小極大法（協(xié)調矛盾法） 在對策論中，常常在作決策時要考慮：“在最不利情況下找出一個最有利”的策略，即所謂“ minmax”，依此，令評價函數(shù) U(F(X))=max fj(X) 1≤j≤p 然后求 min U(F(X))的最優(yōu)解，設為 X* X∈ R 評價函數(shù)也可以采用賦權的形式，即令 (Q) min U(F(X))= min {max λjfj(X)} X∈ R X∈ R 1≤j≤p 其中 λj≥0(j=1,2,…,p) 是一組權系數(shù)。 pjfXfXFUjpjjpjpjjj,...,2,1,0,1,...,))(())((11201??????????????數(shù)它們滿足為事先給定的一組權系其中 處理多目標規(guī)劃的一些方法 ? 3. 理想點法（虛擬點法） 先求 p 個單目標規(guī)劃問題的最優(yōu)解，記 fj*=fj(X(j))=min fj(X) j=1,2,…,p X∈ R 若所有 X(j)( j=1,2,…,p) 都相同，設為 X*，則X*為多目標函數(shù)的絕對最優(yōu)解，但一般不易達到，因此向量 F*=(f1*,f2*,…,f p*) 只是一個理想點。 ???pjjj XfXFU1)())(( ? 處理多目標規(guī)劃的一些方法 ?問題的難點是如何確定合理的權系數(shù)。 由于構造評價函數(shù)的多種多樣，也就出現(xiàn)了多種不同的評價函數(shù)方法。 綜合 (1)(2), 定理得證。 假設 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)相矛盾。進一步有下列定理。 處理多目標規(guī)劃的一些方法 ?如 fj(X)≤fj0, j=2,…,p ， ??????????????pjfXfmiXgXfmiXgXRXffjjiijRXj,...,2,)(,...,2,1,0)()(min:},...,2,1,0)(|{)(min010單目標規(guī)劃問題劃問題化為下面的于是可以把原來的多規(guī)這里 處理多目標規(guī)劃的一些方法 ? 分層序列法 把（ VP）中的 p個目標 f1(X), f2(X),…,f p(X)按其重要性排一個次序；分為最重要目標、次要目標等等。 3處理多目標規(guī)劃的一些方法 ?在167。 ** wppa EE ? 多目標規(guī)劃解的性質 ? 定理 4 在像集 F(R)上，若 Epa*已知，則在約束集合 R上，有 ? 定理 5 在像集 F(R)上，若 Ewp*已知，則在約束集合 R上，有 ? 另外通過對像集的研究，可以更直觀地認識問題，并且可以提供一些處理多目標規(guī)劃的方法。 ? 定義 5 設 F*∈ F(R)，若不存在 F∈ F(R)，滿足 F≤F* 則稱 F*為像集 F(R)的 有效點 ，有效點的全體記為 Epa*. ? 定義 6 設 F*∈ F(R)，若不存在 F∈ F(R)，滿足