第三講動(dòng)態(tài)規(guī)劃高級(jí)運(yùn)籌學(xué)課件

第三講動(dòng)態(tài)規(guī)劃高級(jí)運(yùn)籌學(xué)課件1第一頁(yè)，共五十二頁(yè)，2022年，8月28日§4.1動(dòng)態(tài)規(guī)劃的基本概念和最優(yōu)化原理一、引例（最短路問(wèn)題）

假如上圖是一個(gè)線路網(wǎng)絡(luò)，兩點(diǎn)之間連線上的數(shù)字表示兩點(diǎn)間的距離（或費(fèi)用），我們的問(wèn)題是要將貨物從A地運(yùn)往E地，中間通過(guò)B、C、D三個(gè)區(qū)域，在區(qū)域內(nèi)有多條路徑可走，現(xiàn)求一條由A到E的線路，使總距離最短（或總費(fèi)用最小）。AB1B2B3C1C2C3D1D2E243746324265346333342第二頁(yè)，共五十二頁(yè)，2022年，8月28日

將該問(wèn)題劃分為4個(gè)階段的決策問(wèn)題，即第一階段為從A到Bj（j=1，2，3），有三種決策方案可供選擇；第二階段為從Bj到Cj（j=1,2,3），也有三種方案可供選擇；第三階段為從Cj到Dj(j=1,2)，有兩種方案可供選擇；第四階段為從Dj到E，只有一種方案選擇。如果用完全枚舉法，則可供選擇的路線有3×3×2×1=18（條），將其一一比較才可找出最短路線：A→B1→C2→D3→E

其長(zhǎng)度為12。顯然，這種方法是不經(jīng)濟(jì)的，特別是當(dāng)階段數(shù)很多，各階段可供的選擇也很多時(shí)，這種解法甚至在計(jì)算機(jī)上完成也是不現(xiàn)實(shí)的。由于我們考慮的是從全局上解決求A到E的最短路問(wèn)題，而不是就某一階段解決最短路線，因此可考慮從最后一階段開(kāi)始計(jì)算，由后向前逐步推至A點(diǎn)：3第三頁(yè)，共五十二頁(yè)，2022年，8月28日第四階段，由D1到E只有一條路線，其長(zhǎng)度f(wàn)4（D1）=3，同理f4（D2）=4。第三階段，由Cj到Di分別均有兩種選擇，即，決策點(diǎn)為D1,決策點(diǎn)為D1，決策點(diǎn)為D24第四頁(yè)，共五十二頁(yè)，2022年，8月28日第二階段，由Bj到Cj分別均有三種選擇，即：決策點(diǎn)為C2

決策點(diǎn)為C1或C2決策點(diǎn)為C2

5第五頁(yè)，共五十二頁(yè)，2022年，8月28日第一階段，由A到B，有三種選擇，即：決策點(diǎn)為B3f1（A）=15說(shuō)明從A到E的最短距離為12，最短路線的確定可按計(jì)算順序反推而得。即A→B3→C2→D2→E

上述最短路線問(wèn)題的計(jì)算過(guò)程，也可借助于圖形直觀的表示出來(lái)：6第六頁(yè)，共五十二頁(yè)，2022年，8月28日

圖中各點(diǎn)上方框的數(shù)，表示該點(diǎn)到E的最短距離。圖中紅箭線表示從A到E的最短路線。從引例的求解過(guò)程可以得到以下啟示：

①對(duì)一個(gè)問(wèn)題是否用上述方法求解，其關(guān)鍵在于能否將問(wèn)題轉(zhuǎn)化為相互聯(lián)系的決策過(guò)程相同的多個(gè)階段決策問(wèn)題。

AB1B2B3C1C2C3D1D2E24374632426534633334346769911127第七頁(yè)，共五十二頁(yè)，2022年，8月28日

所謂多階段決策問(wèn)題是：把一個(gè)問(wèn)題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程，也稱(chēng)為序貫決策過(guò)程。如下圖所示：

