第7章 動(dòng)態(tài)規(guī)劃實(shí)驗(yàn)

第7章動(dòng)態(tài)規(guī)劃實(shí)驗(yàn)基礎(chǔ)知識(shí)使用Lingo軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題利用WinQSB

軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題使用MATLAB軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題基礎(chǔ)知識(shí)

動(dòng)態(tài)規(guī)劃是解決多階段決策過(guò)程最優(yōu)化問(wèn)題的一種數(shù)學(xué)方法。20世紀(jì)50年代初，美國(guó)數(shù)學(xué)家貝爾曼（Bellman）等人提出了解決多階段決策問(wèn)題的最優(yōu)性原理，從而創(chuàng)建了解決最優(yōu)化問(wèn)題的一種新方法——?jiǎng)討B(tài)規(guī)劃。該方法將多階段決策問(wèn)題轉(zhuǎn)換成一系列互相聯(lián)系的單階段問(wèn)題，然后逐個(gè)解決。動(dòng)態(tài)規(guī)劃是現(xiàn)代管理中重要的決策方法，可以解決最優(yōu)路徑、資源分配、庫(kù)存、生產(chǎn)過(guò)程優(yōu)化和設(shè)備更新等許多實(shí)際問(wèn)題。動(dòng)態(tài)規(guī)劃模型包含的要素（1）階段：把所給定問(wèn)題的過(guò)程，恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段，以便能按一定的次序求解。階段的劃分，一般是按照時(shí)間或空間的自然特征來(lái)劃分的，將問(wèn)題的過(guò)程轉(zhuǎn)化為多階段決策過(guò)程。（2）狀態(tài)：表示每個(gè)階段開(kāi)始所處的自然狀況或客觀條件，它描述了研究問(wèn)題過(guò)程的狀況。狀態(tài)是某階段做出決策的出發(fā)點(diǎn)和依據(jù)，且有無(wú)后效性。（3）決策：表示當(dāng)過(guò)程處于某一階段的某個(gè)狀態(tài)時(shí)，可以做出不同的決定，從而確定下一階段的狀態(tài)。（4）策略：是按一定順序排列的決策組成的集合。（5）狀態(tài)轉(zhuǎn)移方程：是確定過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程。（6）指標(biāo)函數(shù)和最優(yōu)值函數(shù)：用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的一種數(shù)量指標(biāo)為指標(biāo)函數(shù)；指標(biāo)函數(shù)的最優(yōu)值為最優(yōu)值函數(shù)。基礎(chǔ)知識(shí)

基礎(chǔ)知識(shí)

使用Lingo軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

實(shí)驗(yàn)?zāi)康模?）熟悉使用Lingo軟件求解最短路徑問(wèn)題、背包問(wèn)題和生產(chǎn)與儲(chǔ)存問(wèn)題。（2）通過(guò)使用Lingo軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題，進(jìn)一步熟悉Lingo軟件的基本命令及語(yǔ)法。實(shí)驗(yàn)內(nèi)容例7.1（最短路徑問(wèn)題）網(wǎng)絡(luò)圖如圖7-1所示，求由起點(diǎn)A到訖點(diǎn)E的最短路徑。使用Lingo軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

利用Lingo軟件求解的步驟如下所示。(1)打開(kāi)Lingo軟件，在編輯窗口中輸入下列代碼：使用Lingo軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

(2)單擊“LINGO”菜單中的“Solve”選項(xiàng)或單擊工具欄中的按鈕，求解該模型，得到下列結(jié)果。從運(yùn)算結(jié)果可知，在圖7-1中，起點(diǎn)A到訖點(diǎn)E的最短路徑長(zhǎng)度為8。模型結(jié)果中的F(1)，F(xiàn)(2)，…，F(xiàn)(10)表示各點(diǎn)到訖點(diǎn)E的最短距離。使用Lingo軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

使用Lingo軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

利用Lingo軟件求解的步驟如下所示。sets:goods/A,B,C/:c,w,x;endsets

data:c=346;b=20;w=405070;enddata

