度巍　曾飛

摘要：介紹了LINGO優(yōu)化軟件的使用，指出LINGO在求解動態(tài)規(guī)劃問題時可以不需要目標(biāo)函數(shù)?；贚INGO分別對最短路問題和生產(chǎn)批量計(jì)劃問題使用動態(tài)規(guī)劃法進(jìn)行了求解，給出了相應(yīng)的LINGO求解代碼，增強(qiáng)了學(xué)生對動態(tài)規(guī)劃法的理解同時提高了使用優(yōu)化軟件編程解決問題的能力。

關(guān)鍵詞：LINGO；動態(tài)規(guī)劃； 最短路問題； 生產(chǎn)批量計(jì)劃問題

中圖分類號：G642 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）04-0743-04

在交通專業(yè)課程如《交通運(yùn)籌學(xué)》、《交通系統(tǒng)分析方法》等的教學(xué)過程中，大量涉及到可劃分為多階段的優(yōu)化問題求解，這些問題的求解一般使用動態(tài)規(guī)劃（dynamic programming）方法。動態(tài)規(guī)劃將決策問題的全過程劃分為若干個相互聯(lián)系的子過程（每個子過程為一個階段），然后按照一定的次序來求解。當(dāng)劃分的階段個數(shù)較多時，手工求解動態(tài)規(guī)劃問題相當(dāng)麻煩。由于在實(shí)際的交通工程規(guī)劃實(shí)踐中，涉及到的動態(tài)規(guī)劃優(yōu)化問題規(guī)模往往較大，指導(dǎo)學(xué)生掌握相應(yīng)的優(yōu)化軟件求解動態(tài)規(guī)劃問題一方面能增進(jìn)學(xué)生對動態(tài)規(guī)劃法的理解掌握，另一方面能鍛煉學(xué)生的編程能力，是一項(xiàng)十分有意義的教學(xué)工作。

美國LINDO系統(tǒng)公司開發(fā)的LINGO由其求解問題的高效性和穩(wěn)定性，成為目前廣泛使用的優(yōu)化軟件。LINGO是一套專門用于求解最優(yōu)化問題的軟件包，其內(nèi)置了一種建立最優(yōu)化模型的的語言，可以簡便表達(dá)出問題，同時利用LINGO高效的求解器可快速求解并分析結(jié)果。LINGO在處理含有大量變量和約束條件的優(yōu)化問題時，一般使用數(shù)組和矩陣的輸入方法：LINGO程序首先定義集合段，確定需要的集合及其屬性，然后定義數(shù)據(jù)段，用于輸入已知原始數(shù)據(jù)，最后使用函數(shù)對集合進(jìn)行操作。在通常介紹LINGO使用的文獻(xiàn)中[1][2]，一般著重于敘述其如何求解線性規(guī)劃和非線性規(guī)劃等具有明確目標(biāo)函數(shù)的優(yōu)化問題，很少關(guān)注如何用LINGO求解復(fù)雜的動態(tài)規(guī)劃問題，該文通過分析交通運(yùn)輸中常見的最短路問題和生產(chǎn)批量計(jì)劃問題，給出用動態(tài)規(guī)劃方法求解的LINGO代碼，指出LINGO可以在不需要目標(biāo)函數(shù)的情況同樣很好地求解多階段優(yōu)化問題。

1 動態(tài)規(guī)劃法求解實(shí)例

實(shí)例1 最短路問題

在縱橫交錯的公路網(wǎng)中（圖1所示），貨車司機(jī)希望找到一條從一個城市到另一個城市的最短路。圖中節(jié)點(diǎn)1—8代表貨車可以停靠的城市，弧旁的數(shù)字表示兩個城市之間的距離（百公里）。若貨車要從城市1出發(fā)到達(dá)城市8，問如何選擇行駛路線使所經(jīng)過的路程最短。

問題分析：該最短路問題滿足動態(tài)規(guī)劃的最優(yōu)性原理，即“從節(jié)點(diǎn)1到節(jié)點(diǎn)8的最短路的子路徑仍然是相應(yīng)節(jié)點(diǎn)間的最短路”，用[D（i，j）]表示從節(jié)點(diǎn)[i]和[j]有弧相連時相應(yīng)的距離，[L（i）]表示從節(jié)點(diǎn)1到節(jié)點(diǎn)i的最短路程數(shù)。則不難得到以下的動態(tài)規(guī)劃由前向后遞推方程：

