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

最優(yōu)化多目標(biāo)規(guī)劃動態(tài)規(guī)劃第五章多目標(biāo)規(guī)劃早在1772年，F(xiàn)ranklin就提出了多目標(biāo)問題矛盾如何協(xié)調(diào)的問題，1896年，Pareto首次從數(shù)學(xué)角度提出了多目標(biāo)最優(yōu)決策問題，直到二十世紀(jì)50-70年代Charnes,Karlin,Zadeh等人先后做了許多較有影響的工作，多目標(biāo)規(guī)劃受到人們的關(guān)注。至今多目標(biāo)規(guī)劃已廣泛應(yīng)用于經(jīng)濟(jì)、管理、系統(tǒng)工程等科技的各個領(lǐng)域?！?多目標(biāo)規(guī)劃問題舉例例1生產(chǎn)計劃問題某工廠計劃生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)每件甲的利潤為4元，生產(chǎn)每件乙的利潤為3元，每件甲的加工時間為每件乙的兩倍，若全部時間用來加工乙，則每日可生產(chǎn)乙500件，但工廠每日供給的原料只夠生產(chǎn)甲和乙的總數(shù)共400件，產(chǎn)品甲是緊俏商品，預(yù)測市場日需求量為300件。決策者希望制定一個日生產(chǎn)方案，不僅能得到最大的利潤，且能最大地滿足市場需求。生產(chǎn)計劃問題[問題分析]設(shè)每日生產(chǎn)甲、乙的數(shù)量分別為x1,x2,令X=(x1,x2),則其目標(biāo)函數(shù)為利潤f1(X)=4x1+3x2甲的產(chǎn)量f2(X)=x1

都取最大值滿足約束條件x1+x2≤400（原料供應(yīng)約束）2x1+x2≤500（加工時間約束）x1≥0，x2≥0多目標(biāo)規(guī)劃問題舉例例2投資問題假設(shè)在一段時間內(nèi)有a（億元）的資金可用于建廠投資，若可供選擇的項目記為1,2,…,m,而且一旦對第i個項目投資，則必須用掉ai（億元）;而在這段時間內(nèi)這第個項目可得到的收益為ci（億元）,其中i=1,2,…,m,問如何確定最佳的投資方案？投資問題[問題分析]上述要求的最佳方案應(yīng)為：投資少，收益大。多目標(biāo)規(guī)劃的標(biāo)準(zhǔn)形式V-minF(X)=(f1(X),f2(X),…,fp(X))Ts.t.gi(X)≤0,i=1,2,…,m其中X=(x1,x2,…,xn)T,p≥2這里V-min是指對向量形式的p個目標(biāo)(f1(X),f2(X),…,fp(X))T求最小。一般假設(shè)多目標(biāo)規(guī)劃中的目標(biāo)函數(shù)已經(jīng)是規(guī)范化了的。§2多目標(biāo)規(guī)劃解的概念與性質(zhì)1.多目標(biāo)規(guī)劃解的概念例3[解]分別對單個目標(biāo)求出其最優(yōu)解，對于第一個目標(biāo)的最優(yōu)解x(1)=1;第二個目標(biāo)的最優(yōu)解x(2)=1,為同一點(diǎn)，取x*=1作為多目標(biāo)問題的最優(yōu)解，其目標(biāo)函數(shù)值F*(x)=(-2,-1).可以用變量空間和目標(biāo)函數(shù)空間來分別描述各種解的情況。多目標(biāo)規(guī)劃解的概念下面考察例1中生產(chǎn)計劃問題。問：是否能找到一個可行解X*=(x1*,x2*)T使之同時為f1(X)與f2(X)的最大解？在可行域內(nèi)容易求解maxf1(X)的唯一最優(yōu)解為(100,300),見圖中B點(diǎn)。maxf2(X)的唯一最優(yōu)解為(250,0),見圖中C點(diǎn)。由此可得共同的最優(yōu)解X*并不存在。當(dāng)一目標(biāo)達(dá)到最優(yōu)時，另一目標(biāo)達(dá)不到最優(yōu)，兩目標(biāo)相互矛盾。因此需要根據(jù)別的原則，權(quán)衡兩者之間的得失，從R中找出滿意的方案來。多目標(biāo)規(guī)劃解的概念如何比較方案的好壞呢？就上述問題，設(shè)X∈R，Y∈R，稱X比Y好（或Y比X劣），若f1(X)>f1(Y)f2(X)≥f2(Y)或f1(X)≥f1(Y)f2(X)>f2(Y)不難得到除線段BC之外的其余R上的點(diǎn)均為劣解，而BC上無劣解，且兩兩無法比較，因此決策者只有根據(jù)某些別的考慮從BC上挑選出滿意的方案來。這時稱BC上的點(diǎn)為非劣解，或有效解。多目標(biāo)規(guī)劃解的概念對于一般的多目標(biāo)規(guī)劃問題：(VP)V-minF(X)=(f1(X),f2(X),…,fp(X))Ts.t.gi(X)≤0,i=1,2,…,m其中X=(x1,x2,…,xn)T,p≥2設(shè)R={X|gi(X)≤0,i=1,2,…,m}定義1設(shè)X*∈R，若對任意j=1,2,…,p,以及任意X∈R均有fj(X)≥fj(X*),j=1,2,…,p則稱X*為問題(VP)的絕對最優(yōu)解。最優(yōu)解的全體記為Rab*多目標(biāo)規(guī)劃解的概念對于無絕對最優(yōu)解的情況，引進(jìn)下面的偏好關(guān)系：設(shè)F1=(f11,f21,…,fp1)T,F2=(f12,f22,…,fp2)T(1)F1<F2意味著F1每個分量都嚴(yán)格小于F2的相應(yīng)分量，即fj1<fj2,j=1,2,…,p(2)F1≤F2等價于fj1≤fj2,j=1,2,…,p，且至少存在某個j0(1≤j0≤p),使fj01<fj02(3)F1≦F2等價于fj1≤fj2,j=1,2,…,p多目標(biāo)規(guī)劃解的概念定義2設(shè)X*∈R，若不存在X∈R滿足F(X)≤F(X*),則稱X*為問題(VP)的有效解（或Pareto解）。有效解的全體記為Rpa*定義3設(shè)X*∈R，若不存在X∈R滿足F(X)<F(X*),則稱X*為問題(VP)的弱有效解（或弱Pareto解）。弱有效解的全體記為Rwp*多目標(biāo)規(guī)劃解的性質(zhì)記Rj*為單目標(biāo)問題(Pj)minfj(X)s.t.gi(X)≤0,i=1,2,…,m的最優(yōu)解集合，j=1,2,…,p，可見而R，Rab*，Rpa*，Rwp*，R1*,…,Rp*之間的關(guān)系有下列圖示。并有下列定理。多目標(biāo)規(guī)劃解的性質(zhì)多目標(biāo)規(guī)劃解的性質(zhì)定義4如果f1(X),f2(X),…,fp(X)和g1(X),g2(X),…,gm(X)均為凸函數(shù)，則稱多目標(biāo)數(shù)學(xué)規(guī)劃（VP）為凸多目標(biāo)數(shù)學(xué)規(guī)劃。一般來說，即使（VP）為凸多目標(biāo)數(shù)學(xué)規(guī)劃，Rwp*和Rpa*也不一定為凸集。多目標(biāo)規(guī)劃解的性質(zhì)2.多目標(biāo)規(guī)劃問題的像集在（VP）中，取定一可行解X0∈R，可得到其相應(yīng)的目標(biāo)函數(shù)值F(X0)=(f1(X0),…,fp(X0))T此為EP空間中的一個點(diǎn)，從而確定了從X到F(X)的一個映射，即

