運(yùn)輸問題的求解及其應(yīng)用【畢業(yè)論文】

1、<p><b>　　本科畢業(yè)論文</b></p><p><b>　?。?0 屆）</b></p><p>　　運(yùn)輸問題的求解及其應(yīng)用</p><p>　　所在學(xué)院 </p><p>　　專業(yè)班級 數(shù)學(xué)與應(yīng)用數(shù)學(xué)

2、 </p><p>　　學(xué)生姓名 學(xué)號 </p><p>　　指導(dǎo)教師 職稱 </p><p>　　完成日期 年 月 </p><p>　　摘要：本課題主要探討了如何判別一個運(yùn)輸問題的調(diào)運(yùn)方案是最優(yōu)，對通常采

3、用的兩種閉回路法或位勢法做綜述整理，同時探討更好的一次性算法，既避免了閉回路法中對所有非基變量檢驗(yàn)數(shù)的一一計算,又回避了位勢法中需要多次求解線性方程組以計算位勢的過程。本課題主要利用了已有或已得到的算法對實(shí)際問題進(jìn)行分析研究。</p><p>　　關(guān)鍵詞：運(yùn)輸問題；最優(yōu)方案；一次性算法；閉回路法；位勢法</p><p>　　Transportation problem solving an

4、d its application</p><p>　　Abstract: My subject mainly discusses how to distinguish the transportation problem with optimal solution scheme, then synthetically induces about closed loop method or potentials

5、method which we always use. At the same time, we explore a better method to one-timely get the result. It not only avoids calculating one by one all the basic variable inspection number with closed loop method, but also

6、avoids the process of solving the linear equations many times to calculat potentials with potentials</p><p>　　Key words: Transportation problem; The optimal solution; One-time algorithm; Closed loop method;P

7、otentials method</p><p><b>　　目錄</b></p><p>　　1 運(yùn)輸問題簡介1</p><p>　　2 運(yùn)輸問題模型2</p><p>　　3 幾種常用檢驗(yàn)法的缺陷3</p><p>　　3.1 閉回路法的缺陷4</p><p

8、>　　3.2 位勢法的缺陷8</p><p>　　3.3 改進(jìn)的閉回路法的缺陷12</p><p>　　3.4 動態(tài)規(guī)劃法的缺陷12</p><p>　　4 一種新的檢驗(yàn)方法12</p><p>　　5 應(yīng)用舉例13</p><p>　　6 運(yùn)輸問題在消防中的應(yīng)用15</p>

9、<p><b>　　7 結(jié)束語17</b></p><p>　　致謝錯誤!未定義書簽。</p><p><b>　　參考文獻(xiàn)17</b></p><p><b>　　1 運(yùn)輸問題簡介</b></p><p>　　運(yùn)輸問題是一類具有特殊結(jié)構(gòu)的線性規(guī)劃問題。由

10、于運(yùn)輸問題約束方程組的系數(shù)矩陣是完全么模的，即所有的子行列式為0或±1，存在著比單純形法更簡單的特殊解法。對于規(guī)模不太大的運(yùn)輸問題可用圖上作業(yè)法或表上作業(yè)法求解。這類問題的典型提法是，為了把某種產(chǎn)品從若干個產(chǎn)地調(diào)運(yùn)到若干個銷地，已知每個產(chǎn)地的供應(yīng)量和每個銷地的需求量，如何在許多可行的調(diào)運(yùn)方案中，確定一個總運(yùn)輸費(fèi)或總運(yùn)輸量最少的方案。</p><p>　　具有上述特點(diǎn)的線性規(guī)劃問題通常被稱為運(yùn)輸型問題。現(xiàn)

11、已發(fā)現(xiàn)的運(yùn)輸型問題有以下6類:①一般運(yùn)輸問題,又稱希契科克運(yùn)輸問題，簡稱H問題。②網(wǎng)絡(luò)運(yùn)輸問題，又稱圖上運(yùn)輸問題,簡稱T問題。③最大流量問題,簡稱F問題。④最短路徑問題,簡稱S問題。⑤任務(wù)分配問題，又稱指派問題,簡稱A問題。⑥生產(chǎn)計劃問題，又稱日程計劃問題,簡稱CPS問題。其中一般運(yùn)輸問題、任務(wù)分配問題和生產(chǎn)計劃問題通常都可以用表上作業(yè)法求解，而網(wǎng)絡(luò)運(yùn)輸問題、最大流量問題和最短路徑問題一般可用圖上作業(yè)法或網(wǎng)絡(luò)技術(shù)求解（參見文獻(xiàn)[1]）。