根據(jù)式（1），再進(jìn)一步定義當(dāng)節(jié)點(diǎn)[i]在從節(jié)點(diǎn)1到節(jié)點(diǎn)[j]的最短路徑上時，[P（i，j）=1]，否則[P（i，j）=0]，編寫如下LINGO求解代碼：

運(yùn)行LINGO得到如圖1所示的最優(yōu)解報(bào)告。

從報(bào)告中可以看到，最短路徑找到，由[L（8）]的值可以得出，從城市1到城市8的最短路程數(shù)為14，由各個[P（i，j）]的值分析可知，從城市1到城市8的最短路線為[1→2→5→8]。

實(shí)例2（生產(chǎn)批量計(jì)劃問題）

某企業(yè)生產(chǎn)某種產(chǎn)品用以滿足市場需求。通過統(tǒng)計(jì)，該產(chǎn)品今后[T]4周的外部需求（訂貨量）分別是[d1]千件、[d2]千件、[d3]千件和[d4]千件。如果第[t]周要開工生產(chǎn)，則第[t]周開工所需的生產(chǎn)準(zhǔn)備費(fèi)為[st]千元（與生產(chǎn)的數(shù)量無關(guān)），每件產(chǎn)品的生產(chǎn)費(fèi)為[ct]千元。如果在滿足需求后周末有產(chǎn)品剩余，每千件產(chǎn)品的存儲費(fèi)為[ht]千元。設(shè)第[t]周末的庫存量為[It]，假設(shè)開始沒有庫存，記為[I0=0]且不考慮生產(chǎn)能力限制，問工廠應(yīng)如何安排生產(chǎn)，在按時滿足需求的條件下，使總費(fèi)用最??？

問題分析：對于生產(chǎn)批量計(jì)劃問題，分析可知有如下兩條性質(zhì)成立：

由于以上兩個性質(zhì)，只有當(dāng)上一時段庫存[It-1=0]時，本時段才考慮進(jìn)行生產(chǎn)，且一旦生產(chǎn)，其生產(chǎn)量一定為某些后續(xù)時段需求量的總和，即[xt∈{dt，dt+dt+1，…，dt+dt+1+…+dT}]。這樣如用[ft]表示當(dāng)[t]時段初始庫存為0時，從[t]時段到[T]時段的子問題的最優(yōu)費(fèi)用值，可以建立如下的遞推關(guān)系：

運(yùn)行LINGO得到如下最優(yōu)解報(bào)告：

從報(bào)告可以看到，[F（1）=561]，即從第1周到第4周末的最優(yōu)費(fèi)用為561（千元），分析其它[F]值得到，最優(yōu)的生產(chǎn)批量計(jì)劃為第1周生產(chǎn)2（千件），第2周生產(chǎn)5（千件），第3周不生產(chǎn)，第4周生產(chǎn)4（千件）。

2 結(jié)束語

本文針對用動態(tài)規(guī)劃方法手工求解多階段優(yōu)化決策問題十分繁瑣的特點(diǎn)，利用LINGO軟件將各個動態(tài)規(guī)劃遞推方程簡潔明確地編程實(shí)現(xiàn)，幫助學(xué)生更好的理解了各階段決策變量之間相互遞進(jìn)的關(guān)系，同時更重要的是交通專業(yè)學(xué)生熟練地掌握了軟件的使用，才能解決實(shí)際工程規(guī)劃中的大規(guī)模復(fù)雜優(yōu)化問題，LINGO軟件的教學(xué)實(shí)踐促進(jìn)了《交通運(yùn)籌學(xué)》、《交通系統(tǒng)分析方法》與《交通規(guī)劃》等課程的融合。

參考文獻(xiàn)：

[1] 李曉川，朱曉敏，趙乃東. 基于Lingo的運(yùn)輸優(yōu)化系統(tǒng)設(shè)計(jì)與開發(fā)[J]. 物流技術(shù)，2010（Z1）.

[2] 洪文，朱云鵑. 利用LINGO建立最優(yōu)化模型[C].第六屆（2011）中國管理學(xué)年會——管理科學(xué)與工程分會場，2011.

[3] 姜啟源，謝金星，邢文訓(xùn)，等.大學(xué)數(shù)學(xué)實(shí)驗(yàn)[M].北京：清華大學(xué)出版社，2005.