運(yùn)籌學(xué)課件動(dòng)態(tài)規(guī)劃2511214106104131112396581052C1C3D1AB1B3B2D2EC2最短路徑問(wèn)題求從A到E的最短路徑從起點(diǎn)A到終點(diǎn)E要經(jīng)過(guò)A、B、C、D、E五站，每一站可以在不同的備選地點(diǎn)停留。每一站的備選地點(diǎn)，每個(gè)地點(diǎn)和下一站的各備選地點(diǎn)之間的距離如下圖。第2頁(yè),共43頁(yè)，2024年2月25日，星期天動(dòng)態(tài)規(guī)劃用一種全新的思路來(lái)考慮這樣的問(wèn)題。首先，把一個(gè)復(fù)雜的問(wèn)題歸結(jié)為若干個(gè)與原問(wèn)題性質(zhì)完全相同，但規(guī)模較小的子問(wèn)題，每一個(gè)子問(wèn)題又可以遞歸地歸結(jié)為性質(zhì)相同，規(guī)模更小的下層子問(wèn)題。如此不斷進(jìn)行，一直到子問(wèn)題非常簡(jiǎn)單，可以解決為止。然后，從這些最簡(jiǎn)單的子問(wèn)題出發(fā)，依次計(jì)算上一層子問(wèn)題的最優(yōu)解，直到求出原問(wèn)題的最優(yōu)解。以最短路徑問(wèn)題為例，來(lái)說(shuō)明動(dòng)態(tài)規(guī)劃的基本思想。第3頁(yè),共43頁(yè)，2024年2月25日，星期天從A到E的最短路徑S(A)，可以轉(zhuǎn)化為三個(gè)性質(zhì)完全相同，但規(guī)模較小的子問(wèn)題，即分別從B1、B2、B3到E的最短路徑，記為S(B1),S(B2),S(B3)。121410B1131112B36104B2396581052C1C3D1D2EC2251A第4頁(yè),共43頁(yè)，2024年2月25日，星期天A2121410B11131112B356104B2396581052C1C3D1D2EC2第5頁(yè),共43頁(yè)，2024年2月25日，星期天121410B1131112B36104B2396581052C1C3D1D2EC2同樣，計(jì)算S(B1)、S(B2)、S(B3)又可以歸結(jié)為性質(zhì)完全相同，但規(guī)模更小的問(wèn)題，即分別求C1，C2，C3到E的最短路徑問(wèn)題S(Ci)(i=1,2,3)。第6頁(yè),共43頁(yè)，2024年2月25日，星期天121410B1396581052C1C3D1D2EC2第7頁(yè),共43頁(yè)，2024年2月25日，星期天6104B2396581052C1C3D1D2EC2第8頁(yè),共43頁(yè)，2024年2月25日，星期天131112B3396581052C1C3D1D2EC2第9頁(yè),共43頁(yè)，2024年2月25日，星期天39C1810C352D1D2E65C2計(jì)算S(Ci)又可以歸結(jié)為求從D1和D2到E的最短路徑S(D1)和S(D2)這兩個(gè)子問(wèn)題。第10頁(yè),共43頁(yè)，2024年2月25日，星期天39C152D1D2E第11頁(yè),共43頁(yè)，2024年2月25日，星期天52D1D2E65C2第12頁(yè),共43頁(yè)，2024年2月25日，星期天810C352D1D2E第13頁(yè),共43頁(yè)，2024年2月25日，星期天S(D1)和S(D2)是已知的，它們分別是：S(D1)=5，S(D2)=2。因而，可以從這兩個(gè)值開(kāi)始，逆向遞歸計(jì)算S(A)的值。5D12D2E第14頁(yè),共43頁(yè)，2024年2月25日，星期天[引例]馬車驛站問(wèn)題124833538667863235AB2B1D2D1C3C2C4C1EA—B—C—D—E階段1階段2階段3階段44個(gè)階段EED1

D2D1

D2D1

D2D1

D2C2

C3

C4C1

C2

C31D1E1D2E2C4D1

C4D22C3D1

C3D22C2D1

C2D22C1D1

C1D23B2C2

B2C3

B2C43B1C1

B1C2

B1C3B1

B22AB1

