運(yùn)籌學(xué)課程教學(xué)中的探索與實(shí)踐

王芳華, 馮春生

(湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,湖南湘潭 411105)

運(yùn)籌學(xué)課程教學(xué)中的探索與實(shí)踐

王芳華, 馮春生

(湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,湖南湘潭 411105)

結(jié)合教學(xué)實(shí)踐經(jīng)驗(yàn),從提高學(xué)生的興趣和積極性出發(fā),在運(yùn)籌學(xué)課程的教學(xué)過程中,提出了以學(xué)生為本,改進(jìn)教學(xué)內(nèi)容和教學(xué)方法,并把數(shù)學(xué)建模的思想融到運(yùn)籌學(xué)課程的教學(xué)中去,從而提高學(xué)生的學(xué)習(xí)效果和教師的教學(xué)效果.

運(yùn)籌學(xué);數(shù)學(xué)建模;探索與實(shí)踐

運(yùn)籌學(xué)是一門新興的應(yīng)用學(xué)科,它充分利用現(xiàn)有的科學(xué)技術(shù)知識和數(shù)學(xué)方法,解決實(shí)踐中提出的專門問題,為決策者選擇最優(yōu)決策提供定量依據(jù).它廣泛應(yīng)用于工農(nóng)業(yè)生產(chǎn)、經(jīng)濟(jì)管理、科學(xué)技術(shù)、國防事業(yè)等各個方面.正因?yàn)樗鼞?yīng)用的廣泛性,才決定運(yùn)籌學(xué)課程的重要性,因此在運(yùn)籌學(xué)課程的教學(xué)過程中,必須不斷地進(jìn)行探索與實(shí)踐,提高學(xué)生學(xué)習(xí)運(yùn)籌學(xué)課程的興趣和積極性,幫助他們更好地掌握這門學(xué)科,從而提高他們解決實(shí)際問題的能力.作者從事不同專業(yè)、不同層次的運(yùn)籌學(xué)教學(xué)多年,并在運(yùn)籌學(xué)課程的教學(xué)中一直不斷地進(jìn)行探索與實(shí)踐,下面就介紹作者在教學(xué)中的一些粗淺體會.

1 以學(xué)生為本,改進(jìn)教學(xué)內(nèi)容和方法,提高學(xué)生學(xué)習(xí)的積極性

在線性規(guī)劃中,單純形法是解線性規(guī)劃的一種最基本的方法,而這種方法的實(shí)現(xiàn)是通過單純形表來完成的.這種單純形表,它的功能與增廣矩陣相似,從而在利用單純形表進(jìn)行計(jì)算時,迭代運(yùn)算是通過行變換實(shí)現(xiàn)的,故計(jì)算時比較容易出錯;并且每次迭代時,都需要重新利用基變量和非基變量的價(jià)值系數(shù)來計(jì)算檢驗(yàn)數(shù),由此可以看出,傳統(tǒng)的單純形表不夠簡便,計(jì)算比較麻煩,方法也容易忘記.學(xué)生在做運(yùn)籌學(xué)課程[1]的作業(yè)題,尤其是線性規(guī)劃部分的作業(yè)題時,由于決策變量的個數(shù)不僅僅是兩個,所以線性規(guī)劃模型的求解就不能統(tǒng)統(tǒng)利用圖解法來求解,而是利用單純形法來求解,這必然造成表格多,計(jì)算量大.學(xué)生做作業(yè)題時,往往方法、計(jì)算步驟和原理都掌握了,但僅僅由于表格中的某一個數(shù)字計(jì)算錯誤,造成計(jì)算結(jié)果錯誤,這不僅打擊了學(xué)生學(xué)習(xí)運(yùn)籌學(xué)課程的積極性,還使學(xué)生對自己計(jì)算能力的正確性產(chǎn)生了動搖.面對這種情況,經(jīng)過多年的教學(xué)實(shí)踐,對單純形法進(jìn)行了分析和研究,找到了一種比較好的解決辦法,即通過對傳統(tǒng)的單純形表進(jìn)行改進(jìn),提出了一種簡易的單純形表.