②在處理各階段決策的選取上，不僅只依賴(lài)于當(dāng)前面臨的狀態(tài)，而且還要注意對(duì)以后的發(fā)展。即是從全局考慮解決局部（階段）的問(wèn)題。③各階段選取的決策，一般與“時(shí)序”有關(guān)，決策依賴(lài)于當(dāng)前的狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，整個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)，故有“動(dòng)態(tài)”含義。因此，把這種方法稱(chēng)為動(dòng)態(tài)規(guī)劃方法。④決策過(guò)程是與階段發(fā)展過(guò)程逆向而行。8第八頁(yè)，共五十二頁(yè)，2022年，8月28日

二、多階段決策問(wèn)題的典型例子：企業(yè)在生產(chǎn)過(guò)程中，由于需求是隨著時(shí)間變化的因素，因此企業(yè)為了獲得全年最佳經(jīng)濟(jì)效益，就要在整個(gè)生產(chǎn)過(guò)程中逐月或逐季的根據(jù)庫(kù)存和需求決定生產(chǎn)計(jì)劃。某種機(jī)器，可以在高、低兩種負(fù)荷下生產(chǎn)。高負(fù)荷下生產(chǎn)的產(chǎn)量多，但每生產(chǎn)一個(gè)階段后機(jī)器的完好率低；低負(fù)荷下生產(chǎn)時(shí)的情況則相反?，F(xiàn)在需要安排該種機(jī)器在多個(gè)階段內(nèi)的生產(chǎn)，問(wèn)應(yīng)該如何決定各階段中機(jī)器的使用，使整個(gè)計(jì)劃期內(nèi)的總產(chǎn)量最大。某臺(tái)設(shè)備，例如汽車(chē)，剛買(mǎi)來(lái)時(shí)故障少，耗油低，出車(chē)時(shí)間長(zhǎng)，處理價(jià)值和經(jīng)濟(jì)效益高。隨著使用時(shí)間的增加則變?yōu)楣收隙?，耗油高，維修費(fèi)用增加，經(jīng)濟(jì)效益差。使用時(shí)間愈長(zhǎng)，處理價(jià)值也愈低。另外，每次更新都要付出更新費(fèi)用。因此，應(yīng)當(dāng)如何決定設(shè)備的使用年限，使總的效益最佳。9第九頁(yè)，共五十二頁(yè)，2022年，8月28日三、動(dòng)態(tài)規(guī)劃方法的特點(diǎn)

優(yōu)點(diǎn)：①許多問(wèn)題用動(dòng)態(tài)規(guī)劃研究求解比線性規(guī)劃、非線性規(guī)劃更有效，特別是離散性問(wèn)題，解析數(shù)學(xué)無(wú)用武之地，而動(dòng)態(tài)規(guī)劃成為得力工具；②某些情況下，用動(dòng)態(tài)規(guī)劃處理不僅能作定性描述分析，且可利用計(jì)算機(jī)給出求其數(shù)值解的方法。

缺點(diǎn)：①?zèng)]有統(tǒng)一的處理方法，求解時(shí)要根據(jù)問(wèn)題的性質(zhì)，結(jié)合多種數(shù)學(xué)技巧。因此，實(shí)踐經(jīng)驗(yàn)及創(chuàng)造性思維將起重要的引導(dǎo)作用。②“維數(shù)障礙”：當(dāng)變量個(gè)數(shù)太多時(shí)，由于計(jì)算機(jī)內(nèi)存和速度的限制導(dǎo)致問(wèn)題無(wú)法解決。有些問(wèn)題由于涉及的函數(shù)沒(méi)有理想的性質(zhì)使問(wèn)題只能用動(dòng)態(tài)規(guī)劃描述，而不能用動(dòng)態(tài)規(guī)劃方法求解。10第十頁(yè)，共五十二頁(yè)，2022年，8月28日§4.2動(dòng)態(tài)規(guī)劃的基本概念一、動(dòng)態(tài)規(guī)劃的基本要素

1、階段。階段的劃分，一般根據(jù)時(shí)序和空間的自然特征來(lái)劃分，但要便于把問(wèn)題的過(guò)程能轉(zhuǎn)化為階段決策的過(guò)程。描述階段的變量稱(chēng)為階段變量，常用自然數(shù)k表示。如引例可劃分為4個(gè)階段求解，k=1，2，3，4。