FX——→F(X)集合F(R)={F(X)|X∈R}稱為約束集合R在映射F之下的像集。多目標(biāo)規(guī)劃解的性質(zhì)一般來說，即使（VP）是凸多目標(biāo)規(guī)劃，像集F(R)也不一定為凸集（見例3）。但是，當(dāng)目標(biāo)函數(shù)f1(X),f2(X),…,fp(X)為線性函數(shù)，約束集合R為凸多面體時，可以證明：像集F(R)為EP中的凸多面體。多目標(biāo)規(guī)劃解的性質(zhì)對于像集F(R)，還可以定義有效點(diǎn)及弱有效點(diǎn)。定義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)，滿足F<F*則稱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上的有效解（或弱有效解）。對此，有如下的定理。多目標(biāo)規(guī)劃解的性質(zhì)定理4在像集F(R)上，若Epa*已知，則在約束集合R上，有定理5在像集F(R)上，若Ewp*已知，則在約束集合R上，有另外通過對像集的研究，可以更直觀地認(rèn)識問題，并且可以提供一些處理多目標(biāo)規(guī)劃的方法?！?處理多目標(biāo)規(guī)劃的一些方法在§2中，注意到，要使多目標(biāo)規(guī)劃（VP）中所有子目標(biāo)同時實(shí)現(xiàn)最優(yōu)經(jīng)常是不可解的，那么如何制定比較標(biāo)準(zhǔn)在（弱）有效解集中找到滿意解呢？處理多目標(biāo)規(guī)劃的一些方法3.1約束法（主要目標(biāo)法）在目標(biāo)函數(shù)f1(X),f2(X),…,fp(X)中，選出其中的一個作為主要目標(biāo)，如f1(X),而其它的目標(biāo)f2(X),…,fp(X)只要滿足一定的條件即可。處理多目標(biāo)規(guī)劃的一些方法如fj(X)≤fj0,j=2,…,p，處理多目標(biāo)規(guī)劃的一些方法3.2分層序列法把（VP）中的p個目標(biāo)f1(X),f2(X),…,fp(X)按其重要性排一個次序；分為最重要目標(biāo)、次要目標(biāo)等等。不妨設(shè)p個目標(biāo)責(zé)任制的重要性序列為f1(X),f2(X),…,fp(X)首先求第一個目標(biāo)f1(X)的最優(yōu)解(P1)minf1(X)

X∈R設(shè)其最優(yōu)值為f1*，再求第二個目標(biāo)的最優(yōu)解處理多目標(biāo)規(guī)劃的一些方法(P2)minf2(X)

X∈R1其中R1=R∩{X|f1(X)≤f1*}其最優(yōu)值為f2*，然后求第三個目標(biāo)的最優(yōu)解(P3)minf3(X)

X∈R2其中R2=R1∩{X|f2(X)≤f2*}求得最優(yōu)值為f3*,…，最后求第p個目標(biāo)的最優(yōu)解(Pp)minfp(X)

X∈R

p-1其中Rp-1=Rp-2∩{X|fp-1(X)≤fp-1*}處理多目標(biāo)規(guī)劃的一些方法此時求得最優(yōu)解X*，最優(yōu)值為fp*，則X*就是多目標(biāo)問題(VP)在分層序列意義下的最優(yōu)解。進(jìn)一步有下列定理。定理6設(shè)X*是由分層序列法所得到的最優(yōu)解，則X*∈Rpa*.處理多目標(biāo)規(guī)劃的一些方法[證明]用反證法證明。假設(shè)X*不∈Rpa*，則必存在Y∈R，使F(Y)≤F(X*)下面分兩種情形討論：(1)若f1(Y)<f1(X*),而f1(X*)=f1*,故得(P1)的可行解Y滿足f1(Y)<f1(X*)=f1*此與f1*=minf1(X)相矛盾。

X∈R處理多目標(biāo)規(guī)劃的一些方法(2)若fj(Y)=fj(X*),j=1,2,…,j0-1但fj0(Y)<fj0(X*)2≤j0≤p此時必有fj(Y)=fj(X*)≤fj*,j=1,2,…,j0-1因此，Y是問題(Pj0)minfp(X)X∈Rj0-2∩{X|fj0-1(X)≤fj0-1*}的可行解，又由fj0(Y)<fj0(X*)≤fj0*此與fj0*是問題(Pj0)的最優(yōu)值相矛盾。綜合(1)(2),定理得證。處理多目標(biāo)規(guī)劃的一些方法3.3評價函數(shù)法直接求解多目標(biāo)規(guī)劃問題是比較困難的，有一類方法是通過構(gòu)造一個評價函數(shù)（或效用函數(shù)）U(F(X))將多目標(biāo)規(guī)劃問題(VP)轉(zhuǎn)化為單目標(biāo)規(guī)劃問題minU(F(X))

