陳照輝，唐利明，任澤民

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

?

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

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

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

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

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

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

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

最優(yōu)化方法是一門(mén)理論性和實(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è)開(kāi)設(shè)該課程，使學(xué)生掌握優(yōu)化思想和對(duì)實(shí)際工程問(wèn)題進(jìn)行優(yōu)化處理的能力，也是其需要具備的基本素質(zhì)。

目前國(guó)內(nèi)在最優(yōu)化方法教學(xué)中，較注重一些經(jīng)典的優(yōu)化算法學(xué)習(xí)，在實(shí)踐教學(xué)中也是算法驗(yàn)證性實(shí)驗(yàn)。但是，近些年隨著科技的進(jìn)步，實(shí)際工程中遇到的優(yōu)化問(wèn)題也越來(lái)越復(fù)雜，隨之最優(yōu)化方法也得到了迅速的發(fā)展，應(yīng)用也越發(fā)靈活，課本中所列的經(jīng)典優(yōu)化方法已不能滿足工程需要。現(xiàn)代優(yōu)化算法如遺傳算法、模擬退火法、粒子群算法、蟻群算法等發(fā)展已較為成熟，也在很多工程領(lǐng)域中得到了廣泛的應(yīng)用[4]。 但是，大多最優(yōu)化方法教材并未列寫(xiě)這些相關(guān)內(nèi)容，在實(shí)際教學(xué)中也很少涉及，一般在研究生課程中才會(huì)有所體現(xiàn)。為了順應(yīng)應(yīng)用型人才培養(yǎng)目標(biāo)，作者認(rèn)為應(yīng)在教學(xué)過(guò)程中適當(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é)不但能加深對(duì)所學(xué)理論知識(shí)的理解，而且能提高理論聯(lián)系實(shí)際，解決工程問(wèn)題的能力。另外，通過(guò)實(shí)踐教學(xué)，用現(xiàn)代化技術(shù)手段將優(yōu)化理論和問(wèn)題解決一同展示，對(duì)提高學(xué)生學(xué)習(xí)興趣和積極性無(wú)疑是有幫助的。實(shí)踐教學(xué)要求學(xué)生熟練掌握一門(mén)高級(jí)語(yǔ)言，然而，語(yǔ)言是其面臨的一大難題，這也正說(shuō)明了實(shí)踐課程教學(xué)的重要性。

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

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

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

2.1 車輛路徑問(wèn)題描述與模型

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

(1)

2.2 有時(shí)間窗的車輛路徑問(wèn)題描述與模型

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

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

(2)

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

3 教學(xué)分析

在最優(yōu)化方法理論教學(xué)內(nèi)容中，我們補(bǔ)充學(xué)習(xí)了現(xiàn)代優(yōu)化算法(粒子群算法，遺傳算法)，并且熟悉了這兩種算法的用于求解無(wú)約束優(yōu)化問(wèn)題的軟件操作和編程實(shí)現(xiàn)。然后，提出車輛路徑問(wèn)題，作為單獨(dú)的上機(jī)實(shí)驗(yàn)環(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)計(jì)算Yi點(diǎn)的適應(yīng)值；

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

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

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

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

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

4 結(jié)語(yǔ)

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

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

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

[3] 何堅(jiān)勇.最優(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] 李寧，鄒彤，孫德寶.帶時(shí)間窗車輛路徑問(wèn)題的粒子群算法[J].系統(tǒng)工程理論與實(shí)踐，2004(4):130-135.

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

10.13582/j.cnki.1674-5884.2016.11.011

20160628

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

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

G642.0

A

1674-5884(2016)11-0034-03