通過對單純形表的觀察和整個單純形法迭代過程的研究后發(fā)現(xiàn),在單純形表中,基變量列在整個單純形法迭代過程中都始終保持為一單位列向量,即其技術(shù)系統(tǒng)向量ei=(0,…,0,1,0,…,0)T,其中第i行為1,檢驗(yàn)數(shù)為0,因此可以將單純形表中的基變量列刪除,便得到簡易的單純形表.設(shè)初始基可行解為X0=(b1,b2,…,bm,0,…,0)T,基變量向量XB=(x1,x2,…,xm)T,非基變量向量XN=(xm+1,…,xn)T,系數(shù)矩陣A=(B,N),其中A=(aij)n×m為基矩陣,B=(aij)m×m為基矩陣,N=(aij)n-m,m為非基矩陣,故簡易的初始單純形表如下:

在單純形法中,每迭代一次就得到一個新的簡易單純形表.當(dāng)我們確定xk為換入變量,xl為換出變量時,就以alk為主元進(jìn)行旋轉(zhuǎn)運(yùn)算,列出新的單純形表.

在新的簡易單純形表中,非基變量形中的換入變量xk用換出變量xl替代,同樣基變量列中的換出變量xl用換入變量xk替代,也可以形象地說在原表中,以主元alk為中心,換出變量xl順時針方向旋轉(zhuǎn)90°到達(dá)換入變量xk所在的位置并替代它,同樣換入變量xk逆時針旋轉(zhuǎn)90°到達(dá)換出變量xl所在的位置并替代它.并且在新表中,(i)主元:以1/alk表示(主元的倒數(shù));(ii)主行:(除主元外)用主行除以主元(alk);(iii)主列:(除主元外)用主列除以負(fù)主元(-alk);(iv)其余元素(非主行主列上的元素)用矩形法則確定.

下面介紹矩形法則:設(shè)a,b,c,d為矩形的四個頂點(diǎn),其中a為主元,b,c為主行、主列上的元素,d為非主行主列上的元素,則經(jīng)過迭代后,d就變成d′=d-(即為對角線上的元素減去相鄰元素的乘積除以主元).

在簡易單純形表中,容易知道:(i)非主行主列上的元素(包括檢驗(yàn)數(shù)行上的元素σj和b列上的元素bi)都可以和主元構(gòu)成一個矩形.(ii)主行或主列只要有一個元素為0,則在新表中相應(yīng)的列或行保持不變.

在單純形法中,如果采用這種簡易的單純形表,并在迭代過程中用矩形法則計(jì)算,可以大大地減少計(jì)算量(用傳統(tǒng)的單純形表解一個線性規(guī)劃的平均運(yùn)算工作量為O(m4+m2n)階,而用簡易的單純形表解一個線性規(guī)劃的平均運(yùn)算工作量為O(3m2n+3n)階)并使計(jì)算變得更加簡單,計(jì)算方法也更加易記,而且在計(jì)算過程中也不容易出錯;其次,這種簡易的單純形表的另外一個優(yōu)點(diǎn)就是節(jié)省了存儲量,即只要在開始利用變量的價(jià)值系數(shù)cj,j=1,2,…,n,來計(jì)算非基變量的檢驗(yàn)數(shù),然后在以后的計(jì)算中就可以直接利用矩形法則來計(jì)算非基變量的檢驗(yàn)數(shù)了.

在運(yùn)籌學(xué)課程的教學(xué)過程中,先講授用傳統(tǒng)的單純形表的單純形法,然后在此基礎(chǔ)上,再順理成章地講解這種簡易的單純形表法,把這兩種方法一比較,優(yōu)劣非常明顯.并且經(jīng)過多年的教學(xué)實(shí)踐表明:該法簡單易行,學(xué)生不僅樂于接受而且也易于接受,這就幫助了學(xué)生解決了求解線性規(guī)劃習(xí)題的困難,從而大大提高了學(xué)生學(xué)習(xí)運(yùn)籌學(xué)課程的積極性,從而在教與學(xué)兩方面都取得了比較滿意的效果.

2 將數(shù)學(xué)建模的思想融入到運(yùn)籌學(xué)課程的教學(xué)中,體現(xiàn)問題驅(qū)動的教學(xué)理念

