動態(tài)規(guī)劃案例教學(xué)設(shè)計探討

時間:2022-02-03 09:56:42

導(dǎo)語:動態(tài)規(guī)劃案例教學(xué)設(shè)計探討一文來源于網(wǎng)友上傳,不代表本站觀點,若需要原創(chuàng)文章可咨詢客服老師,歡迎參考。

動態(tài)規(guī)劃案例教學(xué)設(shè)計探討

[摘要]在運(yùn)籌學(xué)的分支體系中,動態(tài)規(guī)劃因其應(yīng)用的廣泛性而占有十分重要的地位。針對動態(tài)規(guī)劃教學(xué)中的難點,可以以最短路問題為引例,以大家耳熟能詳?shù)拿Q對動態(tài)規(guī)劃中的基本概念進(jìn)行闡釋,并對最優(yōu)性原理、無記憶性與記憶性進(jìn)行比較系統(tǒng)的闡述,指出最優(yōu)性原理表現(xiàn)在最短路問題中即是“最短路徑的子路徑必然是最短的”。最后,還可以以最短路分析動態(tài)規(guī)劃求解時常用的“空間換時間”策略。

[關(guān)鍵詞]動態(tài)規(guī)劃;最優(yōu)性原理;無記憶性;記憶性

在運(yùn)籌學(xué)的分支體系中,動態(tài)規(guī)劃因其應(yīng)用的廣泛性而占有十分重要的地位。但動態(tài)規(guī)劃僅僅是解決某類特殊的多階段決策問題的一種方法,不具有統(tǒng)一的數(shù)學(xué)模型和算法步驟[1],而且概念多,因此學(xué)生普遍反應(yīng)“動態(tài)規(guī)劃真的有用但確實難學(xué)”。本文以最短路問題為案例,對動態(tài)規(guī)劃相關(guān)概念、最優(yōu)性原理、無記憶性等進(jìn)行了闡釋。

一、案例的選擇

可用動態(tài)規(guī)劃求解的問題很多,如最短路、資源分配、生產(chǎn)與存儲等,而最短路問題因其空間特征明顯,易于劃分階段、易于描述每階段開始和結(jié)束時的狀態(tài),以及在每個狀態(tài)之下做出的決策、每次決策產(chǎn)生的決策指標(biāo)值等,因此,對初學(xué)者而言,最易接受和理解的例子還是最短路問題。本文以最短路問題作為引例,幫助學(xué)生們理解和掌握動態(tài)規(guī)劃的相關(guān)概念及基本方程、最優(yōu)性原理等。

二、相關(guān)概念的解釋

動態(tài)規(guī)劃相關(guān)概念繁多,從階段、狀態(tài)開始,到過程指標(biāo)函數(shù),剛接觸時,不少學(xué)生感到一頭霧水,十分茫然。而借助于最短路問題,將動態(tài)規(guī)劃的相關(guān)概念與最短路問題中大家耳熟能詳?shù)拿Q相對應(yīng),則十分有助于學(xué)生對動態(tài)規(guī)劃基本概念的把握。

三、最優(yōu)性原理的解釋教材[1]

對最優(yōu)性原理作了如下表述:無論過去的決策和狀態(tài)如何,對前面的決策所形成的當(dāng)前狀態(tài)而言,余下的決策序列必須構(gòu)成最優(yōu)策略,即最優(yōu)策略的子策略總是最優(yōu)的。

四、無記憶性與記憶性