12、</p><p>　　當(dāng)使用表上作業(yè)法求解運(yùn)輸問題時。初始基本可行解的求法有三種：①左上角法。它的基本思想是給運(yùn)輸表中左上角的變量分配運(yùn)輸量以確定產(chǎn)銷關(guān)系。②最小元素法，或最小成本法。它的基本思想是就近供應(yīng)，即從運(yùn)輸表中運(yùn)價最小的格子開始分配運(yùn)輸量以確定產(chǎn)銷關(guān)系。③元素差額法,又稱沃格爾近似法，簡稱VAM法。它是從運(yùn)輸表中各行和各列的最小元素和次小元素的差額來確定產(chǎn)銷關(guān)系。改進(jìn)初始基本可行解的方法有兩種：①閉回路

13、法。這種方法需要對每一個空格尋找一條閉回路，并根據(jù)閉回路求出每個空格的檢驗(yàn)數(shù)。當(dāng)運(yùn)輸問題中m 和n 較大時，計算檢驗(yàn)數(shù)的工作量很大。②位勢法，或乘數(shù)法。先對初始調(diào)運(yùn)方案求出位勢，然后求各空格的檢驗(yàn)數(shù)。當(dāng)所有的檢驗(yàn)數(shù)均為非負(fù)時，就得到最優(yōu)方案。如果出現(xiàn)負(fù)的檢驗(yàn)數(shù)，則從檢驗(yàn)數(shù)為負(fù)的空格出發(fā)，作閉回路，重新計算檢驗(yàn)數(shù)，作進(jìn)一步調(diào)整。用位勢法求檢驗(yàn)數(shù)就是對偶問題的表上作業(yè)法（參見文獻(xiàn)[2]）。</p><p>　　但是我

14、們發(fā)現(xiàn)對于實(shí)際的運(yùn)輸問題，上述優(yōu)化方法很難將運(yùn)輸過程中所發(fā)生的費(fèi)用都考慮進(jìn)去，因此，如果教條地采用上述優(yōu)化方法直接進(jìn)行優(yōu)化，則很難保證此方案是真正的最佳方案。實(shí)際的運(yùn)輸問題中上述方法沒考慮到的因素有：</p><p>　?。?）對運(yùn)輸問題中的中轉(zhuǎn)再分撥，其中轉(zhuǎn)的裝卸搬運(yùn)費(fèi)用，無論是求最小費(fèi)用最大流的優(yōu)化方法還是表上作業(yè)法求具有中轉(zhuǎn)站的運(yùn)輸問題最佳方案時，都沒有考慮此因素，但裝卸搬運(yùn)費(fèi)用及時間在物流費(fèi)用中占有一定的

15、比重。</p><p>　?。?）多種運(yùn)輸方式的聯(lián)合運(yùn)輸問題，當(dāng)物資通過運(yùn)輸網(wǎng)絡(luò)從出發(fā)地運(yùn)往目的地時，由于各線路的不同特點(diǎn)，可能需要采用不同的運(yùn)輸方式，不同的運(yùn)輸方式所產(chǎn)生的費(fèi)用是不同的，但上述的優(yōu)化方法沒有考慮此因素。雖然，人們對多式聯(lián)運(yùn)的優(yōu)化方法也進(jìn)行了一定的研究，但其方法也是有某些前提條件。</p><p>　?。?）對于物流系統(tǒng)中的配送問題，由于實(shí)際的配送問題，其配送方式有多種，按

16、照物流據(jù)點(diǎn)的不同，可分為配送中心配送、倉庫配送、就站配送、就港配送、就廠配送等；按照配送貨物的品種和數(shù)量，可分為單一品種大批量配送、多品種小批量配送、配套成套配送等；按照配送時間和數(shù)量，可分為定時配送、定量配送、定時定量配送、不定時（及時）配送等；按照配送時間和路線，可分為定時定路線配送、不定時定路線配送、定路線巡回配送等；按照配送用戶的范圍，可分為企業(yè)配送、行業(yè)配送、地區(qū)配送、城市配送等；按照配送經(jīng)營形式的不同，可分為銷售配送、供應(yīng)配

17、送、銷售—供應(yīng)一體化配送、代理配送等；按照企業(yè)之間的關(guān)系，可分為共同配送、集團(tuán)配送、單獨(dú)配送等。尋找能綜合解決滿足所有條件的最佳配送方案的方法正是人們所期望的。</p><p>　　（4）對于新的運(yùn)輸網(wǎng)絡(luò)，只知道從各產(chǎn)地運(yùn)往各銷地及可經(jīng)過的線路，這進(jìn)修求最佳方案，需要求多個指標(biāo)的最優(yōu)方案。如各地之間的單位物資的費(fèi)用（即單位運(yùn)價）、最大流量、最優(yōu)路線等（參見文獻(xiàn)[3]）。</p><p>　

