最優(yōu)化方法實(shí)踐課程教學(xué)的一個案例

陳照輝，唐利明，任澤民

(1.重慶科技學(xué)院 數(shù)理學(xué)院，重慶 401331；2.湖北民族學(xué)院 理學(xué)院，湖北 恩施 445000)

?

最優(yōu)化方法實(shí)踐課程教學(xué)的一個案例

陳照輝1，唐利明2，任澤民1

(1.重慶科技學(xué)院 數(shù)理學(xué)院，重慶 401331；2.湖北民族學(xué)院 理學(xué)院，湖北 恩施 445000)

最優(yōu)化方法課程具有較強(qiáng)的實(shí)用性，對該課程實(shí)踐教學(xué)現(xiàn)狀進(jìn)行了分析，闡述了實(shí)踐教學(xué)的必要性，提出案例教學(xué)的重要性和可行性。通過一個實(shí)踐教學(xué)實(shí)例分析案例教學(xué)，說明獨(dú)立設(shè)置上機(jī)實(shí)驗，通過老師指導(dǎo)，以學(xué)生為主體的案例教學(xué)，能有效發(fā)揮學(xué)生學(xué)習(xí)的主觀能動性。

最優(yōu)化方法，案例教學(xué)，實(shí)踐課程，應(yīng)用型

最優(yōu)化方法作為應(yīng)用數(shù)學(xué)專業(yè)一門核心專業(yè)課程，具有較強(qiáng)的理論性和實(shí)用性。該課程的實(shí)踐教學(xué)環(huán)節(jié)對培養(yǎng)大學(xué)生運(yùn)用數(shù)學(xué)知識解決實(shí)際問題的能力起著十分重要的作用。為全面提高應(yīng)用型、創(chuàng)新性人才培養(yǎng)質(zhì)量，本文對最優(yōu)化方法實(shí)踐教學(xué)現(xiàn)狀進(jìn)行分析，闡述實(shí)踐教學(xué)的重要性和案例教學(xué)的可行性，通過一個教學(xué)案例的實(shí)施過程探索改革實(shí)踐教學(xué)內(nèi)容和教學(xué)方法。

1 最優(yōu)化方法實(shí)踐課程教學(xué)的重要性

最優(yōu)化方法是一門理論性和實(shí)用性很強(qiáng)的專業(yè)課程，它研究如何在所有可行方案中搜索出最優(yōu)方案[1,2]。該課程中所涉及到的優(yōu)化方法在諸多領(lǐng)域中得到了廣泛的應(yīng)用[3]。所以，不僅限于數(shù)學(xué)專業(yè)，其它以培養(yǎng)應(yīng)用型人才為目標(biāo)的工程技術(shù)和管理專業(yè)開設(shè)該課程，使學(xué)生掌握優(yōu)化思想和對實(shí)際工程問題進(jìn)行優(yōu)化處理的能力，也是其需要具備的基本素質(zhì)。

目前國內(nèi)在最優(yōu)化方法教學(xué)中，較注重一些經(jīng)典的優(yōu)化算法學(xué)習(xí)，在實(shí)踐教學(xué)中也是算法驗證性實(shí)驗。但是，近些年隨著科技的進(jìn)步，實(shí)際工程中遇到的優(yōu)化問題也越來越復(fù)雜，隨之最優(yōu)化方法也得到了迅速的發(fā)展，應(yīng)用也越發(fā)靈活，課本中所列的經(jīng)典優(yōu)化方法已不能滿足工程需要?，F(xiàn)代優(yōu)化算法如遺傳算法、模擬退火法、粒子群算法、蟻群算法等發(fā)展已較為成熟，也在很多工程領(lǐng)域中得到了廣泛的應(yīng)用[4]。 但是，大多最優(yōu)化方法教材并未列寫這些相關(guān)內(nèi)容，在實(shí)際教學(xué)中也很少涉及，一般在研究生課程中才會有所體現(xiàn)。為了順應(yīng)應(yīng)用型人才培養(yǎng)目標(biāo)，作者認(rèn)為應(yīng)在教學(xué)過程中適當(dāng)補(bǔ)充一些現(xiàn)代優(yōu)化方法的學(xué)習(xí)，側(cè)重在實(shí)踐教學(xué)中使學(xué)生掌握算法的應(yīng)用方法和軟件的使用。