2、狀態(tài)。狀態(tài)就是階段的起始位置。它既是該階段某支路的起點(diǎn)，又是前一階段某支路的終點(diǎn)。（1）狀態(tài)變量和狀態(tài)集合。描述過(guò)程狀態(tài)的變量稱(chēng)為狀態(tài)變量。它可用一個(gè)數(shù)、一組數(shù)或一向量（多維情形）來(lái)描述，常用Sk表示第k階段的狀態(tài)變量。通常一個(gè)階段有若干個(gè)狀態(tài)。第k階段的狀態(tài)就是該階段所有始點(diǎn)的集合。如引例中11第十一頁(yè)，共五十二頁(yè)，2022年，8月28日

（2）狀態(tài)應(yīng)具有無(wú)后效性（即馬爾可夫性）。即如果某階段狀態(tài)給考慮，則在這階段以后過(guò)程的發(fā)展不受這階段以前各階段狀態(tài)的影響。3、決策與決策變量。在某階段對(duì)可供選擇狀態(tài)的決定（或選擇），稱(chēng)為決策。描述的變量稱(chēng)為決策變量。常用dk(Sk)表示第k階段處于狀態(tài)Sk時(shí)的決策變量，它是狀態(tài)變量的函數(shù)。決策變量允許取值的范圍，稱(chēng)為允許決策集合，常用Dk(Sk)表示。顯然dk（Sk）∈Dk(Sk)。如在引例的第二階段中，若從B1出發(fā)，D2（B1）={B1C1,B1C2,B1C3}如果決定選取B1C2，則d2（B1）=B1C2。12第十二頁(yè)，共五十二頁(yè)，2022年，8月28日稱(chēng)可供選擇策略的范圍，為允許策略集，用P表示。動(dòng)態(tài)規(guī)劃方法就是要從允許策略集P中找出最優(yōu)策略P1n*。

4、策略與子策略。策略是一個(gè)決策序列的集合。當(dāng)k=1時(shí)，P1n（S1）={d1(s1),d2(s2),…,dn(sn)}就稱(chēng)為全過(guò)程的一個(gè)策略，簡(jiǎn)稱(chēng)策略，簡(jiǎn)記為P1n(S1).

稱(chēng)Pk,n(Sk)={dk(sk),dk+1(sk+1),…,dn(sn)}為由第k階段開(kāi)始到最后階段止的一個(gè)子策略，簡(jiǎn)稱(chēng)后部子策略。簡(jiǎn)記為Pk,n(Sk)5、狀態(tài)轉(zhuǎn)移方程。它是確定過(guò)程由某一階段的一個(gè)狀態(tài)到下一階段另一狀態(tài)的演變過(guò)程，用Sk+1=Tk(Sk,dk)表示。該方程描述了由第k階段到第k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律。因此又稱(chēng)其為狀態(tài)轉(zhuǎn)移函數(shù)。13第十三頁(yè)，共五十二頁(yè)，2022年，8月28日6、階段指標(biāo)、指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)（1）衡量某階段決策效益優(yōu)劣的數(shù)量指標(biāo)，稱(chēng)為階段指標(biāo)，用vk(Sk,dk)表示第k階段的階段指標(biāo)。在不同的問(wèn)題中，其含義不同。它可以是距離、利潤(rùn)、成本等。在引例中，用dk=vk(Sk,dk)表示在第k階段由點(diǎn)Sk到點(diǎn)Sk+1=dk(Sk)距離。如d2(B3,C1)=6。14第十四頁(yè)，共五十二頁(yè)，2022年，8月28日（2）用于衡量所選定策略優(yōu)劣的數(shù)量指標(biāo)，稱(chēng)為指標(biāo)函數(shù)。它是定義在全過(guò)程和所有后部子過(guò)程上確定的數(shù)量函數(shù)。記為Vk,n(Sk,Pk,n).Vk,n(Sk,Pk,n)=Vk,n(Sk,dk,Sk+1,…Sn+1)k=1,2,…,n。構(gòu)成動(dòng)態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分離性，并滿足遞推關(guān)系。常見(jiàn)的指標(biāo)函數(shù)的形式有：①

②15第十五頁(yè)，共五十二頁(yè)，2022年，8月28日（3）最優(yōu)指標(biāo)函數(shù)fk(Sk),表示從第k階段的狀態(tài)Sk開(kāi)始采用最優(yōu)子策略P*k,n，到第n階段終止時(shí)所得到的指標(biāo)函數(shù)值。即fk(Sk)=OptVk,n(Sk,dk,…Sn+1)