運(yùn)籌學(xué)是一門理論與實(shí)踐相結(jié)合的應(yīng)用學(xué)科,從它的各個分支來看,優(yōu)化思想貫穿于這門學(xué)科的始終.而數(shù)學(xué)建模,自1992年中國工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會創(chuàng)辦全國大學(xué)生數(shù)學(xué)建模競賽以來,越來越受到高校教師和大學(xué)生的重視,它主要是培養(yǎng)學(xué)生運(yùn)用數(shù)學(xué)知識去解決實(shí)際問題的能力,同時它也是優(yōu)化思想的具體表現(xiàn).因此,運(yùn)籌學(xué)與數(shù)學(xué)建模的聯(lián)系非常密切的.數(shù)學(xué)建模,是學(xué)生們運(yùn)用數(shù)學(xué)知識創(chuàng)造性地建立模型去解決豐富多彩的實(shí)際問題,在這一過程中,學(xué)生們獲益不少,故學(xué)生們對數(shù)學(xué)建模表現(xiàn)出了濃厚的興趣和積極性.俗話說“興趣是最好的老師”,興趣更是學(xué)習(xí)最有效的動力.故如何提高學(xué)生學(xué)習(xí)運(yùn)籌學(xué)的興趣,真正學(xué)到運(yùn)籌學(xué)的思想性的東西,培養(yǎng)學(xué)生創(chuàng)造性思維和具備運(yùn)籌學(xué)的理論和方法去解決實(shí)際問題的能力,必須將數(shù)學(xué)建模的思想融入到運(yùn)籌學(xué)課程的教學(xué)中去[2-3].

多年來,作者一直從事數(shù)學(xué)建模和運(yùn)籌學(xué)這兩門課程的教學(xué).這兩門課程既有相似之處,也有各自的特色,在運(yùn)籌學(xué)課程的教學(xué)中,作者試圖把數(shù)學(xué)建模的思想和精神融入到運(yùn)籌學(xué)課程的教學(xué)中去,把運(yùn)籌學(xué)里學(xué)生們認(rèn)為是枯燥無味的概念、理論、方法講得像數(shù)學(xué)建模一樣有聲有色、富有激情,從而提高學(xué)生們學(xué)習(xí)運(yùn)籌學(xué)的興趣和積極性.

一年一度的數(shù)學(xué)建模競賽賽題,為講授運(yùn)籌學(xué)提供了豐富的素材,一方面是因?yàn)閿?shù)學(xué)建模競賽賽題來自于現(xiàn)實(shí)生活,緊跟時代潮流,涉及各個學(xué)科領(lǐng)域而且豐富多彩;另一方面是因?yàn)閿?shù)學(xué)建模競賽是一種選拔性競賽,不是每個大學(xué)生都能參與的,對于大部分學(xué)生來說,雖然不能參與競賽,但也希望能了解數(shù)學(xué)建模競賽賽題.因此,選擇一些歷年數(shù)學(xué)建模競賽賽題作為講授運(yùn)籌學(xué)的例題,可以大大提高學(xué)生學(xué)習(xí)的興趣和求知欲.當(dāng)然如何選取典型的數(shù)學(xué)建模競賽賽題作為講授運(yùn)籌學(xué)的例題是一個比較復(fù)雜的問題,但作者認(rèn)為選擇的標(biāo)準(zhǔn)有三,一是所選的數(shù)學(xué)建模競賽賽題應(yīng)該要比運(yùn)籌學(xué)教材中的應(yīng)用性例題和習(xí)題更能反映解決問題的全過程;二是所選為數(shù)學(xué)建模競賽賽題里所涉及的專業(yè)知識應(yīng)該盡量是廣大學(xué)生所能接受的,所需用到的運(yùn)籌學(xué)知識,是符合教學(xué)內(nèi)容要求的;三是所選數(shù)學(xué)建模競賽賽題要有明確的目的,要與某個內(nèi)容相聯(lián)系,要為某種教學(xué)內(nèi)容服務(wù).

將數(shù)學(xué)建模的思想融入到運(yùn)籌學(xué)課程的教學(xué)中去,并不是把運(yùn)籌學(xué)課程變?yōu)閿?shù)學(xué)建模課程、或者是數(shù)學(xué)試驗(yàn)課,而是有意識地結(jié)合運(yùn)籌學(xué)的教學(xué)內(nèi)容和學(xué)生的知識水平制造實(shí)際問題的情景,把學(xué)生引導(dǎo)到情景中來,讓教師和學(xué)生一起發(fā)現(xiàn)運(yùn)籌學(xué)的概念、理論和方法,再回到實(shí)踐中去.