18、　因此對于復(fù)雜的運(yùn)輸問題的優(yōu)化，要根據(jù)具體情況，綜合應(yīng)用各種優(yōu)化技術(shù)求其最優(yōu)的調(diào)運(yùn)方案。</p><p><b>　　2 運(yùn)輸問題模型</b></p><p>　　設(shè)某種物資有m個產(chǎn)地，有n個銷地，為第i個產(chǎn)地的產(chǎn)量，為第j個銷地的銷量，為從產(chǎn)地i到銷地j的單位運(yùn)價，這些數(shù)據(jù)可匯總于產(chǎn)銷平衡表和單位運(yùn)價表中，見下表。</p><p>　　若用

19、為從產(chǎn)地i到銷地j的調(diào)運(yùn)數(shù)量，，其中i=1，2..，m；j=1,2,….n。問如何調(diào)運(yùn)才能使得總運(yùn)費(fèi)最省?</p><p>　　在產(chǎn)銷平衡的條件下，其數(shù)學(xué)模型為</p><p>　?。?；i=1，2..，m；j=1,2,….n）</p><p>　　由于產(chǎn)銷不平衡運(yùn)輸問題可以通過添加虛擬的產(chǎn)地或銷地而化為產(chǎn)銷平衡運(yùn)輸問題，因此在這里僅研究平衡運(yùn)輸問題即可。</p

20、><p>　　3 幾種常用檢驗(yàn)法的缺陷</p><p>　　近兩年，物流已成為當(dāng)今中國經(jīng)濟(jì)最熱門名詞之一。運(yùn)輸在整個物流中占有很重要的地位，總成本占物流總成本的35％-50％左右，占商品價格的4％-10％。運(yùn)輸對物流總成本的節(jié)約具有舉足輕重的作用。會計學(xué)上將物流成本分為顯性成本和隱性成本（參見文獻(xiàn)[4]）。</p><p>　　在我國現(xiàn)行的物流運(yùn)輸方式中無論是自營物流

21、，合營物流還是第三方物流，隱性成本占據(jù)了很重要的地位，這些隱性成本在物流運(yùn)輸過程中主要包括以下幾個方面：返程或起程空駛：空車無貨載行駛，是不合理運(yùn)輸?shù)淖顕?yán)重形式。在實(shí)際運(yùn)輸組織中，必須調(diào)運(yùn)空車。但是，因調(diào)運(yùn)不當(dāng)貨源計劃不周，形成的空駛，是不合理運(yùn)輸?shù)谋憩F(xiàn)。造成空駛的不合理運(yùn)輸主要有以下幾種原因：依靠自備車送貨提貨，單程空駛的不合理運(yùn)輸。由于工作失誤或計劃不周，造成貨源不實(shí)，由于車輛過分專用，無法搭運(yùn)回程貨物。</p>&l

22、t;p>　　對流運(yùn)輸：在同一線路上或平行線路上作相對方向的運(yùn)送，而與對方運(yùn)程的部分發(fā)生重疊交錯的運(yùn)輸稱對流運(yùn)輸。 </p><p>　　迂回運(yùn)輸：舍近取遠(yuǎn)的一種運(yùn)輸。不選取短距離進(jìn)行運(yùn)輸，卻選擇路程較長路線進(jìn)行運(yùn)輸?shù)囊环N不合理形式。重復(fù)運(yùn)輸：直接將貨物運(yùn)到目的地，在未達(dá)目的地之處，或目的地之外的其它場所將貨卸下，再重復(fù)裝運(yùn)送達(dá)目的地，這是重復(fù)運(yùn)輸。另一種形式是，同品種貨物在同一地點(diǎn)一面運(yùn)進(jìn)，同時又向外

23、運(yùn)出。過遠(yuǎn)運(yùn)輸：是指調(diào)運(yùn)物資舍近求遠(yuǎn)，近處有資源不調(diào)而從遠(yuǎn)處調(diào)，這就造成可采取近程運(yùn)輸而未采取，拉長了貨物運(yùn)距的浪費(fèi)現(xiàn)象。 </p><p>　　運(yùn)力選擇不當(dāng)：在于火車及大型船舶起運(yùn)及到達(dá)目的地的準(zhǔn)備、裝卸時間長，且機(jī)動靈活性不足，在過近距離中利用，發(fā)揮不了運(yùn)速快的優(yōu)勢，延長運(yùn)輸時間。</p><p>　　因此，如何判別一個運(yùn)輸問題的調(diào)運(yùn)方案是否最優(yōu)至關(guān)重要。目前，通常采用閉回路法或位勢法

