最優(yōu)化多目標(biāo)規(guī)劃動(dòng)態(tài)規(guī)劃

1、第五章第五章 多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃 在實(shí)際問(wèn)題中，衡量一個(gè)設(shè)計(jì)方案的在實(shí)際問(wèn)題中，衡量一個(gè)設(shè)計(jì)方案的好壞往往不止一個(gè)。例如：設(shè)計(jì)一個(gè)好壞往往不止一個(gè)。例如：設(shè)計(jì)一個(gè)導(dǎo)彈，既要射程遠(yuǎn)，命中率高，還要導(dǎo)彈，既要射程遠(yuǎn)，命中率高，還要耗燃料少；又如：選擇新廠址，除了耗燃料少；又如：選擇新廠址，除了要考慮運(yùn)費(fèi)、造價(jià)、燃料供應(yīng)費(fèi)等經(jīng)要考慮運(yùn)費(fèi)、造價(jià)、燃料供應(yīng)費(fèi)等經(jīng)濟(jì)指標(biāo)外，還要考慮對(duì)環(huán)境的污染等濟(jì)指標(biāo)外，還要考慮對(duì)環(huán)境的污染等社會(huì)因素。這類(lèi)問(wèn)題即為多目標(biāo)數(shù)學(xué)社會(huì)因素。這類(lèi)問(wèn)題即為多目標(biāo)數(shù)學(xué)規(guī)劃問(wèn)題。規(guī)劃問(wèn)題。第五章第五章 多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃早在早在17721772年，年，F(xiàn)ranklinFrankli

2、n就提出了多目就提出了多目標(biāo)問(wèn)題矛盾如何協(xié)調(diào)的問(wèn)題，標(biāo)問(wèn)題矛盾如何協(xié)調(diào)的問(wèn)題，18961896年，年，ParetoPareto首次從數(shù)學(xué)角度提出了多目標(biāo)首次從數(shù)學(xué)角度提出了多目標(biāo)最優(yōu)決策問(wèn)題，直到二十世紀(jì)最優(yōu)決策問(wèn)題，直到二十世紀(jì)50-7050-70年年代代Charnes, Karlin, ZadehCharnes, Karlin, Zadeh等人先后等人先后做了許多較有影響的工作，多目標(biāo)規(guī)做了許多較有影響的工作，多目標(biāo)規(guī)劃受到人們的關(guān)注。至今多目標(biāo)規(guī)劃劃受到人們的關(guān)注。至今多目標(biāo)規(guī)劃已廣泛應(yīng)用于經(jīng)濟(jì)、管理、系統(tǒng)工程已廣泛應(yīng)用于經(jīng)濟(jì)、管理、系統(tǒng)工程等科技的各個(gè)領(lǐng)域。等科技的各個(gè)領(lǐng)域。1 1多目

3、標(biāo)規(guī)劃問(wèn)題舉例多目標(biāo)規(guī)劃問(wèn)題舉例例例1 1生產(chǎn)計(jì)劃問(wèn)題生產(chǎn)計(jì)劃問(wèn)題 某工廠計(jì)劃生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)每某工廠計(jì)劃生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)每件甲的利潤(rùn)為件甲的利潤(rùn)為4 4元，生產(chǎn)每件乙的利潤(rùn)為元，生產(chǎn)每件乙的利潤(rùn)為3 3元，元，每件甲的加工時(shí)間為每件乙的兩倍，若全部每件甲的加工時(shí)間為每件乙的兩倍，若全部時(shí)間用來(lái)加工乙，則每日可生產(chǎn)乙時(shí)間用來(lái)加工乙，則每日可生產(chǎn)乙500500件，但件，但工廠每日供給的原料只夠生產(chǎn)甲和乙的總數(shù)工廠每日供給的原料只夠生產(chǎn)甲和乙的總數(shù)共共400400件，產(chǎn)品甲是緊俏商品，預(yù)測(cè)市場(chǎng)日需件，產(chǎn)品甲是緊俏商品，預(yù)測(cè)市場(chǎng)日需求量為求量為300300件。決策者希望制定一個(gè)日生產(chǎn)

4、方件。決策者希望制定一個(gè)日生產(chǎn)方案，不僅能得到最大的利潤(rùn)，且能最大地滿案，不僅能得到最大的利潤(rùn)，且能最大地滿足市場(chǎng)需求。足市場(chǎng)需求。生產(chǎn)計(jì)劃問(wèn)題生產(chǎn)計(jì)劃問(wèn)題 問(wèn)題分析問(wèn)題分析 設(shè)每日生產(chǎn)甲、乙的數(shù)量分別為設(shè)每日生產(chǎn)甲、乙的數(shù)量分別為x x1 1, x, x2 2, , 令令X=(xX=(x1 1, , x x2 2), ), 則其目標(biāo)函數(shù)為利潤(rùn)則其目標(biāo)函數(shù)為利潤(rùn) f f1 1(X)=4x(X)=4x1 1 + 3x + 3x2 2 甲的產(chǎn)量甲的產(chǎn)量 f f2 2(X)=x(X)=x1 1 都取最大值都取最大值 滿足約束條件滿足約束條件 x x1 1 + x + x2 2400400（原料供應(yīng)約

5、束）（原料供應(yīng)約束） 2x2x1 1 + x + x2 2500500（加工時(shí)間約束）（加工時(shí)間約束） x x1 100，x x2 200多目標(biāo)規(guī)劃問(wèn)題舉例多目標(biāo)規(guī)劃問(wèn)題舉例例例2 2投資問(wèn)題投資問(wèn)題假設(shè)在一段時(shí)間內(nèi)有假設(shè)在一段時(shí)間內(nèi)有a a（億元）的資金（億元）的資金可用于建廠投資，若可供選擇的項(xiàng)目可用于建廠投資，若可供選擇的項(xiàng)目記為記為1,2,m, 1,2,m, 而且一旦對(duì)第而且一旦對(duì)第i i個(gè)項(xiàng)目個(gè)項(xiàng)目投資，則必須用掉投資，則必須用掉a ai i（億元）（億元）; ; 而在而在這段時(shí)間內(nèi)這第個(gè)項(xiàng)目可得到的收益這段時(shí)間內(nèi)這第個(gè)項(xiàng)目可得到的收益為為c ci i（億元）（億元）, , 其中其中

