數(shù)學(xué)建模動(dòng)態(tài)規(guī)劃

數(shù)學(xué)建模

動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃問(wèn)題實(shí)例動(dòng)態(tài)規(guī)劃的基本概念與原理動(dòng)態(tài)規(guī)劃應(yīng)用舉例動(dòng)態(tài)規(guī)劃是解決多階段決策過(guò)程最優(yōu)化的一種方法。該方法是由美國(guó)數(shù)學(xué)家貝爾曼（R.E.Bellman)等人在20世紀(jì)50年代初提出的。他們針對(duì)多階段決策問(wèn)題的特點(diǎn)，提出了解決這類問(wèn)題的“最優(yōu)化原理”，并成功地解決了生產(chǎn)管理、工程技術(shù)等方面的許多問(wèn)題，從而建立了運(yùn)籌學(xué)的一個(gè)新的分支，即動(dòng)態(tài)規(guī)劃。Bellman在1957年出版了《DynamicProgramming》一書，是動(dòng)態(tài)規(guī)劃領(lǐng)域中的第一本著作。動(dòng)態(tài)規(guī)劃問(wèn)題及實(shí)例動(dòng)態(tài)規(guī)劃是解決多階段決策問(wèn)題的一種方法，是現(xiàn)代企業(yè)管理中的一種重要決策方法，可用于最優(yōu)路徑問(wèn)題、資源分配問(wèn)題、生產(chǎn)計(jì)劃和庫(kù)存問(wèn)題、投資問(wèn)題、裝載問(wèn)題、排序問(wèn)題及生產(chǎn)過(guò)程的最優(yōu)控制等。動(dòng)態(tài)規(guī)劃模型的分類：以“時(shí)間”角度可分成：離散型和連續(xù)型。從信息確定與否可分成：確定型和隨機(jī)型。從目標(biāo)函數(shù)的個(gè)數(shù)可分成：?jiǎn)文繕?biāo)型和多目標(biāo)型。一、多階段決策過(guò)程多階段決策過(guò)程是指這樣一類特殊的活動(dòng)過(guò)程，他們可以按時(shí)間順序分解成若干相互聯(lián)系的階段，在每個(gè)階段都要做出決策，全部過(guò)程的決策是一個(gè)決策序列，所以多階段決策過(guò)程也稱為序貫決策過(guò)程。這種問(wèn)題就稱為多階段決策問(wèn)題。