24、來判別，但這兩種方法的計算量都非常大，而且都有其局限性。</p><p>　　3.1 閉回路法的缺陷</p><p>　　所謂閉回路法，就是對于代表非基變量的空格（其調(diào)運(yùn)量為零），把它的調(diào)運(yùn)量調(diào)整為1，由于產(chǎn)銷平衡的要求,我們必須對這個空格的閉回路的頂點(diǎn)的調(diào)運(yùn)量加上或減少1。最后我們計算出由這些變化給整個運(yùn)輸方案的總運(yùn)輸費(fèi)帶來的變化。如果所有代表非基變量的空格的檢驗(yàn)數(shù)也即非基變量的檢驗(yàn)數(shù)

25、都大于等于零，則已求得最優(yōu)解，否則繼續(xù)迭代找出最優(yōu)解。</p><p>　　例如在給出調(diào)運(yùn)方案的計算表上，如下表，從每一空格出發(fā)找一條閉回路。它是以某空格為起點(diǎn)。用水平或垂直線向前劃，當(dāng)碰到一數(shù)字格時可以轉(zhuǎn)90°后，繼續(xù)前進(jìn)，直到回到起始空格為止（參見文獻(xiàn)[5]）。</p><p>　　任意空格（非基變量）對應(yīng)的系數(shù)列向量可用其閉回路上所有角點(diǎn)出數(shù)字格（基變量）的系數(shù)列向量線性表

26、示。如, i,j∈N可表示為：</p><p>　　其中。這些向量構(gòu)成了閉回路。</p><p>　　閉回路法計算檢驗(yàn)數(shù)的經(jīng)濟(jì)解釋為：在已給出初始解的表中，可從任一空格出發(fā)，如(，)。若讓的產(chǎn)品調(diào)運(yùn)1噸給。為了保持產(chǎn)銷平衡，就要依次作調(diào)整：</p><p>　　在(，)處減少1噸，(，)處增加1噸，(，)處減少1噸，即構(gòu)成了以(，)空格為起點(diǎn)，其他為數(shù)字格的閉回路。

27、如表中的虛線所示。</p><p>　　結(jié)合運(yùn)價，可見這調(diào)整的方案使運(yùn)費(fèi)增加： (+1)×3+(?1)×3+(+1)×2+(?1)×１=1(元)</p><p>　　當(dāng)檢驗(yàn)數(shù)還存在負(fù)數(shù)時，說明原方案不是最優(yōu)解，要繼續(xù)改進(jìn)。但是當(dāng)產(chǎn)銷地點(diǎn)很多時，僅尋找閉回路就相當(dāng)麻煩，并且在當(dāng)前方案不是最優(yōu)解時，調(diào)整的方案需要重新尋找所有非基變量的閉回路，并逐一計算新

28、的檢驗(yàn)數(shù)，顯然計算量很大。</p><p>　　3.2 位勢法的缺陷</p><p>　　設(shè)，，…，；，，…，是對應(yīng)運(yùn)輸問題的m+n個約束條件的對偶變量。從線性規(guī)劃的對偶理論可知</p><p>　　（，，…，；，，…，）</p><p>　　而每個決策變量的系數(shù)向量=+，</p><p>　　所以=+。于是檢驗(yàn)數(shù)&

29、lt;/p><p>　　由單純形法得知所有基變量的檢驗(yàn)數(shù)等于0。即 </p><p>　　例如，在由最小元素法得到基變量及對應(yīng)的檢驗(yàn)數(shù)是：</p><p>　　基變量 檢驗(yàn)數(shù)</p><p>　　?(+)=0 即: 3 ? (+)=0</p><p>　　?(+)=0 10 ? (+)=0<

30、/p><p>　　?(+)=0 1 ? (+)=0</p><p>　　?(+)=0 2 ? (+)=0</p><p>　　? (+)=0 4 ? (+)=0</p><p>　　? (+)=0 5 ? (+)=0</p><p>　　從以上6個方程中,由=0可求得：&

31、lt;/p><p>　　= ? 1, = ? 5, =2, =9, =3, =10</p><p>　　因非基變量的檢驗(yàn)數(shù)為:</p><p>　　這就可以從已知的值中求得。這些計算可在表格中進(jìn)行（參見文獻(xiàn)[5]）。</p><p><b>　　以上例說明。</b></p><p>　　第一步：按最小

