運籌學課程教學中的探索與實踐

王芳華, 馮春生

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

運籌學課程教學中的探索與實踐

王芳華, 馮春生

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

結合教學實踐經驗,從提高學生的興趣和積極性出發,在運籌學課程的教學過程中,提出了以學生為本,改進教學內容和教學方法,并把數學建模的思想融到運籌學課程的教學中去,從而提高學生的學習效果和教師的教學效果.

運籌學;數學建模;探索與實踐

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

1 以學生為本,改進教學內容和方法,提高學生學習的積極性

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

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

在單純形法中,每迭代一次就得到一個新的簡易單純形表.當我們確定xk為換入變量,xl為換出變量時,就以alk為主元進行旋轉運算,列出新的單純形表.

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

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

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

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

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

2 將數學建模的思想融入到運籌學課程的教學中,體現問題驅動的教學理念

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

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

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

將數學建模的思想融入到運籌學課程的教學中去,并不是把運籌學課程變為數學建模課程、或者是數學試驗課,而是有意識地結合運籌學的教學內容和學生的知識水平制造實際問題的情景,把學生引導到情景中來,讓教師和學生一起發現運籌學的概念、理論和方法,再回到實踐中去.

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

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

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

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

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

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

對此目標規劃模型的結構它與線性規劃模型的結構沒有本質的區別,故可用單純形法求解.

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

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

[1] 胡運權.運籌學教程[M].北京：清華大學出版社,1998.

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

[3] 李蘇北,等.運籌學課程建設與改革實踐研究[J].大學數學,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)