二、多階段決策問(wèn)題的特點(diǎn)過(guò)程可分為若干個(gè)相互聯(lián)系的階段；每一階段都對(duì)應(yīng)著一組可供選擇的決策；每一決策的選定即依賴于當(dāng)前面臨的狀態(tài)，又影響以后總體的效果。三、具體實(shí)例1、最短路線問(wèn)題給定一個(gè)線路網(wǎng)絡(luò)，要從A向F鋪設(shè)一條輸油管道，各點(diǎn)間連線上的數(shù)字表示距離，問(wèn)應(yīng)選擇什么路線，可使總距離最短？2、生產(chǎn)與存儲(chǔ)問(wèn)題：某工廠每月需供應(yīng)市場(chǎng)一定數(shù)量的產(chǎn)品。供應(yīng)需求所剩余產(chǎn)品應(yīng)存入倉(cāng)庫(kù)，一般地說(shuō)，某月適當(dāng)增加產(chǎn)量可降低生產(chǎn)成本，但超產(chǎn)部分存入倉(cāng)庫(kù)會(huì)增加庫(kù)存費(fèi)用，要確定一個(gè)每月的生產(chǎn)計(jì)劃，在滿足需求條件下，使一年的生產(chǎn)與存儲(chǔ)費(fèi)用之和最小。動(dòng)態(tài)規(guī)劃的基本概念與原理動(dòng)態(tài)規(guī)劃的基本概念階段；狀態(tài)；決策和策略；狀態(tài)轉(zhuǎn)移方程；指標(biāo)函數(shù)。一、基本概念階段：是指問(wèn)題需要做出決策的步數(shù)。階段總數(shù)常記為n，相應(yīng)的是n個(gè)階段的決策問(wèn)題。階段的序號(hào)常記為k，稱為階段變量，k=1,2,…,n.k即可以是順序編號(hào)也可以是逆序編號(hào)，常用順序編號(hào)。狀態(tài)：各階段開(kāi)始時(shí)的客觀條件，第k階段的狀態(tài)常用狀態(tài)變量表示，狀態(tài)變量取值的集合成為狀態(tài)集合，用表示。例如，案例1中，AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1階段第2階段第3階段第4階段第5階段狀態(tài)1狀態(tài)2狀態(tài)3狀態(tài)4狀態(tài)5狀態(tài)6決策：是指從某階段的某個(gè)狀態(tài)出發(fā)，在若干個(gè)不同方案中做出的選擇。表示決策的變量，稱為決策變量，用表示。表示第k階段當(dāng)狀態(tài)處于sk時(shí)的決策變量。例如：表示走到C階段,當(dāng)處于C2路口時(shí)，下一步奔D1.時(shí)的允許決策集合記為，例如：決策變量允許的取值范圍稱為允許決策集合，第k階段狀態(tài)為狀態(tài)轉(zhuǎn)移方程：是從上一階段的某一狀態(tài)值轉(zhuǎn)變?yōu)橄乱浑A段某一狀態(tài)值的轉(zhuǎn)移規(guī)律，用表示。策略：一個(gè)按順序排列的決策組成的集合。由每段的決策按順序排列組成的決策函數(shù)序列稱為k子過(guò)程策略。簡(jiǎn)稱子策略，記為。即當(dāng)k=1時(shí)，此決策函數(shù)序列成為全過(guò)程的一個(gè)策略，簡(jiǎn)稱策略，記為：在實(shí)際問(wèn)題中，可供選擇的策略有一定的范圍，此范圍稱為允許策略集合，用P表示。指標(biāo)函數(shù)：階段指標(biāo)函數(shù)和過(guò)程指標(biāo)函數(shù)。階段指標(biāo)函數(shù)是指第k階段從狀態(tài)出發(fā)，采取決策時(shí)的效益，用表示。而過(guò)程指標(biāo)函數(shù)是從第k階段的某狀態(tài)出發(fā)，采取子策略效益之和：最優(yōu)指標(biāo)函數(shù)：表示從第k階段狀態(tài)為時(shí)采用最佳策略到過(guò)程終止時(shí)的最佳效益。記為時(shí)所得到的階段其中opt可根據(jù)具體情況取max或min?；痉匠蹋捍藶橹鸲芜f推求和的依據(jù)，一般為：式中opt可根據(jù)題意取max或min.例如，案例1的基本方程為：最優(yōu)性原理：最優(yōu)策略的子策略必為最優(yōu)。不管過(guò)去的狀態(tài)和決策如何，從眼下直到最后的諸決策必構(gòu)成最優(yōu)子策略。動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn)：可把一個(gè)N維優(yōu)化問(wèn)題化成N個(gè)一維優(yōu)化問(wèn)題求解。求得最優(yōu)解以后，可得所有子問(wèn)題的最優(yōu)解。動(dòng)態(tài)規(guī)劃的缺點(diǎn)：“一個(gè)”問(wèn)題，“一個(gè)”模型，“一個(gè)”求解方法。且求解技巧要求比較高，沒(méi)有統(tǒng)一處理方法。狀態(tài)變量維數(shù)不能太高，一般要求小于6。動(dòng)態(tài)規(guī)劃應(yīng)用舉例例1最短路線問(wèn)題基本思想：如果起點(diǎn)A經(jīng)過(guò)B1,C1,D1,E1而到終點(diǎn)F，則由C1出發(fā)經(jīng)D1,E1到F點(diǎn)這條子路線，是從C1到F的最短路線。所以，尋找最短路線，應(yīng)該從最后一段開(kāi)始找，然后往前遞推。狀態(tài)變量：各路線的位置決策變量：第k階段當(dāng)狀態(tài)處于時(shí)，決定下一個(gè)狀態(tài)的位置狀態(tài)轉(zhuǎn)移方程：上一階段到下一階段的轉(zhuǎn)移規(guī)則指標(biāo)函數(shù)：從狀態(tài)出發(fā)，采取決策時(shí)的路程距離最優(yōu)指標(biāo)函數(shù)：第k階段狀態(tài)為時(shí)且采用最佳走線策略，使從k位置及以后的路線最短。逆序遞推方程：（1）k=5時(shí)，狀態(tài)它們到F點(diǎn)的距離即為最短路。AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4時(shí)，狀態(tài)它們到F點(diǎn)需經(jīng)過(guò)中途點(diǎn)E，需一一分析從E到F的最短路：先說(shuō)從D1到F的最短路有兩種選擇：經(jīng)過(guò)E1,E2,比較最短。AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143這說(shuō)明由D1到F的最短距離為7，其路徑為相應(yīng)的決策為：這說(shuō)明由D2到F的最短距離為5，其路徑為相應(yīng)的決策為：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即D3到F的最短距離為5，其路徑為相應(yīng)的決策為：（3）k=3時(shí)，狀態(tài)這說(shuō)明由C1到F的最短距離為12，相應(yīng)的決策為AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即由C2到F的最短距離為10，相應(yīng)的決策為即由C3到F的最短距離為8，相應(yīng)的決策為即由C4到F的最短距離為9，相應(yīng)的決策為AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4）k=2時(shí)，狀態(tài)這說(shuō)明由B1到F的最短距離為13，相應(yīng)的決策為即由B2到F的最短距離為15，相應(yīng)的決策為AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（1）k=1時(shí)，只有一個(gè)狀態(tài)點(diǎn)A,則即由A到F的最短距離為17，相應(yīng)的決策為所以最優(yōu)路線為：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143再按計(jì)算順序反推可得最優(yōu)決策序列：順序遞推方程：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143例1：1階段2階段3階段4階段5階段行走方向AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143K=1時(shí)注意到：所以K=2時(shí)AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143K=3時(shí)AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143或類似地，可算出：最優(yōu)策略：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143或最短路徑：最短路長(zhǎng)：注：順序解法與逆序解法無(wú)本質(zhì)區(qū)別，一般來(lái)說(shuō)，當(dāng)初始狀態(tài)給定時(shí)用逆序解法，當(dāng)終止?fàn)顟B(tài)給定時(shí)用順序解法。若問(wèn)題給定了一個(gè)初始狀態(tài)與一個(gè)終止?fàn)顟B(tài)，則兩種方法均可使用。例2資源分配問(wèn)題（離散型）例：設(shè)有6萬(wàn)元資金用于4個(gè)工廠的擴(kuò)建，已知每個(gè)工廠的利潤(rùn)增長(zhǎng)額同投資額的大小有關(guān)，見(jiàn)下表。問(wèn)應(yīng)如何確定對(duì)這四個(gè)工廠的投資額，使總利潤(rùn)增長(zhǎng)額最大？投資額(j)工廠(i)010020030040050060010204260758590202545576570733018396178909540284765748085

