動態(tài)規(guī)劃模型舉例ppt課件-wenkub.com
2025-05-03 12:08 本頁面
【正文】 已知 =1000，則原問題的最優(yōu)值為 )52(m a x)( 3303333xuxf xu ?? ??3*3 xu ? 333 7)( xxf ?)](),([m a x)( 3322202222xfuxvxf xu ?? ??)](752[m a x)( 222202222uxxuxf xu ???? ?? )(m a x 22022xuxu ?? ??2*2 xu ? 222 )( xxf ?)](),([m a x)( 2211101111xfuxvxf xu ?? ??)]([m a x)( 111101111uxxuxf xu ???? ?? )(m a x 11011xuxu ?? ??0*1 ?u 111 )( xxf ?1 5 7 1 0)( 11 ?xf1x6/3/2022 31 順序求出原問題的最優(yōu)解為 即第一年度應把年初全部完好機器投入低負荷生產(chǎn)，后兩年每年應把年初全部完好機器投入高負荷生產(chǎn)，這樣所得的三年總產(chǎn)量最高，為 15710噸。本題要求的是已知第一年度初擁有的完好機器數(shù) =1000臺，用最優(yōu)方案到第三年度末這段期間的產(chǎn)品產(chǎn)量，將它記為 。若開始時完好的機器數(shù) =1000臺，要求制定一個三年計劃，在每年開始時，決定如何重新分配在兩種不同的負荷下生產(chǎn)的完好機器數(shù)，使在三年內(nèi)產(chǎn)品的總產(chǎn)量達到最大。下面以一個例子加以說明。狀態(tài)應能描述過程的特征，可以直接或間接觀測，并且具有無后效性，即當某階段的狀態(tài)給定時，過程以后的演變與該階段以前的狀態(tài)無關(guān)。第 k部電梯（即第 k階段）開始服務的層次為狀態(tài) xk，它服務的層數(shù)為決策 uk，滿足 xk+1= xk+ u k (1) 當 x=i， u=j時，已知第 k部電梯服務的時間為 vk（ xk， uk） = tij。一批任務由若干設備完成，問題是如何均衡地向每個設備分配各項任務，使這批任務盡早地完成。約束條件是備用件費用之和不應超過 C，決策變量是各部件的備用件數(shù)量，于是問題歸結(jié)為 Max Z = (1) . (2) 這個非線性規(guī)劃轉(zhuǎn)化為動態(tài)規(guī)劃求解比較方便。為提高系統(tǒng)的可靠性，每個部件都裝置備用件，一旦原部件故障，備用件就自動進入系統(tǒng)。而這種情況下，將其轉(zhuǎn)化為 ??nkkkk vug1),(????nkkk umu11 0,????nkkk vmv12 0,6/3/2022 19 動態(tài)規(guī)劃，是一種可行的方法。實際上，多階段決策問題有時也可用靜態(tài)規(guī)劃方法求解，如例 2的生產(chǎn)計劃問題。在用（ 1）式計算時， xk的取值范圍 —— 允許狀態(tài)集合 Xk由（ 2）式及允許決策集合（ 0≤uk≤Uk）決定。 解： 決策變量是第 k周的生產(chǎn)量，記作 uk（ k=1， 2， … ， n）。 稱此為動態(tài)規(guī)劃逆序求解的基本方程 (貝爾曼方程 )。 )( kk xuk kx kx)( kk xD kxk kx)}(,),(),({)( 11 nnkkkkkk xuxuxuxp ????6/3/2022 13 （ 5）狀態(tài)轉(zhuǎn)移方程 如果第 個階段狀態(tài)變量為 ，作出的決策為 ，那么第 階段的狀態(tài)變量 也被完全確定。用 表示第 階段處于狀態(tài) 時的決策變量，它是 的函數(shù)，用 表示 的允許決策集合。即：如果某階段的狀態(tài)給定，則此階段以后過程的發(fā)展不受以前狀態(tài)的影響，未來狀態(tài)只依賴于當前狀態(tài)。各階段的狀態(tài)通常用 狀態(tài)變量 描述。 ???????????? ????0)(1,5,6,) ] ,(),([)(77111)(mi nxfkXxxfxxdxfkkkkkkkxDukkkkk?k k6/3/2022 10 需要指出，上例只是最短路問題的一種形式，實際問題中可以有多種形式，如： 1）路線數(shù)目不定，如圖 3，求任一點（如 B）到 E的最短路線（不論它由幾段組成）； 2）有向路網(wǎng)，如圖 4，求 V1到 V6的有向最短路； 3）旅行商問題，如圖 3，求從 A點出發(fā)，經(jīng)每點一次又回到 A點的最短路 。同法計算出 f5(E3)=9， u5（ E3） =F2， ,532 45m i n)(),( )(),(m i n)(262251612525 ???????????????????FfFEdFfFEdEf,)(,8)(,)(,6)(,)(,75272m i n)(),()(),(m i n)(42343422424214252141511414EDuDfEDu
教學課件相關(guān)推薦
鄂ICP備17016276號-1