32、元素法給出初始解；</p><p>　　第二步：在運(yùn)輸表上增加一行一列，在列中填入，在行中填入 ；</p><p>　　第三步：按計算所有空格的檢驗(yàn)數(shù)。如下表：</p><p>　　表中還有負(fù)檢驗(yàn)數(shù)。說明未得最優(yōu)解，還可以改進(jìn)（參見文獻(xiàn)[6]）。</p><p>　　當(dāng)在表中空格處出現(xiàn)負(fù)檢驗(yàn)數(shù)時，表明未得最優(yōu)解。若有兩個和兩個以上的負(fù)檢驗(yàn)數(shù)時

33、，一般選其中最小的負(fù)檢驗(yàn)數(shù)，以它對應(yīng)的空格為調(diào)入格。即以它對應(yīng)的非基變量為換入變量。由上表得(2，4)為調(diào)入格。以此格為出發(fā)點(diǎn)，作一閉回路，如下表所示。</p><p>　　(2，4)格的調(diào)入量θ是選擇閉回路上具有(-)的數(shù)字格中的最小者。即</p><p>　　θ=min(1,3)=1(其原理與單純形法中按θ規(guī)劃來確定換出變量相同)。然后按閉回路上的正、負(fù)號，加入和減去此值，得到調(diào)整方案

34、，如下表所示。</p><p>　　表中的所有檢驗(yàn)數(shù)都非負(fù)，故為最優(yōu)解。這時得到的總運(yùn)費(fèi)最小是85元（參見文獻(xiàn)[7]）。</p><p>　　如上所知位勢法在求非基變量的檢驗(yàn)數(shù)時，需要先求解一個含有(m+n)個對偶變量和(m+n-1)個方程的線性方程組(此處以有m個產(chǎn)地和n個銷地的平衡運(yùn)輸問題為例)，然后才能一一計算非基變量的檢驗(yàn)數(shù)以確定當(dāng)前方案是否最優(yōu)。當(dāng)產(chǎn)銷地點(diǎn)很多時，其計算量也是很大

35、的，而且特別容易出錯。若當(dāng)前方案不是最優(yōu)的，調(diào)整后的方案需要重新計算線性方程組和所有非基變量的檢驗(yàn)數(shù)(參見文獻(xiàn)[8])。</p><p>　　3.3 改進(jìn)的閉回路法的缺陷</p><p>　　這種方法在第一步對運(yùn)價矩陣進(jìn)行konig變換（指派問題的最優(yōu)解有這樣一個性質(zhì)，若從系數(shù)矩陣的一行列各元素中分別減去該行列的最小元素，得到新矩陣，那么以新矩陣為系數(shù)矩陣求得的最優(yōu)解和用原矩陣求得的最優(yōu)

36、解相同．利用這個性質(zhì)，可使原系數(shù)矩陣變換為含有很多0元素的新矩陣，而最優(yōu)解保持不變．）的“造零”過程中，采用的是先將每一行的元素只是都減去該行中的基變量對應(yīng)元素中的最大運(yùn)價，然后每列的元素減去該列中基變量對應(yīng)元素中的最小值，以致“造零”速度較慢，因而計算量比較大（參見文獻(xiàn)[9]）。</p><p>　　3.4 動態(tài)規(guī)劃法的缺陷</p><p>　　動態(tài)規(guī)劃法是一種強(qiáng)有力的算法設(shè)計技術(shù)，它

37、被廣泛用于求解組合最優(yōu)化問題。這種技術(shù)采用自底向上的方式遞推求值，將待求解的問題分解成若干個子問題，先求解子問題，并把子問題的解存儲起來以便以后用來計算所需要求的解。簡言之，動態(tài)規(guī)劃的基本思想就是把全局的問題化為局部的問題，為了全局最優(yōu)必須局部最優(yōu)。多階段決策問題是根據(jù)問題本身的特點(diǎn)，將其求解的過程劃分為若干個相互獨(dú)立又相互聯(lián)系的階段，在每一個階段都需要做出決策，并且在一個階段的決策確定以后再轉(zhuǎn)移到下一個階段，在每一階段選取其最優(yōu)決策，

38、從而實(shí)現(xiàn)整個過程總體決策最優(yōu)的目的。但是其存在狀態(tài)變量必須滿足無后效性，并且只適用一些維數(shù)相當(dāng)?shù)偷膯栴}（參見文獻(xiàn)[10]）。</p><p>　　4 一種新的檢驗(yàn)方法</p><p>　　本文探討了一種新的更好的一次性算法，這種方法是在匈牙利法（參見文獻(xiàn)[11]）和改進(jìn)的閉回路法（參見文獻(xiàn)[9]）的基礎(chǔ)上提出的一種更為簡便的運(yùn)價矩陣算法，可以一次性算出所有非基變量的檢驗(yàn)數(shù)，既避免了閉回路