AB2AB2B1C4C3C2C1D1D24321終點(diǎn)路線數(shù)可選路線起點(diǎn)階段一共有2×3×2×1=12條不同的路線f(E)=0f(D1)=2f(D2)=1f(C1)=8f(C2)=5f(C3)=4f(C1)=5f(B1)=8f(B2)=11f(A)=13回顧分析過(guò)程:1.將分析對(duì)象劃分成4階段;2.每階段始點(diǎn)狀態(tài)與終點(diǎn)狀態(tài)有關(guān),而不考慮始終點(diǎn)狀態(tài)如何形成(無(wú)記憶性);3.每階段各始點(diǎn)狀態(tài)為終點(diǎn)狀態(tài)與始點(diǎn)至終點(diǎn)距離之和的最小值(狀態(tài)轉(zhuǎn)移)這種最優(yōu)化方法稱為動(dòng)態(tài)規(guī)劃,由美國(guó)數(shù)學(xué)家貝爾曼等人于20世紀(jì)50年代創(chuàng)立.第15頁(yè),共43頁(yè)，2024年2月25日，星期天13.1.1動(dòng)態(tài)規(guī)劃的基本概念1.階段:把所給問(wèn)題的過(guò)程，恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段，以便能按一定的次序去求解。描述階段的變量稱為階段變量，常用k表示。[導(dǎo)入案例]中k=1,2,3,42.狀態(tài)變量:每個(gè)階段開(kāi)始所處的自然狀況或客觀條件(用點(diǎn)集表示).如引例:

第1階段的狀態(tài)就是起點(diǎn)A,記為s1={A};

第2階段有2個(gè)狀態(tài){B1,B2},記為s2={B1,B2};

第3階段有4個(gè)狀態(tài){C1,C2,C3,C4},記為s3={C1,C2,C3,C4};

第4階段有2個(gè)狀態(tài){D1,D2},記為s4={D1,D2};3.決策變量:在某一階段的某個(gè)狀態(tài)時(shí)的不同選擇,如引例中B1狀態(tài)下有3種選擇:

B1—C1,B1—C2,B1—C3

這3種選擇構(gòu)成了允許決策的集合。不同狀態(tài)下允許決策的集合也不同，故決策變量是狀態(tài)變量的函數(shù)，即xk(sk)∈D(sk)124833538667863235AB2B1D2D1C3C2C4C1EA—B—C—D—E階段1階段2階段3階段44個(gè)階段4.策略按順序排列的決策組成的集合，由過(guò)程的第k階段開(kāi)始到終止?fàn)顟B(tài)為止的過(guò)程(或k子過(guò)程),k子過(guò)程的策略稱子策略，記為Pk,n(sk),即Pk,n(sk)={xk(sk),xk+1(sk+1),…,xn(sn)}當(dāng)k=1時(shí)，即為全過(guò)程的一個(gè)策略。如引例中：D—E，即4到5過(guò)程起始有2個(gè)狀態(tài)，D1和D2，因此有P4,5={D1—E，D2—E}5.狀態(tài)轉(zhuǎn)移方程確定過(guò)程是由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程。第k階段狀態(tài)變量值給定后，如果確定決策變量，第k+1階段狀態(tài)變量值就完全確定。即：sk+1=T(sk,xk)如引例中：若對(duì)A—B1,A—B2選擇了A—B1,則s2=5,B1到C有3種選擇:B1—C1、B1—C2、B1—C3，若選擇了B1—C2,則s3=s2+d(B1,C2)=86.指標(biāo)函數(shù)用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的一種數(shù)量指標(biāo)。其基本方程有加法和乘法兩種形式，通常加法形式用的較多，其公式為：7.邊界條件起始或終止條件。第16頁(yè),共43頁(yè)，2024年2月25日，星期天13.1.2動(dòng)態(tài)規(guī)劃的基本原理124833538667863235AB2B1D2D1C3C2C4C1EA—B—C—D—E階段1階段2階段3階段44個(gè)階段最優(yōu)化原理

