多目標(biāo)規(guī)劃課件

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

2、目標(biāo)問題矛盾如何協(xié)調(diào)的問題，標(biāo)問題矛盾如何協(xié)調(diào)的問題，1896年，年，Pareto首次從數(shù)學(xué)角度提出了多目標(biāo)首次從數(shù)學(xué)角度提出了多目標(biāo)最優(yōu)決策問題，直到二十世紀(jì)最優(yōu)決策問題，直到二十世紀(jì)50-70年年代代Charnes, 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)工程等科技的各個領(lǐng)域?？萍嫉母鱾€領(lǐng)域。1多目標(biāo)規(guī)劃問題舉例多目標(biāo)規(guī)劃問題舉例例例1生產(chǎn)計劃問題生產(chǎn)計劃問題 某工廠計劃生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)每件

3、某工廠計劃生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)每件甲的利潤為甲的利潤為4元，生產(chǎn)每件乙的利潤為元，生產(chǎn)每件乙的利潤為3元，元，每件甲的加工時間為每件乙的兩倍，若全部每件甲的加工時間為每件乙的兩倍，若全部時間用來加工乙，則每日可生產(chǎn)乙時間用來加工乙，則每日可生產(chǎn)乙500件，但件，但工廠每日供給的原料只夠生產(chǎn)甲和乙的總數(shù)工廠每日供給的原料只夠生產(chǎn)甲和乙的總數(shù)共共400件，產(chǎn)品甲是緊俏商品，預(yù)測市場日需件，產(chǎn)品甲是緊俏商品，預(yù)測市場日需求量為求量為300件。決策者希望制定一個日生產(chǎn)方件。決策者希望制定一個日生產(chǎn)方案，不僅能得到最大的利潤，且能最大地滿案，不僅能得到最大的利潤，且能最大地滿足市場需求。足市場需求。

4、生產(chǎn)計劃問題生產(chǎn)計劃問題問題分析問題分析 設(shè)每日生產(chǎn)甲、乙的數(shù)量分別為設(shè)每日生產(chǎn)甲、乙的數(shù)量分別為x1, x2, 令令X=(x1, x2), 則其目標(biāo)函數(shù)為利潤則其目標(biāo)函數(shù)為利潤 f1(X)=4x1 + 3x2 甲的產(chǎn)量甲的產(chǎn)量 f2(X)=x1 都取最大值都取最大值 滿足約束條件滿足約束條件 x1 + x2400（原料供應(yīng)約束）（原料供應(yīng)約束） 2x1 + x2500（加工時間約束）（加工時間約束） x10，x20多目標(biāo)規(guī)劃問題舉例多目標(biāo)規(guī)劃問題舉例例例2投資問題投資問題假設(shè)在一段時間內(nèi)有假設(shè)在一段時間內(nèi)有a（億元）的資金（億元）的資金可用于建廠投資，若可供選擇的項目可用于建廠投資，若可供選