其中Opt是最優(yōu)化（Optimum）的縮寫(xiě)，可根據(jù)題意取max或min。在引例中，指標(biāo)函數(shù)Vk,n表示在第k階段由點(diǎn)Sk至終點(diǎn)E的距離。fk(sk)表示第k階段點(diǎn)Sk到終點(diǎn)E的最短距離。f2(B1)=11表示從第2階段中的點(diǎn)B1到點(diǎn)E的最短距離。

16第十六頁(yè)，共五十二頁(yè)，2022年，8月28日7、基本方程（遞推關(guān)系式）從引例求A到E的最短路的計(jì)算過(guò)程中可以看出，在求解的各個(gè)階段，我們利用了k階段與k+1階段之間的遞推關(guān)系一般地，若則有若17第十七頁(yè)，共五十二頁(yè)，2022年，8月28日

1、基本思想：動(dòng)態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫(xiě)出基本方程，因此首先必須將問(wèn)題的過(guò)程劃分為多個(gè)相互聯(lián)系的多階段決策過(guò)程，恰當(dāng)?shù)剡x取狀態(tài)變量和決策變量及定義最優(yōu)指標(biāo)函數(shù)，從而把問(wèn)題化成一族同類(lèi)型的子問(wèn)題。然后從邊界條件開(kāi)始，逆過(guò)程行進(jìn)方向，逐段遞推尋優(yōu)。在每個(gè)子問(wèn)題求解時(shí)，均利用它前面已求出的子問(wèn)題的最優(yōu)化結(jié)果依次進(jìn)行，最后一個(gè)子問(wèn)題所得的最優(yōu)解，就是整個(gè)問(wèn)題的最優(yōu)解。在多階段決策過(guò)程中，動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前的一段和未來(lái)的各段分開(kāi)，又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法。因此，每階段決策的選取是從全局來(lái)考慮，與該段的最優(yōu)選擇一般是不同的。動(dòng)態(tài)規(guī)劃方法的基本思想體現(xiàn)了多階段性、無(wú)后效性、遞歸性、總體優(yōu)化性。二、動(dòng)態(tài)規(guī)劃的基本思想與最優(yōu)化原理18第十八頁(yè)，共五十二頁(yè)，2022年，8月28日

2、最優(yōu)化原理動(dòng)態(tài)規(guī)劃方法基于R·Bellman等人提出的最優(yōu)化原理：“作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)，即無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)于先前的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略?！焙?jiǎn)言之，“一個(gè)最優(yōu)策略的子策略總是最優(yōu)的”。但是，最優(yōu)化原理僅是策略最優(yōu)性的必要條件，而基本方程是策略最優(yōu)性的充要條件。由此可見(jiàn)，基本方程是動(dòng)態(tài)規(guī)劃理論與方法的基礎(chǔ)?！?.3動(dòng)態(tài)規(guī)劃模型的建立與求解一、構(gòu)成動(dòng)態(tài)規(guī)劃模型的條件19第十九頁(yè)，共五十二頁(yè)，2022年，8月28日

應(yīng)用動(dòng)態(tài)規(guī)劃解決問(wèn)題時(shí)必須首先建立動(dòng)態(tài)規(guī)劃模型，再用逆序或順序算法求解。寫(xiě)一個(gè)問(wèn)題的動(dòng)態(tài)規(guī)劃模型一般包含以下6個(gè)步驟：（1）階段劃分k=1,2,…,n

（2）確定狀態(tài)變量sk

（3）確定決策變量dk

（4）確定狀態(tài)轉(zhuǎn)移方程sk+1=f(sk,dk)或sk-1=f(sk,dk)

（5）確定階段指標(biāo)V(sk,dk)

（6）確定基本遞推方程或20第二十頁(yè)，共五十二頁(yè)，2022年，8月28日二、求解動(dòng)態(tài)規(guī)劃模型的方法1、在已知初始狀態(tài)S1下，采用逆序解法：（反向遞歸）