(Optimalityprinciple):最優(yōu)策略具備這樣的性質(zhì):無(wú)論初始狀態(tài)與初始決策如何,以后諸決策對(duì)以第一個(gè)決策所形成的狀態(tài)作為初始狀態(tài)的過(guò)程而言,必然構(gòu)成最優(yōu)策策略.通俗地說(shuō):最優(yōu)策略的子策略也是最優(yōu)的.例如，在導(dǎo)入案例中，最優(yōu)策略是A—B1—C2—D1—E,最短距離為13,其子策略:B1—C2—D1—E,C2—D1—E,D1—E也是最優(yōu)的。依據(jù)這一原理，從后往前推各階段最優(yōu)子過(guò)程，從而得到全程最優(yōu)過(guò)程。設(shè)f(i)表示從點(diǎn)i到終點(diǎn)E的最短距離,d(i,j)表示點(diǎn)i,j之間的距離.顯然f(E)=0,為該問(wèn)題的邊界條件.k=4決策：D1Ek=3決策：D2E決策：C1D1決策：C2D1k=2決策：C3D2決策：C4D2決策：B1C2決策：B2C3k=1決策：AB1最短路線:AB1C2D1E最短路長(zhǎng):13第17頁(yè),共43頁(yè)，2024年2月25日，星期天動(dòng)態(tài)規(guī)劃用一種全新的思路來(lái)考慮這樣的問(wèn)題。首先，把一個(gè)復(fù)雜的問(wèn)題歸結(jié)為若干個(gè)與原問(wèn)題性質(zhì)完全相同，但規(guī)模較小的子問(wèn)題，每一個(gè)子問(wèn)題又可以遞歸地歸結(jié)為性質(zhì)相同，規(guī)模更小的下層子問(wèn)題。如此不斷進(jìn)行，一直到子問(wèn)題非常簡(jiǎn)單，可以解決為止。然后，從這些最簡(jiǎn)單的子問(wèn)題出發(fā)，依次計(jì)算上一層子問(wèn)題的最優(yōu)解，直到求出原問(wèn)題的最優(yōu)解。第18頁(yè),共43頁(yè)，2024年2月25日，星期天Bellman最優(yōu)性原理“作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：無(wú)論過(guò)去的狀態(tài)和決策如何，相對(duì)于前面決策所形成的狀態(tài)，余下的決策必然形成最優(yōu)子策略”一個(gè)最優(yōu)策略的子策略總是最優(yōu)的。第19頁(yè),共43頁(yè)，2024年2月25日，星期天劃分階段確定狀態(tài)變量及允許狀態(tài)集合確定決策變量及決策空間確定狀態(tài)轉(zhuǎn)移方程確定最優(yōu)指標(biāo)函數(shù)并建立遞歸方程

13.2.1動(dòng)態(tài)規(guī)劃模型的建立第20頁(yè),共43頁(yè)，2024年2月25日，星期天例：最短路徑問(wèn)題找出A到E的最短路徑

第21頁(yè),共43頁(yè)，2024年2月25日，星期天（1）分為四階段，k=1,2,3,4。（2）令Sk

（k→n）為k階段初所處的位置。（3）令決策變量xk為處于某階段某位置時(shí)，選擇下一個(gè)位置。（4）狀態(tài)轉(zhuǎn)移方程

（5）遞歸方程（k→n）第22頁(yè),共43頁(yè)，2024年2月25日，星期天1、劃分為4個(gè)階段2、用點(diǎn)集表示各階段的狀態(tài)S1=｛A｝;s2=｛B1,B2,B3｝,s3=｛C1,C2,C3｝;s4=｛D1,D2｝3、指標(biāo)函數(shù)：Vk，4（i）為第k階段第i點(diǎn)到E點(diǎn)的距離4、最優(yōu)值函數(shù)fk（i）為i點(diǎn)到E的最短距離5、決策變量xk=d[i,j]為第k階段第i狀態(tài)的選擇6、邊界條件：f5（E）=07、基本方程：fk（i）=min｛d[i,j]+fk+1（j）｝(k=1,2,3,4)第23頁(yè),共43頁(yè)，2024年2月25日，星期天模型求解逆序法已知邊界條件終點(diǎn)順序法已知始點(diǎn)邊界條件第24頁(yè),共43頁(yè)，2024年2月25日，星期天逆序法求解k=4第25頁(yè),共43頁(yè)，2024年2月25日，星期天

k=3第26頁(yè),共43頁(yè)，2024年2月25日，星期天

k=2第27頁(yè),共43頁(yè)，2024年2月25日，星期天k=1最優(yōu)路徑為最短距離為19第28頁(yè),共43頁(yè)，2024年2月25日，星期天最優(yōu)解第29頁(yè),共43頁(yè)，2024年2月25日，星期天總結(jié)：逆序法最優(yōu)值函數(shù)f(k):從k階段到E的最短距離；階段指標(biāo)函數(shù),即該階段選擇不同路線的距離。從后向前推。S1={A}S2={B1,B2}S3={C1,C2,C3,C4}S4={D1,D2}S5={E}f5(E)=0同理f4(D1)=2,f4(D2)=1同理f3(C2)=5,f3(C3)=4,f3(c4)=5同理f2(B2)=11124833538667863235AB2B1D2D1C3C2C4C1EA—B—C—D—E階段1階段2階段3階段4第30頁(yè),共43頁(yè)，2024年2月25日，星期天13.2.2動(dòng)態(tài)規(guī)劃問(wèn)題的解法:順序法124833538667863235AB2B1D2D1C3C2C4C1EA—B—C—D—E階段1階段2階段3階段4最優(yōu)值函數(shù)f(k):從A到k階段的最短距離；階段指標(biāo)函數(shù),即該階段選擇不同路線的距離。從前向后推。S0={A}S1={B1,B2}S2={C1,C2,C3,C4}S3={D1,D2}S4={E}最優(yōu)值函數(shù):f0(A)=0f1(B1)=5,f2(B2)=3f2(C1)=7,f3(C2)=8,f3(C3)=10,f3(c4)=9f3(D1)=11,f4(D2)=13第31頁(yè),共43頁(yè)，2024年2月25日，星期天案例---資源分配解把生產(chǎn)第k種產(chǎn)品看成是第k階段，劃分為n個(gè)階段.設(shè)sk表示第k階段初資源可用量（狀態(tài)變量）