39、法中對所有非基變量檢驗(yàn)數(shù)的一一計算，又回避了位勢法中需要多次求解線性方程組以計算位勢的過程。同時，在當(dāng)前方案不是最優(yōu)解時，不需重新從第一步開始計算，只需在前一次檢驗(yàn)數(shù)矩陣的基礎(chǔ)上稍加修改即可一次完成方案調(diào)整后的檢驗(yàn)數(shù)的計算。</p><p>　　由某種算法(如最小元素法)得到初始調(diào)運(yùn)方案，在運(yùn)價矩陣中將基變量對應(yīng)的元素用“()”括住。</p><p>　　第一步：對平衡運(yùn)輸問題的運(yùn)價矩陣C

40、進(jìn)行變換，使得各行各列中均出現(xiàn)零元素。</p><p>　　1)先對價格矩陣中的每一行元素施行“行加”運(yùn)算，使得處于同一列的基變量對應(yīng)的元素(被括住的元素)都變成同一個數(shù)值。一般情況下該數(shù)值是運(yùn)算前該列中基變量對應(yīng)的元素(被括住的元素)中的最大值。</p><p>　　2)再對價格矩陣中的每一列元素施行“列減”運(yùn)算，即每列減去該列中基變量對應(yīng)的元素(被括住的元素)。</p>

41、<p>　　至此，運(yùn)價矩陣C中所有的基變量對應(yīng)的元素(被括住的元素)全部轉(zhuǎn)化為零了，此時得到的矩陣，即為決策變量的檢驗(yàn)數(shù)矩陣。</p><p>　　第二步：當(dāng)檢驗(yàn)數(shù)矩陣，中所有未被括住的數(shù)字均大于0(即所有非基變量的檢驗(yàn)數(shù)<0)，則初始調(diào)運(yùn)方案為唯一最優(yōu)解；若檢驗(yàn)數(shù) ，≥0(即非基變量的檢驗(yàn)數(shù)中有等于0的)，則原問題有多重最優(yōu)解；當(dāng)存在檢驗(yàn)數(shù) <0時，則表明初始調(diào)運(yùn)方案非最優(yōu)解，轉(zhuǎn)第三步。&

42、lt;/p><p>　　第三步：在檢驗(yàn)數(shù)矩陣，中找出非基變量的檢驗(yàn)數(shù)中絕對值最大的負(fù)數(shù)，令其對應(yīng)的非基變量進(jìn)基(即在此數(shù)字上加上括號)，并找出相應(yīng)的閉回路，按閉回路法確定相應(yīng)的出基變量(即去掉此數(shù)字上的括號)與調(diào)整量，轉(zhuǎn)第一步，直至所有非基變量的檢驗(yàn)數(shù)大于或等于0。當(dāng)存在幾個檢驗(yàn)數(shù)為負(fù)數(shù)，若各檢驗(yàn)數(shù)所在的閉回路不相關(guān)時，可同時調(diào)整進(jìn)基變量和出基變量并實(shí)施計算。 </p><p><b&g

43、t;　　5 應(yīng)用舉例</b></p><p>　　某運(yùn)輸問題的運(yùn)輸價格矩陣與產(chǎn)銷平衡表見表1，求最優(yōu)調(diào)運(yùn)方案（參見文獻(xiàn)[12]-[13]）。</p><p>　　解 根據(jù)最小元素法可得初始調(diào)運(yùn)方案為（，，，，，）=（3，1，4，5，2，2），其相應(yīng)的費(fèi)用為137元。

44、

45、 </p><p>　　C= ——————

46、 ——————</p><p>　　— =</p><p>　　(公式中的———— ，————— 分別表示矩陣的第i行或第j列元素都加上數(shù)值k。)</p><p>　　因?yàn)榇嬖趦蓚€非基變量的檢驗(yàn)數(shù)為負(fù)，表明初始方案不是最優(yōu)的，需要進(jìn)行調(diào)整。取最小的負(fù)數(shù)所對應(yīng)的非基變量為進(jìn)基變量，其所在的閉回路————中的偶數(shù)頂

47、點(diǎn)中的基變量的最小值=2為調(diào)整量，且為出基變量。又因?yàn)?所在的閉回路————與所在的閉回路互不相關(guān)，故可以同時將取為進(jìn)基變量，取為出基變量，并實(shí)施計算，則有</p><p>　　=— ——— —————— </p><p>　　—— ————— =</p><