X∈R然后求解該問題，并將其最優(yōu)解X*作為(VP)的最優(yōu)解。由于構(gòu)造評價函數(shù)的多種多樣，也就出現(xiàn)了多種不同的評價函數(shù)方法。處理多目標(biāo)規(guī)劃的一些方法1.線性加權(quán)和法對(VP)中的p個目標(biāo)f1(X),f2(X),…,fp(X)按其重要程度給以適當(dāng)?shù)臋?quán)系數(shù)λj≥0(j=1,2,…,p),且∑λj=1，然后構(gòu)造評價函數(shù)目標(biāo)函數(shù)是一種和的形式，這里要求所有應(yīng)具有相同量綱，若量綱不同，必須進(jìn)行統(tǒng)一量綱或無量綱化處理。處理多目標(biāo)規(guī)劃的一些方法問題的難點(diǎn)是如何確定合理的權(quán)系數(shù)。(1)“老手法”(2)α-方法處理多目標(biāo)規(guī)劃的一些方法2.平方和加權(quán)法對單目標(biāo)規(guī)劃問題(Pj)minfj(X)j=1,2,…,pX∈R求出一個盡可能好的下界f10,…,fp0（可看成是規(guī)定值），minfj(X)≥fj0j=1,2,…,pX∈R處理多目標(biāo)規(guī)劃的一些方法構(gòu)造評價函數(shù)然后求minU(F(X))

X∈R

求得最優(yōu)解X*作為多目標(biāo)規(guī)劃的解。處理多目標(biāo)規(guī)劃的一些方法3.理想點(diǎn)法（虛擬點(diǎn)法）先求p

個單目標(biāo)規(guī)劃問題的最優(yōu)解，記fj*=fj(X(j))=minfj(X)j=1,2,…,p

X∈R若所有X(j)(j=1,2,…,p)都相同，設(shè)為X*，則X*為多目標(biāo)函數(shù)的絕對最優(yōu)解，但一般不易達(dá)到，因此向量F*=(f1*,f2*,…,fp*)只是一個理想點(diǎn)。處理多目標(biāo)規(guī)劃的一些方法Cалуквалзе（1975）提出的理想點(diǎn)，其中心思想是定義一個模，在這個模的意義下，找一個點(diǎn)盡量接近理想點(diǎn)F*，即求minU(F(X))=min||F(X)-F*||X∈RX∈R處理多目標(biāo)規(guī)劃的一些方法一般定義處理多目標(biāo)規(guī)劃的一些方法例4設(shè)f1(X)=3x1-2x2,f2(X)=-4x1-3x2,約束集R={X|2x1+3x2≤18,2x1+x2≤10,x1≥0,x2≥0}試用理想點(diǎn)法求解V-minF(X)=(f1(X),f2(X))T

X∈R[解]先分別對單目標(biāo)求出最優(yōu)解X(1)=(0,6)T,X(2)=(3,4)T,對應(yīng)的目標(biāo)函數(shù)值為f1(X(1))=f1*=-12,f2(X(2))=f2*=-24,故理想點(diǎn)為F*=(f1*,f2*)T=(-12,-24)T處理多目標(biāo)規(guī)劃的一些方法取q=2,此時要求可解得最優(yōu)解X*=(0.53,5.65)T,對應(yīng)的目標(biāo)函數(shù)值分別為f1*=-9.72,f2*=-19.06,其解空間、像空間如圖。處理多目標(biāo)規(guī)劃的一些方法4.極小極大法（協(xié)調(diào)矛盾法）在對策論中，常常在作決策時要考慮：“在最不利情況下找出一個最有利”的策略，即所謂“min-max”，依此，令評價函數(shù)U(F(X))=maxfj(X)

1≤j≤p然后求minU(F(X))的最優(yōu)解，設(shè)為X*

X∈R評價函數(shù)也可以采用賦權(quán)的形式，即令(Q)minU(F(X))=min{maxλjfj(X)}