按上圖示意的求解方法稱(chēng)為逆序法。例如引例的求解，就是把A看作始端，E為終端，規(guī)定從A到E為過(guò)程的行進(jìn)方向，而尋優(yōu)則是從E到A逆過(guò)程進(jìn)行，所以是采用了逆序法。階段1s1d1(s1)v1(s1,d1)階段2s2d2(s2)v2(s2,d2)…階段kskdk(sk)vk(sk,dk)階段k+1sk+1dk+1(sk+1)vk+1(sk+1,dk+1)階段nsndn(sn)vn(sn,dn)…vk,nfk(sk)=optVk,n尋優(yōu)方向21第二十一頁(yè)，共五十二頁(yè)，2022年，8月28日2、在已知終止?fàn)顟B(tài)Sn下，采用順序解法（正向遞歸）

如果我們把引例中E看作始端，A為終端，規(guī)定從E到A過(guò)程為行進(jìn)方向，而尋優(yōu)則是從A到E過(guò)程進(jìn)行求解的方法稱(chēng)為順序法。其示意圖如下：

逆序法與順序法的不同僅在對(duì)始端終端看法的顛倒或在規(guī)定的行進(jìn)方向不同。但在尋優(yōu)時(shí)卻都是逆行進(jìn)方向，從最后一階段開(kāi)始，逐段逆推向前計(jì)算，找出最優(yōu)結(jié)果。…階段1s0d1(s1)v1(s1,d1)階段2s1d2(s2)v2(s2,d2)階段kdk(sk)vk(sk,dk)階段k+1sk+1dk+1(sk+1)vk+1(sk+1,dk+1)階段ndn(sn)vn(sn,dn)…vk,nfk(sk)=optV1,k尋優(yōu)方向sksn22第二十二頁(yè)，共五十二頁(yè)，2022年，8月28日3、兩種解法在建模時(shí)的區(qū)別如下表所示23第二十三頁(yè)，共五十二頁(yè)，2022年，8月28日案例1

某商店在未來(lái)四個(gè)月里，利用一個(gè)倉(cāng)庫(kù)經(jīng)銷(xiāo)某種商品。該倉(cāng)庫(kù)的最大容量為1000件，每月中旬訂購(gòu)商品，并于下月初取到訂貨。據(jù)估計(jì)，今后四個(gè)月這種商品的購(gòu)價(jià)和售價(jià)如下表所示。假定商店在1月初開(kāi)始經(jīng)銷(xiāo)時(shí)倉(cāng)庫(kù)已存有該種商品500件，每月市場(chǎng)需求不限，問(wèn)應(yīng)如何計(jì)劃每個(gè)月的訂購(gòu)與銷(xiāo)售量，使這四個(gè)月的總利潤(rùn)最大（不考慮倉(cāng)庫(kù)的存儲(chǔ)費(fèi)用）？月份k購(gòu)價(jià)pk售價(jià)qk110122993111341517解：首先建立動(dòng)態(tài)規(guī)劃模型。（1）問(wèn)題劃分為四個(gè)階段K=1，2，3，4；（2）狀態(tài)變量sk表示第k階段初的庫(kù)存量，且s1=50024第二十四頁(yè)，共五十二頁(yè)，2022年，8月28日（3）決策變量xk表示第k月的訂貨量，yk表示第k月的銷(xiāo)售量；（4）狀態(tài)轉(zhuǎn)移方程sk+1=sk+xk-yk,（5）指標(biāo)函數(shù)表示第k月的利潤(rùn)V(sk,xk,yk)=qkyk-pkxk（6）基本方程為其逆序計(jì)算過(guò)程見(jiàn)課本P10425第二十五頁(yè)，共五十二頁(yè)，2022年，8月28日解：當(dāng)K=4時(shí)，根據(jù)基本遞推方程顯然，y4*=s4,x4*=0為最優(yōu)決策，這時(shí)，f4(s4)=17s4當(dāng)K=3時(shí)，這是一個(gè)線性規(guī)劃問(wèn)題，解得最優(yōu)解為y3*=s3,x3*=H，f3(s3)=13s3+6H26第二十六頁(yè)，共五十二頁(yè)，2022年，8月28日當(dāng)K=2時(shí)，得最優(yōu)解為y2*=s2,x2*=H，f2(s2)=9s2+10H當(dāng)K=1時(shí)，得最優(yōu)解為y1*=s1,x1*=0，f1(s1)=12s1+10H將s1=500,H=1000代入上式，并按計(jì)算順序反推，得：x1*=0，y1*=s1=500x2*=H=1000，y2*=s2=s1+x1*-y1*=0x3*=H=1000，y2*=s3=s2+x2*-y2*=1000x4*=0，y4*=s4=s3+x3*-y3*=100027第二十七頁(yè)，共五十二頁(yè)，2022年，8月28日案例2