48、;p>　　經(jīng)過調(diào)整，可得新的調(diào)運(yùn)方案為（，，，，，）=（1，2，1，3，6，4），相應(yīng)的費(fèi)用為118元。為新調(diào)運(yùn)方案的檢驗(yàn)數(shù)矩陣，因而基變量的檢驗(yàn)數(shù)全部大于零，則可知此方案為最優(yōu)解。</p><p>　　6 運(yùn)輸問題在消防中的應(yīng)用</p><p>　　現(xiàn)實(shí)生活中，運(yùn)輸問題往往與實(shí)際需求緊密結(jié)合，特別是在消防救援力量部署和運(yùn)送物資方面具有重要的應(yīng)用價值。四川5.12大地震發(fā)生之后，消

49、防部門面臨的重要問題就是如何以最短的時間、最快的效益將救援物資送到災(zāi)區(qū)人民的手里，下面介紹下運(yùn)輸問題在消防救援戰(zhàn)斗中的實(shí)際應(yīng)用。</p><p>　　實(shí)例：在抗震救災(zāi)中，成都消防支隊接到命令，其所屬的三支中隊，，向四個受災(zāi)地區(qū)，，，運(yùn)送救援物資，運(yùn)輸問題如下表所示（單位：小時\噸）</p><p>　　解：用最小元素法求得初始解如下表所示</p><p>　　于是得

50、到該運(yùn)輸問題的一個初始解：=10，=6，=8，=2，=14，=8，即中隊運(yùn)10噸物資給c災(zāi)區(qū)，運(yùn)6噸物資給災(zāi)區(qū)；中隊運(yùn)8噸物資給災(zāi)區(qū)，運(yùn)2噸物資給災(zāi)區(qū)；中隊運(yùn)14噸物資給災(zāi)區(qū)，運(yùn)8噸物資給災(zāi)區(qū)。</p><p>　　總時間=10×4+6×11+8×2+2×3+14×5+8×6=246(小時)（參見文獻(xiàn)[15]）。</p><p>

51、　　用新的檢驗(yàn)方法進(jìn)行檢驗(yàn)</p><p>　　C= —————— ——————</p><p>　　— =</p><p>　　因?yàn)榇嬖趦蓚€非基變量的檢驗(yàn)數(shù)為負(fù)，表明初始方案不是最優(yōu)的，需要進(jìn)行調(diào)整。取最小的負(fù)數(shù)所對應(yīng)的非基變量為進(jìn)基變量，由于min{,}={6,2}=2，因此對解

52、作如下調(diào)整：</p><p><b>　?。杭?，：減2</b></p><p><b>　?。杭?，：減2</b></p><p>　　得到新的基可行解：=12，=4，=8，=2，=14，=8 ，即由中隊向?yàn)?zāi)區(qū)運(yùn)送12噸物資，向運(yùn)送4噸物資；中隊向和分別運(yùn)送8噸和2噸物資；中隊向和分別運(yùn)送14噸和8噸物資。</p&

53、gt;<p>　　此時，總時間=246+2（-1）=244（小時）</p><p>　　繼續(xù)使用同樣方法對新調(diào)運(yùn)方案進(jìn)行檢驗(yàn)，得到的檢驗(yàn)數(shù)矩陣的非基變量的檢驗(yàn)數(shù)全部大于零，則可知此方案為最優(yōu)解。</p><p><b>　　7 結(jié)束語</b></p><p>　　本文主要對運(yùn)輸問題的解法與應(yīng)用做了介紹，首先解釋了什么是運(yùn)輸問題，

54、并且簡單介紹了其模型。然后通過如何判別一個運(yùn)輸問題的調(diào)運(yùn)方案是否最優(yōu)，對通常采用的兩種閉回路法、位勢法等方法做綜述整理，并簡單介紹了這些方法的不足。其次本文探討了一種新的檢驗(yàn)方法，并對其進(jìn)行了應(yīng)有舉例。最后本文還闡述了運(yùn)輸問題在消防救援中的應(yīng)用。</p><p>　　從本文對運(yùn)輸問題最優(yōu)方案的檢驗(yàn)法的討論中不難看出，新的運(yùn)價矩陣法對簡化非基變量的檢驗(yàn)數(shù)計算具有重要意義。該方法不僅每次只需進(jìn)行兩次矩陣變換就可以一次

