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

1、<p><b>　　本科畢業(yè)論文</b></p><p><b>　　（20 屆）</b></p><p>　　運輸問題的求解及其應(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>　　摘要：本課題主要探討了如何判別一個運輸問題的調(diào)運方案是最優(yōu)，對通常采

3、用的兩種閉回路法或位勢法做綜述整理，同時探討更好的一次性算法，既避免了閉回路法中對所有非基變量檢驗數(shù)的一一計算,又回避了位勢法中需要多次求解線性方程組以計算位勢的過程。本課題主要利用了已有或已得到的算法對實際問題進行分析研究。</p><p>　　關(guā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 運輸問題簡介1</p><p>　　2 運輸問題模型2</p><p>　　3 幾種常用檢驗法的缺陷3</p><p>　　3.1 閉回路法的缺陷4</p><p

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29、lt;/p><p>　　由單純形法得知所有基變量的檢驗數(shù)等于0。即 </p><p>　　例如，在由最小元素法得到基變量及對應(yīng)的檢驗數(shù)是：</p><p>　　基變量 檢驗數(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>　　因非基變量的檢驗數(shù)為:</p><p>　　這就可以從已知的值中求得。這些計算可在表格中進行（參見文獻[5]）。</p><p><b>　　以上例說明。</b></p><p>　　第一步：按最小

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

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

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

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

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

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

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

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

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

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

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

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

44、

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

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

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

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

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

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

51、　　用新的檢驗方法進行檢驗</p><p>　　C= —————— ——————</p><p>　　— =</p><p>　　因為存在兩個非基變量的檢驗數(shù)為負(fù)，表明初始方案不是最優(yōu)的，需要進行調(diào)整。取最小的負(fù)數(shù)所對應(yīng)的非基變量為進基變量，由于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 ，即由中隊向災(zāi)區(qū)運送12噸物資，向運送4噸物資；中隊向和分別運送8噸和2噸物資；中隊向和分別運送14噸和8噸物資。</p&

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

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

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

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

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

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

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

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

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

62、;/p><p>　　[15] 額爾登圖,運輸問題在消防救援中的應(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