P118練習(xí)4.4

某工廠有100臺(tái)機(jī)器，擬分四期使用，在每一期都有兩種生產(chǎn)任務(wù)。據(jù)經(jīng)驗(yàn)，若把x1臺(tái)機(jī)器投入第一種生產(chǎn)任務(wù)，則在本期結(jié)束時(shí)將有1/3x1臺(tái)機(jī)器損壞報(bào)廢，剩下的機(jī)器全部投入第二種生產(chǎn)任務(wù)，則有1/10的機(jī)器在期未損壞報(bào)廢。如果干第一種生產(chǎn)任務(wù)時(shí)每臺(tái)機(jī)器可獲得利潤(rùn)10，干第二種生產(chǎn)任務(wù)時(shí)每臺(tái)機(jī)器可獲利潤(rùn)7，問(wèn)應(yīng)怎樣分配使用機(jī)器以使四期的總利潤(rùn)最大（期未剩下的完好機(jī)器數(shù)量不限）？解：1、首先建立動(dòng)態(tài)規(guī)劃模型。（1）問(wèn)題劃分為四個(gè)階段K=1，2，3，4；（2）狀態(tài)變量sk表示第k階段初可用于分配的機(jī)器數(shù)，且s1=100（3）決策變量xk表示第k階段分配于干第一種任務(wù)的機(jī)器數(shù)，則干第二種任務(wù)的機(jī)器數(shù)為sk-xk28第二十八頁(yè)，共五十二頁(yè)，2022年，8月28日（4）狀態(tài)轉(zhuǎn)移方程sk+1=2/3xk+9/10（sk-xk）=9/10sk-7/30xk,（5）階段指標(biāo)表示第k期的利潤(rùn)V(sk,xk)=10xk+7（sk-xk）=3xk+7sk（6）基本方程為：2、用逆序算法求解（見(jiàn)習(xí)題集P104）當(dāng)K=4時(shí)，根據(jù)基本遞推方程最優(yōu)解為x4*=s4,f4(s4)=10s429第二十九頁(yè)，共五十二頁(yè)，2022年，8月28日當(dāng)K=3時(shí)，最優(yōu)解為x3*=s3,f3(s3)=50s3/3當(dāng)K=2時(shí)，最優(yōu)解為x2*=0,f2(s2)=22s230第三十頁(yè)，共五十二頁(yè)，2022年，8月28日P106案例3