5、擇的項目記為記為1,2,m, 而且一旦對第而且一旦對第i個項目投個項目投資，則必須用掉資，則必須用掉ai（億元）（億元）; 而在這段而在這段時間內(nèi)這第個項目可得到的收益為時間內(nèi)這第個項目可得到的收益為ci（億元）（億元）, 其中其中i=1,2,m, 問如何確定問如何確定最佳的投資方案？最佳的投資方案？投資問題投資問題問題分析問題分析上述要求的最佳方案應(yīng)為：投資少，收益大。上述要求的最佳方案應(yīng)為：投資少，收益大。 mixxaxaxcxxxfxaxxxfiixiimiiimiiimmiiimi,.,2,1,0)1(,),.,(,),.,(01112121211且且要要滿滿足足下下列列約約束束條條件

6、件取取最最大大而而最最小小問問題題即即求求個個項項目目不不投投資資若若對對第第個個項項目目投投資資若若決決定定對對第第設(shè)設(shè)多目標(biāo)規(guī)劃的標(biāo)準(zhǔn)形式多目標(biāo)規(guī)劃的標(biāo)準(zhǔn)形式V-min F(X)=(f1(X), f2(X),fp(X)T s.t. gi(X)0, i=1,2,m 其中其中X=(x1,x2,xn)T, p2 這里這里V-min 是指對向量形式的是指對向量形式的p個目標(biāo)個目標(biāo)(f1(X), f2(X),fp(X)T求最小。求最小。一般假設(shè)多目標(biāo)規(guī)劃中的目標(biāo)函數(shù)已一般假設(shè)多目標(biāo)規(guī)劃中的目標(biāo)函數(shù)已經(jīng)是規(guī)范化了的。經(jīng)是規(guī)范化了的。2 多目標(biāo)規(guī)劃解的概念與性質(zhì)多目標(biāo)規(guī)劃解的概念與性質(zhì)1. 多目標(biāo)規(guī)劃解

7、的概念多目標(biāo)規(guī)劃解的概念例例3解解分別對單個目標(biāo)求出其最優(yōu)解，對于第分別對單個目標(biāo)求出其最優(yōu)解，對于第一個目標(biāo)的最優(yōu)解一個目標(biāo)的最優(yōu)解x(1)=1; 第二個目標(biāo)的最優(yōu)第二個目標(biāo)的最優(yōu)解解x(2)=1, 為同一點，取為同一點，取x*=1作為多目標(biāo)問題作為多目標(biāo)問題的最優(yōu)解，其目標(biāo)函數(shù)值的最優(yōu)解，其目標(biāo)函數(shù)值F*(x) =(-2,-1). 可以用變量空間和目標(biāo)函數(shù)空間來分別描可以用變量空間和目標(biāo)函數(shù)空間來分別描述各種解的情況。述各種解的情況。RxxFVRxxxxxfxxxf )(min,2 , 0213210)(,42)(221求求設(shè)設(shè)多目標(biāo)規(guī)劃解的概念多目標(biāo)規(guī)劃解的概念下面考察例下面考察例1中生

8、產(chǎn)計劃問題。問：是否能找到中生產(chǎn)計劃問題。問：是否能找到一個可行解一個可行解X*=(x1*, x2*)T使之同時為使之同時為f1(X)與與f2(X)的最大解？的最大解？在可行域內(nèi)容易求解在可行域內(nèi)容易求解 max f1(X)的唯一最優(yōu)解為的唯一最優(yōu)解為 (100, 300), 見圖中見圖中B點。點。 max f2(X)的唯一最優(yōu)解為的唯一最優(yōu)解為 (250, 0), 見圖中見圖中C點。點。 由此可得共同的最優(yōu)解由此可得共同的最優(yōu)解X*并不存在。當(dāng)一目標(biāo)并不存在。當(dāng)一目標(biāo)達(dá)到最優(yōu)時，另一目標(biāo)達(dá)不到最優(yōu)，兩目標(biāo)相互達(dá)到最優(yōu)時，另一目標(biāo)達(dá)不到最優(yōu)，兩目標(biāo)相互矛盾。因此需要根據(jù)別的原則，權(quán)衡兩者之間的

9、矛盾。因此需要根據(jù)別的原則，權(quán)衡兩者之間的得失，從得失，從R中找出滿意的方案來。中找出滿意的方案來。多目標(biāo)規(guī)劃解的概念多目標(biāo)規(guī)劃解的概念 如何比較方案的好壞呢？如何比較方案的好壞呢？ 就上述問題，設(shè)就上述問題，設(shè)XR，YR，稱，稱X比比Y好好（或（或Y比比X劣），若劣），若 f1(X)f1(Y) f2(X) f2(Y) 或或 f1(X)f1(Y) f2(X) f2(Y) 不難得到除線段不難得到除線段BC之外的其余之外的其余R上的點均為上的點均為劣解，而劣解，而BC上無劣解，且兩兩無法比較，上無劣解，且兩兩無法比較，因此決策者只有根據(jù)某些別的考慮從因此決策者只有根據(jù)某些別的考慮從BC上上挑選出滿

10、意的方案來。這時稱挑選出滿意的方案來。這時稱BC上的點為上的點為非劣解非劣解，或，或有效解有效解。多目標(biāo)規(guī)劃解的概念多目標(biāo)規(guī)劃解的概念對于一般的多目標(biāo)規(guī)劃問題：對于一般的多目標(biāo)規(guī)劃問題： (VP) V-min F(X)=(f1(X), f2(X),fp(X)T s.t. gi(X)0, i=1,2,m其中其中X=(x1,x2,xn)T, p2設(shè)設(shè)R=X| gi(X)0, i=1,2,m定義定義1 設(shè)設(shè)X*R，若對任意，若對任意j=1,2,p, 以及任意以及任意XR均有均有 fj(X)fj(X*), j=1,2,p 則稱則稱X*為問題為問題(VP)的的絕對最優(yōu)解絕對最優(yōu)解。最優(yōu)解的全。最優(yōu)解的全

11、體記為體記為Rab*多目標(biāo)規(guī)劃解的概念多目標(biāo)規(guī)劃解的概念對于無絕對最優(yōu)解的情況，引進(jìn)下面的對于無絕對最優(yōu)解的情況，引進(jìn)下面的偏好關(guān)系偏好關(guān)系：設(shè)設(shè)F1=(f11, f21, ,fp1)T, F2=(f12, f22, ,fp2)T(1)F1F2意味著意味著F1每個分量都嚴(yán)格小于每個分量都嚴(yán)格小于F2的相應(yīng)分量，即的相應(yīng)分量，即fj1fj2, j=1,2,p(2)F1F2等價于等價于fj1fj2, j=1,2,p，且至，且至少存在某個少存在某個j0 (1j0p), 使使fj01fj02(3)F1F2等價于等價于fj1fj2, j=1,2,p多目標(biāo)規(guī)劃解的概念多目標(biāo)規(guī)劃解的概念定義定義2 設(shè)設(shè)X*

12、R，若不存在，若不存在XR滿足滿足F(X)F(X*), 則稱則稱X*為問題為問題(VP)的的有效解有效解（或或Pareto解解）。有效解的全體記為）。有效解的全體記為Rpa*定義定義3 設(shè)設(shè)X*R，若不存在，若不存在XR滿足滿足F(X)F(X*), 則稱則稱X*為問題為問題(VP)的的弱有效解弱有效解（或弱或弱Pareto解解）。弱有效解的全體記為）。弱有效解的全體記為Rwp*多目標(biāo)規(guī)劃解的性質(zhì)多目標(biāo)規(guī)劃解的性質(zhì)記記Rj*為單目標(biāo)問題為單目標(biāo)問題(Pj) min fj(X) s.t. gi(X)0, i=1,2,m的最優(yōu)解集合，的最優(yōu)解集合，j=1,2,p，可見，可見而而R，Rab*，Rpa*

13、，Rwp*，R1*, Rp*之間的之間的關(guān)系有下列圖示。并有下列定理。關(guān)系有下列圖示。并有下列定理。*1*jpjabRR 多目標(biāo)規(guī)劃解的性質(zhì)多目標(biāo)規(guī)劃解的性質(zhì)*321paabwpjwppaRRRRRRR 定定理理定定理理定定理理多目標(biāo)規(guī)劃解的性質(zhì)多目標(biāo)規(guī)劃解的性質(zhì)定義定義4 如果如果f1(X), f2(X),fp(X)和和g1(X), g2(X),gm(X)均為凸函數(shù)，則稱多目均為凸函數(shù)，則稱多目標(biāo)數(shù)學(xué)規(guī)劃（標(biāo)數(shù)學(xué)規(guī)劃（VP）為）為凸多目標(biāo)數(shù)學(xué)規(guī)劃凸多目標(biāo)數(shù)學(xué)規(guī)劃。一般來說，即使（一般來說，即使（VP）為凸多目標(biāo)數(shù)）為凸多目標(biāo)數(shù)學(xué)規(guī)劃，學(xué)規(guī)劃，Rwp*和和Rpa*也不一定為凸集。也不一定為凸集

14、。多目標(biāo)規(guī)劃解的性質(zhì)多目標(biāo)規(guī)劃解的性質(zhì)2. 多目標(biāo)規(guī)劃問題的像集多目標(biāo)規(guī)劃問題的像集 在（在（VP）中，取定一可行解）中，取定一可行解X0R，可得，可得到其相應(yīng)的目標(biāo)函數(shù)值到其相應(yīng)的目標(biāo)函數(shù)值 F(X0)=( f1(X0), , fp(X0)T 此為此為EP空間中的一個點，從而確定了從空間中的一個點，從而確定了從X到到F(X)的一個映射，即的一個映射，即 F XF(X)F(X) 集合集合F(R)=F(X) |XR稱為約束集合稱為約束集合R在映在映射射F之下的像集。之下的像集。多目標(biāo)規(guī)劃解的性質(zhì)多目標(biāo)規(guī)劃解的性質(zhì)一般來說，即使（一般來說，即使（VP）是凸多目標(biāo)規(guī)劃，）是凸多目標(biāo)規(guī)劃，像集像集F(

15、R)也不一定為凸集（見例也不一定為凸集（見例3）。）。但是，當(dāng)目標(biāo)函數(shù)但是，當(dāng)目標(biāo)函數(shù)f1(X), f2(X),fp(X)為為線性函數(shù)，約束集合線性函數(shù)，約束集合R為凸多面體時，可為凸多面體時，可以證明：像集以證明：像集F(R)為為EP中的凸多面體。中的凸多面體。多目標(biāo)規(guī)劃解的性質(zhì)多目標(biāo)規(guī)劃解的性質(zhì) 對于像集對于像集F(R)，還可以定義有效點及弱有效，還可以定義有效點及弱有效點。點。定義定義5 設(shè)設(shè)F*F(R)，若不存在，若不存在FF(R)，滿足，滿足 FF* 則稱則稱F*為像集為像集F(R)的的有效點有效點，有效點的全體，有效點的全體記為記為Epa*.定義定義6 設(shè)設(shè)F*F(R)，若不存在，

16、若不存在FF(R)，滿足，滿足 FF* 則稱則稱F*為像集為像集F(R)的的弱有效點弱有效點，弱有效點的，弱有效點的全體記為全體記為Ewp*.多目標(biāo)規(guī)劃解的性質(zhì)多目標(biāo)規(guī)劃解的性質(zhì)類似地可證明：像集類似地可證明：像集F(R)的有效點一的有效點一定是弱有效點，即定是弱有效點，即通過在像集通過在像集F(R)上尋找有效點（或弱上尋找有效點（或弱有效點），就可以確定約束集合有效點），就可以確定約束集合R上上的有效解（或弱有效解）。對此，有的有效解（或弱有效解）。對此，有如下的定理。如下的定理。*wppaEE 多目標(biāo)規(guī)劃解的性質(zhì)多目標(biāo)規(guī)劃解的性質(zhì)定理定理4 在像集在像集F(R)上，若上，若Epa*已知，則

17、在約已知，則在約束集合束集合R上，有上，有定理定理5 在像集在像集F(R)上，若上，若Ewp*已知，則在約已知，則在約束集合束集合R上，有上，有另外通過對像集的研究，可以更直觀地認(rèn)另外通過對像集的研究，可以更直觀地認(rèn)識問題，并且可以提供一些處理多目標(biāo)規(guī)識問題，并且可以提供一些處理多目標(biāo)規(guī)劃的方法。劃的方法。),(|*RXXFFXRpaEFpa ),(|*RXXFFXRwpEFwp 3處理多目標(biāo)規(guī)劃的一些方法處理多目標(biāo)規(guī)劃的一些方法在在2中，注意到，要使多目標(biāo)規(guī)劃中，注意到，要使多目標(biāo)規(guī)劃（VP）中所有子目標(biāo)同時實現(xiàn)最優(yōu)經(jīng)）中所有子目標(biāo)同時實現(xiàn)最優(yōu)經(jīng)常是不可解的，那么如何制定比較標(biāo)常是不可解的，

18、那么如何制定比較標(biāo)準(zhǔn)在（弱）有效解集中找到滿意解呢？準(zhǔn)在（弱）有效解集中找到滿意解呢？處理多目標(biāo)規(guī)劃的一些方法處理多目標(biāo)規(guī)劃的一些方法3.1 約束法（主要目標(biāo)法）約束法（主要目標(biāo)法） 在目標(biāo)函數(shù)在目標(biāo)函數(shù)f1(X), f2(X),fp(X)中，選中，選出其中的一個作為主要目標(biāo)，如出其中的一個作為主要目標(biāo)，如f1(X), 而其它的目標(biāo)而其它的目標(biāo)f2(X),fp(X)只要滿足一只要滿足一定的條件即可。定的條件即可。處理多目標(biāo)規(guī)劃的一些方法處理多目標(biāo)規(guī)劃的一些方法如如fj(X)fj0, j=2,p， pjfXfmiXgXfmiXgXRXffjjiijRXj,.,2,)(,.,2 , 1, 0)()

19、(min:,.,2 , 1, 0)(|)(min010單單目目標(biāo)標(biāo)規(guī)規(guī)劃劃問問題題劃劃問問題題化化為為下下面面的的于于是是可可以以把把原原來來的的多多規(guī)規(guī)這這里里處理多目標(biāo)規(guī)劃的一些方法處理多目標(biāo)規(guī)劃的一些方法3.2 分層序列法分層序列法 把（把（VP）中的）中的p個目標(biāo)個目標(biāo)f1(X), f2(X),fp(X)按按其重要性排一個次序；分為最重要目標(biāo)、次其重要性排一個次序；分為最重要目標(biāo)、次要目標(biāo)等等。不妨設(shè)要目標(biāo)等等。不妨設(shè)p個目標(biāo)責(zé)任制的重要性個目標(biāo)責(zé)任制的重要性序列為序列為 f1(X), f2(X),fp(X) 首先求第一個目標(biāo)首先求第一個目標(biāo)f1(X)的最優(yōu)解的最優(yōu)解 (P1) min

20、 f1(X) XR 設(shè)其最優(yōu)值為設(shè)其最優(yōu)值為f1*，再求第二個目標(biāo)的最優(yōu)解，再求第二個目標(biāo)的最優(yōu)解處理多目標(biāo)規(guī)劃的一些方法處理多目標(biāo)規(guī)劃的一些方法(P2) min f2(X) XR1 其中其中R1=RX |f1(X)f1* 其最優(yōu)值為其最優(yōu)值為f2*，然后求第三個目標(biāo)的最優(yōu)解，然后求第三個目標(biāo)的最優(yōu)解 (P3) min f3(X) XR2 其中其中R2=R1X |f2(X)f2* 求得最優(yōu)值為求得最優(yōu)值為f3*,，最后求第，最后求第p個目標(biāo)的最優(yōu)解個目標(biāo)的最優(yōu)解 (Pp) min fp(X) XR p-1 其中其中Rp-1=Rp-2X |fp-1(X)fp-1*處理多目標(biāo)規(guī)劃的一些方法處理多目

21、標(biāo)規(guī)劃的一些方法此時求得最優(yōu)解此時求得最優(yōu)解X*，最優(yōu)值為，最優(yōu)值為fp*，則，則X*就是多目標(biāo)問題就是多目標(biāo)問題(VP)在分層序列意在分層序列意義下的最優(yōu)解。進(jìn)一步有下列定理。義下的最優(yōu)解。進(jìn)一步有下列定理。定理定理6 設(shè)設(shè)X*是由分層序列法所得到的是由分層序列法所得到的最優(yōu)解，則最優(yōu)解，則X*Rpa*.處理多目標(biāo)規(guī)劃的一些方法處理多目標(biāo)規(guī)劃的一些方法證明證明用反證法證明。用反證法證明。 假設(shè)假設(shè)X*不不Rpa*，則必存在，則必存在YR，使，使 F(Y)F(X*) 下面分兩種情形討論：下面分兩種情形討論：(1)若若f1(Y)f1(X*), 而而f1(X*)=f1*, 故得故得(P1)的可的可

22、行解行解Y滿足滿足 f1(Y)f1(X*)=f1* 此與此與f1*=min f1(X)相矛盾。相矛盾。 XR處理多目標(biāo)規(guī)劃的一些方法處理多目標(biāo)規(guī)劃的一些方法(2)若若fj(Y)= fj(X*), j=1,2,j0-1 但但fj0(Y)fj0(X*) 2j0p 此時必有此時必有fj(Y)= fj(X*)fj*, j=1,2,j0-1 因此，因此，Y是問題是問題 (Pj0) min fp(X) XRj0-2X |fj0-1(X)fj0-1* 的可行解，又由的可行解，又由 fj0(Y)0, j=1,2,p不妨設(shè)其中不妨設(shè)其中k個個f1(X), f2(X),fk(X)要求實現(xiàn)要求實現(xiàn)最小，其余最小，其

23、余fk+1(X), ,fp(X)要求實現(xiàn)最大，要求實現(xiàn)最大，則可構(gòu)造評價函數(shù)則可構(gòu)造評價函數(shù)然后求然后求min U(F(X) XR)().()().()()(121XfXfXfXfXfXFUpkk 3.4 評價函數(shù)的收斂性評價函數(shù)的收斂性上節(jié)中，用不同的評價函數(shù)上節(jié)中，用不同的評價函數(shù)U(F(X)將將多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃(VP)轉(zhuǎn)化為單目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題 min U(F(X) XR 來處理，并將其解來處理，并將其解X*作為作為(VP)的解。的解。 而而X*是否為是否為(VP)的有效解或弱有效解的有效解或弱有效解呢？呢？評價函數(shù)的收斂性評價函數(shù)的收斂性定義定義7 若對任意若對任意F, FE

24、p, 當(dāng)當(dāng)FF時，時，都有都有 U(F)U(F) 成立，則稱成立，則稱U(F)是是F的的嚴(yán)格單調(diào)增函數(shù)嚴(yán)格單調(diào)增函數(shù)。定義定義8 若對任意若對任意F, FEp, 當(dāng)當(dāng)FF時，時，都有都有 U(F)U(F) 成立，則稱成立，則稱U(F)是是F的的單調(diào)增函數(shù)單調(diào)增函數(shù)。評價函數(shù)的收斂性評價函數(shù)的收斂性定理定理8 若對若對FEp，U(F)是嚴(yán)格單調(diào)增函數(shù)，則單是嚴(yán)格單調(diào)增函數(shù)，則單目標(biāo)問題目標(biāo)問題 min U(F(X) XR 的最優(yōu)解的最優(yōu)解X*Rpa*證明證明用反證法。用反證法。 若若X*不不Rpa*，即存在，即存在YR，使，使 F(Y)F(X*) 由由U(F)的嚴(yán)格單調(diào)性，有的嚴(yán)格單調(diào)性，有 U

25、(F(Y)0，j=1,2,p時，時，U(F)為嚴(yán)格單調(diào)增函數(shù)。為嚴(yán)格單調(diào)增函數(shù)。 這是因為，若這是因為，若j0，j=1,2,p, 且且F0，于，于是是 j0fj00，j=1,2,p時，對時，對FF，則，則 jfjjfj j=1,2,p 由由FF，則則至少存在某個至少存在某個j0(1j0p)，使，使 fj0fj0 從而從而 j0fj0j0fj0 相加得相加得 ) ()(11FUffFUpjjjpjjj 評價函數(shù)的收斂性評價函數(shù)的收斂性2. 平方和加權(quán)法平方和加權(quán)法 U(F)為為F的嚴(yán)格單調(diào)增函數(shù)。的嚴(yán)格單調(diào)增函數(shù)。pjffffFUjjjpjjjpjjj,.,2 , 1, 0, 1)()(0120

26、1 這這里里評價函數(shù)的收斂性評價函數(shù)的收斂性這是因為，若這是因為，若FF，由于，由于FF0，F(xiàn)F0，故，故 0fj-fj0fj-fj0 j=1,2,p 且至少存在某個且至少存在某個j0(1j0p)，有，有 fj-fj0fj-fj0 從而從而 j0fj0j0fj0 故故U(F)0，j=1,2,p. 這是因為，若這是因為，若FF，則對，則對j=1,2,p, 均有均有 fjfj 于是，若記于是，若記 j0fj0= max jfj 1jp 則則 U(F)=max jfj =j0fj00, j=1,2,p 可證可證U(G)為為G的嚴(yán)格單調(diào)增函數(shù)。的嚴(yán)格單調(diào)增函數(shù)。jpjjjjpkkgGUFUpjkfkj

27、fgfffffFU1121)()(111.)( 化為化為則評價函數(shù)則評價函數(shù)當(dāng)當(dāng)當(dāng)當(dāng)令令評價函數(shù)的收斂性評價函數(shù)的收斂性這是因為，若這是因為，若GG，則由，則由G0, G0及及 gjgj j=1,2,p 且至少存在某個且至少存在某個j0(1j0p)使使 gj00),2,3,5求求得的最優(yōu)解得的最優(yōu)解 X*Rpa*而由方法而由方法1(j0)，4得到的最優(yōu)解得到的最優(yōu)解 X*Rwp*3.5 逐步法逐步法（交替式對話方法）（交替式對話方法）由于問題的復(fù)雜性，有時決策者所提供的由于問題的復(fù)雜性，有時決策者所提供的信息不足以使分析者確定各目標(biāo)函數(shù)之間信息不足以使分析者確定各目標(biāo)函數(shù)之間的關(guān)系，因此需要在

28、決策者和分析者之間的關(guān)系，因此需要在決策者和分析者之間建立一種交互式的對話方法（如建立一種交互式的對話方法（如Step Method, STEM, 逐步法），分析者根據(jù)決逐步法），分析者根據(jù)決策者提供的信息（經(jīng)修改和補(bǔ)充后的）給策者提供的信息（經(jīng)修改和補(bǔ)充后的）給出中間結(jié)果，決策者對中間結(jié)果發(fā)表意見，出中間結(jié)果，決策者對中間結(jié)果發(fā)表意見，可根據(jù)中間結(jié)果進(jìn)一步提供信息，讓分析可根據(jù)中間結(jié)果進(jìn)一步提供信息，讓分析者重新計算，直到求得滿意解為止。者重新計算，直到求得滿意解為止。逐步法逐步法下面介紹多目標(biāo)線性規(guī)劃中的下面介紹多目標(biāo)線性規(guī)劃中的STEM步驟步驟: 求求 V-min F(X)=(f1(X)

29、, f2(X),fp(X)T XR0,|,.,2 , 1,)(1 XbAXXRpixcXfnjjiji設(shè)設(shè)逐步法逐步法1.求求p個線性規(guī)劃的最優(yōu)解個線性規(guī)劃的最優(yōu)解 min fi(X) = fi(X(i) = fi* i=1,2,p XR 令令 fimax max fi(X(j) i=1,2,p 1jp 顯然顯然 fimaxfi* i=1,2,p 不妨設(shè)不完全取等號。不妨設(shè)不完全取等號。逐步法逐步法2.決策者不能給出加權(quán)系數(shù)決策者不能給出加權(quán)系數(shù)，分析者只好，分析者只好根據(jù)函數(shù)根據(jù)函數(shù)fi(X)和和R的性質(zhì)給出一種算法：的性質(zhì)給出一種算法： 0)(10)(1,.,2 , 1*12*max*12

30、max*max12121injijiiiinjijiiiipjjiifcffffcfffpi當(dāng)當(dāng)當(dāng)當(dāng)其中其中令令 逐步法逐步法3. 求線性規(guī)劃求線性規(guī)劃 的最優(yōu)解的最優(yōu)解(X(0), t(0) RXpitfXftPiii,.,2 , 1)(min)(*0 逐步法逐步法4. 決策者對決策者對F(X(0)與與F*=(f1*,fp*)T進(jìn)行比較，若進(jìn)行比較，若對對X(0)比較滿意，則迭代停止；否則，對最滿意的比較滿意，則迭代停止；否則，對最滿意的fj0(X(0)提出允許變大的上限提出允許變大的上限fj0, 而對其它而對其它fi(X)(ij0)則不允許變大，因此把則不允許變大，因此把(P0)改成求改成

31、求 的最優(yōu)解的最優(yōu)解(X(1), t(1)。 RXjipiXfXffXfXfjipitfXftPiijjjiii0)0(0)0(000*1,.,2 , 1)()()()(,.,2 , 1)(min)( 逐步法逐步法若對若對X(1)仍不滿意，則可用這種思想在仍不滿意，則可用這種思想在(P1)中添加新的約束，或修改中添加新的約束，或修改fj的值，的值，再求新的解，這種交互式對話進(jìn)行若再求新的解，這種交互式對話進(jìn)行若干次，直到?jīng)Q策者滿意為止。干次，直到?jīng)Q策者滿意為止。第六章第六章 動態(tài)規(guī)劃動態(tài)規(guī)劃 動態(tài)規(guī)劃（動態(tài)規(guī)劃（Dynamic Programming）是最優(yōu)化的一個分支。是最優(yōu)化的一個分支。1

32、951年美國數(shù)年美國數(shù)學(xué)家學(xué)家R.Bellman（貝爾曼）等人根據(jù)一（貝爾曼）等人根據(jù)一類多階段決策問題的特性，提出了解類多階段決策問題的特性，提出了解決這類問題的決這類問題的“最優(yōu)性原理最優(yōu)性原理”，并研，并研究了許多實際問題，從而建立了最優(yōu)究了許多實際問題，從而建立了最優(yōu)化的一個分支化的一個分支動態(tài)規(guī)劃。動態(tài)規(guī)劃。動態(tài)規(guī)劃動態(tài)規(guī)劃 動態(tài)規(guī)劃把比較復(fù)雜的問題劃分成若干階段，通動態(tài)規(guī)劃把比較復(fù)雜的問題劃分成若干階段，通過逐段求解，最終求得全局最優(yōu)解。特別對于離過逐段求解，最終求得全局最優(yōu)解。特別對于離散性問題，由于解析數(shù)學(xué)無法運(yùn)用，動態(tài)規(guī)劃就散性問題，由于解析數(shù)學(xué)無法運(yùn)用，動態(tài)規(guī)劃就成為非常有

33、效的工具。然而動態(tài)規(guī)劃目前還存在成為非常有效的工具。然而動態(tài)規(guī)劃目前還存在以下弱點：以下弱點：1）動態(tài)規(guī)劃沒有一個統(tǒng)一的算法，它）動態(tài)規(guī)劃沒有一個統(tǒng)一的算法，它必須針對各種問題的性質(zhì)，利用最優(yōu)性原理得出必須針對各種問題的性質(zhì)，利用最優(yōu)性原理得出函數(shù)方程后，再結(jié)合其它數(shù)學(xué)技巧來求解，而沒函數(shù)方程后，再結(jié)合其它數(shù)學(xué)技巧來求解，而沒有一種統(tǒng)一的處理方法，從而我們稱動態(tài)規(guī)劃是有一種統(tǒng)一的處理方法，從而我們稱動態(tài)規(guī)劃是一種方法。一種方法。2）當(dāng)變數(shù)的個數(shù)（維數(shù)）太大時，這）當(dāng)變數(shù)的個數(shù)（維數(shù)）太大時，這類問題雖可以用動態(tài)規(guī)劃來描述，但由于計算機(jī)類問題雖可以用動態(tài)規(guī)劃來描述，但由于計算機(jī)存貯容量和計算機(jī)速

34、度的限制，使問題無法解決，存貯容量和計算機(jī)速度的限制，使問題無法解決，此即所謂此即所謂“維數(shù)障礙維數(shù)障礙”。動態(tài)規(guī)劃動態(tài)規(guī)劃 動態(tài)規(guī)劃根據(jù)多階段決策過程的時間動態(tài)規(guī)劃根據(jù)多階段決策過程的時間參量是離散的還是連續(xù)的和其決策過參量是離散的還是連續(xù)的和其決策過程的演變是確定性的還是隨機(jī)的，可程的演變是確定性的還是隨機(jī)的，可以分為離散確定性、離散隨機(jī)性、連以分為離散確定性、離散隨機(jī)性、連續(xù)確定性、連續(xù)隨機(jī)性四種決策過程續(xù)確定性、連續(xù)隨機(jī)性四種決策過程模型。模型。1多階段決策問題及實例多階段決策問題及實例所謂多階段決策問題，是指一類活動過程，所謂多階段決策問題，是指一類活動過程，它可以分為互相聯(lián)系的若干

35、個階段，在每它可以分為互相聯(lián)系的若干個階段，在每一階段都需要作出決策，從而使整個過程一階段都需要作出決策，從而使整個過程達(dá)到最優(yōu)的活動效果。因此，各個階段決達(dá)到最優(yōu)的活動效果。因此，各個階段決策的選取常依賴于當(dāng)前面臨的狀態(tài)，又影策的選取常依賴于當(dāng)前面臨的狀態(tài)，又影響下一個階段的決策，從而影響整個過程響下一個階段的決策，從而影響整個過程的活動路線，這種把一個問題看成一個前的活動路線，這種把一個問題看成一個前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程多階段決策過程，也稱，也稱序貫決策過程序貫決策過程。多階段決策問題及實例多階段決策問題及實例各個階段的決策

36、確定以后就構(gòu)成一個決策各個階段的決策確定以后就構(gòu)成一個決策序列，稱為一個策略。由于每一個階段可序列，稱為一個策略。由于每一個階段可供選擇的決策不止一個，因而對應(yīng)于整個供選擇的決策不止一個，因而對應(yīng)于整個活動過程就有許多策略選擇采用，從中選活動過程就有許多策略選擇采用，從中選出一個效果最好的為最優(yōu)策略。在多階段出一個效果最好的為最優(yōu)策略。在多階段決策問題中，既然引入了階段的概念，也決策問題中，既然引入了階段的概念，也就與時間密不可分，決策過程從一個狀態(tài)就與時間密不可分，決策過程從一個狀態(tài)到另一個狀態(tài)，隨著時間的變化在變化，到另一個狀態(tài)，隨著時間的變化在變化，也就有了也就有了“動態(tài)動態(tài)”的含義。有

37、一些問題表的含義。有一些問題表面上處來與時間無關(guān)，只要人為地引入面上處來與時間無關(guān)，只要人為地引入“時間時間”因素，也可以變?yōu)橄聜€多階段決因素，也可以變?yōu)橄聜€多階段決策問題，用動態(tài)規(guī)劃方法來處理。策問題，用動態(tài)規(guī)劃方法來處理。多階段決策問題及實例多階段決策問題及實例例例1 最短路線問題最短路線問題AB1B2C1C2C3C4D1E1F1GD2D3E2E3F2531368766835338422123335526643437597681310912131618多階段決策問題及實例多階段決策問題及實例例例2 多階段資源分配問題多階段資源分配問題某工廠生產(chǎn)某工廠生產(chǎn)A, B和和C三種產(chǎn)品，都要使用某種

38、原材三種產(chǎn)品，都要使用某種原材料，原材料共有料，原材料共有4噸。將不同數(shù)量的這種原料分配噸。將不同數(shù)量的這種原料分配給各種產(chǎn)品時產(chǎn)生收益如下表（單位：萬元），試給各種產(chǎn)品時產(chǎn)生收益如下表（單位：萬元），試確定使總收益最大的分配法。確定使總收益最大的分配法。 原料的分配量原料的分配量 產(chǎn)品種類產(chǎn)品種類 （噸）（噸） A B C 0 0 0 0 1 10 6 8 2 17 17 11 3 20 18 -2動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念一、最短路線問題的解一、最短路線問題的解 首先討論最短路線問題的求解方法首先討論最短路線問題的求解方法 解法一解法一枚舉法枚舉法 48條不同路線條不同路線 48

39、6=2886=288步加法步加法 47次路線長度的比較次路線長度的比較 最短路長為最短路長為18最短路線問題的解最短路線問題的解解法二解法二共有共有6個階段個階段 記記f1(A) A到到G的最短距離的最短距離 則則 f1(A)依賴于依賴于f2(B1), f2(B2), 而而f6(F1)=4, f6(F2)=3 故由后向前寫出相應(yīng)公式的形式。故由后向前寫出相應(yīng)公式的形式。 解法二稱為逆推解法（逆序解法）解法二稱為逆推解法（逆序解法）最短路線問題的解最短路線問題的解上面的做法極其簡單，從中我們可以上面的做法極其簡單，從中我們可以處到這樣一個規(guī)律，即最短路線必須處到這樣一個規(guī)律，即最短路線必須且只能

40、由最短子路線組成，在求且只能由最短子路線組成，在求A到到G的最短路線時，附帶求得了從所有中的最短路線時，附帶求得了從所有中間頂點到間頂點到G的最短路，它們是作為整的最短路，它們是作為整個問題的子問題出現(xiàn)的，并且被嵌入個問題的子問題出現(xiàn)的，并且被嵌入較大問題之中，這常常是動態(tài)規(guī)劃方較大問題之中，這常常是動態(tài)規(guī)劃方法的一個特點。法的一個特點。二、動態(tài)規(guī)劃的基本概念二、動態(tài)規(guī)劃的基本概念(1)階段階段(Stage) 對所給問題的過程，根據(jù)時間和空對所給問題的過程，根據(jù)時間和空間的自然特征，恰當(dāng)?shù)貏澐譃槿舾蓚€間的自然特征，恰當(dāng)?shù)貏澐譃槿舾蓚€相互聯(lián)系的階段，以便能按一定的次相互聯(lián)系的階段，以便能按一定的

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

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

43、最優(yōu)控制中也稱為控制。描述決策的變量稱為決策變量，常用策的變量稱為決策變量，常用uk(sk)表示第表示第k個階段當(dāng)狀態(tài)處于個階段當(dāng)狀態(tài)處于sk時的決策變量，它是狀時的決策變量，它是狀態(tài)變量的函數(shù)。決策變量的取值范圍稱為態(tài)變量的函數(shù)。決策變量的取值范圍稱為允許決策集合，常用允許決策集合，常用Dk(sk)表示第表示第k階段從階段從狀態(tài)狀態(tài)sk出發(fā)的允許決策集合，有出發(fā)的允許決策集合，有uk(sk)Dk(sk)。動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念(4)策略策略(Policy)策略是一個按順序排列的決策序列，用策略是一個按順序排列的決策序列，用 pk,n(sk)=uk(sk), uk+1(sk+1)

44、, un(sn) 表示從第表示從第k階段階段sk狀態(tài)開始到終止的決狀態(tài)開始到終止的決策序列，稱為策序列，稱為 k子過程策略；當(dāng)子過程策略；當(dāng)k=1時，時，即為全過程的一個策略，簡稱策略。即為全過程的一個策略，簡稱策略。動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念(5)狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。在第到另一個狀態(tài)的演變過程。在第k階段階段當(dāng)狀態(tài)處于當(dāng)狀態(tài)處于sk時，若該段的決策變量時，若該段的決策變量uk一經(jīng)確定，則第一經(jīng)確定，則第k+1階段的狀態(tài)變量階段的狀態(tài)變量sk+1的值也就隨之確定，從而的值也就隨之確定，從而sk

45、+1的值的值隨隨sk和和uk的值變化而變化，記為的值變化而變化，記為sk+1=Tk(sk, uk)，稱為狀態(tài)轉(zhuǎn)移方程。，稱為狀態(tài)轉(zhuǎn)移方程。動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念(6)指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)和最優(yōu)值函數(shù) 指標(biāo)函數(shù)是用以衡量多階段決策過程實現(xiàn)效果的指標(biāo)函數(shù)是用以衡量多階段決策過程實現(xiàn)效果的一種數(shù)量指標(biāo)，用一種數(shù)量指標(biāo)，用Vk, n表示，即表示，即 Vk, n=Vk, n(sk, uk, sk+1,sn+1)，k=1,2,n 指標(biāo)函數(shù)應(yīng)具有可分離性，并滿足遞推關(guān)系指標(biāo)函數(shù)應(yīng)具有可分離性，并滿足遞推關(guān)系 Vk, n(sk, uk, sk+1,sn+1)=k(sk, uk,Vk+1,

46、 n(sk+1,sn+1)指標(biāo)函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)，記為指標(biāo)函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)，記為fk(sk)，即即 fk(sk)=OptimizationVk, n(sk, uk, sk+1,sn+1) uk, , un3最優(yōu)性原理和泛函方程最優(yōu)性原理和泛函方程一、動態(tài)規(guī)劃的最優(yōu)性原理一、動態(tài)規(guī)劃的最優(yōu)性原理 20世紀(jì)世紀(jì)50年代，年代，R.Bellman等人根據(jù)研究一等人根據(jù)研究一類多階段決策問題，提出了最優(yōu)性原理。類多階段決策問題，提出了最優(yōu)性原理。 動態(tài)規(guī)劃的最優(yōu)性原理動態(tài)規(guī)劃的最優(yōu)性原理：一個（整個過程的）一個（整個過程的）最優(yōu)策略所具有的性質(zhì)是，不論過去的狀最優(yōu)策略所具有的性質(zhì)

47、是，不論過去的狀態(tài)和決策如何，其余下的諸決策必構(gòu)成一態(tài)和決策如何，其余下的諸決策必構(gòu)成一個最優(yōu)子策略。個最優(yōu)子策略。動態(tài)規(guī)劃的最優(yōu)性原理動態(tài)規(guī)劃的最優(yōu)性原理利用最優(yōu)性原理，可以把多階段決策問題利用最優(yōu)性原理，可以把多階段決策問題的求解過程看成是一個連續(xù)的遞推過程，的求解過程看成是一個連續(xù)的遞推過程，由后向前逐步推算（因條件不同，也可能由后向前逐步推算（因條件不同，也可能由前向后推算）。在求解時，各狀態(tài)前面由前向后推算）。在求解時，各狀態(tài)前面的狀態(tài)和決策對其后面的子問題來說，只的狀態(tài)和決策對其后面的子問題來說，只不過相當(dāng)于其初始條件而已，并不影響后不過相當(dāng)于其初始條件而已，并不影響后面過程的最優(yōu)

48、策略。面過程的最優(yōu)策略。為了利用最優(yōu)性原理求解多階段決策問題，為了利用最優(yōu)性原理求解多階段決策問題，還要導(dǎo)出一些遞推公式，便于運(yùn)算。還要導(dǎo)出一些遞推公式，便于運(yùn)算。二、泛函方程二、泛函方程在最短路的計算中，若記在最短路的計算中，若記fk(sk)表示第表示第k階段階段處于狀態(tài)處于狀態(tài)sk時到終點的最短距離，時到終點的最短距離，dk(sk, uk(sk)表示從狀態(tài)表示從狀態(tài)sk到由決策到由決策uk(sk)所決定的狀態(tài)所決定的狀態(tài)sk+1之間的距離，則有下列遞推關(guān)系式之間的距離，則有下列遞推關(guān)系式 fn+1(sn+1)=0 fk(sk)=mindk(sk, uk(sk) + fk+1(sk+1) k

49、=n,n-1,2,1 ukDk(sk) 泛函方程泛函方程一般地，所有動態(tài)規(guī)劃過程之間的相似性一般地，所有動態(tài)規(guī)劃過程之間的相似性在于，構(gòu)造一組特殊類型泛函方程，稱為在于，構(gòu)造一組特殊類型泛函方程，稱為遞推關(guān)系，這些遞推關(guān)系使得我們能夠以遞推關(guān)系，這些遞推關(guān)系使得我們能夠以簡單的方式從簡單的方式從fk+1(sk+1)算出算出fk(sk)，典型的指，典型的指標(biāo)函數(shù)可以為標(biāo)函數(shù)可以為“和和”的形式或的形式或“積積”的形的形式。式。 上述遞推關(guān)系式即為極小化的泛函方程，上述遞推關(guān)系式即為極小化的泛函方程，且指標(biāo)函數(shù)為和的形式，當(dāng)其中的加號改且指標(biāo)函數(shù)為和的形式，當(dāng)其中的加號改為乘號時，即轉(zhuǎn)化為積的形式

50、。為乘號時，即轉(zhuǎn)化為積的形式。三、動態(tài)規(guī)劃的基本方法三、動態(tài)規(guī)劃的基本方法用動態(tài)規(guī)劃求解實際問題時，為了遵循動態(tài)規(guī)劃用動態(tài)規(guī)劃求解實際問題時，為了遵循動態(tài)規(guī)劃的最優(yōu)性原理，需要將實際問題轉(zhuǎn)化為動態(tài)規(guī)劃的最優(yōu)性原理，需要將實際問題轉(zhuǎn)化為動態(tài)規(guī)劃的數(shù)學(xué)模型，一般按下列步驟進(jìn)行：的數(shù)學(xué)模型，一般按下列步驟進(jìn)行：(1)根據(jù)時間或空間的自然特征，將問題劃分為恰根據(jù)時間或空間的自然特征，將問題劃分為恰當(dāng)?shù)碾A段當(dāng)?shù)碾A段(2)正確選擇狀態(tài)變量正確選擇狀態(tài)變量sk，使其既能方便描述過程的，使其既能方便描述過程的演變，又能滿足無后效性演變，又能滿足無后效性(3)確定決策變量確定決策變量uk及每個階段的允許決策集合

51、及每個階段的允許決策集合Dk(sk)(4)寫出狀態(tài)轉(zhuǎn)移方程寫出狀態(tài)轉(zhuǎn)移方程sk+1=Tk(sk, uk)動態(tài)規(guī)劃的基本方法動態(tài)規(guī)劃的基本方法(5)正確寫出指標(biāo)函數(shù)正確寫出指標(biāo)函數(shù)Vk, n，其應(yīng)滿足下列三個性質(zhì)，其應(yīng)滿足下列三個性質(zhì) a)是定義在全過程和所有后部子過程上的數(shù)量函是定義在全過程和所有后部子過程上的數(shù)量函數(shù)數(shù) b)具有可分離性，并滿足遞推關(guān)系，即具有可分離性，并滿足遞推關(guān)系，即 Vk, n(sk, uk, sk+1,sn+1)=k(sk, uk,Vk+1, n(sk+1,sn+1) c)函數(shù)函數(shù)k(sk, uk,Vk+1, n(sk+1,sn+1)對變量對變量Vk+1, n要嚴(yán)要嚴(yán)

52、格單調(diào)。格單調(diào)。4 函數(shù)空間與策略空間迭代法函數(shù)空間與策略空間迭代法多階段決策問題其階段數(shù)有可能是固多階段決策問題其階段數(shù)有可能是固定的，也有可能不是固定的，此時可定的，也有可能不是固定的，此時可用泛函方程來求解。用泛函方程來求解。設(shè)有設(shè)有N個點，以個點，以1, 2, , N記之，任兩記之，任兩點點 i, j之間的長度為之間的長度為Cij, 當(dāng)當(dāng)i, j間有一弧間有一弧直接連接時，直接連接時，0Cij+, 當(dāng)當(dāng)i, j間不直接間不直接連接它們的弧時，連接它們的弧時，Cij=+. 今設(shè)今設(shè)N為終為終點，求任一點點，求任一點i至終點至終點N的最短距離。的最短距離。函數(shù)空間與策略空間迭代法函數(shù)空間與

53、策略空間迭代法定義定義f(i)為由為由i點出發(fā)至終點點出發(fā)至終點N的最短距的最短距離，則由最優(yōu)性原理可得離，則由最優(yōu)性原理可得 f(i) = min(Cij + f(j), i=1,2,N-1 f(N)=0這樣的泛函方程不是遞推方程，而且這樣的泛函方程不是遞推方程，而且f(i)出現(xiàn)在方程的兩邊，不能通過簡單出現(xiàn)在方程的兩邊，不能通過簡單的遞推求得結(jié)果。的遞推求得結(jié)果。 下面用兩種迭代法來求解。下面用兩種迭代法來求解。1、函數(shù)空間迭代法、函數(shù)空間迭代法設(shè)設(shè)fk(i)表示由表示由i點出發(fā)向點出發(fā)向N走走k步所構(gòu)成的所步所構(gòu)成的所有路線中的最短距離。有路線中的最短距離。 函數(shù)空間迭代法求解步驟如下：

54、函數(shù)空間迭代法求解步驟如下： 1f1(i) = CiN, i=1,2,N-1 f1(N)=0 2fk(i) = min(Cij + fk-1(j), i=1,2,N-1 j fk(N)=0 3反復(fù)迭代反復(fù)迭代2直到直到fk(i) = fk+1(i) = =f(i) 為止，為止，i=1,2,N函數(shù)空間迭代法函數(shù)空間迭代法可以證明：可以證明： (1)由上述步驟確定的函數(shù)序列由上述步驟確定的函數(shù)序列fk(i) 不超過不超過N-1步單調(diào)下降收斂于問題的最步單調(diào)下降收斂于問題的最優(yōu)函數(shù)優(yōu)函數(shù)f(i) (2)若若0Cij0)xi0, i=1,2,3動態(tài)規(guī)劃的解法及應(yīng)用舉例動態(tài)規(guī)劃的解法及應(yīng)用舉例例例2用動

55、態(tài)規(guī)劃解下列問題（用動態(tài)規(guī)劃解下列問題（P332） max z=8x1 + 7x2 2x1 + x28 5x1 + 2x215 x1, x2為非負(fù)整數(shù)為非負(fù)整數(shù)動態(tài)規(guī)劃的解法及應(yīng)用舉例動態(tài)規(guī)劃的解法及應(yīng)用舉例解解用逆序解法，將問題分為兩個階段，對應(yīng)用逆序解法，將問題分為兩個階段，對應(yīng)狀態(tài)變量：狀態(tài)變量：vj, wj分別為第分別為第j階段，第一、第二約束階段，第一、第二約束可供分配的右端數(shù)值可供分配的右端數(shù)值決策變量：決策變量：x1,x2，于是，于是f2*(v2,w2)=max7x2=7minv2, w2/2 0 x2v2 0 2x2 w2 x2取整數(shù)取整數(shù)f1*(v1,w1)=max8x1+

56、f2*(v1-2x1,w1-5x1) 02x1v1 0 5x1 w1 x1取整數(shù)取整數(shù)而而v1=8, w1=15,所以所以動態(tài)規(guī)劃的解法及應(yīng)用舉例動態(tài)規(guī)劃的解法及應(yīng)用舉例f1*(8,15)=max8x1+ 7min(8-2x1,(15-5x1)/2) 02x18 0 5x1 15 x1取整數(shù)取整數(shù)由于由于x1 min(8/2,15/5)=3, 因而因而f1*(8,15)=max8x1+ 7min(8-2x1,(15-5x1)/2) x1=0,1,2,3 =max8x1+ 7(15-5x1)/2=49 x1=0,1,2,3x1*=0由由v2=v1-2x1=8, w2=w1-5x1=15, 得得x

57、2*= min8, 15/2=7最優(yōu)解為最優(yōu)解為x1*=0, x2*= 7, z*=49動態(tài)規(guī)劃的解法及應(yīng)用舉例動態(tài)規(guī)劃的解法及應(yīng)用舉例1例例2 多階段資源分配問題多階段資源分配問題某工廠生產(chǎn)某工廠生產(chǎn)A, B和和C三種產(chǎn)品，都要使用某種原材三種產(chǎn)品，都要使用某種原材料，原材料共有料，原材料共有4噸。將不同數(shù)量的這種原料分配噸。將不同數(shù)量的這種原料分配給各種產(chǎn)品時產(chǎn)生收益如下表（單位：萬元），試給各種產(chǎn)品時產(chǎn)生收益如下表（單位：萬元），試確定使總收益最大的分配法。確定使總收益最大的分配法。 原料分配量原料分配量 產(chǎn)品種類產(chǎn)品種類 （噸）（噸） A B C 0 0 0 0 1 10 6 8 2

58、17 17 11 3 20 18 -動態(tài)規(guī)劃的解法及應(yīng)用舉例動態(tài)規(guī)劃的解法及應(yīng)用舉例下面求下面求1中的例中的例2，將資源分配劃分，將資源分配劃分為三個階段，分配給生產(chǎn)產(chǎn)品為三個階段，分配給生產(chǎn)產(chǎn)品A，B，C的數(shù)量設(shè)為的數(shù)量設(shè)為x1,x2,x3，其狀態(tài)，其狀態(tài)(資源剩資源剩余量余量)s1=4, s2=s1-x1, s3=s2-x2, sn+1=s4=0.現(xiàn)列表計算如下：現(xiàn)列表計算如下：動態(tài)規(guī)劃的解法及應(yīng)用舉例動態(tài)規(guī)劃的解法及應(yīng)用舉例由上述表知，最大總收益等于由上述表知，最大總收益等于35，最，最優(yōu)決策序列是優(yōu)決策序列是x1*=1, x2*=2, x3*=1動態(tài)規(guī)劃的解法及應(yīng)用舉例動態(tài)規(guī)劃的解法及應(yīng)用舉例例例3 資源連續(xù)分配問題：資源連續(xù)分配問題：設(shè)有數(shù)量為設(shè)有數(shù)量為s1的某種資源，可投入生產(chǎn)的某種資源，可投入生產(chǎn)A和和B兩兩種產(chǎn)品，第一年若以數(shù)量種產(chǎn)品，第一年若以數(shù)量u1投入生產(chǎn)投入生產(chǎn)A，剩下的，剩下的s1-u1投入生產(chǎn)投入生產(chǎn)B，其收入為，其收入為g(u1)+h(s1-u1)，這里，這里g(0)=h(0)=0，在，在A、B生產(chǎn)后，資源的回收率分生產(chǎn)后，資源的回收率分別為別為0a1, 0bai時時 t工件工件i-1t-ai+bi排序問題排序問題得到得到 記