運(yùn)籌學(xué)“運(yùn)輸問題”的教學(xué)方法探討

1、運(yùn)籌學(xué)“運(yùn)輸問題”的教學(xué)方法探討【摘要】 用運(yùn)籌學(xué)的思想探討運(yùn)籌學(xué)課程的教學(xué)方法。運(yùn)籌學(xué)中的指派問題、最短路問題，最小費(fèi)用流問題可轉(zhuǎn)化為運(yùn)輸問題或轉(zhuǎn)運(yùn)問題，從而可以統(tǒng)籌安排這些教學(xué)內(nèi)容，為提高教學(xué)效果，減少教學(xué)時(shí)間找出更優(yōu)的教學(xué)方法。 【關(guān)鍵詞】 運(yùn)輸問題; 轉(zhuǎn)運(yùn)問題; 運(yùn)籌學(xué); 教學(xué)方法運(yùn)籌學(xué)是一門應(yīng)用科學(xué)，它運(yùn)用數(shù)學(xué)方法對經(jīng)濟(jì)和管理系統(tǒng)中的各種有限資源進(jìn)行統(tǒng)籌安排，為決策者提供最優(yōu)參考方案，以實(shí)現(xiàn)有效的科學(xué)管理。運(yùn)籌學(xué)是管理類專業(yè)的專業(yè)基礎(chǔ)課，對管理類人才培養(yǎng)有著重要的意義。該課程的特點(diǎn)是將數(shù)學(xué)知識(shí)、數(shù)學(xué)建模、經(jīng)濟(jì)管理與計(jì)算機(jī)應(yīng)用四者融為一體，通過各類實(shí)際問題的案例，培養(yǎng)學(xué)生分析、解決實(shí)際

2、問題的能力。該課程本身有一定的難度，作為教師，應(yīng)努力探索教育教學(xué)規(guī)律，認(rèn)真把握課程的特點(diǎn)，以獲得良好的教學(xué)效果。如何在現(xiàn)有的有限資源條件下(如學(xué)時(shí)、生源、師資)，將這門課上好，不也正是運(yùn)籌學(xué)研究的內(nèi)容嗎?運(yùn)籌學(xué)涉及內(nèi)容較多，線性規(guī)劃是最主要的一個(gè)分支，其理論最完善、方法最成熟，應(yīng)用也最廣泛，涉及的很多問題都是經(jīng)典的問題，如運(yùn)輸問題、指派問題、最短路問題，最小費(fèi)用流問題等。自己在運(yùn)籌學(xué)教學(xué)過程中發(fā)現(xiàn)，這些問題有相同的共性，可以歸結(jié)為同一個(gè)問題，從而可以統(tǒng)籌安排教學(xué)內(nèi)容，為運(yùn)籌學(xué)課程提高教學(xué)效果，減少教學(xué)時(shí)間找出更優(yōu)的教學(xué)方法。1 運(yùn)輸問題和轉(zhuǎn)運(yùn)問題1.1 運(yùn)輸問題運(yùn)輸問題一般指貨物可直接從產(chǎn)地運(yùn)

3、往銷地。下面以運(yùn)費(fèi)問題為例進(jìn)行說明。記si 為產(chǎn)地Ai(i=1,2,n) 的產(chǎn)量，dj 為銷地Bj(j=1,2,m) 的銷量，cij 為把貨物從產(chǎn)地Ai 運(yùn)往銷地Bj 的單位運(yùn)價(jià)。設(shè)xij 為從產(chǎn)地Ai 運(yùn)到銷地Bj 的貨物量，則運(yùn)費(fèi)最少的產(chǎn)銷平衡問題的線性規(guī)劃模型為1,4：目標(biāo)函數(shù) min z=ni=1 mj=1cijxij約束條件 mj=1xij=si ，(i=1,2,n) (1)ni=1xij=dj ，(j=1,2,m) (2)xij0 ,對所有的i 和j 。對于不同的實(shí)際問題，有時(shí)還需加一些約束條件。例如，當(dāng)貨物量的單位為“件”、“箱”時(shí)，還需加上xij 為整數(shù)的約束條件。對于產(chǎn)銷不平