下面是將數(shù)學(xué)建模的思想和精神融入到運(yùn)籌學(xué)課程的教學(xué)中去的一部分嘗試.在講解《運(yùn)籌學(xué)》的第四章目標(biāo)規(guī)劃時,根據(jù)選擇建模競賽賽題的三個標(biāo)準(zhǔn),挑選了2004年建模競賽題目:公交車的調(diào)度模型.雖然乘坐共交車是生活的一部分,但我們很少用運(yùn)籌學(xué)的理論和方法去分析它、優(yōu)化它.故用這樣一個貼近生活的實(shí)際問題作為講解目標(biāo)規(guī)劃的例題,一下子就拉近了我們與運(yùn)籌學(xué)中的抽象的概念、理論和方法的距離,很自然地把學(xué)生導(dǎo)入到實(shí)際問題的情景中來,然后水到渠成講解目標(biāo)規(guī)劃的概念、理論和方法.

在公交車調(diào)度問題中我們邊分析問題邊引入概念,當(dāng)分析到從乘客的利益出發(fā),高峰時段乘客的候車時間不超過5分鐘,即t1≤5,(t1為高峰時段的公交車的發(fā)車時間間隔,也可以理解為大多數(shù)乘客的平均候車時間),因上t1≤5是我們追求的第一個目標(biāo),其中5就是目標(biāo)值,但是很明顯不能把它作為模型的目標(biāo)函數(shù),故如何根據(jù)追求的第一個目標(biāo)t1≤5,找到一個與之聯(lián)系的目標(biāo)函數(shù)呢?很容易根據(jù)坐公交車的經(jīng)驗(yàn),候車時間t1有可能大于5或者小于5,因此,把候車時間t1大于目標(biāo)值5的那一部分,稱為正偏差,記為,把候車時間t1小于目標(biāo)值5的那一部分,稱為負(fù)偏差,記為.從乘客的利益出發(fā),希望候車時間t1小于目標(biāo)值的那部分不限,但要盡可能縮小大于目標(biāo)值5的那一部分正偏差,即為min,故第一個目標(biāo)函數(shù)為min.同時要考慮目標(biāo)函數(shù)min是不是會受到某些條件的約束呢?從乘客到站候車的這個過程來看,是一個隨機(jī)的泊松過程,故希望候車時間t1的均值(數(shù)學(xué)期望值)應(yīng)該等于目標(biāo)值5,記為:t1+-=5,這就是目標(biāo)函數(shù)所受到的約束條件,稱為目標(biāo)約束(即包含有正負(fù)偏差的等式約束條件),目標(biāo)約束是一種軟約束.同時可以分析平峰時段乘客的候車時間不超過10分鐘,即t2≤10,(t2為平峰時段的公交車的發(fā)車時間間隔,也可以理解為大多數(shù)乘客的平均候車時間)的情況,即第二個目標(biāo)函數(shù)為:min,目標(biāo)約束為t2+-=10.

在公交車的調(diào)度問題中,不僅要考慮乘客的利益,而且也要考慮公交公司的利益.從公交公司的利益出發(fā),公交車的平均載客率p≥50%,也就是說:要求超過目標(biāo)值,即超過量不限,但要盡可能縮小沒有達(dá)到載客率為50%的那一部分(負(fù)偏差),即第三個目標(biāo)函數(shù)為:min,目標(biāo)約束為: p+-=50%.

在公交車的調(diào)度問題中,由于公交車的容量有限,故存在一個最大載客率pmax=120%,所有的公交車的載客率都必須小于或等于120%,即為:p≤120%,這個約束條件是不能違背的,也就是說不允許發(fā)生p＞120%這種情況,這樣的約束條件稱為絕對約束,是一種硬約束.

通過以上分析,易知公交車的調(diào)度問題有三個目標(biāo)需要考慮:t1≤5,t2≤10,p≥50%,故該公交車的調(diào)度問題模型為一個多目標(biāo)規(guī)劃(目標(biāo)函數(shù)為兩個或兩個以上的規(guī)劃),其中

