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

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

［關(guān)鍵詞］動(dòng)態(tài)規(guī)劃；最優(yōu)性原理；無(wú)記憶性；記憶性

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

一、案例的選擇

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

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

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

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

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

四、無(wú)記憶性與記憶性

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

五、結(jié)束語(yǔ)

經(jīng)教學(xué)實(shí)踐證明，在動(dòng)態(tài)規(guī)劃教學(xué)中以最短路為引例，有利于學(xué)生對(duì)動(dòng)態(tài)規(guī)劃相關(guān)概念的理解，尤其有利于學(xué)生掌握最優(yōu)性原理和無(wú)記憶性、記憶性這些晦澀難懂的原理與性質(zhì)，為學(xué)生學(xué)好、用好動(dòng)態(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é)》教材編寫(xiě)組.運(yùn)籌學(xué)（第三版）［M］．北京：清華大學(xué)出版社，2005：194-215．

［5］韓伯棠.管理運(yùn)籌學(xué)（第二版）［M］．北京：高等教育出版社，2005：256-262．

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