4、衡問題一般用兩種方法解決：第一種方法是建立一個(gè)假想(虛擬)的產(chǎn)地或銷地，根據(jù)實(shí)際問題，將從產(chǎn)地運(yùn)往銷地的單位運(yùn)價(jià)設(shè)為0或一個(gè)很大的數(shù)，再轉(zhuǎn)化為產(chǎn)銷平衡問題，這一方法比較復(fù)雜一些。另一種更簡單的方法是，對產(chǎn)大于銷問題，將(1)式中的等式變?yōu)?，對銷大于產(chǎn)問題，將(2)式中的等式變?yōu)?，這種方法更直觀，易于學(xué)生理解和掌握。1.2 轉(zhuǎn)運(yùn)問題轉(zhuǎn)運(yùn)問題是運(yùn)輸問題的一個(gè)擴(kuò)充，當(dāng)產(chǎn)地的貨物不能直接運(yùn)往銷地時(shí)，需通過中轉(zhuǎn)站。記產(chǎn)地為發(fā)點(diǎn)，銷地為收點(diǎn)，中轉(zhuǎn)站為中轉(zhuǎn)點(diǎn)，cij 為把貨物從點(diǎn)i 運(yùn)往點(diǎn)j 的單位運(yùn)價(jià)。設(shè)xij 為從點(diǎn) i運(yùn)往點(diǎn)j 的貨物量，則運(yùn)費(fèi)最少的產(chǎn)銷平衡轉(zhuǎn)運(yùn)問題的線性規(guī)劃模型為1,4 ：目標(biāo)函

5、數(shù) min z=所有的弧cijxij約束條件 ：對發(fā)點(diǎn)i 有 所有的流出量xij-所有的流入量xij=si (3)對中轉(zhuǎn)點(diǎn)有 所有的流出量xij-所有的流入量xij=0 (4)對收點(diǎn)j 有 所有的流出量xij-所有的流入量xij=di (5)xij0 ，對所有的i 和j 。對于產(chǎn)銷不平衡問題，可根據(jù)實(shí)際問題將(3)或(5)式中的等號(hào)改為不等號(hào)。2 可轉(zhuǎn)化為運(yùn)輸問題的問題2.1 指派問題一般的指派問題為1,4：有n 項(xiàng)任務(wù)，恰好有n 個(gè)人可分別承擔(dān)這些任務(wù)，由于各人特長不同，完成各項(xiàng)任務(wù)的效率等情況(如時(shí)間)也不同，現(xiàn)假設(shè)必須指派每個(gè)人去完成一項(xiàng)任務(wù)，怎樣把n 項(xiàng)任務(wù)指派給n 個(gè)人，使完成n 項(xiàng)

6、任務(wù)的總效率最高。以完成任務(wù)的效率是時(shí)間為例，說明指派問題可轉(zhuǎn)化為運(yùn)輸問題。將每個(gè)人看成產(chǎn)地，產(chǎn)量均為1，si=1 ，即每個(gè)人生產(chǎn)出一個(gè)勞動(dòng)力;將每項(xiàng)工作看成銷地，銷量為1，dj=1 ，即每項(xiàng)工作需要一個(gè)勞動(dòng)力來完成;將每個(gè)人完成各項(xiàng)任務(wù)的時(shí)間看成單位運(yùn)價(jià)cij ;設(shè)xij=1 為指派第 i個(gè)人完成第j 項(xiàng)工作，設(shè)xij=0 為不指派第i 個(gè)人完成第j 項(xiàng)工作，則上述指派問題可轉(zhuǎn)化為產(chǎn)銷平衡的運(yùn)輸問題。當(dāng)任務(wù)項(xiàng)數(shù)多于人數(shù)時(shí)，可看成是銷大于產(chǎn)的情況，當(dāng)人數(shù)多于任務(wù)項(xiàng)數(shù)時(shí)，可看成是產(chǎn)大于銷的情況，由此可轉(zhuǎn)化為產(chǎn)銷不平衡的運(yùn)輸問題。2.2 特殊的背包問題一般的背包問為1：設(shè)背包攜帶物品的重量限制為W