xk表示分配給第k階段資源的數(shù)量（決策變量），顯然有：允許決策集合

sk+1=sk-xk

（狀態(tài)轉(zhuǎn)移方程）s1=a

（邊界條件）指標(biāo)函數(shù)：若fk(sk)表示數(shù)量為sk資源分配給第k種產(chǎn)品時(shí)，從第k階段到第n階段總收益，則有：設(shè)某公司有某種原料，其數(shù)量為a，用于生產(chǎn)n種產(chǎn)品。若分配數(shù)量xi用于生產(chǎn)第i種產(chǎn)品，其收益為gi（xi）。問(wèn)應(yīng)如何分配，才能使生產(chǎn)n種產(chǎn)品的總收入最大？第32頁(yè),共43頁(yè)，2024年2月25日，星期天例1資源分配問(wèn)題5臺(tái)設(shè)備分配給3個(gè)工廠，盈利表如下，如何分配可使獲利最大？

臺(tái)數(shù)工廠012345甲乙丙00045389711119111211111212分析3個(gè)工廠看成3個(gè)階段.階段變量k(k=1,2,3)；狀態(tài)變量sk表示為分配給第k個(gè)工廠至第n個(gè)工廠的設(shè)備臺(tái)數(shù)；決策變量xk

表示分配給第k個(gè)工廠的設(shè)備臺(tái)數(shù)；則有sk+1=sk-xk；Pk(xk)表示為xk

臺(tái)設(shè)備分配到第k個(gè)工廠所得贏利值；fk(sk)表示為臺(tái)設(shè)備分配給第k個(gè)工廠至第n個(gè)工廠所得到的最大贏利值。則有:第33頁(yè),共43頁(yè)，2024年2月25日，星期天k=3x3s3P3(x3)f3(s3)x3*0123450123450379111203791112012345k=2x2s2P2(x2)+f3(s2-x2)f2(s2)x2*01234501234500+30+70+90+110+125+05+35+75+95+119+09+39+79+911+011+311+712+012+312+00591216180121，222，3k=1x1s1P1(x1)+f2(s1-x1)f1(s1)x1*01234550+184+168+1211+911+511+0201，2，3012345甲乙丙00045389711119111211111212方案一:1,2,2方案二:2,1,2方案三:2,2,1方案四:3,2,0第34頁(yè),共43頁(yè)，2024年2月25日，星期天案例2設(shè)備負(fù)荷問(wèn)題某種機(jī)器可在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)，設(shè)機(jī)器在高負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為g=9x，其中x為投入生產(chǎn)的機(jī)器數(shù)量，季度完好率為a=0.65，在低負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為h=4y，其中y為投入生產(chǎn)的機(jī)器數(shù)量，季度完好率為b=0.95。設(shè)資源擁有量100.解4季度看成4階段

sk第k季初擁有完好機(jī)器數(shù)

xk第k季分配給高負(fù)荷機(jī)器數(shù),則低負(fù)荷分配數(shù)sk-xk

下季度初完好機(jī)器數(shù)sk+1=0.65xk+0.95(sk-xk)

第k季產(chǎn)量vk=6xk+4(sk-xk)第35頁(yè),共43頁(yè)，2024年2月25日，星期天k=4f4是x4的增函數(shù),故最大值解為x4*=s4,相應(yīng)地有f4(s4)=9s4k=3f3是x3的增函數(shù),故最大值解為x3*=s3,相應(yīng)地有f3(s3)=14.85s3第36頁(yè),共43頁(yè)，2024年2月25日，星期天k=2f2是x2的增函數(shù),故最大值解為x2*=s2,相應(yīng)地有f2(s2)=18.6525s2k=1f1是x1的減函數(shù),故最大值解為x1*=0,相應(yīng)地有f1(s1)=21.719875s1=2172反向推算，由s1=100，x1﹡=0，知s2=95，x2﹡=95，s3=61.75，x3﹡=61.75，s4=40.14，x4﹡=40.14，s5=26.09。即第1季度設(shè)備100%全部分配給低負(fù)荷第2季度初完好設(shè)備為95%，全部分配給高負(fù)荷第3季度完好設(shè)備為61.75%，全部分配給高負(fù)荷第4季度完好設(shè)備為40.14%，全部分配給高負(fù)荷。全年結(jié)束后，設(shè)備完好率為26.09%.最大產(chǎn)量2172。第37頁(yè),共4