【正文】 如果 ，則可證明 {xi*, yi*}為原問題的最優(yōu)解；如果 ，可調(diào)整 λ的值 (利用插值法逐漸確定 λ)，直到滿足 為止。 第二年將資源數(shù)量 s2中的 u2和 s2u2分別投入生產(chǎn) A和 B，又得到收入為 g(u2)+h(s2u2)，如此繼續(xù)進(jìn)行 n年，問如何決定每年投入 A生產(chǎn)的資源量，才能使總的收入最大？ 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 此問題等價于下列規(guī)劃問題： max Z=g(u1)+h(s1u1)+g(u2)+h(s2u2)+…+ g(u n) + h(snun) s2=au1+b(s1u1) s3=au2+b(s2u2) ……………… sn=aun1+b(sn1un1) 0≤ui≤si, i=1,2,…,n 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 下面用動態(tài)規(guī)劃的方法來處理。反復(fù)迭代，可逐次求得 {uk(i)}和{fk(i)}，若對某一 k， uk(i)=uk1(i)對所有 i成立，則稱策略收斂，此時 {uk(i)}就是最優(yōu)策略，其相應(yīng)的 {fk(i)}為最優(yōu)值。 函數(shù)空間與策略空間迭代法 ?定義 f(i)為由 i點(diǎn)出發(fā)至終點(diǎn) N的最短距離，則由最優(yōu)性原理可得 f(i) = min(Cij + f(j)), i=1,2,…,N 1 f(N)=0 ?這樣的泛函方程不是遞推方程，而且f(i)出現(xiàn)在方程的兩邊，不能通過簡單的遞推求得結(jié)果。決策變量的取值范圍稱為允許決策集合，常用 Dk(sk)表示第 k階段從狀態(tài) sk出發(fā)的允許決策集合，有 uk(sk)∈ Dk(sk)。由于每一個階段可供選擇的決策不止一個，因而對應(yīng)于整個活動過程就有許多策略選擇采用，從中選出一個效果最好的為最優(yōu)策略。(39。 故 U(F)U(F39。 j=1,2,…,p 又由 ∑ λj=1可知，至少存在某個 j0(1≤j0≤p)，使 λj00，于是 λj0fj0λj0fj039。 處理多目標(biāo)規(guī)劃的一些方法 ? 5. 乘除法（幾何平均法） ? 在 (VP)中，設(shè)各目標(biāo)函數(shù)值均有 ? fj(X)0, j=1,2,…,p ? 不妨設(shè)其中 k個 f1(X), f2(X),…,f k(X)要求實(shí)現(xiàn)最小，其余 fk+1(X), …,f p(X)要求實(shí)現(xiàn)最大，則可構(gòu)造評價函數(shù) ? 然后求 min U(F(X)) ? X∈ R )()...()()...()())((121XfXfXfXfXfXFUpkk?? 評價函數(shù)的收斂性 ?上節(jié)中，用不同的評價函數(shù) U(F(X))將多目標(biāo)規(guī)劃 (VP)轉(zhuǎn)化為單目標(biāo)問題 min U(F(X)) X∈ R 來處理，并將其解 X*作為 (VP)的解。 X∈ R 處理多目標(biāo)規(guī)劃的一些方法 ? (2)若 fj(Y)= fj(X*), j=1,2,…,j 01 但 fj0(Y)fj0(X*) 2≤j0≤p 此時必有 fj(Y)= fj(X*)≤fj*, j=1,2,…,j 01 因此， Y是問題 (Pj0) min fp(X) X∈ Rj02∩{X |fj01(X)≤fj01*} 的可行解，又由 fj0(Y)fj0(X*)≤fj0* 此與 fj0*是問題 (Pj0)的最優(yōu)值相矛盾。 ?一般來說，即使（ VP）為凸多目標(biāo)數(shù)學(xué)規(guī)劃， Rwp*和 Rpa*也不一定為凸集。 2 多目標(biāo)規(guī)劃解的概念與性質(zhì) ? 1. 多目標(biāo)規(guī)劃解的概念 ? 例 3 ? [解 ]分別對單個目標(biāo)求出其最優(yōu)解，對于第一個目標(biāo)的最優(yōu)解 x(1)=1。這類問題即為多目標(biāo)數(shù)學(xué)規(guī)劃問題。 由此可得共同的最優(yōu)解 X*并不存在。 ? 定義 5 設(shè) F*∈ F(R)，若不存在 F∈ F(R)，滿足 F≤F* 則稱 F*為像集 F(R)的 有效點(diǎn) ，有效點(diǎn)的全體記為 Epa*. ? 定義 6 設(shè) F*∈ F(R)，若不存在 F∈ F(R)，滿足 FF* 則稱 F*為像集 F(R)的 弱有效點(diǎn) ，弱有效點(diǎn)的全體記為 Ewp*. 多目標(biāo)規(guī)劃解的性質(zhì) ?類似地可證明：像集 F(R)的有效點(diǎn)一定是弱有效點(diǎn)，即 ?通過在像集 F(R)上尋找有效點(diǎn)（或弱有效點(diǎn)），就可以確定約束集合 R上的有效解（或弱有效解）。 ???pjjj XfXFU1)())(( ? 處理多目標(biāo)規(guī)劃的一些方法 ?問題的難點(diǎn)是如何確定合理的權(quán)系數(shù)。 ?定義 8 若對任意 F, F39。 j=1,2,…,p 由 F≤F39。這里 λj0， j=1,2,…,p. 這是因?yàn)?，?FF39。 第六章 動態(tài)規(guī)劃 ? 動態(tài)規(guī)劃（ Dynamic Programming）是最優(yōu)化的一個分支。 原料的分配量 產(chǎn)品種類 （噸） A B C 0 0 0 0 1 10 6 8 2 17 17 11 3 20 18 167。 3最優(yōu)性原理和泛函方程 ? 一、動態(tài)規(guī)劃的最優(yōu)性原理 20世紀(jì) 50年代， 類多階段決策問題，提出了最優(yōu)性原理。 fk(i) = min(Cij + fk1(j)), i=1,2,…,N 1 j fk(N)=0 3176。 先選取一不構(gòu)成回路的初始策略 {u1(i)}： u1(1)=3， u1(2)=3， u1(3)=5， u1(4)=5 然后根據(jù)策略空間迭代法步驟中的 2176。 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 下面以簡單的例子 n=3, a=, b=, g(y)=, h(y)=的步驟。因此，只考慮在 A、B上具有相同的加工順序 。 狀態(tài)轉(zhuǎn)移方程： Xk+1=Xkxk Yk+1=Ykyk 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 允許決策集合： Dk(Xk,Yk)={(xk,yk)|0≤xk≤Xk,0≤yk≤Yk} ? 令 fk(Xk,Yk)表示當(dāng)狀態(tài)為 (Xk,Yk)時分別用于第 k種生產(chǎn)到 n種生產(chǎn)所得到的最大收入，則由最優(yōu)性原理，得： fn(Xn,Yn)=g(Xn,Yn) fk(Xk,Yk)=max {gk(xk,yk) + fk+1(Xkxk, Ykyk)}, k=n1,…,2,1 0≤xk≤Xk 0≤yk≤Yk 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ?由此遞推關(guān)系式可求得 f1(a,b)，即為所求問題的最大收入。 5動態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 一維資源分配問題 例 1用逆推法解 max z=x1x22x3 x1+x2+x3=C (C0) xi≥0, i=1,2,3 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ?例 2用動態(tài)規(guī)劃解下列問題（ P332） max z=8x1 + 7x2 2x1 + x2≤8 5x1 + 2x2≤15 x1, x2為非負(fù)整數(shù) 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ? [解 ]用逆序解法，將問題分為兩個階段，對應(yīng) ? 狀態(tài)變量： vj, wj分別為第 j階段，第一、第二約束可供分配的右端數(shù)值 ? 決策變量： x1,x2，于是 ? f2*(v2,w2)=max{7x2}=7min{[v2], [w2/2]} 0≤x2≤v2 0 ≤2x2 ≤w2 x2取整數(shù) ? f1*(v1,w1)=max{8x1+ f2*(v12x1,w15x1)} 0≤2x1≤v1 0 ≤5x1 ≤w1 x1取整數(shù) ? 而 v1=8, w1=15,所以 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ? f1*(8,15)=max{8x1+ 7min([82x1],[(155x1)/2])} 0≤2x1≤8 0 ≤5x1 ≤15 x1取整數(shù) ? 由于 x1 ≤min([8/2],[15/5])=3, 因而 ? f1*(8,15)=max{8x1+ 7min([82x1],[(155x1)/2])} x1=0,1,2,3 =max{8x1+ 7[(155x1)/2]}=49 x1=0,1,2,3 ? x1*=0 ? 由 v2=v12x1=8, w2=w15x1=15, 得 ? x2*= min{[8], [15/2]}=7 ? ∴ 最優(yōu)解為 x1*=0, x2*= 7, z*=49 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 167。在此策略下作方程組 fk(i) = Ci, uk(i) + fk[uk(i)], i=1,2,…,N 1 fk(N)=0 求解 fk(i)，這里 Ci, uk(i)為已知值 3176。 ? 上述遞推關(guān)系式即為極小化的泛函方程，且指標(biāo)函數(shù)為和的形式，當(dāng)其中的加號改為乘號時，即轉(zhuǎn)化為積的形式。描述狀態(tài)的變量稱為狀態(tài)變量，用 sk表示第 k個階段的狀態(tài)變量，用 Sk表示所有可能狀態(tài)的集合。 動態(tài)規(guī)劃 ? 動態(tài)規(guī)劃根據(jù)多階段決策過程的時間參量是離散的還是連續(xù)的和其決策過程的演變是確定性的還是隨機(jī)的，可以分為離散確定性、離散隨機(jī)性、連續(xù)確定性、連續(xù)隨機(jī)性四種決策過程模型。 jpjjjjpkkgGUFUpjkfkjfgfffffFU1121)()(111......)(????????????????化為則評價函數(shù)當(dāng)當(dāng)令 評價函數(shù)的收斂性 ?這是因?yàn)?，?G≤G39。 pjffffFUjjjpjjjpjjj,...,2,1,0,1)()(01201?????????????這里 評價函數(shù)的收斂性 ? 這是因?yàn)椋?F≤F39。 X∈ R 評價函數(shù)的收斂性 ?類似地可證得下面的定理。有下面等價的定理。 處理多目標(biāo)規(guī)劃的一些方法 ?如 fj(X)≤fj0, j=2,…,p ， ??????????????pjfXfmiXgXfmiXgXRXffjjiijRXj,...,2,)(,...,2,1,0)()(min:},...,2,1,0)(|{)(min010單目標(biāo)規(guī)劃問題劃問題化為下面的于是可以把原來的多規(guī)這里 處理多目標(biāo)規(guī)劃的一些方法 ? 分層序列法 把（ VP）中的 p個目標(biāo) f1(X), f2(X),…,f p(X)按其重要性排一個次序；分為最重要目標(biāo)、次要目標(biāo)等等。最優(yōu)解的全體記為 Rab* 多目標(biāo)規(guī)劃解的概念 對于無絕對最優(yōu)解的情況，引進(jìn)下面的偏好關(guān)系 ： 設(shè) F1=(f11, f21, …,f p1)T, F2=(f12, f22