max=@sum(goods:w*x);@sum(goods:c*x)<=b;@for(goods:@gin(x));(1)在Lingo軟件編輯窗口中輸入下列代碼：(2)單擊“LINGO”菜單中的“Solve”選項(xiàng)或單擊工具欄中的按鈕，求解該模型，得到下列結(jié)果。由運(yùn)行結(jié)果可知，A、B、C三種貨物裝入背包的數(shù)量分別為4、2和0，最大價(jià)值為260元。使用Lingo軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

例7.3（生產(chǎn)與儲(chǔ)存問(wèn)題）某工廠要對(duì)一種產(chǎn)品制訂下一年四個(gè)季度的生產(chǎn)計(jì)劃，據(jù)估計(jì)，在下一年中，各季度市場(chǎng)對(duì)于該產(chǎn)品的需求量和每個(gè)季度生產(chǎn)單位產(chǎn)品的成本如表7-1所示。每個(gè)季度生產(chǎn)能力所允許的最大生產(chǎn)批量不超過(guò)6個(gè)單位；每個(gè)季度末未售出的產(chǎn)品，每單位需付庫(kù)存費(fèi)0.5萬(wàn)元。假定第一季度的初始庫(kù)存量為0，第四季度末庫(kù)存量為0。試問(wèn)：該廠應(yīng)如何安排各個(gè)季度的生產(chǎn)與儲(chǔ)存，才能在滿足市場(chǎng)需要的條件下，使總成本最??？使用Lingo軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

使用Lingo軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

利用Lingo軟件求解的步驟如下所示。Model:sets:quarter/1..4/:c,x,e,d,s;endsetsdata:d=2324;c=2343;e=0.50.50.50.5;a=6;enddatamin=@sum(quarter:c*x+e*s);@for(quarter(i)|i#lt#4:s(i+1)=s(i)+x(i)-d(i));s(1)=0;s(4)+x(4)-d(4)=0;@for(quarter:x<=a);End(1)在Lingo軟件編輯窗口中輸入下列代碼：(2)單擊“LINGO”菜單中的“Solve”選項(xiàng)或單擊工具欄中的按鈕，求解該模型，得到下列結(jié)果使用Lingo軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

由運(yùn)行結(jié)果可知，該工廠在下一年的四個(gè)季度依次生產(chǎn)6個(gè)單位、1個(gè)單位、0個(gè)單位和4個(gè)單位的產(chǎn)品，庫(kù)存量為0個(gè)單位、4個(gè)單位、2個(gè)單位和0個(gè)單位。最小總成本為30萬(wàn)元。利用WinQSB軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

用WinQSB

軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題時(shí)調(diào)用“DynamicProgramming”模塊，該模塊中有三個(gè)子塊，能求解最短路徑問(wèn)題、背包問(wèn)題和生產(chǎn)與儲(chǔ)存問(wèn)題，其他動(dòng)態(tài)規(guī)劃問(wèn)題可以轉(zhuǎn)化成上面三類問(wèn)題進(jìn)行求解。WinQSB

軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題是基于表格的建模方式的，因此可以展示求解步驟。實(shí)驗(yàn)?zāi)康模?）熟悉用WinQSB

軟件求解最短路徑問(wèn)題、背包問(wèn)題和生產(chǎn)與儲(chǔ)存問(wèn)題的求解方法與步驟。（2）熟悉用WinQSB

軟件求解設(shè)備更新問(wèn)題的方法。（3）通過(guò)用WinQSB

軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題，進(jìn)一步理解動(dòng)態(tài)規(guī)劃問(wèn)題的理論知識(shí)。利用WinQSB軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

實(shí)驗(yàn)內(nèi)容例7.4利用WinQSB

軟件求解例7.1。(1)選擇“開(kāi)始”→“程序”→“WinQSB”→“DynamicProgramming”→“File”→“NewProblem”菜單命令，生成對(duì)話框，選擇求解問(wèn)題類型（見(jiàn)圖7-2），單擊“OK”按鈕。(2)選擇“Edit”→“NodeNames”菜單命令，彈出對(duì)話框（見(jiàn)圖7-3），更改節(jié)點(diǎn)名，再單擊“OK”按鈕，得到圖7-4所示的數(shù)據(jù)輸入窗口，輸入節(jié)點(diǎn)間距離。圖7-2選擇求解問(wèn)題類型圖7-3更改節(jié)點(diǎn)名對(duì)話框圖7-4數(shù)據(jù)輸入窗口利用WinQSB軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