某廠在未來(lái)3個(gè)月連續(xù)生產(chǎn)某種產(chǎn)品。每月初開(kāi)始生產(chǎn)，月產(chǎn)量為x，生產(chǎn)成本為x2，庫(kù)存費(fèi)為每月每單位1元。假如3個(gè)月的需求量預(yù)測(cè)為：b1=100,b2=110,b3=120，且初始存貨s0=0，第三個(gè)月的期未存貨s3=0，問(wèn)應(yīng)如何安排生產(chǎn)使總成本最?。慨?dāng)K=1時(shí)，最優(yōu)解為x1*=0,f1(s1)=134s1/5=2680逆順序回推，得x1*=0，s1=100x2*=0，s2=9s1/10-7x1*/30=90x3*=s3=81，s3=9s2/10-7x2*/30=81x4*=s4=54，s4=9s3/10-7x3*/30=5431第三十一頁(yè)，共五十二頁(yè)，2022年，8月28日解法1：建立用逆序算法求解的動(dòng)態(tài)規(guī)劃模型（1）階段：K=1，2，3（2）狀態(tài)變量：SK表示第K月初的庫(kù)存，且已知S1=0，S4=0（3）決策變量：XK表示第K月的生產(chǎn)量（4）狀態(tài)轉(zhuǎn)移方程：Sk+1=Sk+Xk-bk，表示第K+1月初的庫(kù)存等于第K月的庫(kù)存加上該月的生產(chǎn)量再減去該月的需求量。（5）指標(biāo)函數(shù)：Vk(Sk,Xk)=Xk2+Sk，表示第K月的總費(fèi)用（生產(chǎn)成本加上庫(kù)存費(fèi)）（6）基本遞推方程：可用逆序得法進(jìn)行求解。32第三十二頁(yè)，共五十二頁(yè)，2022年，8月28日解法2：建立用順序算法求解的動(dòng)態(tài)規(guī)劃模型（1）階段：K=1，2，3（2）狀態(tài)變量：SK表示第K月末的庫(kù)存，且已知S0=0，S3=0（3）決策變量：XK表示第K月的生產(chǎn)量（4）狀態(tài)轉(zhuǎn)移方程：Sk-1=Sk-Xk+bk，表示第K-1月初的庫(kù)存等于第K月的庫(kù)存減去該月的生產(chǎn)量再加上該月的需求量。（5）指標(biāo)函數(shù)：Vk(Sk,Xk)=Xk2+Sk，表示第K月的總費(fèi)用（生產(chǎn)成本加上庫(kù)存費(fèi)）（6）基本遞推方程：可用順序得法進(jìn)行求解，詳細(xì)求解過(guò)程見(jiàn)課本P106。33第三十三頁(yè)，共五十二頁(yè)，2022年，8月28日當(dāng)K=1時(shí)當(dāng)K=2時(shí)利用微分求極值的方法,得34第三十四頁(yè)，共五十二頁(yè)，2022年，8月28日當(dāng)K=3時(shí)利用微分求極值的方法,得按計(jì)算順序反推,得最優(yōu)解為:35第三十五頁(yè)，共五十二頁(yè)，2022年，8月28日案例3（生產(chǎn)存貯問(wèn)題）某工廠與購(gòu)貨單位簽訂的供貨合同如下表。該廠每月最大產(chǎn)量為4百件，倉(cāng)庫(kù)的存貨能力為3百件。已知每一百件貨物的生產(chǎn)費(fèi)為一萬(wàn)元。在生產(chǎn)的月份，每批產(chǎn)品的生產(chǎn)準(zhǔn)備費(fèi)為4千元，倉(cāng)庫(kù)保管費(fèi)為每一百件貨物每月一千元。假定1月初開(kāi)始時(shí)及6月底交貨后倉(cāng)庫(kù)中都無(wú)存貨。問(wèn)該廠應(yīng)該如何安排每月的生產(chǎn)與庫(kù)存，才能既滿足交貨合同的要求，又使總費(fèi)用最?。吭路?23456交貨量（百件）125321解：1、建立動(dòng)態(tài)規(guī)劃模型（1）階段劃分：k=1，2，3，4，5，6（2）狀態(tài)變量sk表示第k月初的庫(kù)存量，s1=0（3）決策變量dk表示第k月的計(jì)劃生產(chǎn)量表示第月的合同交貨量36第三十六頁(yè)，共五十二頁(yè)，2022年，8月28日（4）狀態(tài)轉(zhuǎn)移方程：（5）第k月的總費(fèi)用包括生產(chǎn)費(fèi)和庫(kù)存費(fèi)（6）基本遞推方程2、用逆序算法求解當(dāng)k=6時(shí)，s6+d6-1=s7=0,所以s6+d6=1f6(s6)=min{v6(s6,d6)}

當(dāng)s6=0,d6=1,f6(s6)=14

當(dāng)s6=1,d6=0,f6(s6)=137第三十七頁(yè)，共五十二頁(yè)，2022年，8月28日當(dāng)k=5時(shí)，s5+d5-2=s6,所以請(qǐng)對(duì)照課本P108表4.6結(jié)果。38第三十八頁(yè)，共五十二頁(yè)，2022年，8月28日當(dāng)k=4時(shí)，s4+d4-3=s5,所以39第三十九頁(yè)，共五十二頁(yè)，2022年，8月28日求解結(jié)果對(duì)照課本P108表4.7結(jié)果。余下求解結(jié)果參看課本P108，所求最優(yōu)決策結(jié)果如下表：月初存貨量

sk最優(yōu)生產(chǎn)量