55、性算出所有非基變量的檢驗(yàn)數(shù)，而且從上述算例及與其他大量運(yùn)籌學(xué)教材中的例題對比，該方法所得結(jié)果和用閉回路法或位勢法或其他方法所介紹的方法所得的結(jié)果是完全一致的，但該方法的優(yōu)越性是顯而易見的。但是本文研究的基礎(chǔ)是產(chǎn)銷平衡問題，即中隊可供應(yīng)的物資總量等于災(zāi)區(qū)所需要的物資總量。然而在實(shí)際應(yīng)用中，涉及到的多是產(chǎn)銷不平衡問題，如供大于求和供不應(yīng)求兩類，應(yīng)當(dāng)先將非平衡問題轉(zhuǎn)化成平衡問題，再通過表上作業(yè)法來求解。在應(yīng)用表上作業(yè)法求解的過程中，要注意兩種

56、特殊情況，一是當(dāng)?shù)阶顑?yōu)解時，如果有某非基變量的檢驗(yàn)數(shù)等于零，則說明該運(yùn)輸問題有多重最優(yōu)解；二是當(dāng)運(yùn)輸問題某部分產(chǎn)地的產(chǎn)量和等于某一部分銷地的銷量和相等時，在迭代過程中有可能在某個格填入一個運(yùn)量時同時劃去一行和一列，出現(xiàn)退化（參見文獻(xiàn)[16]）。為了保證迭代，退化時應(yīng)在同時劃去的一行或一列中的某個格中填入數(shù)字0，表示這個格中的變量是取值為0 的基變量，使迭代過程中基可行解的分量恰好是（m+n-1）個。</p><p

57、><b>　　參考文獻(xiàn)</b></p><p>　　[1] 胡運(yùn)權(quán). 運(yùn)籌學(xué)(第三版)[M].北京:清華大學(xué)出版社,2007.4.</p><p>　　[2] 林同曾.運(yùn)籌學(xué)[M].北京:機(jī)械工業(yè)出版社,1986,6.　</p><p>　　[3] 云俊.運(yùn)輸問題優(yōu)化方法的綜合應(yīng)用[J].武漢理工大學(xué)學(xué)報,2

58、001,3:323-325.</p><p>　　[4] 張軍.我國物流運(yùn)輸?shù)碾[性成本及控制[J].水運(yùn)文獻(xiàn)信息,2006,2:25-26.</p><p>　　[5] Hamdy A.Taha. Operations Research An Introduction(運(yùn)籌學(xué)導(dǎo)論)[M]. 北京：人民郵電出版社,2007

59、,01.</p><p>　　[6]郭強(qiáng).一般網(wǎng)絡(luò)上的運(yùn)輸問題及其算法[M]. 西北工業(yè)大學(xué),2005,4.</p><p>　　[7]盧厚清,張永良.求解運(yùn)輸問題的一種算法[J]．運(yùn)籌與管理,1999,1:27—33．</p><p>　　[8]岳貴新．匈牙利方法在運(yùn)輸問題初始優(yōu)化解上的推廣[J]．沈陽工業(yè)學(xué)院學(xué)報,2001,3:70—74．</p

60、><p>　　[9]王建平,李玉萍.運(yùn)輸問題中最優(yōu)調(diào)運(yùn)方案的檢驗(yàn)[J]．河南科學(xué),2007,3:367—371．</p><p>　　[10]孫曉燕,李自良,彭雄鳳,傅亞力,梁志強(qiáng).利用動態(tài)規(guī)劃法求解運(yùn)輸問題的最短路徑[J]. 機(jī)械設(shè)計與制造,2010,2:223-224.</p><p>　　[11]孫嶙平.運(yùn)籌學(xué)[M].北京:科學(xué)出版社,2005:52—68．<

61、;/p><p>　　[12] 謬慧芬,邵小兵. 動態(tài)規(guī)劃算法的原理及應(yīng)用[J]. 中國科技信息,2005,21:42.</p><p>　　[13] 李敏.運(yùn)輸問題中最優(yōu)調(diào)運(yùn)方案的新檢驗(yàn)法[J]. 荊楚理工學(xué)院學(xué)報,2009,24(9):71-73.</p><p>　　[14] 李榮鈞,鄺英強(qiáng).運(yùn)籌學(xué)[M].華南理工大學(xué)出版社,2003,3.<

62、;/p><p>　　[15] 額爾登圖,運(yùn)輸問題在消防救援中的應(yīng)用[J].科技信息,2010,8:88.</p><p>　　[16] DU Ting-song, FEI Pu-sheng, JIAN Ji-gui. Relaxation-strategy-based Modification Branch-and-Bound Algorithm for Solving a Class of