在動態(tài)規(guī)劃一章中,教師經(jīng)常會提到“無記憶性”與“記憶性”兩個看似完全矛盾的概念,不少學(xué)生也感到十分茫然。其實,這兩個概念在動態(tài)規(guī)劃中得到了完美的統(tǒng)一。“無記憶性”指的是可用動態(tài)規(guī)劃方法求解的多階段決策問題,在劃分階段時,狀態(tài)必須滿足的一個特性,也稱為無后效性或馬爾科夫性。其實質(zhì)是:某階段的狀態(tài)一旦確定,則此后過程的演變不再受此前各狀態(tài)及決策的影響。即“未來與過去無關(guān)”,當(dāng)前的狀態(tài)是此前歷史的一個完整總結(jié),此前的歷史只能通過當(dāng)前的狀態(tài)去影響過程未來的演變。[1]“記性性”指的是用動態(tài)規(guī)劃方法求解多階段決策問題時(以逆序為例),為求得第K步最優(yōu)子策略fk(Sk),必須先計算出從第K+1階段的各狀態(tài)出發(fā)所對應(yīng)的最優(yōu)子策略fk+1(Sk+1),并由第K+1步的最優(yōu)子策略fk+1(Sk+1)去求取第K步最優(yōu)子策略fk(Sk)。這些后續(xù)狀態(tài)對應(yīng)的最優(yōu)子策略實際上構(gòu)成了一張查找表(LookupTable)。[3]為更好地理解無記憶性與記憶性,仍以最短路問題為例進(jìn)行說明。假設(shè)有一個可分為10個階段的最短路問題,每階段有10個狀態(tài)可供選擇?!盁o記憶性”指的是當(dāng)游客在第k階段處于狀態(tài)Sk時,則該游客從Sk出發(fā)到終點的最短路徑(K步最優(yōu)子策略)只與Sk相關(guān),而與Sk之前的狀態(tài)、決策無任何關(guān)系?!坝洃浶浴敝傅氖钱?dāng)用動態(tài)規(guī)劃方法求解最短路問題時,第K步最優(yōu)子策略是由第K步的決策和第K+1步的最優(yōu)子策略共同決定的,而第K+1步的最優(yōu)子策略已在之前求出并存放于內(nèi)存之中,這就是記憶性。動態(tài)規(guī)劃的記憶性可節(jié)省大量的計算時間,但會占用較多的計算機(jī)內(nèi)存,即常用的“空間換時間”策略。以上題為例,10個階段每階段10個狀態(tài)的最短路問題,如果采用窮舉法,則需要計算的路徑條數(shù)(相當(dāng)于動態(tài)規(guī)劃中的全策略)為109條,每條路徑需要進(jìn)行10次加法運(yùn)算;在109條路徑中找出最短路徑需要進(jìn)行109-1次比較運(yùn)算,則總的基本運(yùn)算是11*109-1次。而采用動態(tài)規(guī)劃方法時,每階段的每個狀態(tài)需要進(jìn)行10次加法運(yùn)算和9次比較運(yùn)算,則總的基本運(yùn)算次數(shù)為1539次(其中加法運(yùn)算810次,比較運(yùn)算729次),和窮舉法比較可節(jié)省大量的計算時間。從該例題的分析可知,一個多階段決策問題之所以可采用有“記憶性”的動態(tài)規(guī)劃方法求解,恰恰是因為該問題在劃分階段時,各階段的自然特征(即狀態(tài))滿足“無記憶性”。因此,我們說,“記憶性”與“無記憶性”在動態(tài)規(guī)劃中得到了完美的統(tǒng)一。

五、結(jié)束語

經(jīng)教學(xué)實踐證明,在動態(tài)規(guī)劃教學(xué)中以最短路為引例,有利于學(xué)生對動態(tài)規(guī)劃相關(guān)概念的理解,尤其有利于學(xué)生掌握最優(yōu)性原理和無記憶性、記憶性這些晦澀難懂的原理與性質(zhì),為學(xué)生學(xué)好、用好動態(tài)規(guī)劃打下了良好基礎(chǔ)。

[參考文獻(xiàn)]

[1]胡運(yùn)權(quán).運(yùn)籌學(xué)教程(第四版)[M].北京:清華大學(xué)出版社,2012:191-232.

[2][M].普林斯頓大學(xué)出版社,1957:58-92.

[3]北京:人民郵電出版社,2008:744-754.

[4]《運(yùn)籌學(xué)》教材編寫組.運(yùn)籌學(xué)(第三版)[M].北京:清華大學(xué)出版社,2005:194-215.

[5]韓伯棠.管理運(yùn)籌學(xué)(第二版)[M].北京:高等教育出版社,2005:256-262.

作者:劉光霆 蔡萬銘 沈鑫 向朝參 單位:后勤工程學(xué)院