X∈RX∈R1≤j≤p其中λj≥0(j=1,2,…,p)是一組權(quán)系數(shù)。處理多目標(biāo)規(guī)劃的一些方法對于極小極大問題，可以用增加一個變量t及p個約束的方法將其化為通常的數(shù)學(xué)規(guī)劃模型。有下面等價的定理。定理7設(shè)（X*，t*）為的最優(yōu)解，則X*必為(Q)的最優(yōu)解；反之，設(shè)X*為(Q)的最優(yōu)解，令t*=maxλjfj(X*)，則(X*，t*）必為(Qt)的最優(yōu)解。

1≤j≤p處理多目標(biāo)規(guī)劃的一些方法[證明]設(shè)(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≤p1≤j≤p即X*為(Q)的最優(yōu)解。處理多目標(biāo)規(guī)劃的一些方法反之，設(shè)X*為(Q)的最優(yōu)解，最小值為maxλjfj(X*)≡t*1≤j≤p易見(X*,t*)是(Qt)的可行解。設(shè)(X,t)為(Qt)的任一可行解，由λjfj(X)≤t,j=1,2,…,p,X∈R知maxλjfj(X)≤t對任意X∈R1≤j≤p由此t*=maxλjfj(X*)≤maxλjfj(X)≤t

1≤j≤p1≤j≤p即t*為(Qt)的最小值，(X*，t*）為(Qt)的最優(yōu)解。處理多目標(biāo)規(guī)劃的一些方法5.乘除法（幾何平均法）在(VP)中，設(shè)各目標(biāo)函數(shù)值均有fj(X)>0,j=1,2,…,p不妨設(shè)其中k個f1(X),f2(X),…,fk(X)要求實(shí)現(xiàn)最小，其余fk+1(X),…,fp(X)要求實(shí)現(xiàn)最大，則可構(gòu)造評價函數(shù)然后求minU(F(X))

X∈R3.4評價函數(shù)的收斂性上節(jié)中，用不同的評價函數(shù)U(F(X))將多目標(biāo)規(guī)劃(VP)轉(zhuǎn)化為單目標(biāo)問題minU(F(X))

X∈R來處理，并將其解X*作為(VP)的解。而X*是否為(VP)的有效解或弱有效解呢？評價函數(shù)的收斂性定義7若對任意F,F'∈Ep,當(dāng)F≤F'時，都有U(F)<U(F')成立，則稱U(F)是F的嚴(yán)格單調(diào)增函數(shù)。定義8若對任意F,F'∈Ep,當(dāng)F<F'時，都有U(F)<U(F')成立，則稱U(F)是F的單調(diào)增函數(shù)。評價函數(shù)的收斂性定理8若對F∈Ep，U(F)是嚴(yán)格單調(diào)增函數(shù)，則單目標(biāo)問題minU(F(X))

X∈R的最優(yōu)解X*∈Rpa*[證明]用反證法。若X*不∈Rpa*，即存在Y∈R，使F(Y)≤F(X*)由U(F)的嚴(yán)格單調(diào)性，有U(F(Y))<U(F(X*))此與X*是minU(F(X))的最優(yōu)解矛盾。

X∈R評價函數(shù)的收斂性類似地可證得下面的定理。定理9若對F∈Ep，U(F)是單調(diào)增函數(shù)，則單目標(biāo)問題minU(F(X))

X∈R的最優(yōu)解X*∈Rwp*評價函數(shù)的收斂性針對3.3中使用的評價函數(shù)，由分析知均為嚴(yán)格單調(diào)函數(shù)或單調(diào)函數(shù)，從而由定理8和定理9知，求得的X*∈Rpa*或X*∈Rwp*評價函數(shù)的收斂性1.線性加權(quán)和法λj≥0，j=1,2,…,p,且∑λj=1，此時U(F)為單調(diào)增函數(shù)。特別當(dāng)λj>0，j=1,2,…,p時，U(F)為嚴(yán)格單調(diào)增函數(shù)。這是因?yàn)?，若λj≥0，j=1,2,…,p,且F<F'，則λjfj≤λjfj'j=1,2,…,p又由∑λj=1可知，至少存在某個j0(1≤j0≤p)，使λj0>0，于是λj0fj0<λj0fj0'相加得

評價函數(shù)的收斂性特別當(dāng)λj>0，j=1,2,…,p時，對F≤F'，則λjfj≤λjfj'j=1,2,…,p由F≤F'，則至少存在某個j0(1≤j0≤p)，使fj0<fj0'從而λj0fj0<λj0fj0'相加得

評價函數(shù)的收斂性2.平方和加權(quán)法U(F)為F的嚴(yán)格單調(diào)增函數(shù)。評價函數(shù)的收斂性這是因?yàn)?，若F≤F'，由于F≥F0，F(xiàn)'≥F0，故0≤fj-fj0≤fj'-fj0j=1,2,…,p且至少存在某個j0(1≤j0≤p)，有fj-fj0<fj'-fj0

從而λj0fj0<λj0fj0'故U(F)<U(F')即U(F)為F的嚴(yán)格單調(diào)增函數(shù)。評價函數(shù)的收斂性3.理想點(diǎn)法式中fj≥fj*，j=1,2,…,p為F的嚴(yán)格單調(diào)增函數(shù)?？梢苑抡?的證法類似證明。評價函數(shù)的收斂性4.極小極大法U(F)=maxλjfj

1≤j≤p為F的單調(diào)增函數(shù)。這里λj>0，j=1,2,…,p.這是因?yàn)?，若F<F'，則對j=1,2,…,p,均有fj<fj'于是，若記λj0fj0=maxλjfj1≤j≤p則U(F)=maxλjfj=λj0fj0<λj0fj0'≤maxλjfj'=U(F')

1≤j≤p

1≤j≤p評價函數(shù)的收斂性5.乘除法且gj>0,j=1,2,…,p可證U(G)為G的嚴(yán)格單調(diào)增函數(shù)。評價函數(shù)的收斂性這是因?yàn)?，若G≤G'，則由G>0,G'>0及gj≤gj'j=1,2,…,p且至少存在某個j0(1≤j0≤p)使gj0<gj0'則有評價函數(shù)的收斂性由上述討論知：由方法1(λj>0),2,3,5求得的最優(yōu)解X*∈Rpa*而由方法1(λj≥0)，4得到的最優(yōu)解X*∈Rwp*3.5逐步法（交替式對話方法）由于問題的復(fù)雜性，有時決策者所提供的信息不足以使分析者確定各目標(biāo)函數(shù)之間的關(guān)系，因此需要在決策者和分析者之間建立一種交互式的對話方法（如StepMethod,STEM,逐步法），分析者根據(jù)決策者提供的信息（經(jīng)修改和補(bǔ)充后的）給出中間結(jié)果，決策者對中間結(jié)果發(fā)表意見，可根據(jù)中間結(jié)果進(jìn)一步提供信息，讓分析者重新計算，直到求得滿意解為止。逐步法下面介紹多目標(biāo)線性規(guī)劃中的STEM步驟:求V-minF(X)=(f1(X),f2(X),…,fp(X))T

X∈R逐步法1.求p個線性規(guī)劃的最優(yōu)解minfi(X)=fi(X(i))=fi*i=1,2,…,p

