第五節(jié) 一般數(shù)學(xué)規(guī)劃模型的動(dòng)態(tài)規(guī)劃解法

1、2010年5月管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)1第五節(jié)第五節(jié) 一般數(shù)學(xué)模型的動(dòng)態(tài)規(guī)劃解法一般數(shù)學(xué)模型的動(dòng)態(tài)規(guī)劃解法了解一般數(shù)學(xué)模型的動(dòng)態(tài)規(guī)劃解法了解一般數(shù)學(xué)模型的動(dòng)態(tài)規(guī)劃解法2010年5月管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)2動(dòng)態(tài)規(guī)劃的一般性動(dòng)態(tài)規(guī)劃的一般性動(dòng)態(tài)規(guī)劃的一局限性動(dòng)態(tài)規(guī)劃的一局限性2010年5月管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)3例例6：用動(dòng)態(tài)規(guī)劃的逆序法求解下列非線性規(guī)劃問(wèn)題3, 2, 1, 01223max32131ixxxxixziii解：解：將變量x1、x2、x3的取值分為三個(gè)階段k=1,2,3， xi分別為第i個(gè)階段的決策變量。2010年5月管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)4(1)狀態(tài)變量設(shè)為sk，有s1=1

2、2 ，s2=s1-x1，s3=s2-3x2， s4=s3-2x3。(2)各決策變量的允許值為：0 x1s1， 0 x2s2/3，0 x3s3/2。解：解：將變量x1、x2、x3的取值分為三個(gè)階段k=1,2,3， xi分別為第i個(gè)階段的決策變量。2010年5月管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)5(3)數(shù)學(xué)模型為 bsfasfkxsfkkksDckkkkk12. 8112. 8max4411 3*334432/03323,233max33sxssfxsfsx當(dāng)k=3時(shí)2010年5月管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)66,43232max2*2222223/022sxsxsxsx當(dāng)k=2時(shí) 22323/02232max

3、22xsfxsfsx2010年5月管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)7當(dāng)k=1時(shí) 4,641241max41maxmax*1211120211112011210111111xxxxsxxsfxsfxxsx由s1=12 ，x1*=4知s2=8，x2*=4/3，得s3=4 ，x3*=2。2010年5月管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)8例例7：用動(dòng)態(tài)規(guī)劃方法求解線性規(guī)劃問(wèn)題：用動(dòng)態(tài)規(guī)劃方法求解線性規(guī)劃問(wèn)題：0,1823122453max21212121xxxxxxxxz2010年5月管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)9解：解：先將這個(gè)問(wèn)題化為動(dòng)態(tài)規(guī)劃的模型。先將這個(gè)問(wèn)題化為動(dòng)態(tài)規(guī)劃的模型。(1)把確定把確定x1、x2的值看作分

4、兩個(gè)階段的決策，用的值看作分兩個(gè)階段的決策，用k表表示階段數(shù)。狀態(tài)變量為示階段數(shù)。狀態(tài)變量為k階段初各約束條件右端項(xiàng)的階段初各約束條件右端項(xiàng)的剩余值，分別用剩余值，分別用R1k、R2k、R3k來(lái)表示，它為下階段決來(lái)表示，它為下階段決策變量提供依據(jù)。策變量提供依據(jù)。11313221221111123183124xxRRRRxxRR(2)狀態(tài)轉(zhuǎn)移為：狀態(tài)轉(zhuǎn)移為：: 2010年5月管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)101, 31, 21, 11321,max,kkkkkkRDxkkkkRRRfxcRRRfikkk(3)指標(biāo)函數(shù)為：Vk,2=ckxk+Vk+1,2， ck為xk在目標(biāo)函數(shù)中的系數(shù)。(4)動(dòng)態(tài)規(guī)劃

5、的遞推方程可表為：(5)邊際條件f3(R13, R23, R33)=0。2010年5月管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)11當(dāng)k=2時(shí)，322222,2min0332313322,2min03222122,25min5max,5max,3222232222RRxRRRfxRRRfRRxRRx2,2min3222*2RRx則 (取到上限)2010年5月管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)1213121111212,min031211113,3max,31111xRRxRfxRRRfRRx131211403,25min3max1xRRxx當(dāng)k=1時(shí)，2010年5月管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)13因?yàn)?2159023021590,30min318,1225min3,25min1111113121xxxxxxRR236229452303max22159032303max,*11111401111140312111111xxxxxxxxxxRRRfxx所以2010年5月