第七章 運籌學 動態(tài)規(guī)劃

第七章運籌學動態(tài)規(guī)劃第一頁，共六十三頁，編輯于2023年，星期四教學目的與要求:使學生學會利用多階段問題的決策思想處理一些簡單的實際問題,并會用WinQSB求解動態(tài)規(guī)劃.重點與難點:重點是離散型資源分配問題;難點是動態(tài)規(guī)劃建模和求解方法.教學方法:從多階段最短路引入基本概念和數(shù)學模型,再講解離散型DP和連續(xù)型DP.思考題,討論題,作業(yè):本章習題.參考資料:見前言.學時分配:6學時.第二頁，共六十三頁，編輯于2023年，星期四前言:動態(tài)規(guī)劃是最優(yōu)化的一個分支,它是解決多階段決策過程最優(yōu)化的一種方法.動態(tài)規(guī)劃的創(chuàng)始人是美國數(shù)學家貝爾曼(R.Bellman).它在四十年代后期和五十年代初期在美國蘭德公司工作,針對一些多階段決策問題提出了解決這類問題的最優(yōu)化原理,并在1957年出版了動態(tài)規(guī)劃的第一本書《Dynamicprogramming》.在企業(yè)管理方面,動態(tài)規(guī)劃可以解決庫存問題,資源分配問題,設(shè)備更新問題,運輸問題,生產(chǎn)過程最優(yōu)控制問題.它的弱點是,根據(jù)最優(yōu)化原理建立的動態(tài)規(guī)劃基本方程,尚無統(tǒng)一的解法,而要根據(jù)其數(shù)學結(jié)構(gòu)靈活處理;此外,變量個數(shù)不能太多,否則計算量太大,這稱為維數(shù)問題.第三頁，共六十三頁，編輯于2023年，星期四第一節(jié)多階段決策問題及實例所謂多階段決策問題,是指一個大問題可以劃分為若干個階段,每個階段形成一個子問題,各個階段是互相聯(lián)系的,每個階段都要作出決策,并且一個階段的決策確定以后會影響下一階段的決策,從而影響整個過程的活動路線.各個階段所確定的決策構(gòu)成一個決策序列,稱為一個策略,對于不同的策略其效果不同(效果可以用數(shù)量來衡量).多階段決策問題就是選擇一個最優(yōu)策略,使在給定的標準下達到最好的效果.第四頁，共六十三頁，編輯于2023年，星期四典型例題:例1多階段網(wǎng)絡(luò)的最短路2511214106104131112396581052C1C3D1AB1B3B2D2EC2狀態(tài)1狀態(tài)2狀態(tài)3狀態(tài)4終點第五頁，共六十三頁，編輯于2023年，星期四例題特點:⒈階段:如圖的階段,分為四段;⒉狀態(tài):頂點;⒊決策:選弧;⒋轉(zhuǎn)移:從一個頂點走到另一個頂點;⒌目標:路長最短.第六頁，共六十三頁，編輯于2023年，星期四例2資源分配問題設(shè)有數(shù)量x的某種資源,將它投入兩種生產(chǎn)A,B.若以y投入生產(chǎn)A,剩下的x-y投入生產(chǎn)B,則收入函數(shù)為g(y)+h(x-y),如果生產(chǎn)后可以回收再生產(chǎn),其回收率分別為0≤a,b≤1,則在第一階段生產(chǎn)后回收的總資源為再將投入生產(chǎn)A,B,若以分別投入生產(chǎn)A,B則又可得收入因此兩階段的總收入為第七頁，共六十三頁，編輯于2023年，星期四如果上面的過程進行了n個階段,而且我們希望選擇使n個階段的總收入最大,問題變?yōu)榈诎隧?，共六十三頁，編輯?023年，星期四例題特點:⒈階段:年(月)⒉狀態(tài):資金數(shù)⒊決策:分配給A的資金數(shù)⒋轉(zhuǎn)移:⒌效益:n個階段的總收入最大第九頁，共六十三頁，編輯于2023年，星期四第二節(jié)最優(yōu)化原理與動態(tài)規(guī)劃基本方程一.動態(tài)規(guī)劃的基本概念⒈階段(stage):是指一個問題需要作出決策的步驟,用k表示階段數(shù),k稱為階段變量.通常以時間作為階段變量.⒉狀態(tài)(state):狀態(tài)表示在任一階段所處的位置,通常一個階段有若干個狀態(tài),描述過程狀態(tài)的變量稱為狀態(tài)變量,第k階段的狀態(tài)變量用表示.狀態(tài)變量取值的全體稱為狀態(tài)空間或狀態(tài)集合.第十頁，共六十三頁，編輯于2023年，星期四在例1中各階段的狀態(tài)變量集合如下:第一階段狀態(tài)變量第二階段狀態(tài)變量第三階段狀態(tài)變量第四階段狀態(tài)變量終點E第十一頁，共六十三頁，編輯于2023年，星期四注意:狀態(tài)變量是動態(tài)規(guī)劃中最關(guān)鍵的一個參數(shù),它既反映前面各階段決策的結(jié)局,又是本階段作出決策的出發(fā)點,狀態(tài)是動態(tài)規(guī)劃問題各階段信息的傳遞點和結(jié)合點.⒊決策(decision):決策是指某階段狀態(tài)給定后,從該階段演變到下一階段某狀態(tài)的選擇.決策變量表示第k階段狀態(tài)為時對方案的選擇.表示k階段狀態(tài)為時決策允許的取值集合.例如:例1中⒋策略(policy)和子策略(subpolicy):動態(tài)規(guī)劃問題各階段決策組成的序列總體稱為一個策略.第十二頁，共六十三頁，編輯于2023年，星期四是n個階段DP的一個策略.⒌狀態(tài)轉(zhuǎn)移律:從的某一狀態(tài)值出發(fā),當決策變量的取值決定后,下一階段狀態(tài)變量的取值也隨之確定.這種從上一階段的某一狀態(tài)值到下一階段某一狀態(tài)值的轉(zhuǎn)移規(guī)律稱為狀態(tài)轉(zhuǎn)變移律.可表示為第十三頁，共六十三頁，編輯于2023年，星期四⒍指標函數(shù)(indexfunction):指標函數(shù)是用來衡量實現(xiàn)過程優(yōu)劣的一種數(shù)量指標.它是從狀態(tài)出發(fā)至過程最終,當采取某種策略時,按預(yù)定標準得到的效益值,這個值既與有關(guān),又與以后所選取的策略有關(guān),它是兩者的函數(shù),稱為過程指標函數(shù),記為特別地,僅第k階段的指標函數(shù),可記為第十四頁，共六十三頁，編輯于2023年，星期四最優(yōu)指標函數(shù):是指對某一確定狀態(tài)選取最優(yōu)策略后得到的指標函數(shù)值,也就是對應(yīng)某一最優(yōu)子策略的某種效益度量,這個度量值可以是成本,產(chǎn)量,距離等等.對應(yīng)于從狀態(tài)出發(fā)的最優(yōu)子策略的效益值記為其中optimization是最優(yōu)化的意思,在具體問題中,可以是最小化(min)也可以是最大化(max).第十五頁，共六十三頁，編輯于2023年，星期四二.最優(yōu)化原理與動態(tài)規(guī)劃基本方程貝爾曼(R.Bellman)最優(yōu)化原理:作為整個過程的最優(yōu)策略具有這樣的性質(zhì),無論過去的狀態(tài)和決策如何,對先前決策所形成的狀態(tài)而言,余下的諸決策必構(gòu)成最優(yōu)策略.根據(jù)這一原理,計算動態(tài)規(guī)劃問題的遞推關(guān)系式(逆序法)稱為動態(tài)規(guī)劃基本方程:其中,稱為邊界條件.第十六頁，共六十三頁，編輯于2023年，星期四用動態(tài)規(guī)劃求解例1:2511214106104131112396581052C1C3D1AB1B3B2D2EC2第十七頁，共六十三頁，編輯于2023年，星期四動態(tài)規(guī)劃基本方程為:第十八頁，共六十三頁，編輯于2023年，星期四2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0第十九頁，共六十三頁，編輯于2023年，星期四2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0第二十頁，共六十三頁，編輯于2023年，星期四2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5第二十一頁，共六十三頁，編輯于2023年，星期四2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5第二十二頁，共六十三頁，編輯于2023年，星期四2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8第二十三頁，共六十三頁，編輯于2023年，星期四2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7第二十四頁，共六十三頁，編輯于2023年，星期四2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=8第二十五頁，共六十三頁，編輯于2023年，星期四2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=8第二十六頁，共六十三頁，編輯于2023年，星期四2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=14第二十七頁，共六十三頁，編輯于2023年，星期四2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21第二十八頁，共六十三頁，編輯于2023年，星期四2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C1第二十九頁，共六十三頁，編輯于2023年，星期四2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C1（C1，D1）D1第三十頁，共六十三頁，編輯于2023年，星期四2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C1（C1，D1）D1（D1，E）E從A到E的最短路徑為19，路線為A→B2→C1→D1→E第三十一頁，共六十三頁，編輯于2023年，星期四第三節(jié)離散確定型動態(tài)規(guī)劃模型的求解例2資源分配問題:某公司有五套先進設(shè)備,需分配給下屬的甲,乙,丙三個工廠,各工廠得此設(shè)備后每年為公司上繳的利潤如下表,問如何分配可使公司獲得最大利潤?甲乙丙012345