X∈R令fimax≡max{fi(X(j))}i=1,2,…,p1≤j≤p顯然fimax≥fi*i=1,2,…,p不妨設(shè)不完全取等號。逐步法2.決策者不能給出加權(quán)系數(shù)λ，分析者只好根據(jù)函數(shù)fi(X)和R的性質(zhì)給出一種算法：逐步法3.求線性規(guī)劃的最優(yōu)解(X(0),t(0))逐步法4.決策者對F(X(0))與F*=(f1*,…,fp*)T進(jìn)行比較，若對X(0)比較滿意，則迭代停止；否則，對最滿意的fj0(X(0))提出允許變大的上限Δfj0,而對其它fi(X)(i≠j0)則不允許變大，因此把(P0)改成求的最優(yōu)解(X(1),t(1))。逐步法若對X(1)仍不滿意，則可用這種思想在(P1)中添加新的約束，或修改Δfj的值，再求新的解，這種交互式對話進(jìn)行若干次，直到?jīng)Q策者滿意為止。第六章動態(tài)規(guī)劃動態(tài)規(guī)劃（DynamicProgramming）是最優(yōu)化的一個分支。1951年美國數(shù)學(xué)家R.Bellman（貝爾曼）等人根據(jù)一類多階段決策問題的特性，提出了解決這類問題的“最優(yōu)性原理”，并研究了許多實(shí)際問題，從而建立了最優(yōu)化的一個分支——動態(tài)規(guī)劃。動態(tài)規(guī)劃動態(tài)規(guī)劃把比較復(fù)雜的問題劃分成若干階段，通過逐段求解，最終求得全局最優(yōu)解。特別對于離散性問題，由于解析數(shù)學(xué)無法運(yùn)用，動態(tài)規(guī)劃就成為非常有效的工具。然而動態(tài)規(guī)劃目前還存在以下弱點(diǎn)：1）動態(tài)規(guī)劃沒有一個統(tǒng)一的算法，它必須針對各種問題的性質(zhì)，利用最優(yōu)性原理得出函數(shù)方程后，再結(jié)合其它數(shù)學(xué)技巧來求解，而沒有一種統(tǒng)一的處理方法，從而我們稱動態(tài)規(guī)劃是一種方法。2）當(dāng)變數(shù)的個數(shù)（維數(shù)）太大時，這類問題雖可以用動態(tài)規(guī)劃來描述，但由于計算機(jī)存貯容量和計算機(jī)速度的限制，使問題無法解決，此即所謂“維數(shù)障礙”。動態(tài)規(guī)劃動態(tài)規(guī)劃根據(jù)多階段決策過程的時間參量是離散的還是連續(xù)的和其決策過程的演變是確定性的還是隨機(jī)的，可以分為離散確定性、離散隨機(jī)性、連續(xù)確定性、連續(xù)隨機(jī)性四種決策過程模型?！?多階段決策問題及實(shí)例所謂多階段決策問題，是指一類活動過程，它可以分為互相聯(lián)系的若干個階段，在每一階段都需要作出決策，從而使整個過程達(dá)到最優(yōu)的活動效果。因此，各個階段決策的選取常依賴于當(dāng)前面臨的狀態(tài)，又影響下一個階段的決策，從而影響整個過程的活動路線，這種把一個問題看成一個前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，也稱序貫決策過程。多階段決策問題及實(shí)例各個階段的決策確定以后就構(gòu)成一個決策序列，稱為一個策略。由于每一個階段可供選擇的決策不止一個，因而對應(yīng)于整個活動過程就有許多策略選擇采用，從中選出一個效果最好的為最優(yōu)策略。在多階段決策問題中，既然引入了階段的概念，也就與時間密不可分，決策過程從一個狀態(tài)到另一個狀態(tài)，隨著時間的變化在變化，也就有了“動態(tài)”的含義。有一些問題表面上處來與時間無關(guān)，只要人為地引入“時間”因素，也可以變?yōu)橄聜€多階段決策問題，用動態(tài)規(guī)劃方法來處理。多階段決策問題及實(shí)例例1最短路線問題AB1B2C1C2C3C4D1E1F1GD2D3E2E3F2531368766835338422123335526643437597681310912131618多階段決策問題及實(shí)例例2多階段資源分配問題某工廠生產(chǎn)A,B和C三種產(chǎn)品，都要使用某種原材料，原材料共有4噸。將不同數(shù)量的這種原料分配給各種產(chǎn)品時產(chǎn)生收益如下表（單位：萬元），試確定使總收益最大的分配法。原料的分配量產(chǎn)品種類（噸）ABC000011068217171132018--§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故由后向前寫出相應(yīng)公式的形式。解法二稱為逆推解法（逆序解法）最短路線問題的解上面的做法極其簡單，從中我們可以處到這樣一個規(guī)律，即最短路線必須且只能由最短子路線組成，在求A到G的最短路線時，附帶求得了從所有中間頂點(diǎn)到G的最短路，它們是作為整個問題的子問題出現(xiàn)的，并且被嵌入較大問題之中，這常常是動態(tài)規(guī)劃方法的一個特點(diǎn)。二、動態(tài)規(guī)劃的基本概念(1)階段(Stage)對所給問題的過程，根據(jù)時間和空間的自然特征，恰當(dāng)?shù)貏澐譃槿舾蓚€相互聯(lián)系的階段，以便能按一定的次序去求解。描述階段的變量稱為階段變量，用k表示。動態(tài)規(guī)劃的基本概念(2)狀態(tài)(State)狀態(tài)表示某階段開始所處的自然狀況（或條件），它既是本階段的起始位置，又是上一階段的終了位置，通常一個階段包含若干個狀態(tài)。描述狀態(tài)的變量稱為狀態(tài)變量，用sk表示第k個階段的狀態(tài)變量，用Sk表示所有可能狀態(tài)的集合。狀態(tài)的選擇不是任意的，必須具有下列性質(zhì)：若某階段狀態(tài)給定后，則在這階段以后過程的發(fā)展不受這以前各階段狀態(tài)的影響，這個性質(zhì)稱為無后效性（即馬爾科夫性）。動態(tài)規(guī)劃的基本概念(3)決策(Decision)決策表示當(dāng)過程處于某一階段的某個狀態(tài)時，可以作出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策。在最優(yōu)控制中也稱為控制。描述決策的變量稱為決策變量，常用uk(sk)表示第k個階段當(dāng)狀態(tài)處于sk時的決策變量，它是狀態(tài)變量的函數(shù)。決策變量的取值范圍稱為允許決策集合，常用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合，有uk(sk)∈Dk(sk)。動態(tài)規(guī)劃的基本概念(4)策略(Policy)策略是一個按順序排列的決策序列，用pk,n(sk)={uk(sk),uk+1(sk+1),…un(sn)}表示從第k階段sk狀態(tài)開始到終止的決策序列，稱為k子過程策略；當(dāng)k=1時，即為全過程的一個策略，簡稱策略。動態(tài)規(guī)劃的基本概念(5)狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。在第k階段當(dāng)狀態(tài)處于sk時，若該段的決策變量uk一經(jīng)確定，則第k+1階段的狀態(tài)變量sk+1的值也就隨之確定，從而sk+1的值隨sk和uk的值變化而變化，記為sk+1=Tk(sk,uk)，稱為狀態(tài)轉(zhuǎn)移方程。動態(tài)規(guī)劃的基本概念(6)指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)是用以衡量多階段決策過程實(shí)現(xiàn)效果的一種數(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)系Vk,n(sk,uk,sk+1,…sn+1)=φk(sk,uk,Vk+1,n(sk+1,…sn+1))指標(biāo)函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)，記為fk(sk)，即fk(sk)=OptimizationVk,n(sk,uk,sk+1,…sn+1){uk,…,un}§3最優(yōu)性原理和泛函方程一、動態(tài)規(guī)劃的最優(yōu)性原理20世紀(jì)50年代，R.Bellman等人根據(jù)研究一類多階段決策問題，提出了最優(yōu)性原理。動態(tài)規(guī)劃的最優(yōu)性原理：一個（整個過程的）最優(yōu)策略所具有的性質(zhì)是，不論過去的狀態(tài)和決策如何，其余下的諸決策必構(gòu)成一個最優(yōu)子策略。動態(tài)規(guī)劃的最優(yōu)性原理利用最優(yōu)性原理，可以把多階段決策問題的求解過程看成是一個連續(xù)的遞推過程，由后向前逐步推算（因條件不同，也可能由前向后推算）。在求解時，各狀態(tài)前面的狀態(tài)和決策對其后面的子問題來說，只不過相當(dāng)于其初始條件而已，并不影響后面過程的最優(yōu)策略。為了利用最優(yōu)性原理求解多階段決策問題，還要導(dǎo)出一些遞推公式，便于運(yùn)算。二、泛函方程在最短路的計算中，若記fk(sk)表示第k階段處于狀態(tài)sk時到終點(diǎn)的最短距離，dk(sk,uk(sk)表示從狀態(tài)sk到由決策uk(sk)所決定的狀態(tài)sk+1之間的距離，則有下列遞推關(guān)系式fn+1(sn+1)=0fk(sk)=min{dk(sk,uk(sk))+fk+1(sk+1)}k=n,n-1,…,2,1uk∈Dk(sk)

泛函方程一般地，所有動態(tài)規(guī)劃過程之間的相似性在于，構(gòu)造一組特殊類型泛函方程，稱為遞推關(guān)系，這些遞推關(guān)系使得我們能夠以簡單的方式從fk+1(sk+1)算出fk(sk)，典型的指標(biāo)函數(shù)可以為“和”的形式或“積”的形式。上述遞推關(guān)系式即為極小化的泛函方程，且指標(biāo)函數(shù)為和的形式，當(dāng)其中的加號改為乘號時，即轉(zhuǎn)化為積的形式。三、動態(tài)規(guī)劃的基本方法用動態(tài)規(guī)劃求解實(shí)際問題時，為了遵循動態(tài)規(guī)劃的最優(yōu)性原理，需要將實(shí)際問題轉(zhuǎn)化為動態(tài)規(guī)劃的數(shù)學(xué)模型，一般按下列步驟進(jìn)行：(1)根據(jù)時間或空間的自然特征，將問題劃分為恰當(dāng)?shù)碾A段(2)正確選擇狀態(tài)變量sk，使其既能方便描述過程的演變，又能滿足無后效性(3)確定決策變量uk及每個階段的允許決策集合Dk(sk)(4)寫出狀態(tài)轉(zhuǎn)移方程sk+1=Tk(sk,uk)動態(tài)規(guī)劃的基本方法(5)正確寫出指標(biāo)函數(shù)Vk,n，其應(yīng)滿足下列三個性質(zhì)a)是定義在全過程和所有后部子過程上的數(shù)量函數(shù)b)具有可分離性，并滿足遞推關(guān)系，即Vk,n(sk,uk,sk+1,…sn+1)=φk(sk,uk,Vk+1,n(sk+1,…sn+1))c)函數(shù)φk(sk,uk,Vk+1,n(sk+1,…sn+1))對變量Vk+1,n要嚴(yán)格單調(diào)?！?函數(shù)空間與策略空間迭代法多階段決策問題其階段數(shù)有可能是固定的，也有可能不是固定的，此時可用泛函方程來求解。設(shè)有N個點(diǎn)，以1,2,…,N記之，任兩點(diǎn)i,j之間的長度為Cij,當(dāng)i,j間有一弧直接連接時，0≤Cij<+∞,當(dāng)i,j間不直接連接它們的弧時，Cij=+∞.今設(shè)N為終點(diǎn)，求任一點(diǎn)i至終點(diǎn)N的最短距離。函數(shù)空間與策略空間迭代法定義f(i)為由i點(diǎn)出發(fā)至終點(diǎn)N的最短距離，則由最優(yōu)性原理可得f(i)=min(Cij+f(j)),i=1,2,…,N-1f(N)=0這樣的泛函方程不是遞推方程，而且f(i)出現(xiàn)在方程的兩邊，不能通過簡單的遞推求得結(jié)果。下面用兩種迭代法來求解。1、函數(shù)空間迭代法設(shè)fk(i)表示由i點(diǎn)出發(fā)向N走k步所構(gòu)成的所有路線中的最短距離。函數(shù)空間迭代法求解步驟如下：1°f1(i)=CiN,i=1,2,…,N-1f1(N)=02°fk(i)=min(Cij+fk-1(j)),i=1,2,…,N-1