7、 ，N 種物品中第i 種物品的重量為wi ，價(jià)值為ci ，總數(shù)量為ni ，如何決定這N 種物品中的每一種物品多少數(shù)量裝入背包內(nèi)，使得裝入背包物品的總價(jià)值最大?？紤]wi 都相等的特殊情況，即每種物品的重量都相等，不妨設(shè)為1。將第i 種物品看成產(chǎn)地Ai ，產(chǎn)量為ni ;將背包看成唯一的一個(gè)銷地，銷量為W ，將第i 種物品的價(jià)值負(fù)數(shù)看成單位運(yùn)價(jià)-ci ，設(shè)xi 為攜帶的第i 種物品的數(shù)量，則這種背包問題可轉(zhuǎn)化為銷大于產(chǎn)的的運(yùn)輸問題。3 可轉(zhuǎn)化為轉(zhuǎn)運(yùn)問題的問題3.1 最短路問題一般的最短路問題為1：對一個(gè)賦權(quán)的有向圖，找到一條從一個(gè)指定的起點(diǎn)到另一個(gè)指定的終點(diǎn)的路，使這條路上所有弧的權(quán)數(shù)的總和最小。將

8、起點(diǎn)看成唯一的一個(gè)產(chǎn)地(發(fā)點(diǎn))，產(chǎn)量為1;將終點(diǎn)看成唯一的一個(gè)銷地(收點(diǎn))，銷量為1;將其余點(diǎn)看成中轉(zhuǎn)點(diǎn)，任兩點(diǎn)的權(quán)看成單位運(yùn)價(jià)，并設(shè)xij=1 為最短路經(jīng)過弧(i ，j )， xij=0為最短路不經(jīng)過弧(i ，j )，則最短路問題可轉(zhuǎn)化為產(chǎn)銷平衡的轉(zhuǎn)運(yùn)問題。在實(shí)際應(yīng)用中遇到更多的是無向圖的最短路問題。這時(shí)需將無向圖添加方向變?yōu)橛邢驁D。由于最短路不可能由起點(diǎn)出發(fā)再回到起點(diǎn)，到了終點(diǎn)也不會(huì)再轉(zhuǎn)向其它點(diǎn)，而其它情況的各種可能性都有，所以可用如下方法為無向圖添加方向：與起點(diǎn)相連的弧，方向由起點(diǎn)指向另一點(diǎn);與終點(diǎn)相連的弧，方向由另一點(diǎn)指向終點(diǎn);與起點(diǎn)、終點(diǎn)無關(guān)的弧，給出雙向的方向(圖1)?；?i ，j

9、 )和弧(i ，j )權(quán)相同。圖1 無向圖(左)添加方向成為有向圖(右)，其中1為起點(diǎn)，5為終點(diǎn)3.2 最大流問題一般的最大流問題為1 ：給了一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在不超過每條弧的容量的前提下，求出從發(fā)點(diǎn)到收點(diǎn)的最大流量。記發(fā)點(diǎn)為v1 ，收點(diǎn)為vn ，fij 為弧(vi,vj) 上的容量，M=rk=2f1k ，各條弧上的單位運(yùn)價(jià)為c1k=-1 ，k=2,3,r ，其余cij=0 。設(shè)xij 為弧(vi,vj) 上的流量，則上述最大流問題可轉(zhuǎn)化為只有一個(gè)產(chǎn)地(發(fā)點(diǎn))，產(chǎn)量為M，只有一個(gè)銷點(diǎn)(收點(diǎn))，銷量為rk=2x1k 的產(chǎn)大于銷的轉(zhuǎn)運(yùn)問題：目標(biāo)函數(shù) min z=所有的弧