000354

7106

91111121112131112第三十二頁，共六十三頁，編輯于2023年，星期四解:將問題按三個工廠分為三個階段,即k=1,2,3.第三十三頁，共六十三頁，編輯于2023年，星期四根據(jù)最優(yōu)化原理得出動態(tài)規(guī)劃基本方程:動態(tài)規(guī)劃的求解方法通常是采取逆序解法,即從第三階段向前推導.第三十四頁，共六十三頁，編輯于2023年，星期四0123450123450461112120

4

6

111212012345

第三十五頁，共六十三頁，編輯于2023年，星期四01234501234500+45+00+65+410+00+115+610+411+00+125+1110+611+411+00+125+1210+1111+611+411+0051014162101221,22第三十六頁，共六十三頁，編輯于2023年，星期四01234550+213+167+149+1012+513+0210,2最優(yōu)方案一:甲廠0臺,乙廠2臺,丙廠3臺;最優(yōu)方案二:甲廠2臺,乙廠2臺,丙廠1臺.最大盈利值為21萬元.第三十七頁，共六十三頁，編輯于2023年，星期四第四節(jié)連續(xù)確定型動態(tài)規(guī)劃模型的求解例3(p208例5)第三十八頁，共六十三頁，編輯于2023年，星期四解:階段變量是以年作為化分單位,k=1,2,3.狀態(tài)變量為k年初可用于工作的完好機器數(shù).決策變量為第k年用于完成A項任務(wù)的機器數(shù),則為用于完成B項任務(wù)的機器數(shù).狀態(tài)轉(zhuǎn)移方程是動態(tài)規(guī)劃基本方程及邊界條件為第三十九頁，共六十三頁，編輯于2023年，星期四當k=3時,第四十頁，共六十三頁，編輯于2023年，星期四當k=2時,第四十一頁，共六十三頁，編輯于2023年，星期四當k=1時,第四十二頁，共六十三頁，編輯于2023年，星期四