jfk(N)=03°反復(fù)迭代2°直到fk(i)=fk+1(i)=…=f(i)為止，i=1,2,…,N函數(shù)空間迭代法可以證明：(1)由上述步驟確定的函數(shù)序列{fk(i)}不超過N-1步單調(diào)下降收斂于問題的最優(yōu)函數(shù)f(i)(2)若0≤Cij<+∞（i,j=1,2,…,N）,則收斂步驟P有下列估計：2、策略空間迭代法策略空間的迭代就是先給出初始策略{u1(i)}，然后按某種方式求得新策略{u2(i)},{u3(i)},…，直至最終求出最優(yōu)策略。其步驟如下：1°選一無回路的初始策略{u1(i),i=1,2,…,N-1},u1(i)表示在此策略下由i點(diǎn)到達(dá)的下一個點(diǎn)。令

k=1策略空間迭代法2°在此策略下作方程組fk(i)=Ci,uk(i)+fk[uk(i)],i=1,2,…,N-1fk(N)=0求解fk(i)，這里Ci,uk(i)為已知值3°由指標(biāo)函數(shù)fk(i)求策略uk+1(i)，其中uk+1(i)是min{Ci,u+fk(u)]}的解。令k=k+14°按2°,3°反復(fù)迭代，可逐次求得{uk(i)}和{fk(i)}，若對某一k，uk(i)=uk-1(i)對所有i成立，則稱策略收斂，此時{uk(i)}就是最優(yōu)策略，其相應(yīng)的{fk(i)}為最優(yōu)值。策略空間迭代法可以證明：若初始策略{u1(i)}不構(gòu)成回路，則以后迭代所得的策略{uk(i)}也不構(gòu)成回路（即解是唯一的），且{fk(i)}一致收斂于泛函方程的解。函數(shù)空間與策略空間迭代法例3下圖為一街區(qū)的單行道交通網(wǎng)絡(luò)，分別用函數(shù)空間迭代法和策略空間迭代法求各點(diǎn)到頂點(diǎn)5的最短路線。