表1利潤(rùn)增長(zhǎng)額

（百元）解：把對(duì)四個(gè)工廠的投資依次看成4個(gè)階段的決策過(guò)程，確定對(duì)第k個(gè)工廠的投資額看成第k個(gè)階段的決策，k=1,2,3,4。圖示如下：狀態(tài)變量：可用于第k,k+1,…n個(gè)工廠的投資額。決策變量：第k階段對(duì)第k個(gè)工廠的投資額。允許決策集：工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態(tài)狀態(tài)狀態(tài)狀態(tài)轉(zhuǎn)移方程：其中階段指標(biāo)函數(shù)：第k階段投資元時(shí)所產(chǎn)生的利潤(rùn)。（見(jiàn)上表）最優(yōu)指標(biāo)函數(shù)：第k階段狀態(tài)為且采取最佳投資策略，從第k個(gè)工廠以及以后的最大總利潤(rùn)。逆序法基本遞推方程：工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態(tài)狀態(tài)狀態(tài)投資額(j)工廠(i)010020030040050060040284765748085

表1利潤(rùn)增長(zhǎng)額

（百元）解：（1）k=4時(shí)考慮：若到最后一個(gè)，第4個(gè)工廠投資時(shí)，還有資金，若投資于第4個(gè)工廠的資金為，則最大利潤(rùn)為工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態(tài)狀態(tài)狀態(tài)投資額(j)工廠(i)010020030040050060040284765748085

表1利潤(rùn)增長(zhǎng)額