10、cijxij=-rk=2x1k 約束條件 ：對發(fā)點(diǎn)1 有 rk=2x1kM (6)對中轉(zhuǎn)點(diǎn)有 所有的流出量xij-所有的流入量xij=0對收點(diǎn)n 有 所有的流入量xin=rk=2x1k0xijfij ，對所有的 i和j 。其實(shí)(6)式是多余的，由 0xijfij可以得到，這里僅為了說明該問題可轉(zhuǎn)化為轉(zhuǎn)運(yùn)問題。3.3 最小費(fèi)用流問題一般的最小費(fèi)用流問題為4：給了一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，對每一條弧除給出了容量外，還給出了這條弧的單位流量的費(fèi)用，要求一個(gè)可行流，并使得總運(yùn)送費(fèi)最小。若可行流是最大流時(shí)，則為最小費(fèi)用最大流問題。最小費(fèi)用最大流問題分兩步解，第一步，先求出最大流F;第二步，在最大流F的所有解中

11、，找出一個(gè)最小費(fèi)用的解。關(guān)于第一步求最大流問題，已在前面討論過。第二步求最小費(fèi)用問題，將發(fā)點(diǎn)看成唯一的產(chǎn)地，產(chǎn)量為F(或可行流)，將收點(diǎn)看成唯一的銷地，銷量為F(或可行流)，每條弧的單位流量的費(fèi)用看成單位運(yùn)價(jià)，由此可轉(zhuǎn)化為產(chǎn)銷平衡的轉(zhuǎn)運(yùn)問題。4 討論在教學(xué)中，將看似不同的問題歸納轉(zhuǎn)化為同一問題，非常重要。首先，這涉及到教學(xué)內(nèi)容的結(jié)構(gòu)問題，原來看似不同的問題可能在教材的不同章節(jié)，轉(zhuǎn)化為同一問題后可并入同一章節(jié)。第二，對提高教學(xué)效果有一定的幫助。對老師而言，可減少教學(xué)時(shí)間，原先要花較多時(shí)間講解不同的問題，現(xiàn)在只需講解一個(gè)問題，然后作為同一問題舉一反三，不僅可將原問題講授得更清楚，也解決了新問題。對

12、學(xué)生而言，原先要記多種問題的解法，現(xiàn)在只需記一種解法就可以了，減輕了學(xué)習(xí)負(fù)擔(dān)。第三，更重要的是，啟發(fā)學(xué)生對問題有更深入的理解，抓住事物的本質(zhì)，而不是停留在表面，這對培養(yǎng)學(xué)生抽象思維、綜合歸納能力是大有裨益的。當(dāng)然，要做到這一點(diǎn)，對老師的要求顯然更高，必須要花更多的時(shí)間和精力研究問題，吃透教材，理解精髓，融會(huì)貫通，非一般的應(yīng)付教學(xué)所能解決的。最后，在用計(jì)算機(jī)求解方面，可用同一程序處理這些類似的問題。因此，將看似不同的問題歸納轉(zhuǎn)化為同一問題，可以統(tǒng)籌安排教學(xué)內(nèi)容，在現(xiàn)有的教學(xué)條件下，能幫助我們提高教學(xué)效果，減少教學(xué)時(shí)間。這正是運(yùn)籌學(xué)的精髓，對各種有限資源進(jìn)行統(tǒng)籌安排，找出最優(yōu)方案。所以本文與其說是教學(xué)體會(huì)，還不如說是運(yùn)籌學(xué)方法的運(yùn)用，用運(yùn)籌學(xué)方法探討運(yùn)籌學(xué)的教學(xué)問題，為運(yùn)籌學(xué)教學(xué)找到一種更好的方法?！緟⒖嘉墨I(xiàn)】1 韓伯棠.管理運(yùn)籌學(xué).第2版.北京：高等教育出版社,2005.2 羅榮桂，原海英.運(yùn)籌學(xué)教學(xué)改革與探索.理工高教研究，2005，24(3)：4950.3 黃宇林.從運(yùn)籌學(xué)教學(xué)談人才培養(yǎng)模式與實(shí)踐.中國教育導(dǎo)刊，2005，(2)：7677.4 朱道立，徐慶，葉耀華.運(yùn)籌學(xué).北京：高等教育出版社,