③263①1

2

3⑤345②④2函數(shù)空間與策略空間迭代法[解]先用函數(shù)空間迭代法求解。為了便于運(yùn)算，將距離Cij寫成下列矩陣的形式，將fk(i)寫成列向量的形式，利用函數(shù)空間迭代法求解，步驟迭代如下：iCijj12345f1(i)f2(i)f3(i)f4(i)u(i)1036∞∞∞87722∞022∞∞44433∞1032222254∞∞405555555∞∞3∞000005其中最后一列u(i)為i點(diǎn)的最優(yōu)決策，于是得到各點(diǎn)到頂點(diǎn)5的最短路線和最短距離如下表：函數(shù)空間與策略空間迭代法i點(diǎn)最短路線最短距離1→2→3→572→3→543→524→55函數(shù)空間與策略空間迭代法再用策略空間迭代法求解。先選取一不構(gòu)成回路的初始策略{u1(i)}：u1(1)=3，u1(2)=3，u1(3)=5，u1(4)=5然后根據(jù)策略空間迭代法步驟中的2°,3°,4°，求得結(jié)果如下：iCijj12345u1(i)f1(i)u2(i)f2(i)u3(i)1036∞∞382722∞022∞343433∞1032525254∞∞405555555∞∞3∞050505其最短距離與最短路線與函數(shù)空間迭代法一致。函數(shù)空間與策略空間迭代法注意：在求解這類問題中，若網(wǎng)絡(luò)中出現(xiàn)負(fù)權(quán)邊，由于有可能出現(xiàn)負(fù)圈，故上述方法不太適用。§5動態(tài)規(guī)劃的解法及應(yīng)用舉例5.1一維資源分配問題例1用逆推法解maxz=x1x22x3x1+x2+x3=C(C>0)xi≥0,i=1,2,3動態(tài)規(guī)劃的解法及應(yīng)用舉例例2用動態(tài)規(guī)劃解下列問題（P332）maxz=8x1+7x22x1+x2≤85x1+2x2≤15x1,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≤v20≤2x2≤w2x2取整數(shù)f1*(v1,w1)=max{8x1+f2*(v1-2x1,w1-5x1)}0≤2x1≤v10≤5x1≤w1x1取整數(shù)而v1=8,w1=15,所以動態(tài)規(guī)劃的解法及應(yīng)用舉例f1*(8,15)=max{8x1+7min([8-2x1],[(15-5x1)/2])}0≤2x1≤80≤5x1≤15x1取整數(shù)由于x1≤min([8/2],[15/5])=3,因而f1*(8,15)=max{8x1+7min([8-2x1],[(15-5x1)/2])}x1=0,1,2,3=max{8x1+7[(15-5x1)/2]}=49x1=0,1,2,3x1*=0由v2=v1-2x1=8,w2=w1-5x1=15,得x2*=min{[8],[15/2]}=7∴最優(yōu)解為x1*=0,x2*=7,z*=49動態(tài)規(guī)劃的解法及應(yīng)用舉例§1例2多階段資源分配問題某工廠生產(chǎn)A,B和C三種產(chǎn)品，都要使用某種原材料，原材料共有4噸。將不同數(shù)量的這種原料分配給各種產(chǎn)品時產(chǎn)生收益如下表（單位：萬元），試確定使總收益最大的分配法。原料分配量產(chǎn)品種類（噸）ABC000011068217171132018--動態(tài)規(guī)劃的解法及應(yīng)用舉例下面求§1中的例2，將資源分配劃分為三個階段，分配給生產(chǎn)產(chǎn)品A，B，C的數(shù)量設(shè)為x1,x2,x3，其狀態(tài)(資源剩余量)s1=4,s2=s1-x1,s3=s2-x2,sn+1=s4=0.現(xiàn)列表計算如下：動態(tài)規(guī)劃的解法及應(yīng)用舉例由上述表知，最大總收益等于35，最優(yōu)決策序列是x1*=1,x2*=2,x3*=1動態(tài)規(guī)劃的解法及應(yīng)用舉例例3資源連續(xù)分配問題：設(shè)有數(shù)量為s1的某種資源，可投入生產(chǎn)A和B兩種產(chǎn)品，第一年若以數(shù)量u1投入生產(chǎn)A，剩下的s1-u1投入生產(chǎn)B，其收入為g(u1)+h(s1-u1)，這里g(0)=h(0)=0，在A、B生產(chǎn)后，資源的回收率分別為0<a<1,0<b<1,則在第一年生產(chǎn)后，回收的資源量合計為s2=au1+b(s1-u1);第二年將資源數(shù)量s2中的u2和s2-u2分別投入生產(chǎn)A和B，又得到收入為g(u2)+h(s2-u2)，如此繼續(xù)進(jìn)行n年，問如何決定每年投入A生產(chǎn)的資源量，才能使總的收入最大？動態(tài)規(guī)劃的解法及應(yīng)用舉例此問題等價于下列規(guī)劃問題：maxZ=g(u1)+h(s1-u1)+g(u2)+h(s2-u2)+…+g(un)+h(sn-un)s2=au1+b(s1-u1)s3=au2+b(s2-u2)………………sn=aun-1+b(sn-1-un-1)0≤ui≤si,i=1,2,…,n動態(tài)規(guī)劃的解法及應(yīng)用舉例下面用動態(tài)規(guī)劃的方法來處理。設(shè)sk為狀態(tài)變量，表示在第k階段（第k年）可投入A、B兩種生產(chǎn)的資源量。uk為決策變量，它表示在第k階段用于A生產(chǎn)的資源量，則sk-uk表示用于B生產(chǎn)的資源量。狀態(tài)轉(zhuǎn)移方程為sk+1=auk+b(sk-uk)最優(yōu)值函數(shù)fk(sk)表示當(dāng)資源量為sk時，從第k階段至第n階段采取最優(yōu)分配方案進(jìn)行生產(chǎn)后所得到的最大總收入。動態(tài)規(guī)劃的解法及應(yīng)用舉例因此可寫出動態(tài)規(guī)劃的遞推關(guān)系式為：fn(sn)=max{g(un)+h(sn-un)}0≤un≤snfk(sk)=max{g(uk)+h(sk-uk)+fk+1(auk+b(sk-uk))},0≤uk≤skk=n-1,…,2,1最后求出f1(s1)即為所求問題的最大總收入。動態(tài)規(guī)劃的解法及應(yīng)用舉例下面以簡單的例子n=3,a=0.3,b=0.6,g(y)=0.8y,h(y)=0.5y來求解以說明遞推求解的步驟。先計算f3(s3),得f3(s3)=max{0.8u3+0.5(s3-u3)}0≤u3≤s3=max{0.3u3+0.5s3}=0.8s30≤u3≤s3u3*=s3動態(tài)規(guī)劃的解法及應(yīng)用舉例而f2(s2)=max{g(u2)+h(s2-u2)+f3(au2+b(s2-u2))}0≤u2≤s2=max{0.98s2+0.06u2}=1.04s20≤u2≤s2u2*=s2f1(s1)=max{g(u1)+h(s1-u1)+f2(au1+b(s1-u1))}0≤u1≤s1=max{1.124s1-0.012u1}=1.124s10≤u1≤s1u1*=0動態(tài)規(guī)劃的解法及應(yīng)用舉例上述結(jié)果可列表如下：實(shí)際階段投入A的量投入B的量收入剩余量10s10.5s10.6s120.6s100.48s10.18s130.18s100.144s1