第五節(jié)一般數(shù)學規(guī)劃模型的動態(tài)規(guī)劃解法用動態(tài)規(guī)劃解數(shù)學規(guī)劃的方法是:把依次決定各個變量的取值看成是一個多階段決策問題,因而模型中含有幾個變量,就分為幾個階段,用狀態(tài)變量表示數(shù)學規(guī)劃中約束條件右邊常數(shù)項,它表示可分配的資源數(shù).第四十三頁，共六十三頁，編輯于2023年，星期四例3某投資者有40萬元的固定資本,他可以在三種不同的投資機會中投資(股票,銀行,土地)投資額為x,y,z.假定他做過預(yù)測,知道每項投資可獲得的效益分別為問如何分配投資額,才能獲得最大效益.第四十四頁，共六十三頁，編輯于2023年，星期四解:依題意,列出數(shù)學模型設(shè)為決策變量,階段變量為k,k=1,2,3.為狀態(tài)變量,即投放到第k個項目上的資金數(shù).狀態(tài)轉(zhuǎn)移律為效益函數(shù)為.動態(tài)規(guī)劃基本方程為第四十五頁，共六十三頁，編輯于2023年，星期四K=3,這是單增的線性函數(shù),它在區(qū)間右端點取得最大值,顯然時,上式有最大值.第四十六頁，共六十三頁，編輯于2023年，星期四K=2,設(shè),求其極大