dk月底存貨量

sk+104130214503303210140第四十頁(yè)，共五十二頁(yè)，2022年，8月28日案例4

（背包問(wèn)題）某工廠生產(chǎn)三種產(chǎn)品，各種產(chǎn)品重量與利潤(rùn)的關(guān)系下表所示。現(xiàn)將此三種產(chǎn)品運(yùn)往市場(chǎng)出售，運(yùn)輸能力總重量不超過(guò)6噸，問(wèn)如何安排使運(yùn)輸總利潤(rùn)最大？種類(lèi)重量（噸/件）利潤(rùn)（元/件）12802418033130解：其實(shí)本例是一個(gè)整數(shù)規(guī)劃問(wèn)題，其整數(shù)規(guī)劃模型如下但是由于整數(shù)規(guī)劃的求解需用分枝定界法求解，計(jì)算量非常大，因而在此我們選用動(dòng)態(tài)規(guī)劃方法來(lái)解。41第四十一頁(yè)，共五十二頁(yè)，2022年，8月28日1、建立動(dòng)態(tài)規(guī)劃模型（在此用的是逆序算法求解，與課本不同）（1）階段劃分：k=1,2,3，把裝載一種產(chǎn)品看成一個(gè)階段（2）狀態(tài)變量sk表示第k階段初可用于裝載產(chǎn)品的總?cè)萘苛?，s1=6（3）決策變量dk表示第k階段裝載第k種貨物的件數(shù)。（4）狀態(tài)轉(zhuǎn)移方程：其中ak表示第k種貨物的單件重量（6）基本遞推方程（5）指標(biāo)函數(shù)：vk(sk,dk)表示裝載第k種貨物dk件所得的利潤(rùn)，即v1(s1,d1)=80d1,v2(s2,d2)=180d2,v3(s3,d3)=130d342第四十二頁(yè)，共五十二頁(yè)，2022年，8月28日2、用逆序法求解。其結(jié)果如下表s3d3f3(s3)d3*000*01000200030101301401013015010130160120130260*243第四十三頁(yè)，共五十二頁(yè)，2022年，8月28日其計(jì)算結(jié)果如下表s2d2s3f3(s3)f2(s2)d2*00000010100020200030313013014014013000+130180+0*1501511301800+130180+01601622601800+260*180+0044第四十四頁(yè)，共五十二頁(yè)，2022年，8月28日其計(jì)算結(jié)果如下表s1d1s2f2(s2)f1(s1)d1*601236420260180000+260*80+180*160+0240+001按計(jì)算次序反推，得到最優(yōu)解有兩個(gè)：（1）x1=0,x2=0,x3=2；（2）x1=1,x2=1,x3=0；45第四十五頁(yè)，共五十二頁(yè)，2022年，8月28日案例5（一維資源分配問(wèn)題）某公司擬將3千萬(wàn)元資金用于改造擴(kuò)建所屬的3個(gè)工廠，每個(gè)工廠的利潤(rùn)增長(zhǎng)額與所分配到的投資額有關(guān)。各工廠在獲得不同的投資額時(shí)所能增加的利潤(rùn)如下表。問(wèn)應(yīng)如何分配這些資金，使公司總的利潤(rùn)增長(zhǎng)額最大？

投資工廠0102030102.541020358.530269解：這是一個(gè)靜態(tài)問(wèn)題，通過(guò)將對(duì)三個(gè)工廠的投資看成三個(gè)階段化為一個(gè)多階段的動(dòng)態(tài)問(wèn)題。1、建立動(dòng)態(tài)規(guī)劃模型（1）階段劃分：k=1,2,3，把對(duì)每個(gè)工廠的投資看成一個(gè)階段（2）狀態(tài)變量sk表示第k階段初可用于投資的投資總額，s1=346第四十六頁(yè)，共五十二頁(yè)，2022年，8月28日（3）決策變量dk表示第k階段對(duì)第k個(gè)工廠的投資額。（4）狀態(tài)轉(zhuǎn)移方程：（5）階段指標(biāo)vk(sk,dk)表示對(duì)k第個(gè)工廠投資dk后所增加的利潤(rùn)，其值為表中數(shù)據(jù)。（6）基本遞推方程2、用逆序算法求解。