6、i=1,2,m, i=1,2,m, 問(wèn)問(wèn)如何確定最佳的投資方案？如何確定最佳的投資方案？投資問(wèn)題投資問(wèn)題 問(wèn)題分析問(wèn)題分析 上述要求的最佳方案應(yīng)為：投資少，收益大。上述要求的最佳方案應(yīng)為：投資少，收益大。 mixxaxaxcxxxfxaxxxfiixiimiiimiiimmiiimi,.,2,1,0)1(,),.,(,),.,(01112121211且要滿足下列約束條件且要滿足下列約束條件取最大取最大而而最小最小問(wèn)題即求問(wèn)題即求個(gè)項(xiàng)目不投資個(gè)項(xiàng)目不投資若對(duì)第若對(duì)第個(gè)項(xiàng)目投資個(gè)項(xiàng)目投資若決定對(duì)第若決定對(duì)第設(shè)設(shè)多目標(biāo)規(guī)劃的標(biāo)準(zhǔn)形式多目標(biāo)規(guī)劃的標(biāo)準(zhǔn)形式V-min F(X)=(fV-min F(X)=

7、(f1 1(X), (X), f f2 2(X),f(X),fp p(X)(X)T T s.t. g s.t. gi i(X)0, i=1,2,m(X)0, i=1,2,m 其中其中X=(xX=(x1 1,x,x2 2,x,xn n) )T T, p2, p2 這里這里V-min V-min 是指對(duì)向量形式的是指對(duì)向量形式的p p個(gè)個(gè)目標(biāo)目標(biāo)(f(f1 1(X), f(X), f2 2(X),f(X),fp p(X)(X)T T求最小。求最小。一般假設(shè)多目標(biāo)規(guī)劃中的目標(biāo)函數(shù)已一般假設(shè)多目標(biāo)規(guī)劃中的目標(biāo)函數(shù)已經(jīng)是規(guī)范化了的。經(jīng)是規(guī)范化了的。2 2 多目標(biāo)規(guī)劃解的概念與性質(zhì)多目標(biāo)規(guī)劃解的概念與性質(zhì)

8、1. 1. 多目標(biāo)規(guī)劃解的概念多目標(biāo)規(guī)劃解的概念例例3 3 解解 分別對(duì)單個(gè)目標(biāo)求出其最優(yōu)解，對(duì)于分別對(duì)單個(gè)目標(biāo)求出其最優(yōu)解，對(duì)于第一個(gè)目標(biāo)的最優(yōu)解第一個(gè)目標(biāo)的最優(yōu)解x x(1)(1)=1; =1; 第二個(gè)目標(biāo)的第二個(gè)目標(biāo)的最優(yōu)解最優(yōu)解x x(2)(2)=1, =1, 為同一點(diǎn)，取為同一點(diǎn)，取x x* *=1=1作為多目作為多目標(biāo)問(wèn)題的最優(yōu)解，其目標(biāo)函數(shù)值標(biāo)問(wèn)題的最優(yōu)解，其目標(biāo)函數(shù)值F F* *(x) =(-(x) =(-2,-1). 2,-1). 可以用變量空間和目標(biāo)函數(shù)空間來(lái)分別可以用變量空間和目標(biāo)函數(shù)空間來(lái)分別描述各種解的情況。描述各種解的情況。RxxFVRxxxxxfxxxf )(mi

9、n,2 , 0213210)(,42)(221求求設(shè)設(shè)多目標(biāo)規(guī)劃解的概念多目標(biāo)規(guī)劃解的概念下面考察例下面考察例1 1中生產(chǎn)計(jì)劃問(wèn)題。問(wèn)：是否能找到中生產(chǎn)計(jì)劃問(wèn)題。問(wèn)：是否能找到一個(gè)可行解一個(gè)可行解X X* *=(x=(x1 1* *, x, x2 2* *) )T T使之同時(shí)為使之同時(shí)為f f1 1(X)(X)與與f f2 2(X)(X)的最大解？的最大解？在可行域內(nèi)容易求解在可行域內(nèi)容易求解 max fmax f1 1(X)(X)的唯一最優(yōu)解為的唯一最優(yōu)解為 (100, 300), (100, 300), 見(jiàn)圖見(jiàn)圖中中B B點(diǎn)。點(diǎn)。 max fmax f2 2(X)(X)的唯一最優(yōu)解為的唯一

10、最優(yōu)解為 (250, 0), (250, 0), 見(jiàn)圖中見(jiàn)圖中C C點(diǎn)。點(diǎn)。 由此可得共同的最優(yōu)解由此可得共同的最優(yōu)解X X* *并不存在。當(dāng)一目標(biāo)并不存在。當(dāng)一目標(biāo)達(dá)到最優(yōu)時(shí)，另一目標(biāo)達(dá)不到最優(yōu)，兩目標(biāo)相互達(dá)到最優(yōu)時(shí)，另一目標(biāo)達(dá)不到最優(yōu)，兩目標(biāo)相互矛盾。因此需要根據(jù)別的原則，權(quán)衡兩者之間的矛盾。因此需要根據(jù)別的原則，權(quán)衡兩者之間的得失，從得失，從R R中找出滿意的方案來(lái)。中找出滿意的方案來(lái)。多目標(biāo)規(guī)劃解的概念多目標(biāo)規(guī)劃解的概念 如何比較方案的好壞呢？如何比較方案的好壞呢？ 就上述問(wèn)題，設(shè)就上述問(wèn)題，設(shè)XRXR，YRYR，稱(chēng)，稱(chēng)X X比比Y Y好好（或（或Y Y比比X X劣），若劣），若 f

11、f1 1(X)f(X)f1 1(Y) f(Y) f2 2(X) (X) ff2 2(Y)(Y) 或或 f f1 1(X)f(X)f1 1(Y) f(Y) f2 2(X) (X) ff2 2(Y)(Y) 不難得到除線段不難得到除線段BCBC之外的其余之外的其余R R上的點(diǎn)均上的點(diǎn)均為劣解，而為劣解，而B(niǎo)CBC上無(wú)劣解，且兩兩無(wú)法比較，上無(wú)劣解，且兩兩無(wú)法比較，因此決策者只有根據(jù)某些別的考慮從因此決策者只有根據(jù)某些別的考慮從BCBC上上挑選出滿意的方案來(lái)。這時(shí)稱(chēng)挑選出滿意的方案來(lái)。這時(shí)稱(chēng)BCBC上的點(diǎn)為上的點(diǎn)為非劣解非劣解，或，或有效解有效解。多目標(biāo)規(guī)劃解的概念多目標(biāo)規(guī)劃解的概念對(duì)于一般的多目標(biāo)規(guī)

12、劃問(wèn)題：對(duì)于一般的多目標(biāo)規(guī)劃問(wèn)題： (VP) V-min F(X)=(f(VP) V-min F(X)=(f1 1(X), (X), f f2 2(X),f(X),fp p(X)(X)T T s.t. g s.t. gi i(X)0, (X)0, i=1,2,mi=1,2,m其中其中X=(xX=(x1 1,x,x2 2,x,xn n) )T T, p2, p2設(shè)設(shè)R=X| gR=X| gi i(X)0, i=1,2,m(X)0, i=1,2,m定義定義1 1 設(shè)設(shè)X X* *RR，若對(duì)任意，若對(duì)任意j=1,2,p, j=1,2,p, 以及任意以及任意XRXR均有均有 f fj j(X)f(X)

13、fj j(X(X* *), j=1,2,p), j=1,2,p 則稱(chēng)則稱(chēng)X X* *為問(wèn)題為問(wèn)題(VP)(VP)的的絕對(duì)最優(yōu)解絕對(duì)最優(yōu)解。最優(yōu)解的全。最優(yōu)解的全體記為體記為R Rabab* *多目標(biāo)規(guī)劃解的概念多目標(biāo)規(guī)劃解的概念對(duì)于無(wú)絕對(duì)最優(yōu)解的情況，引進(jìn)下面的對(duì)于無(wú)絕對(duì)最優(yōu)解的情況，引進(jìn)下面的偏好關(guān)系偏好關(guān)系：設(shè)設(shè)F F1 1=(f=(f1 11 1, f, f2 21 1, ,f, ,fp p1 1) )T T, F, F2 2=(f=(f1 12 2, , f f2 22 2, ,f, ,fp p2 2) )T T(1)F(1)F1 1FF2 2意味著意味著F F1 1每個(gè)分量都嚴(yán)格小于

14、每個(gè)分量都嚴(yán)格小于F F2 2的相應(yīng)分量，即的相應(yīng)分量，即f fj j1 1ffj j2 2, j=1,2,p, j=1,2,p(2)F(2)F1 1FF2 2等價(jià)于等價(jià)于f fj j1 1ffj j2 2, j=1,2,p, j=1,2,p，且至少存在某個(gè)且至少存在某個(gè)j j0 0 (1j(1j0 0p), p), 使使f fj0j01 1ffj0j02 2(3)F(3)F1 1FF2 2等價(jià)于等價(jià)于f fj j1 1ffj j2 2, j=1,2,p, j=1,2,p多目標(biāo)規(guī)劃解的概念多目標(biāo)規(guī)劃解的概念定義定義2 2 設(shè)設(shè)X X* *RR，若不存在，若不存在XRXR滿足滿足F(X)F(XF

15、(X)F(X* *), ), 則稱(chēng)則稱(chēng)X X* *為問(wèn)題為問(wèn)題(VP)(VP)的的有效解有效解（或或ParetoPareto解解）。有效解的全體記為）。有效解的全體記為R Rpapa* *定義定義3 3 設(shè)設(shè)X X* *RR，若不存在，若不存在XRXR滿足滿足F(X)F(XF(X)F(X* *), ), 則稱(chēng)則稱(chēng)X X* *為問(wèn)題為問(wèn)題(VP)(VP)的的弱有效弱有效解解（或弱或弱ParetoPareto解解）。弱有效解的全體記）。弱有效解的全體記為為R Rwpwp* *多目標(biāo)規(guī)劃解的性質(zhì)多目標(biāo)規(guī)劃解的性質(zhì)記記R Rj j* *為單目標(biāo)問(wèn)題為單目標(biāo)問(wèn)題(P(Pj j) min f) min f

16、j j(X)(X) s.t. g s.t. gi i(X)0, (X)0, i=1,2,mi=1,2,m的最優(yōu)解集合，的最優(yōu)解集合，j=1,2,pj=1,2,p，可見(jiàn)，可見(jiàn)而而R R，R Rabab* *，R Rpapa* *，R Rwpwp* *，R R1 1* *, R, Rp p* *之間的關(guān)之間的關(guān)系有下列圖示。并有下列定理。系有下列圖示。并有下列定理。*1*jpjabRR 多目標(biāo)規(guī)劃解的性質(zhì)多目標(biāo)規(guī)劃解的性質(zhì)*321paabwpjwppaRRRRRRR 定理定理定理定理定理定理多目標(biāo)規(guī)劃解的性質(zhì)多目標(biāo)規(guī)劃解的性質(zhì)定義定義4 4 如果如果f f1 1(X), f(X), f2 2(X)

17、,f(X),fp p(X)(X)和和g g1 1(X), g(X), g2 2(X),g(X),gm m(X)(X)均為凸函數(shù)，均為凸函數(shù)，則稱(chēng)多目標(biāo)數(shù)學(xué)規(guī)劃（則稱(chēng)多目標(biāo)數(shù)學(xué)規(guī)劃（VPVP）為）為凸多目標(biāo)凸多目標(biāo)數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃。一般來(lái)說(shuō)，即使（一般來(lái)說(shuō)，即使（VPVP）為凸多目標(biāo)數(shù)）為凸多目標(biāo)數(shù)學(xué)規(guī)劃，學(xué)規(guī)劃，R Rwpwp* *和和R Rpapa* *也不一定為凸集。也不一定為凸集。多目標(biāo)規(guī)劃解的性質(zhì)多目標(biāo)規(guī)劃解的性質(zhì)2. 2. 多目標(biāo)規(guī)劃問(wèn)題的像集多目標(biāo)規(guī)劃問(wèn)題的像集 在（在（VPVP）中，取定一可行解）中，取定一可行解X X0 0RR，可得，可得到其相應(yīng)的目標(biāo)函數(shù)值到其相應(yīng)的目標(biāo)函數(shù)值

18、 F(XF(X0 0)=( f)=( f1 1(X(X0 0), , f), , fp p(X(X0 0)T T 此為此為E EP P空間中的一個(gè)點(diǎn)，從而確定了從空間中的一個(gè)點(diǎn)，從而確定了從X X到到F(X)F(X)的一個(gè)映射，即的一個(gè)映射，即 F F XF(X) XF(X) 集合集合F(R)=F(X) |XRF(R)=F(X) |XR稱(chēng)為約束集合稱(chēng)為約束集合R R在映射在映射F F之下的像集。之下的像集。多目標(biāo)規(guī)劃解的性質(zhì)多目標(biāo)規(guī)劃解的性質(zhì)一般來(lái)說(shuō)，即使（一般來(lái)說(shuō)，即使（VPVP）是凸多目標(biāo)規(guī)劃，）是凸多目標(biāo)規(guī)劃，像集像集F(R)F(R)也不一定為凸集（見(jiàn)例也不一定為凸集（見(jiàn)例3 3）。）。

19、但是，當(dāng)目標(biāo)函數(shù)但是，當(dāng)目標(biāo)函數(shù)f f1 1(X), f(X), f2 2(X),f(X),fp p(X)(X)為線性函數(shù)，約束集合為線性函數(shù)，約束集合R R為凸多面體時(shí)，為凸多面體時(shí)，可以證明：像集可以證明：像集F(R)F(R)為為E EP P中的凸多面體。中的凸多面體。多目標(biāo)規(guī)劃解的性質(zhì)多目標(biāo)規(guī)劃解的性質(zhì) 對(duì)于像集對(duì)于像集F(R)F(R)，還可以定義有效點(diǎn)及弱有，還可以定義有效點(diǎn)及弱有效點(diǎn)。效點(diǎn)。定義定義5 5 設(shè)設(shè)F F* *F(R)F(R)，若不存在，若不存在FF(R)FF(R)，滿足，滿足 FFFF* * 則稱(chēng)則稱(chēng)F F* *為像集為像集F(R)F(R)的的有效點(diǎn)有效點(diǎn)，有效點(diǎn)的全，

20、有效點(diǎn)的全體記為體記為E Epapa* *. .定義定義6 6 設(shè)設(shè)F F* *F(R)F(R)，若不存在，若不存在FF(R)FF(R)，滿足，滿足 FFFF* * 則稱(chēng)則稱(chēng)F F* *為像集為像集F(R)F(R)的的弱有效點(diǎn)弱有效點(diǎn)，弱有效點(diǎn)，弱有效點(diǎn)的全體記為的全體記為E Ewpwp* *. .多目標(biāo)規(guī)劃解的性質(zhì)多目標(biāo)規(guī)劃解的性質(zhì)類(lèi)似地可證明：像集類(lèi)似地可證明：像集F(R)F(R)的有效點(diǎn)一的有效點(diǎn)一定是弱有效點(diǎn)，即定是弱有效點(diǎn)，即通過(guò)在像集通過(guò)在像集F(R)F(R)上尋找有效點(diǎn)（或弱上尋找有效點(diǎn)（或弱有效點(diǎn)），就可以確定約束集合有效點(diǎn)），就可以確定約束集合R R上的上的有效解（或弱有效解

21、）。對(duì)此，有如有效解（或弱有效解）。對(duì)此，有如下的定理。下的定理。*wppaEE 多目標(biāo)規(guī)劃解的性質(zhì)多目標(biāo)規(guī)劃解的性質(zhì)定理定理4 4 在像集在像集F(R)F(R)上，若上，若E Epapa* *已知，則在約已知，則在約束集合束集合R R上，有上，有定理定理5 5 在像集在像集F(R)F(R)上，若上，若E Ewpwp* *已知，則在約已知，則在約束集合束集合R R上，有上，有另外通過(guò)對(duì)像集的研究，可以更直觀地認(rèn)另外通過(guò)對(duì)像集的研究，可以更直觀地認(rèn)識(shí)問(wèn)題，并且可以提供一些處理多目標(biāo)規(guī)識(shí)問(wèn)題，并且可以提供一些處理多目標(biāo)規(guī)劃的方法。劃的方法。),(|*RXXFFXRpaEFpa ),(|*RXXFF

22、XRwpEFwp 3 3處理多目標(biāo)規(guī)劃的一些方法處理多目標(biāo)規(guī)劃的一些方法在在2 2中，注意到，要使多目標(biāo)規(guī)劃中，注意到，要使多目標(biāo)規(guī)劃（VPVP）中所有子目標(biāo)同時(shí)實(shí)現(xiàn)最優(yōu)經(jīng)）中所有子目標(biāo)同時(shí)實(shí)現(xiàn)最優(yōu)經(jīng)常是不可解的，那么如何制定比較標(biāo)常是不可解的，那么如何制定比較標(biāo)準(zhǔn)在（弱）有效解集中找到滿意解呢？準(zhǔn)在（弱）有效解集中找到滿意解呢？處理多目標(biāo)規(guī)劃的一些方法處理多目標(biāo)規(guī)劃的一些方法3.1 3.1 約束法（主要目標(biāo)法）約束法（主要目標(biāo)法） 在目標(biāo)函數(shù)在目標(biāo)函數(shù)f f1 1(X), f(X), f2 2(X),f(X),fp p(X)(X)中，選出其中的一個(gè)作為主要目標(biāo)，中，選出其中的一個(gè)作為主要目標(biāo)

23、，如如f f1 1(X), (X), 而其它的目標(biāo)而其它的目標(biāo)f f2 2(X),f(X),fp p(X)(X)只要滿足一定的條件即可。只要滿足一定的條件即可。處理多目標(biāo)規(guī)劃的一些方法處理多目標(biāo)規(guī)劃的一些方法如如f fj j(X)f(X)fj j0 0, j=2,p, j=2,p， pjfXfmiXgXfmiXgXRXffjjiijRXj,.,2,)(,.,2 , 1, 0)()(min:,.,2 , 1, 0)(|)(min010單目標(biāo)規(guī)劃問(wèn)題單目標(biāo)規(guī)劃問(wèn)題劃問(wèn)題化為下面的劃問(wèn)題化為下面的于是可以把原來(lái)的多規(guī)于是可以把原來(lái)的多規(guī)這里這里處理多目標(biāo)規(guī)劃的一些方法處理多目標(biāo)規(guī)劃的一些方法3.2

24、3.2 分層序列法分層序列法 把（把（VPVP）中的）中的p p個(gè)目標(biāo)個(gè)目標(biāo)f f1 1(X), (X), f f2 2(X),f(X),fp p(X)(X)按其重要性排一個(gè)次序；分按其重要性排一個(gè)次序；分為最重要目標(biāo)、次要目標(biāo)等等。不妨設(shè)為最重要目標(biāo)、次要目標(biāo)等等。不妨設(shè)p p個(gè)目個(gè)目標(biāo)責(zé)任制的重要性序列為標(biāo)責(zé)任制的重要性序列為 f f1 1(X), f(X), f2 2(X),f(X),fp p(X)(X) 首先求第一個(gè)目標(biāo)首先求第一個(gè)目標(biāo)f f1 1(X)(X)的最優(yōu)解的最優(yōu)解 (P(P1 1) min f) min f1 1(X)(X) XRXR 設(shè)其最優(yōu)值為設(shè)其最優(yōu)值為f f1 1*

25、 *，再求第二個(gè)目標(biāo)的最優(yōu)，再求第二個(gè)目標(biāo)的最優(yōu)解解處理多目標(biāo)規(guī)劃的一些方法處理多目標(biāo)規(guī)劃的一些方法(P(P2 2) min f) min f2 2(X)(X) XRXR1 1 其中其中R R1 1=RX |f=RX |f1 1(X)f(X)f1 1* * 其最優(yōu)值為其最優(yōu)值為f f2 2* *，然后求第三個(gè)目標(biāo)的最優(yōu)解，然后求第三個(gè)目標(biāo)的最優(yōu)解 (P(P3 3) min f) min f3 3(X)(X) XRXR2 2 其中其中R R2 2=R=R1 1X |fX |f2 2(X)f(X)f2 2* * 求得最優(yōu)值為求得最優(yōu)值為f f3 3* *,，最后求第，最后求第p p個(gè)目標(biāo)的最優(yōu)解個(gè)

26、目標(biāo)的最優(yōu)解 (P(Pp p) min f) min fp p(X)(X) XRXR p-1p-1 其中其中R Rp-1p-1=R=Rp-2p-2X |fX |fp-1p-1(X)f(X)fp-1p-1* * 處理多目標(biāo)規(guī)劃的一些方法處理多目標(biāo)規(guī)劃的一些方法此時(shí)求得最優(yōu)解此時(shí)求得最優(yōu)解X X* *，最優(yōu)值為，最優(yōu)值為f fp p* *，則，則X X* *就是多目標(biāo)問(wèn)題就是多目標(biāo)問(wèn)題(VP)(VP)在分層序列意在分層序列意義下的最優(yōu)解。進(jìn)一步有下列定理。義下的最優(yōu)解。進(jìn)一步有下列定理。定理定理6 6 設(shè)設(shè)X X* *是由分層序列法所得到的是由分層序列法所得到的最優(yōu)解，則最優(yōu)解，則X X* *RR

27、papa* *. .處理多目標(biāo)規(guī)劃的一些方法處理多目標(biāo)規(guī)劃的一些方法 證明證明 用反證法證明。用反證法證明。 假設(shè)假設(shè)X X* *不不R Rpapa* *，則必存在，則必存在YRYR，使，使 F(Y)F(XF(Y)F(X* *) ) 下面分兩種情形討論：下面分兩種情形討論：(1)(1)若若f f1 1(Y)f(Y)f1 1(X(X* *), ), 而而f f1 1(X(X* *)=f)=f1 1* *, , 故得故得(P(P1 1) )的可行解的可行解Y Y滿足滿足 f f1 1(Y)f(Y)f1 1(X(X* *)=f)=f1 1* * 此與此與f f1 1* *=min f=min f1

28、1(X)(X)相矛盾。相矛盾。 XRXR處理多目標(biāo)規(guī)劃的一些方法處理多目標(biāo)規(guī)劃的一些方法(2)(2)若若f fj j(Y)= f(Y)= fj j(X(X* *), j=1,2,j), j=1,2,j0 0-1-1 但但f fj0j0(Y)f(Y)fj0j0(X(X* *) 2j) 2j0 0p p 此時(shí)必有此時(shí)必有f fj j(Y)= f(Y)= fj j(X(X* *)f)fj j* *, , j=1,2,jj=1,2,j0 0-1 -1 因此，因此，Y Y是問(wèn)題是問(wèn)題 (P(Pj0j0) min f) min fp p(X)(X) XR XRj0-2j0-2X |fX |fj0-1j0-

29、1(X)f(X)fj0-j0-1 1* * 的可行解，又由的可行解，又由 f fj0j0(Y)f(Y)0, j=1,2,p(X)0, j=1,2,p不妨設(shè)其中不妨設(shè)其中k k個(gè)個(gè)f f1 1(X), f(X), f2 2(X),f(X),fk k(X)(X)要求要求實(shí)現(xiàn)最小，其余實(shí)現(xiàn)最小，其余f fk+1k+1(X), ,f(X), ,fp p(X)(X)要求實(shí)現(xiàn)要求實(shí)現(xiàn)最大，則可構(gòu)造評(píng)價(jià)函數(shù)最大，則可構(gòu)造評(píng)價(jià)函數(shù)然后求然后求min U(F(X)min U(F(X) XRXR)().()().()()(121XfXfXfXfXfXFUpkk 3.4 3.4 評(píng)價(jià)函數(shù)的收斂性評(píng)價(jià)函數(shù)的收斂性上節(jié)

30、中，用不同的評(píng)價(jià)函數(shù)上節(jié)中，用不同的評(píng)價(jià)函數(shù)U(F(X)U(F(X)將將多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃(VP)(VP)轉(zhuǎn)化為單目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題 min U(F(X)min U(F(X) XRXR 來(lái)處理，并將其解來(lái)處理，并將其解X X* *作為作為(VP)(VP)的解。的解。 而而X X* *是否為是否為(VP)(VP)的有效解或弱有效的有效解或弱有效解呢？解呢？評(píng)價(jià)函數(shù)的收斂性評(píng)價(jià)函數(shù)的收斂性定義定義7 7 若對(duì)任意若對(duì)任意F, FEF, FEp p, , 當(dāng)當(dāng)FFFF時(shí)，都有時(shí)，都有 U(F)U(F)U(F)U(F) 成立，則稱(chēng)成立，則稱(chēng)U(F)U(F)是是F F的的嚴(yán)格單調(diào)增函嚴(yán)格單調(diào)增函

31、數(shù)數(shù)。定義定義8 8 若對(duì)任意若對(duì)任意F, FEF, FEp p, , 當(dāng)當(dāng)FFFF時(shí)，時(shí)，都有都有 U(F)U(F)U(F)U(F) 成立，則稱(chēng)成立，則稱(chēng)U(F)U(F)是是F F的的單調(diào)增函數(shù)單調(diào)增函數(shù)。評(píng)價(jià)函數(shù)的收斂性評(píng)價(jià)函數(shù)的收斂性定理定理8 8 若對(duì)若對(duì)FEFEp p，U(F)U(F)是嚴(yán)格單調(diào)增函數(shù)，則單是嚴(yán)格單調(diào)增函數(shù)，則單目標(biāo)問(wèn)題目標(biāo)問(wèn)題 min U(F(X)min U(F(X) XRXR 的最優(yōu)解的最優(yōu)解X X* *RRpapa* * 證明證明 用反證法。用反證法。 若若X X* *不不R Rpapa* *，即存在，即存在YRYR，使，使 F(Y)F(XF(Y)F(X* *)

32、 ) 由由U(F)U(F)的嚴(yán)格單調(diào)性，有的嚴(yán)格單調(diào)性，有 U(F(Y)U(F(XU(F(Y)00，j=1,2,pj=1,2,p時(shí)，時(shí)，U(F)U(F)為嚴(yán)格單調(diào)增函數(shù)。為嚴(yán)格單調(diào)增函數(shù)。 這是因?yàn)椋暨@是因?yàn)?，若j j00，j=1,2,p, j=1,2,p, 且且FFF00，于是，于是 j0j0f fj0j000，j=1,2,pj=1,2,p時(shí)，對(duì)時(shí)，對(duì)FFFF，則則 j jf fj jj jf fj j j=1,2,pj=1,2,p 由由FFFF，則至少存在某個(gè)，則至少存在某個(gè)j j0 0(1j(1j0 0p)p)，使使 f fj0j0ffj0j0 從而從而 j0j0f fj0j0j0j0

33、f fj0j0 相加得相加得 ) ()(11FUffFUpjjjpjjj 評(píng)價(jià)函數(shù)的收斂性評(píng)價(jià)函數(shù)的收斂性2. 2. 平方和加權(quán)法平方和加權(quán)法 U(F)U(F)為為F F的嚴(yán)格單調(diào)增函數(shù)。的嚴(yán)格單調(diào)增函數(shù)。pjffffFUjjjpjjjpjjj,.,2 , 1, 0, 1)()(01201 這里這里評(píng)價(jià)函數(shù)的收斂性評(píng)價(jià)函數(shù)的收斂性這是因?yàn)?，若這是因?yàn)椋鬎FFF，由于，由于FFFF0 0，F(xiàn)FFF0 0，故故 0f0fj j-f-fj j0 0ffj j -f-fj j0 0 j=1,2,pj=1,2,p 且至少存在某個(gè)且至少存在某個(gè)j j0 0(1j(1j0 0p)p)，有，有 f fj j

34、-f-fj j0 0ffj j -f-fj j0 0 從而從而 j0j0f fj0j0j0j0f fj0j0 故故U(F)U(F)U(F)00，j=1,2,p.j=1,2,p. 這是因?yàn)?，若這是因?yàn)?，若FFFF，則對(duì)，則對(duì)j=1,2,p, j=1,2,p, 均有均有 f fj jffj j 于是，若記于是，若記 j0j0f fj0j0= max = max j jf fj j 1jp 1jp 則則 U(F)=max U(F)=max j jf fj j = =j0j0f fj0j00, j=1,2,p0, j=1,2,p 可證可證U(G)U(G)為為G G的嚴(yán)格單調(diào)增函數(shù)。的嚴(yán)格單調(diào)增函數(shù)。j

35、pjjjjpkkgGUFUpjkfkjfgfffffFU1121)()(111.)( 化為化為則評(píng)價(jià)函數(shù)則評(píng)價(jià)函數(shù)當(dāng)當(dāng)當(dāng)當(dāng)令令評(píng)價(jià)函數(shù)的收斂性評(píng)價(jià)函數(shù)的收斂性這是因?yàn)?，若這是因?yàn)椋鬐GGG，則由，則由G0, G0G0, G0及及 g gj jggj j j=1,2,pj=1,2,p 且至少存在某個(gè)且至少存在某個(gè)j j0 0(1j(1j0 0p)p)使使 g gj0j0g0),2,3,50),2,3,5求得的最優(yōu)解求得的最優(yōu)解 X X* *RRpapa* *而由方法而由方法1(1(j j0)0)，4 4得到的最優(yōu)解得到的最優(yōu)解 X X* *RRwpwp* *3.5 3.5 逐步法逐步法（交替式

36、對(duì)話方法）（交替式對(duì)話方法）由于問(wèn)題的復(fù)雜性，有時(shí)決策者所提供的由于問(wèn)題的復(fù)雜性，有時(shí)決策者所提供的信息不足以使分析者確定各目標(biāo)函數(shù)之間信息不足以使分析者確定各目標(biāo)函數(shù)之間的關(guān)系，因此需要在決策者和分析者之間的關(guān)系，因此需要在決策者和分析者之間建立一種交互式的對(duì)話方法（如建立一種交互式的對(duì)話方法（如Step Step Method, STEM, Method, STEM, 逐步法），分析者根據(jù)決逐步法），分析者根據(jù)決策者提供的信息（經(jīng)修改和補(bǔ)充后的）給策者提供的信息（經(jīng)修改和補(bǔ)充后的）給出中間結(jié)果，決策者對(duì)中間結(jié)果發(fā)表意見(jiàn)，出中間結(jié)果，決策者對(duì)中間結(jié)果發(fā)表意見(jiàn)，可根據(jù)中間結(jié)果進(jìn)一步提供信息，讓

37、分析可根據(jù)中間結(jié)果進(jìn)一步提供信息，讓分析者重新計(jì)算，直到求得滿意解為止。者重新計(jì)算，直到求得滿意解為止。逐步法逐步法下面介紹多目標(biāo)線性規(guī)劃中的下面介紹多目標(biāo)線性規(guī)劃中的STEMSTEM步驟步驟: : 求求 V-min F(X)=(fV-min F(X)=(f1 1(X), (X), f f2 2(X),f(X),fp p(X)(X)T T XRXR0,|,.,2 , 1,)(1 XbAXXRpixcXfnjjiji設(shè)設(shè)逐步法逐步法1.1.求求p p個(gè)線性規(guī)劃的最優(yōu)解個(gè)線性規(guī)劃的最優(yōu)解 min fmin fi i(X) = f(X) = fi i(X(X(i)(i) = f) = fi i* *

38、 i=1,2,pi=1,2,p XRXR 令令 f fi imaxmax max f max fi i(X(X(j)(j) ) i=1,2,pi=1,2,p 1jp 1jp 顯然顯然 f fi imaxmaxffi i* * i=1,2,p i=1,2,p 不妨設(shè)不完全取等號(hào)。不妨設(shè)不完全取等號(hào)。逐步法逐步法2.2.決策者不能給出加權(quán)系數(shù)決策者不能給出加權(quán)系數(shù)，分析者只，分析者只好根據(jù)函數(shù)好根據(jù)函數(shù)f fi i(X)(X)和和R R的性質(zhì)給出一種算法：的性質(zhì)給出一種算法： 0)(10)(1,.,2 , 1*12*max*12max*max12121injijiiiinjijiiiipjjiif

39、cffffcfffpi當(dāng)當(dāng)當(dāng)當(dāng)其中其中令令 逐步法逐步法3. 3. 求線性規(guī)劃求線性規(guī)劃 的最優(yōu)解的最優(yōu)解(X(X(0)(0), t, t(0)(0) ) RXpitfXftPiii,.,2 , 1)(min)(*0 逐步法逐步法4. 4. 決策者對(duì)決策者對(duì)F(XF(X(0)(0) )與與F F* *=(f=(f1 1* *,f,fp p* *) )T T進(jìn)行比較，進(jìn)行比較，若對(duì)若對(duì)X X(0)(0)比較滿意，則迭代停止；否則，對(duì)最滿意比較滿意，則迭代停止；否則，對(duì)最滿意的的f fj0j0(X(X(0)(0) )提出允許變大的上限提出允許變大的上限ffj0j0, , 而對(duì)其它而對(duì)其它f fi

40、i(X)(ij(X)(ij0 0) )則不允許變大，因此把則不允許變大，因此把(P(P0 0) )改成求改成求 的最優(yōu)解的最優(yōu)解(X(X(1)(1), t, t(1)(1) )。 RXjipiXfXffXfXfjipitfXftPiijjjiii0)0(0)0(000*1,.,2 , 1)()()()(,.,2 , 1)(min)( 逐步法逐步法若對(duì)若對(duì)X X(1)(1)仍不滿意，則可用這種思想在仍不滿意，則可用這種思想在(P(P1 1) )中添加新的約束，或修改中添加新的約束，或修改ffj j的的值，再求新的解，這種交互式對(duì)話進(jìn)值，再求新的解，這種交互式對(duì)話進(jìn)行若干次，直到?jīng)Q策者滿意為止。行

41、若干次，直到?jīng)Q策者滿意為止。第六章第六章 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃（動(dòng)態(tài)規(guī)劃（Dynamic ProgrammingDynamic Programming）是最優(yōu)化的一個(gè)分支。是最優(yōu)化的一個(gè)分支。19511951年美國(guó)數(shù)年美國(guó)數(shù)學(xué)家學(xué)家R.BellmanR.Bellman（貝爾曼）等人根據(jù)一（貝爾曼）等人根據(jù)一類(lèi)多階段決策問(wèn)題的特性，提出了解類(lèi)多階段決策問(wèn)題的特性，提出了解決這類(lèi)問(wèn)題的決這類(lèi)問(wèn)題的“最優(yōu)性原理最優(yōu)性原理”，并研，并研究了許多實(shí)際問(wèn)題，從而建立了最優(yōu)究了許多實(shí)際問(wèn)題，從而建立了最優(yōu)化的一個(gè)分支化的一個(gè)分支動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃把比較復(fù)雜的問(wèn)題劃分成若干階

42、段，通動(dòng)態(tài)規(guī)劃把比較復(fù)雜的問(wèn)題劃分成若干階段，通過(guò)逐段求解，最終求得全局最優(yōu)解。特別對(duì)于離過(guò)逐段求解，最終求得全局最優(yōu)解。特別對(duì)于離散性問(wèn)題，由于解析數(shù)學(xué)無(wú)法運(yùn)用，動(dòng)態(tài)規(guī)劃就散性問(wèn)題，由于解析數(shù)學(xué)無(wú)法運(yùn)用，動(dòng)態(tài)規(guī)劃就成為非常有效的工具。然而動(dòng)態(tài)規(guī)劃目前還存在成為非常有效的工具。然而動(dòng)態(tài)規(guī)劃目前還存在以下弱點(diǎn)：以下弱點(diǎn)：1 1）動(dòng)態(tài)規(guī)劃沒(méi)有一個(gè)統(tǒng)一的算法，它）動(dòng)態(tài)規(guī)劃沒(méi)有一個(gè)統(tǒng)一的算法，它必須針對(duì)各種問(wèn)題的性質(zhì)，利用最優(yōu)性原理得出必須針對(duì)各種問(wèn)題的性質(zhì)，利用最優(yōu)性原理得出函數(shù)方程后，再結(jié)合其它數(shù)學(xué)技巧來(lái)求解，而沒(méi)函數(shù)方程后，再結(jié)合其它數(shù)學(xué)技巧來(lái)求解，而沒(méi)有一種統(tǒng)一的處理方法，從而我們稱(chēng)動(dòng)態(tài)規(guī)劃是

43、有一種統(tǒng)一的處理方法，從而我們稱(chēng)動(dòng)態(tài)規(guī)劃是一種方法。一種方法。2 2）當(dāng)變數(shù)的個(gè)數(shù)（維數(shù)）太大時(shí)，這）當(dāng)變數(shù)的個(gè)數(shù)（維數(shù)）太大時(shí)，這類(lèi)問(wèn)題雖可以用動(dòng)態(tài)規(guī)劃來(lái)描述，但由于計(jì)算機(jī)類(lèi)問(wèn)題雖可以用動(dòng)態(tài)規(guī)劃來(lái)描述，但由于計(jì)算機(jī)存貯容量和計(jì)算機(jī)速度的限制，使問(wèn)題無(wú)法解決，存貯容量和計(jì)算機(jī)速度的限制，使問(wèn)題無(wú)法解決，此即所謂此即所謂“維數(shù)障礙維數(shù)障礙”。動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃根據(jù)多階段決策過(guò)程的時(shí)間動(dòng)態(tài)規(guī)劃根據(jù)多階段決策過(guò)程的時(shí)間參量是離散的還是連續(xù)的和其決策過(guò)參量是離散的還是連續(xù)的和其決策過(guò)程的演變是確定性的還是隨機(jī)的，可程的演變是確定性的還是隨機(jī)的，可以分為離散確定性、離散隨機(jī)性、連以分為離散確定性

44、、離散隨機(jī)性、連續(xù)確定性、連續(xù)隨機(jī)性四種決策過(guò)程續(xù)確定性、連續(xù)隨機(jī)性四種決策過(guò)程模型。模型。1 1多階段決策問(wèn)題及實(shí)例多階段決策問(wèn)題及實(shí)例所謂多階段決策問(wèn)題，是指一類(lèi)活動(dòng)過(guò)程，所謂多階段決策問(wèn)題，是指一類(lèi)活動(dòng)過(guò)程，它可以分為互相聯(lián)系的若干個(gè)階段，在每它可以分為互相聯(lián)系的若干個(gè)階段，在每一階段都需要作出決策，從而使整個(gè)過(guò)程一階段都需要作出決策，從而使整個(gè)過(guò)程達(dá)到最優(yōu)的活動(dòng)效果。因此，各個(gè)階段決達(dá)到最優(yōu)的活動(dòng)效果。因此，各個(gè)階段決策的選取常依賴(lài)于當(dāng)前面臨的狀態(tài)，又影策的選取常依賴(lài)于當(dāng)前面臨的狀態(tài)，又影響下一個(gè)階段的決策，從而影響整個(gè)過(guò)程響下一個(gè)階段的決策，從而影響整個(gè)過(guò)程的活動(dòng)路線，這種把一個(gè)問(wèn)題

45、看成一個(gè)前的活動(dòng)路線，這種把一個(gè)問(wèn)題看成一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程就稱(chēng)為后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程就稱(chēng)為多階段決策過(guò)程多階段決策過(guò)程，也稱(chēng)，也稱(chēng)序貫決策過(guò)程序貫決策過(guò)程。多階段決策問(wèn)題及實(shí)例多階段決策問(wèn)題及實(shí)例各個(gè)階段的決策確定以后就構(gòu)成一個(gè)決策各個(gè)階段的決策確定以后就構(gòu)成一個(gè)決策序列，稱(chēng)為一個(gè)策略。由于每一個(gè)階段可序列，稱(chēng)為一個(gè)策略。由于每一個(gè)階段可供選擇的決策不止一個(gè)，因而對(duì)應(yīng)于整個(gè)供選擇的決策不止一個(gè)，因而對(duì)應(yīng)于整個(gè)活動(dòng)過(guò)程就有許多策略選擇采用，從中選活動(dòng)過(guò)程就有許多策略選擇采用，從中選出一個(gè)效果最好的為最優(yōu)策略。在多階段出一個(gè)效果最好的為最優(yōu)策略。在多階段決策問(wèn)題中，既然

46、引入了階段的概念，也決策問(wèn)題中，既然引入了階段的概念，也就與時(shí)間密不可分，決策過(guò)程從一個(gè)狀態(tài)就與時(shí)間密不可分，決策過(guò)程從一個(gè)狀態(tài)到另一個(gè)狀態(tài)，隨著時(shí)間的變化在變化，到另一個(gè)狀態(tài)，隨著時(shí)間的變化在變化，也就有了也就有了“動(dòng)態(tài)動(dòng)態(tài)”的含義。有一些問(wèn)題表的含義。有一些問(wèn)題表面上處來(lái)與時(shí)間無(wú)關(guān)，只要人為地引入面上處來(lái)與時(shí)間無(wú)關(guān)，只要人為地引入“時(shí)間時(shí)間”因素，也可以變?yōu)橄聜€(gè)多階段決因素，也可以變?yōu)橄聜€(gè)多階段決策問(wèn)題，用動(dòng)態(tài)規(guī)劃方法來(lái)處理。策問(wèn)題，用動(dòng)態(tài)規(guī)劃方法來(lái)處理。多階段決策問(wèn)題及實(shí)例多階段決策問(wèn)題及實(shí)例例例1 1 最短路線問(wèn)題最短路線問(wèn)題AB1B2C1C2C3C4D1E1F1GD2D3E2E3F2

47、531368766835338422123335526643437597681310912131618多階段決策問(wèn)題及實(shí)例多階段決策問(wèn)題及實(shí)例例例2 2 多階段資源分配問(wèn)題多階段資源分配問(wèn)題某工廠生產(chǎn)某工廠生產(chǎn)A, BA, B和和C C三種產(chǎn)品，都要使用某種原材三種產(chǎn)品，都要使用某種原材料，原材料共有料，原材料共有4 4噸。將不同數(shù)量的這種原料分配噸。將不同數(shù)量的這種原料分配給各種產(chǎn)品時(shí)產(chǎn)生收益如下表（單位：萬(wàn)元），試給各種產(chǎn)品時(shí)產(chǎn)生收益如下表（單位：萬(wàn)元），試確定使總收益最大的分配法。確定使總收益最大的分配法。 原料的分配量原料的分配量 產(chǎn)品種類(lèi)產(chǎn)品種類(lèi) （噸）（噸） A A B CB C

48、0 0 0 0 0 00 0 1 10 1 10 6 86 8 2 17 2 17 17 1117 11 3 20 3 20 18 -18 -2 2動(dòng)態(tài)規(guī)劃的基本概念動(dòng)態(tài)規(guī)劃的基本概念一、最短路線問(wèn)題的解一、最短路線問(wèn)題的解 首先討論最短路線問(wèn)題的求解方法首先討論最短路線問(wèn)題的求解方法 解法一解法一 枚舉法枚舉法 4848條不同路線條不同路線 48486=2886=288步加法步加法 4747次路線長(zhǎng)度的比較次路線長(zhǎng)度的比較 最短路長(zhǎng)為最短路長(zhǎng)為1818最短路線問(wèn)題的解最短路線問(wèn)題的解 解法二解法二 共有共有6 6個(gè)階段個(gè)階段 記記f f1 1(A) A(A) A到到G G的最短距離的最短距離

49、 則則 f f1 1(A)(A)依賴(lài)于依賴(lài)于f f2 2(B(B1 1), f), f2 2(B(B2 2),), 而而f f6 6(F(F1 1)=4, f)=4, f6 6(F(F2 2)=3)=3 故由后向前寫(xiě)出相應(yīng)公式的形式。故由后向前寫(xiě)出相應(yīng)公式的形式。 解法二稱(chēng)為逆推解法（逆序解法）解法二稱(chēng)為逆推解法（逆序解法）最短路線問(wèn)題的解最短路線問(wèn)題的解上面的做法極其簡(jiǎn)單，從中我們可以上面的做法極其簡(jiǎn)單，從中我們可以處到這樣一個(gè)規(guī)律，即最短路線必須處到這樣一個(gè)規(guī)律，即最短路線必須且只能由最短子路線組成，在求且只能由最短子路線組成，在求A A到到G G的最短路線時(shí)，附帶求得了從所有中的最短路線

50、時(shí)，附帶求得了從所有中間頂點(diǎn)到間頂點(diǎn)到G G的最短路，它們是作為整個(gè)的最短路，它們是作為整個(gè)問(wèn)題的子問(wèn)題出現(xiàn)的，并且被嵌入較問(wèn)題的子問(wèn)題出現(xiàn)的，并且被嵌入較大問(wèn)題之中，這常常是動(dòng)態(tài)規(guī)劃方法大問(wèn)題之中，這常常是動(dòng)態(tài)規(guī)劃方法的一個(gè)特點(diǎn)。的一個(gè)特點(diǎn)。二、動(dòng)態(tài)規(guī)劃的基本概念二、動(dòng)態(tài)規(guī)劃的基本概念(1)(1)階段階段(Stage)(Stage) 對(duì)所給問(wèn)題的過(guò)程，根據(jù)時(shí)間和對(duì)所給問(wèn)題的過(guò)程，根據(jù)時(shí)間和空間的自然特征，恰當(dāng)?shù)貏澐譃槿舾煽臻g的自然特征，恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)相互聯(lián)系的階段，以便能按一定的個(gè)相互聯(lián)系的階段，以便能按一定的次序去求解。描述階段的變量稱(chēng)為階次序去求解。描述階段的變量稱(chēng)為階段變量，用段變

51、量，用k k表示。表示。動(dòng)態(tài)規(guī)劃的基本概念動(dòng)態(tài)規(guī)劃的基本概念(2)(2)狀態(tài)狀態(tài)(State)(State) 狀態(tài)表示某階段開(kāi)始所處的自然狀況狀態(tài)表示某階段開(kāi)始所處的自然狀況（或條件），它既是本階段的起始位置，（或條件），它既是本階段的起始位置，又是上一階段的終了位置，通常一個(gè)階段又是上一階段的終了位置，通常一個(gè)階段包含若干個(gè)狀態(tài)。描述狀態(tài)的變量稱(chēng)為狀包含若干個(gè)狀態(tài)。描述狀態(tài)的變量稱(chēng)為狀態(tài)變量，用態(tài)變量，用s sk k表示第表示第k k個(gè)階段的狀態(tài)變量，個(gè)階段的狀態(tài)變量，用用S Sk k表示所有可能狀態(tài)的集合。表示所有可能狀態(tài)的集合。狀態(tài)的選擇不是任意的，必須具有下列性狀態(tài)的選擇不是任意的，必

52、須具有下列性質(zhì)：若某階段狀態(tài)給定后，則在這階段以質(zhì)：若某階段狀態(tài)給定后，則在這階段以后過(guò)程的發(fā)展不受這以前各階段狀態(tài)的影后過(guò)程的發(fā)展不受這以前各階段狀態(tài)的影響，這個(gè)性質(zhì)稱(chēng)為響，這個(gè)性質(zhì)稱(chēng)為無(wú)后效性無(wú)后效性（即馬爾科夫（即馬爾科夫性）。性）。動(dòng)態(tài)規(guī)劃的基本概念動(dòng)態(tài)規(guī)劃的基本概念(3)(3)決策決策(Decision)(Decision) 決策表示當(dāng)過(guò)程處于某一階段的某個(gè)決策表示當(dāng)過(guò)程處于某一階段的某個(gè)狀態(tài)時(shí)，可以作出不同的決定（或選擇），狀態(tài)時(shí)，可以作出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱(chēng)為從而確定下一階段的狀態(tài)，這種決定稱(chēng)為決策。在最優(yōu)控制中也稱(chēng)為控制。描述決決策。在最優(yōu)控

53、制中也稱(chēng)為控制。描述決策的變量稱(chēng)為決策變量，常用策的變量稱(chēng)為決策變量，常用u uk k(s(sk k) )表示第表示第k k個(gè)階段當(dāng)狀態(tài)處于個(gè)階段當(dāng)狀態(tài)處于s sk k時(shí)的決策變量，它是時(shí)的決策變量，它是狀態(tài)變量的函數(shù)。決策變量的取值范圍稱(chēng)狀態(tài)變量的函數(shù)。決策變量的取值范圍稱(chēng)為允許決策集合，常用為允許決策集合，常用D Dk k(s(sk k) )表示第表示第k k階段階段從狀態(tài)從狀態(tài)s sk k出發(fā)的允許決策集合，有出發(fā)的允許決策集合，有u uk k(s(sk k)D)Dk k(s(sk k) )。動(dòng)態(tài)規(guī)劃的基本概念動(dòng)態(tài)規(guī)劃的基本概念(4)(4)策略策略(Policy)(Policy)策略是一

54、個(gè)按順序排列的決策序列，用策略是一個(gè)按順序排列的決策序列，用 p pk,nk,n(s(sk k)=u)=uk k(s(sk k), u), uk+1k+1(s(sk+1k+1), ), u un n(s(sn n) 表示從第表示從第k k階段階段s sk k狀態(tài)開(kāi)始到終止的狀態(tài)開(kāi)始到終止的決策序列，稱(chēng)為決策序列，稱(chēng)為 k k子過(guò)程策略；當(dāng)子過(guò)程策略；當(dāng)k=1k=1時(shí)，即為全過(guò)程的一個(gè)策略，簡(jiǎn)稱(chēng)策略。時(shí)，即為全過(guò)程的一個(gè)策略，簡(jiǎn)稱(chēng)策略。動(dòng)態(tài)規(guī)劃的基本概念動(dòng)態(tài)規(guī)劃的基本概念(5)(5)狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程是確定過(guò)程由一個(gè)狀態(tài)狀態(tài)轉(zhuǎn)移方程是確定過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程。在

55、第到另一個(gè)狀態(tài)的演變過(guò)程。在第k k階段階段當(dāng)狀態(tài)處于當(dāng)狀態(tài)處于s sk k時(shí)，若該段的決策變量時(shí)，若該段的決策變量u uk k一經(jīng)確定，則第一經(jīng)確定，則第k+1k+1階段的狀態(tài)變量階段的狀態(tài)變量s sk+1k+1的值也就隨之確定，從而的值也就隨之確定，從而s sk+1k+1的值的值隨隨s sk k和和u uk k的值變化而變化，記為的值變化而變化，記為s sk+1k+1=T=Tk k(s(sk k, u, uk k) )，稱(chēng)為狀態(tài)轉(zhuǎn)移方程。，稱(chēng)為狀態(tài)轉(zhuǎn)移方程。動(dòng)態(tài)規(guī)劃的基本概念動(dòng)態(tài)規(guī)劃的基本概念(6)(6)指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)和最優(yōu)值函數(shù) 指標(biāo)函數(shù)是用以衡量多階段決策過(guò)程實(shí)現(xiàn)效果指標(biāo)

56、函數(shù)是用以衡量多階段決策過(guò)程實(shí)現(xiàn)效果的一種數(shù)量指標(biāo)，用的一種數(shù)量指標(biāo)，用V Vk, nk, n表示，即表示，即 V Vk, nk, n=V=Vk, nk, n(s(sk k, u, uk k, s, sk+1k+1,s,sn+1n+1) )，k=1,2,nk=1,2,n 指標(biāo)函數(shù)應(yīng)具有可分離性，并滿足遞推關(guān)系指標(biāo)函數(shù)應(yīng)具有可分離性，并滿足遞推關(guān)系 V Vk, nk, n(s(sk k, u, uk k, s, sk+1k+1,s,sn+1n+1)=)=k k(s(sk k, u, uk k,V,Vk+1, k+1, n n(s(sk+1k+1,s,sn+1n+1)指標(biāo)函數(shù)的最優(yōu)值，稱(chēng)為最優(yōu)值函

57、數(shù)，記為指標(biāo)函數(shù)的最優(yōu)值，稱(chēng)為最優(yōu)值函數(shù)，記為f fk k(s(sk k) )，即，即 f fk k(s(sk k)=OptimizationV)=OptimizationVk, nk, n(s(sk k, u, uk k, , s sk+1k+1,s,sn+1n+1) ) u uk k, , u, , un n 3 3最優(yōu)性原理和泛函方程最優(yōu)性原理和泛函方程一、動(dòng)態(tài)規(guī)劃的最優(yōu)性原理一、動(dòng)態(tài)規(guī)劃的最優(yōu)性原理 2020世紀(jì)世紀(jì)5050年代，年代，R.BellmanR.Bellman等人根據(jù)研究等人根據(jù)研究一類(lèi)多階段決策問(wèn)題，提出了最優(yōu)性原理。一類(lèi)多階段決策問(wèn)題，提出了最優(yōu)性原理。 動(dòng)態(tài)規(guī)劃的最優(yōu)

58、性原理動(dòng)態(tài)規(guī)劃的最優(yōu)性原理：一個(gè)（整個(gè)過(guò)程一個(gè)（整個(gè)過(guò)程的）最優(yōu)策略所具有的性質(zhì)是，不論過(guò)去的）最優(yōu)策略所具有的性質(zhì)是，不論過(guò)去的狀態(tài)和決策如何，其余下的諸決策必構(gòu)的狀態(tài)和決策如何，其余下的諸決策必構(gòu)成一個(gè)最優(yōu)子策略。成一個(gè)最優(yōu)子策略。動(dòng)態(tài)規(guī)劃的最優(yōu)性原理動(dòng)態(tài)規(guī)劃的最優(yōu)性原理利用最優(yōu)性原理，可以把多階段決策問(wèn)題利用最優(yōu)性原理，可以把多階段決策問(wèn)題的求解過(guò)程看成是一個(gè)連續(xù)的遞推過(guò)程，的求解過(guò)程看成是一個(gè)連續(xù)的遞推過(guò)程，由后向前逐步推算（因條件不同，也可能由后向前逐步推算（因條件不同，也可能由前向后推算）。在求解時(shí)，各狀態(tài)前面由前向后推算）。在求解時(shí)，各狀態(tài)前面的狀態(tài)和決策對(duì)其后面的子問(wèn)題來(lái)說(shuō)，只

59、的狀態(tài)和決策對(duì)其后面的子問(wèn)題來(lái)說(shuō)，只不過(guò)相當(dāng)于其初始條件而已，并不影響后不過(guò)相當(dāng)于其初始條件而已，并不影響后面過(guò)程的最優(yōu)策略。面過(guò)程的最優(yōu)策略。為了利用最優(yōu)性原理求解多階段決策問(wèn)題，為了利用最優(yōu)性原理求解多階段決策問(wèn)題，還要導(dǎo)出一些遞推公式，便于運(yùn)算。還要導(dǎo)出一些遞推公式，便于運(yùn)算。二、泛函方程二、泛函方程在最短路的計(jì)算中，若記在最短路的計(jì)算中，若記f fk k(s(sk k) )表示第表示第k k階段階段處于狀態(tài)處于狀態(tài)s sk k時(shí)到終點(diǎn)的最短距離，時(shí)到終點(diǎn)的最短距離，d dk k(s(sk k, , u uk k(s(sk k) )表示從狀態(tài)表示從狀態(tài)s sk k到由決策到由決策u uk

60、 k(s(sk k) )所決定的所決定的狀態(tài)狀態(tài)s sk+1k+1之間的距離，則有下列遞推關(guān)系式之間的距離，則有下列遞推關(guān)系式 f fn+1n+1(s(sn+1n+1)=0)=0 f fk k(s(sk k)=mind)=mindk k(s(sk k, u, uk k(s(sk k) + f) + fk+1k+1(s(sk+1k+1) ) k=n,n-1,2,1k=n,n-1,2,1 u uk kDDk k(s(sk k) ) 泛函方程泛函方程一般地，所有動(dòng)態(tài)規(guī)劃過(guò)程之間的相似性一般地，所有動(dòng)態(tài)規(guī)劃過(guò)程之間的相似性在于，構(gòu)造一組特殊類(lèi)型泛函方程，稱(chēng)為在于，構(gòu)造一組特殊類(lèi)型泛函方程，稱(chēng)為遞推關(guān)系