在公交車的調(diào)度問題模型中,有三個目標(biāo)需要達(dá)到,在考慮這些目標(biāo)時,是有主次或輕重緩急的不同.當(dāng)考慮到公交車的主要功能:社會公益性,并在滿足這種前提的基礎(chǔ)上,再考慮公交公司的利益,故可以把這多個目標(biāo)分成不同的優(yōu)先等級(優(yōu)先因子),即把第一個目標(biāo)(高峰時段達(dá)到的目標(biāo))賦予優(yōu)先等級P1,這要求第一位達(dá)到的目標(biāo)(主要目標(biāo));把第二個目標(biāo)(平峰時段達(dá)到的目標(biāo))和第三個目標(biāo)(公交公司達(dá)到的目標(biāo))賦予相同的優(yōu)先等級P2,這是第二位要達(dá)到的目標(biāo)(次要目標(biāo)).規(guī)定P1?P2,表示P1級目標(biāo)比P2級目標(biāo)有更大優(yōu)先權(quán),即首先保證P1級目標(biāo)的實(shí)現(xiàn),這時可不考慮次級目標(biāo)(P2級目標(biāo));而P2級目標(biāo)是在實(shí)現(xiàn)P1目標(biāo)的基礎(chǔ)上考慮的.對處在同一優(yōu)先等級P2的兩個目標(biāo)(平峰時段達(dá)到的目標(biāo)和公交公司達(dá)到的目標(biāo)),又根據(jù)它們的重要程度,賦予不同的權(quán)重wj,其中1＞wj＞0, j=1,2,且w1+w2=1.故對高峰時段達(dá)到的目標(biāo)有:P1d+1;對平峰時段達(dá)到的目標(biāo)和公交公司達(dá)到的目標(biāo)有:P2(w1d+2+w2d+3).經(jīng)過上述分析,把關(guān)于公交車的調(diào)度問題的一個多目標(biāo)規(guī)劃模型轉(zhuǎn)化成為只有一個目標(biāo)函數(shù)的目標(biāo)規(guī)劃模型為

對此目標(biāo)規(guī)劃模型的結(jié)構(gòu)它與線性規(guī)劃模型的結(jié)構(gòu)沒有本質(zhì)的區(qū)別,故可用單純形法求解.

通過對公交車的調(diào)度問題的分析和建立其目標(biāo)規(guī)劃模型,使學(xué)生們很松地理解和掌握了目標(biāo)規(guī)劃的基本概念、理論和方法,從而提高了教和學(xué)的效果.

總之,在運(yùn)籌學(xué)課程的教學(xué)過程中,通過不斷地進(jìn)行探索與實(shí)踐,不斷地改善教學(xué)內(nèi)容和教學(xué)方法,并把數(shù)學(xué)建模的思想和精神不斷地融入到運(yùn)籌學(xué)課程的教學(xué)中去,使學(xué)生們對運(yùn)籌學(xué)的學(xué)習(xí)不再枯燥乏味了,運(yùn)籌學(xué)也變得生動有趣了;老師對運(yùn)籌學(xué)的講解也不再是枯燥的理論講解了,而是在具體問題的解決中使知識的掌握更牢固了.

[1] 胡運(yùn)權(quán).運(yùn)籌學(xué)教程[M].北京：清華大學(xué)出版社,1998.

[2] 張兵.案例教學(xué)在運(yùn)籌學(xué)教學(xué)中的應(yīng)用[J].徐州教育學(xué)院學(xué)報(bào),2008,23(3)：153-154.

[3] 李蘇北,等.運(yùn)籌學(xué)課程建設(shè)與改革實(shí)踐研究[J].大學(xué)數(shù)學(xué),2005,21(5)：15-17.

Research and Pratics in Course of Teaching Operations Research

WA N G Fang-hua, FEN G Chun-sheng
(School of Mathematics and Computational Science,Xiangtan University,Xiangtan 411105,China)

Integrated with the experiences of pratical teaching activities,from the increased interest and enthusiasm of the students,teaching in the process of operational research,we present to the student-centered,improve teaching content and teaching methods,and to the idea of mathematical modeling is integrated into the teaching of opeartions research to improve student learning and teachers teaching effectiveness.

operations research;mathematical medeling;research and practice

G423

C

1672-1454(2011)05-0185-04

2011-05-24

湖南省教育廳資助科研項(xiàng)目(10C1289;10C1265)