實(shí)踐教學(xué)是能夠讓學(xué)生從工程的角度理解優(yōu)化思想的重要環(huán)節(jié)。實(shí)踐教學(xué)不但能加深對所學(xué)理論知識的理解，而且能提高理論聯(lián)系實(shí)際，解決工程問題的能力。另外，通過實(shí)踐教學(xué)，用現(xiàn)代化技術(shù)手段將優(yōu)化理論和問題解決一同展示，對提高學(xué)生學(xué)習(xí)興趣和積極性無疑是有幫助的。實(shí)踐教學(xué)要求學(xué)生熟練掌握一門高級語言，然而，語言是其面臨的一大難題，這也正說明了實(shí)踐課程教學(xué)的重要性。

面對解決工程中的優(yōu)化問題，需要首先將現(xiàn)實(shí)問題模型化，這一點(diǎn)能夠培養(yǎng)學(xué)生自主分析問題和將優(yōu)化問題轉(zhuǎn)化為數(shù)學(xué)模型的能力。所以，篩選合適的案例是實(shí)踐教學(xué)的首要任務(wù)。為了讓實(shí)踐教學(xué)發(fā)揮出更好的效果，案例要突出較強(qiáng)的實(shí)戰(zhàn)性，同時，要緊密結(jié)合所學(xué)優(yōu)化方法。另外，案例要兼顧難易度適中，并具有挑戰(zhàn)性，還要具有互動性，這樣才能激發(fā)學(xué)生學(xué)習(xí)探索的積極性。

2 一個實(shí)踐教學(xué)案例

車輛路徑問題(Vehicle Routing Problem，VRP)是由Dantzig和 Ramser于1959年首次提出的，屬于完全NP問題，該問題在最優(yōu)化、物流管理、計算機(jī)等領(lǐng)域中得到了廣泛的關(guān)注和研究[5]。該問題背景清晰、易懂且具有針對性和實(shí)戰(zhàn)性，所以，在最優(yōu)化方法實(shí)踐教學(xué)過程中選擇該問題作為一個案例。

2.1 車輛路徑問題描述與模型

一般地，車輛路徑問題可描述為：對一系列發(fā)貨點(diǎn)或收貨點(diǎn)，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過它們，在滿足一定的約束條件下，達(dá)到一定的目標(biāo)。例如，有一個中心倉庫，擁有K輛車，第k輛車的最大載重量或容量記為qk(k=1,2,…,K)，負(fù)責(zé)向L個需求點(diǎn)配送貨物，第i個需求點(diǎn)的貨物需求量為gi(i=1,2,…,L)，且maxgi≤maxqk；cij表示車輛從需求點(diǎn)i到需求點(diǎn)j的配送成本(距離、費(fèi)用或時間)。求滿足需求的成本最小的車輛行駛路徑。

(1)

2.2 有時間窗的車輛路徑問題描述與模型

如果在上述車輛路徑問題中，增加一種約束，即完成需求點(diǎn)i的貨物配送必須在時間窗口[ETi,LTi]需完成，且需要的時間為Ti，其中ETi表示為需求點(diǎn)i配送的最早開始時間，LTi表示為需求點(diǎn)i配送的最遲開始時間。如果車輛到達(dá)需求點(diǎn)i的時間早于ETi，則車輛需要等待，增加了時間成本；如果晚于LTi到達(dá)，則需支付一定的罰金，增加了配送成本。那么，這種考慮了配送時間約束的車輛路徑問題為具有時間窗的車輛路徑問題(Vehicle Routing Problem with Time Windows，VRPTW)。

以ti表示車輛到達(dá)第i個需求點(diǎn)的時間，pE表示提前到達(dá)的單位時間等待成本，pL表示延遲到達(dá)的單位時間懲罰成本，則具有時間窗約束的車輛路徑問題模型中目標(biāo)函數(shù)為

(2)

約束條件與(1)相同。從模型(1)(2)易知，當(dāng)ETi=0，LTi→∞時，(2)等價于(1)。

3 教學(xué)分析

在最優(yōu)化方法理論教學(xué)內(nèi)容中，我們補(bǔ)充學(xué)習(xí)了現(xiàn)代優(yōu)化算法(粒子群算法，遺傳算法)，并且熟悉了這兩種算法的用于求解無約束優(yōu)化問題的軟件操作和編程實(shí)現(xiàn)。然后，提出車輛路徑問題，作為單獨(dú)的上機(jī)實(shí)驗環(huán)節(jié)要求用粒子群算法進(jìn)行解決。具體操作如下：

