王芳華, 馮春生

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

運籌學(xué)課程教學(xué)中的探索與實踐

王芳華, 馮春生

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

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

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

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

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

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

通過對單純形表的觀察和整個單純形法迭代過程的研究后發(fā)現(xiàn),在單純形表中,基變量列在整個單純形法迭代過程中都始終保持為一單位列向量,即其技術(shù)系統(tǒng)向量ei=(0,…,0,1,0,…,0)T,其中第i行為1,檢驗數(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為主元進行旋轉(zhuǎn)運算,列出新的單純形表.

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

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

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

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

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

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

運籌學(xué)是一門理論與實踐相結(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é)生運用數(shù)學(xué)知識去解決實際問題的能力,同時它也是優(yōu)化思想的具體表現(xiàn).因此,運籌學(xué)與數(shù)學(xué)建模的聯(lián)系非常密切的.數(shù)學(xué)建模,是學(xué)生們運用數(shù)學(xué)知識創(chuàng)造性地建立模型去解決豐富多彩的實際問題,在這一過程中,學(xué)生們獲益不少,故學(xué)生們對數(shù)學(xué)建模表現(xiàn)出了濃厚的興趣和積極性.俗話說“興趣是最好的老師”,興趣更是學(xué)習(xí)最有效的動力.故如何提高學(xué)生學(xué)習(xí)運籌學(xué)的興趣,真正學(xué)到運籌學(xué)的思想性的東西,培養(yǎng)學(xué)生創(chuàng)造性思維和具備運籌學(xué)的理論和方法去解決實際問題的能力,必須將數(shù)學(xué)建模的思想融入到運籌學(xué)課程的教學(xué)中去[2-3].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[3] 李蘇北,等.運籌學(xué)課程建設(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

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