總收入1.124s1

動態(tài)規(guī)劃的解法及應(yīng)用舉例上面的例子較簡單，但當(dāng)n很大時，且g(u),h(u)是復(fù)雜函數(shù)時，問題的求解也是不容易的。當(dāng)g(u),h(u)為凸函數(shù)，且h(0)=g(0)=0時，可以證明：在每個階段上u(i)的最優(yōu)決策總是取其上限或下限，因此，對于解的結(jié)構(gòu)來說，它與g(u),h(u)是線性情況是類似的。動態(tài)規(guī)劃的解法及應(yīng)用舉例5.2二維(兩種)資源分配問題設(shè)有兩種資源數(shù)量各為a和b，需要分配于n種生產(chǎn)，若第一種物資以數(shù)量xi，第二種以數(shù)量yi投入第i種生產(chǎn)時，得到的收益為gi(xi,yi)，問應(yīng)如何分配這兩種物資于n種生產(chǎn)使總收入最大？動態(tài)規(guī)劃的解法及應(yīng)用舉例這個問題可化為下述數(shù)學(xué)規(guī)劃問題：maxZ=g1(x1,y1)+g2(x2,y2)+…+gn(xn,yn)x1+x2+…+xn=ay1+y2+…+yn=bxi≥0,yi≥0i=1,2,…,n動態(tài)規(guī)劃的解法及應(yīng)用舉例用動態(tài)規(guī)劃的方法求解。設(shè)狀態(tài)變量為(Xk,Yk),Xk,Yk分別表示分配用于第k種生產(chǎn)至n種生產(chǎn)的兩種物資的數(shù)量(資源剩余量)。決策變量為(xk,yk),xk,yk分別表示分配用于第k種生產(chǎn)的兩種物資的數(shù)量。狀態(tài)轉(zhuǎn)移方程：Xk+1=Xk-xkYk+1=Yk-yk動態(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(Xk-xk,Yk-yk)},k=n-1,…,2,10≤xk≤Xk0≤yk≤Yk動態(tài)規(guī)劃的解法及應(yīng)用舉例由此遞推關(guān)系式可求得f1(a,b)，即為所求問題的最大收入。由于狀態(tài)變量為二維情形，其計算量比一般問題成平方增長，其計算量和記憶容量都顯著增加。為了能使計算可行，可以采用拉長計算時間減少存儲量的辦法來實(shí)現(xiàn)，以求得它的解或近似解。動態(tài)規(guī)劃的解法及應(yīng)用舉例(1)Lagrange乘子法引入Lagrange乘子λ，將上述問題化為max{g1(x1,y1)+g2(x2,y2)+…+gn(xn,yn)–λ(y1+y2+…+yn)}滿足條件x1+x2+…+xn=axi≥0,yi≥0i=1,2,…,n其中λ作為一個固定的參數(shù)。動態(tài)規(guī)劃的解法及應(yīng)用舉例令hi(xi)=hi(xi,λ)=max[gi(xi,yi)–λyi]yi≥0于是問題變?yōu)閙ax[h1(x1)+h1(x1)+…+hn(xn)]滿足條件x1+x2+…+xn=axi≥0,i=1,2,…,n動態(tài)規(guī)劃的解法及應(yīng)用舉例這是一個一維分配問題，可用對一維的方法求解，這里由于λ是參數(shù)，因此，最優(yōu)解xi*是參數(shù)λ的函數(shù)，相應(yīng)的yi*也是λ的函數(shù)，即xi=xi*(λ),yi=yi*(λ)為其解。如果，則可證明{xi*,yi*}為原問題的最優(yōu)解；如果，可調(diào)整λ的值(利用插值法逐漸確定λ)，直到滿足為止。動態(tài)規(guī)劃的解法及應(yīng)用舉例(2)逐次逼近法這是另一種降維方法，先保持一個變量不變，對另一個變量實(shí)現(xiàn)最優(yōu)化，然后交替地固定變量，以迭代的形式反復(fù)進(jìn)行，直到獲得某種要求為止。逐次逼近法先設(shè)x(0)={x1(0),x2(0),…,xn(0)}為滿足x1(0)+x2(0)+…+xn(0)=a的一個可行解，固定x在x(0)，求max{g1(x1(0),y1)+g2(x2(0),y2)+…+gn(xn(0),yn)}滿足條件y1+y2+…+yn=byi≥0i=1,2,…,n的解，設(shè)這個解為y(0)={y1(0),y2(0),…,yn(0)}逐次逼近法然后再固定y為y(0),求max{g1(x1,y1(0))+g2(x2,y2(0))+…+gn(xn,yn(0))}滿足條件x1+x2+…+xn=axi≥0i=1,2,…,n的解，設(shè)其解為x(1)={x1(