(3)選擇“SolveandAnalyze”→“SolvetheProblem”菜單命令，彈出對(duì)話框（見(jiàn)圖7-5），選擇起點(diǎn)和訖點(diǎn)。圖7-5起、訖點(diǎn)選擇對(duì)話框(4)單擊圖7-5所示對(duì)話框中的“Solve”按鈕，得到模型結(jié)果（見(jiàn)圖7-6）。圖7-6模型結(jié)果由圖7-6可知，起點(diǎn)A到訖點(diǎn)E的最短路徑A→B1→C1→D2→E，最短距離為8。圖7-5起、訖點(diǎn)選擇對(duì)話框圖7-6模型結(jié)果利用WinQSB軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

例7.5某單位計(jì)劃購(gòu)買一臺(tái)設(shè)備在今后4年內(nèi)使用?？梢栽诘?年年初購(gòu)買該設(shè)備，連續(xù)使用四年，也可以在任何一年年末將設(shè)備賣掉，于下年年初更換新設(shè)備。表7-2所示為各年年初購(gòu)置新設(shè)備的價(jià)格，表7-3所示為設(shè)備的維護(hù)費(fèi)及賣掉舊設(shè)備的回收費(fèi)。如何確定設(shè)備的更新策略，可以使4年內(nèi)的總費(fèi)用最少？利用WinQSB軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

利用WinQSB軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

(1)選擇“開(kāi)始”→“程序”→“WinQSB”→“DynamicProgramming”→“File”→“NewProblem”菜單命令，生成對(duì)話框（見(jiàn)圖7-8），選擇求解問(wèn)題的類型。(2)單擊圖

7-8所示的“OK”按鈕，輸入節(jié)點(diǎn)間弧的權(quán)重（見(jiàn)圖7-9）。圖7-8例7.5動(dòng)態(tài)規(guī)劃類型選擇對(duì)話框圖7-9輸入權(quán)重?cái)?shù)據(jù)利用WinQSB軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

（3）選擇“SolveandAnalyze”→“SolvetheProblem”菜單命令，彈出對(duì)話框（見(jiàn)圖7-10），選擇起點(diǎn)和訖點(diǎn)。（4）單擊圖7-10所示的“Solve”按鈕，得到例7.5的模型結(jié)果（見(jiàn)圖7-11）。由圖7-11所示的結(jié)果可知，第1年年初購(gòu)置新設(shè)備后在第1年年末將設(shè)備賣掉，在第2年年初再買進(jìn)新設(shè)備一直用到第4年年末將其賣掉。在這種設(shè)備更新方案下，4年內(nèi)的總費(fèi)用最少，最少費(fèi)用為2.6。圖7-10例7.5的起、訖點(diǎn)選擇對(duì)話框圖7-11例7.5的模型結(jié)果利用WinQSB軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

例7.6利用WinQSB

軟件求解例7.2。（1）選擇“開(kāi)始”→“程序”→“WinQSB”→“DynamicProgramming”→“File”→“NewProblem”菜單命令，生成對(duì)話框（見(jiàn)圖7-12），選擇求解問(wèn)題的類型，單擊“OK”按鈕。（2）在WinQSB

軟件的編輯窗口中輸入模型（見(jiàn)圖7-13）。（3）選擇“SolveandAnalyze”→“SolvetheProblem”菜單命令求解，得到例7.6的模型結(jié)果（見(jiàn)圖7-14）。由模型結(jié)果可知，A、B、C三種貨物裝入背包的數(shù)量分別為4、2和0，最大價(jià)值為260元。圖7-12例7.6的動(dòng)態(tài)規(guī)劃類型選擇對(duì)話框圖7-13例7.6的數(shù)據(jù)編輯窗口圖7-14例7.6的模型結(jié)果利用WinQSB軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