（百元）（注意到此時(shí)=0）自然問(wèn)：現(xiàn)在還有多少錢？即=？=0，100，200，300，400，500，600都有可能。下面分情況討論：工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態(tài)狀態(tài)狀態(tài)投資額(j)工廠(i)010020030040050060040284765748085

表1利潤(rùn)增長(zhǎng)額

（百元）時(shí)，時(shí)，其他種情況類似討論，我們把所有的結(jié)果匯總成一個(gè)表2。投資額(j)工廠(i)010020030040050060040284765748085

表1利潤(rùn)增長(zhǎng)額

（百元）01002003004005006000100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600表2

k=4時(shí)決策表投資額(j)工廠(i)010020030040050060010204260758590202545576570733018396178909540284765748085

表1利潤(rùn)增長(zhǎng)額

（百元）（2）k=3時(shí)到第三個(gè)工廠投資時(shí)，可利用的資金還有，若向第三個(gè)工廠投資（萬(wàn)元），則自此即以后最大利潤(rùn)為：

表1利潤(rùn)增長(zhǎng)額

（百元）投資額(j)工廠(i)010020030040050060030183961789095同樣問(wèn)：=？，即現(xiàn)在還有多少錢？它是允許決策集上界。同理僅舉一例：投資額(j)工廠(i)010020030040050060030183961789095

表1利潤(rùn)增長(zhǎng)額

（百元）01002003004005006000100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600表2

k=4時(shí)決策表投資額(j)工廠(i)010020030040050060030183961789095表1利潤(rùn)增長(zhǎng)額（百元）所有情況討論結(jié)果匯總成下表：010020030040050060001002003004005006000+00+2818+00+4718+2839+00+6518+4739+2861+00+7418+6539+4761+2878+00+8018+7439+6561+7478+2890+00+8518+8039+7461+6578+4790+2895+0028476789108126000200300300300表3

k=3時(shí)決策表（3）k=2時(shí)僅舉一例：投資額(j)工廠(i)010020030040050060020254557657073表1利潤(rùn)增長(zhǎng)額（百元）010020030040050060001002003004005006000+00+2818+00+4718+2839+00+6518+4739+2861+00+7418+6539+4761+2878+00+8018+7439+6561+7478+2890+00+8518+8039+7461+6578+4790+2895+0028476789108126000200300300300表3

k=3時(shí)決策表關(guān)于的其它取值情況及相應(yīng)的最優(yōu)決策列于下表010020030040050060001002003004005006000+00+2825+00+4725+2845+00+6725+4745+2857+00+8925+6745+4757+2865+00+10825+8945+6757+4765+2870+00+12625+10845+8957+6765+4770+2873+002853739211413400100200100或200100200

表4k=2時(shí)決策表（4）k=1時(shí)，此時(shí)投資額(j)工廠(i)010020030040050060010204260758590表1利潤(rùn)增長(zhǎng)額（百元）010020030040050060001002003004005006000+00+2825+00+4725+2845+00+6725+4745+2857+00+8925+6745+4757+2865+00+10825+8945+6757+4765+2870+00+12625+10845+8957+6765+4770+2873+002853739211413400100200100或200100200表4k=2時(shí)決策表匯一表格：0100200300400500600600134134134133138113901340或100或200表5k=1時(shí)決策表此時(shí)對(duì)應(yīng)最大值134的有三個(gè)值：

所對(duì)應(yīng)的最優(yōu)策略分別為：時(shí)，由狀態(tài)轉(zhuǎn)移方程知：所對(duì)應(yīng)的010020030040050060001002003004005006000+00+2825+00+4725+2845+00+6725+4745+2857+00+8925+6745+4757+2865+00+10825+8945+6757+4765+2870+00+12625+10845+8957+6765+4770+2873+002853739211413400100200100或200100200表4k=2時(shí)決策表對(duì)應(yīng)的

再由狀態(tài)轉(zhuǎn)移方程對(duì)應(yīng)的

010020030040050060001002003004005006000+00+2818+00+4718+2839+00+6518+4739+2861+00+7418+6539+4761+2878+00+8018+7439+6561+7478+2890+00+8518+8039+7461+6578+4790+2895+0028476789108126000200300300300表3

k=3時(shí)決策表所對(duì)應(yīng)的

再由狀態(tài)轉(zhuǎn)移方程對(duì)應(yīng)的

0100200300400500600010020030040050060000280284702847650284765