a. 編碼

b. 構(gòu)造適應(yīng)值函數(shù)

(3)

其中M是充分大的數(shù)。顯然，(3)中令pE=0,pL=0便是VRP的適應(yīng)值函數(shù)，其完全可用Lingo解決。

c. 算法步驟

第1步：初始化參數(shù)K,L,N,w,c1,c2,M，最大迭代次數(shù)Nmax，粒子群Xi=(xi1,xi2,…,xi,K+L-1)和初始速度Vi=(vi1,vi2,…,vi,K+L-1)，i=1, 2, …,N，其中-1≤xij≤1；

第2步：按照a中的編碼方法將Xi映射到Y(jié)i∈B,i=1, 2, … ,N；

第3步：根據(jù)(3)計算Yi點(diǎn)的適應(yīng)值；

第4步：根據(jù)Yi的適應(yīng)值，修改個體最優(yōu)Pi和全局最優(yōu)Pg；

第5步： 根據(jù)粒子群算法迭代式更新粒子的位置；

第6步：判斷終止條件是否滿足，是，停止迭代并輸出Pg；否，返回到第2步。

解決該問題具有挑戰(zhàn)性，首先需要編碼，這一步能加深學(xué)生了解相應(yīng)算法；然后需要構(gòu)造適應(yīng)值函數(shù)，這一步能促使學(xué)生深入了解罰函數(shù)法處理約束條件；最后需要按照算法的步驟構(gòu)建解決VRPTW的算法，這一步驟能夠使得學(xué)生進(jìn)一步深入熟悉算法的結(jié)構(gòu)和在組合優(yōu)化問題中的使用方法。

在教學(xué)過程中，有的學(xué)生利用Lingo 軟件解決了VRP，在解決VRPTW中遇到了困難。大多數(shù)同學(xué)能夠在實(shí)驗中通過團(tuán)隊協(xié)作，完成基本粒子群算法程序的修改，從而成功解決該問題。

4 結(jié)語

最優(yōu)化方法課程中應(yīng)用案例進(jìn)行教學(xué)，取得非常好的效果。以學(xué)生為主體，通過對問題分析、建模、解決實(shí)現(xiàn)的過程，進(jìn)行了師生間的互動。在老師的引導(dǎo)下，使得學(xué)生充分發(fā)揮其主觀能動性，不但能提高分析問題，建立模型，解決問題和編程的能力，而且能夠充分發(fā)掘?qū)W生的創(chuàng)新潛能。本文首先分析最優(yōu)化方法實(shí)踐課程教學(xué)現(xiàn)狀，說明實(shí)踐教學(xué)在提高學(xué)生分析問題和解決問題能力中扮演重要角色，列舉一個案例旨在闡述最優(yōu)化方法實(shí)踐課程教學(xué)的一個可操作方法。

[1] 袁亞湘，孫文瑜.最優(yōu)化理論與方法[M].北京：科學(xué)出版社，1997.

[2] 郭科，陳聆，魏友華.最優(yōu)化方法及其應(yīng)用[M].北京：高等教育出版社，2007.

[3] 何堅勇.最優(yōu)化方法[M].清華大學(xué)出版社，2007.

[4] 張火明，陸萍藍(lán)，王強(qiáng).“講座式”教學(xué)方法在最優(yōu)化方法課程教學(xué)中的實(shí)踐與效果分析[J].技術(shù)監(jiān)督教育學(xué)刊，2009(2):6-9.

[5] 李寧，鄒彤，孫德寶.帶時間窗車輛路徑問題的粒子群算法[J].系統(tǒng)工程理論與實(shí)踐，2004(4):130-135.

(責(zé)任校對 謝宜辰)

10.13582/j.cnki.1674-5884.2016.11.011

20160628

重慶科技學(xué)院教改項目(201245)；湖北民族學(xué)院教學(xué)研究項目(2015JY008)

陳照輝(1980- )，男，河南周口人，副教授，博士，主要從事智能優(yōu)化、系統(tǒng)穩(wěn)定控制研究。

G642.0

A

1674-5884(2016)11-0034-03