例7.7（生產(chǎn)與儲(chǔ)存問(wèn)題）某工廠要對(duì)一種產(chǎn)品制訂下一年四個(gè)季度的生產(chǎn)計(jì)劃，據(jù)估計(jì)，在下一年中，各季度市場(chǎng)對(duì)于該產(chǎn)品的需求量如表7-5所示。假設(shè)該廠生產(chǎn)每批產(chǎn)品的固定成本為3萬(wàn)元，若不生產(chǎn)則為0；每單位產(chǎn)品成本為1萬(wàn)元，每個(gè)季度生產(chǎn)能力所允許的最大生產(chǎn)批量不超過(guò)6個(gè)單位；每個(gè)季度末未售出的產(chǎn)品，每單位需付庫(kù)存費(fèi)0.5萬(wàn)元。還假定第一季度的初始庫(kù)存量為0，第四季度末庫(kù)存量為0。試問(wèn)：該廠應(yīng)如何安排各季度的生產(chǎn)與儲(chǔ)存，才能在滿足市場(chǎng)需要的條件下使總成本最??？利用WinQSB軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

(1)選擇“開(kāi)始”→“程序”→“WinQSB”→“DynamicProgramming”→“File”→“NewProblem”菜單命令，生成對(duì)話框（見(jiàn)圖7-15），選擇求解問(wèn)題的類型，單擊“OK”按鈕。(2)在WinQSB

軟件的編輯窗口中輸入模型（見(jiàn)圖7-16）。(3)選擇“SolveandAnalyze”→“SolvetheProblem”菜單命令求解，得到例7.7的模型結(jié)果（見(jiàn)圖7-17）。由模型結(jié)果可知，該廠在下一年的四個(gè)季度依次生產(chǎn)5個(gè)單位、0個(gè)單位、6個(gè)單位和0個(gè)單位的產(chǎn)品，庫(kù)存量為3個(gè)單位、0個(gè)單位、4個(gè)單位和0個(gè)單位，最小總成本為20.5萬(wàn)元。圖7-15例7.7的動(dòng)態(tài)規(guī)劃類型選擇對(duì)話框圖7-16例7.7的數(shù)據(jù)輸入窗口圖7-17例7.7的模型結(jié)果使用MATLAB軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

對(duì)于動(dòng)態(tài)規(guī)劃問(wèn)題，MATLAB軟件優(yōu)化工具箱沒(méi)有提供求解的函數(shù)，因此需要依據(jù)相關(guān)的算法自行編寫程序，進(jìn)行動(dòng)態(tài)規(guī)劃問(wèn)題的求解。本節(jié)利用Floyd算法求解動(dòng)態(tài)規(guī)劃問(wèn)題中的最短路徑問(wèn)題；用逆序算法求解背包問(wèn)題和生產(chǎn)與儲(chǔ)存問(wèn)題。實(shí)驗(yàn)?zāi)康模?）熟悉用MATLAB軟件求解最短路徑問(wèn)題、背包問(wèn)題和生產(chǎn)與儲(chǔ)存問(wèn)題的基本命令和M文件的編寫。（2）通過(guò)用MATLAB軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題，進(jìn)一步理解動(dòng)態(tài)規(guī)劃問(wèn)題的理論知識(shí)。使用MATLAB軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

實(shí)驗(yàn)內(nèi)容例7.8用MATLAB軟件求解例7.1。function[D,path]=DPexample1()a=[0,3,5,4,inf,inf,inf,inf,inf,inf;inf,0,inf,inf,1,5,inf,inf,inf,inf;inf,inf,0,inf,8,4,6,inf,inf,inf;inf,inf,inf,0,4,4,2,inf,inf,inf;inf,inf,inf,inf,0,inf,inf,4,2,inf;inf,inf,inf,inf,inf,0,inf,6,9,inf;inf,inf,inf,inf,inf,inf,0,7,5,inf;inf,inf,inf,inf,inf,inf,inf,0,inf,1;inf,inf,inf,inf,inf,inf,inf,inf,0,2;inf,inf,inf,inf,inf,inf,inf,inf,inf,0];A=1;E=10;n=size(a,1);D=a;path=zeros(n,n);i=0;k=1;r(k)=A;p=path(A,E);while(i==0)ifp~=Ek=k+1;r(k)=p;p=path(p,E);elser(k+1)=E;

i=1;endendm=size(r);short_path=rshort_path_length=D(1,10)fori=1:nforj=1:nifD(i,j)~=infpath(i,j)=j;endendendfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)<D(i,j)D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);endendendend(1)打開(kāi)MATLAB軟件，創(chuàng)建一個(gè)新的“.m”文件，在編輯窗口中輸入下列代碼：使用MATLAB軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題

(1)選擇“Debug”→“R