運(yùn)輸問題的求解及其應(yīng)用【畢業(yè)論文+文獻(xiàn)綜述+開題報(bào)告】

1、<p><b>　?。?0_ _屆）</b></p><p><b>　　本科畢業(yè)論文</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>　　摘要：本課題主要探討了如何判別一個(gè)運(yùn)輸問題的調(diào)運(yùn)方案是最優(yōu)，對通常

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

4、nd 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;

7、Potentials 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><

8、p>　　3.2 位勢法的缺陷8</p><p>　　3.3 改進(jìn)的閉回路法的缺陷12</p><p>　　3.4 動(dòng)態(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>　　致謝錯(cuò)誤!未定義書簽。</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)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷地，已知每個(gè)產(chǎn)地的供應(yīng)量和每個(gè)銷地的需求量，如何在許多可行的調(diào)運(yùn)方案中，確定一個(gè)總運(yùn)輸費(fèi)或總運(yùn)輸量最少的方案。</p><p>　　具有上述特點(diǎn)的線性規(guī)劃問題通常被稱為運(yùn)輸型問題。

11、現(xiàn)已發(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)計(jì)劃問題，又稱日程計(jì)劃問題,簡稱CPS問題。其中一般運(yùn)輸問題、任務(wù)分配問題和生產(chǎn)計(jì)劃問題通常都可以用表上作業(yè)法求解，而網(wǎng)絡(luò)運(yùn)輸問題、最大流量問題和最短路徑問題一般可用圖上作業(yè)法或網(wǎng)絡(luò)技術(shù)求解（參見文獻(xiàn)[1]）

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

13、路法。這種方法需要對每一個(gè)空格尋找一條閉回路，并根據(jù)閉回路求出每個(gè)空格的檢驗(yàn)數(shù)。當(dāng)運(yùn)輸問題中m 和n 較大時(shí)，計(jì)算檢驗(yàn)數(shù)的工作量很大。②位勢法，或乘數(shù)法。先對初始調(diào)運(yùn)方案求出位勢，然后求各空格的檢驗(yàn)數(shù)。當(dāng)所有的檢驗(yàn)數(shù)均為非負(fù)時(shí)，就得到最優(yōu)方案。如果出現(xiàn)負(fù)的檢驗(yàn)數(shù)，則從檢驗(yàn)數(shù)為負(fù)的空格出發(fā)，作閉回路，重新計(jì)算檢驗(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)輸問題最佳方案時(shí)，都沒有考慮此因素，但裝卸搬運(yùn)費(fèi)用及時(shí)間在物流費(fèi)用中占有一定

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

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

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

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

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

22、lt;p>　　對流運(yùn)輸：在同一線路上或平行線路上作相對方向的運(yùn)送，而與對方運(yùn)程的部分發(fā)生重疊交錯(cuò)的運(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)，同時(shí)又向

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)備、裝卸時(shí)間長，且機(jī)動(dòng)靈活性不足，在過近距離中利用，發(fā)揮不了運(yùn)速快的優(yōu)勢，延長運(yùn)輸時(shí)間。</p><p>　　因此，如何判別一個(gè)運(yùn)輸問題的調(diào)運(yùn)方案是否最優(yōu)至關(guān)重要。目前，通常采用閉回路法或位勢

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

25、數(shù)都大于等于零，則已求得最優(yōu)解，否則繼續(xù)迭代找出最優(yōu)解。</p><p>　　例如在給出調(diào)運(yùn)方案的計(jì)算表上，如下表，從每一空格出發(fā)找一條閉回路。它是以某空格為起點(diǎn)。用水平或垂直線向前劃，當(dāng)碰到一數(shù)字格時(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>　　閉回路法計(jì)算檢驗(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)價(jià)，可見這調(diào)整的方案使運(yùn)費(fèi)增加： (+1)×3+(?1)×3+(+1)×2+(?1)×１=1(元)</p><p>　　當(dāng)檢驗(yàn)數(shù)還存在負(fù)數(shù)時(shí)，說明原方案不是最優(yōu)解，要繼續(xù)改進(jìn)。但是當(dāng)產(chǎn)銷地點(diǎn)很多時(shí)，僅尋找閉回路就相當(dāng)麻煩，并且在當(dāng)前方案不是最優(yōu)解時(shí)，調(diào)整的方案需要重新尋找所有非基變量的閉回路，并逐一計(jì)算

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

29、</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個(gè)方程中,由=0可求得：

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

32、小元素法給出初始解；</p><p>　　第二步：在運(yùn)輸表上增加一行一列，在列中填入，在行中填入 ；</p><p>　　第三步：按計(jì)算所有空格的檢驗(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ù)時(shí)，表明未得最優(yōu)解。若有兩個(gè)和兩個(gè)以上的負(fù)檢驗(yàn)數(shù)

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

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

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

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

38、，從而實(shí)現(xiàn)整個(gè)過程總體決策最優(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)價(jià)矩陣算法，可以一次性算出所有非基變量的檢驗(yàn)數(shù)，既避免了閉回

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

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

41、<p>　　至此，運(yùn)價(jià)矩陣C中所有的基變量對應(yīng)的元素(被括住的元素)全部轉(zhuǎn)化為零了，此時(shí)得到的矩陣，即為決策變量的檢驗(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時(shí)，則表明初始調(diào)運(yùn)方案非最優(yōu)解，轉(zhuǎn)第三步。

42、</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)存在幾個(gè)檢驗(yàn)數(shù)為負(fù)數(shù)，若各檢驗(yàn)數(shù)所在的閉回路不相關(guān)時(shí)，可同時(shí)調(diào)整進(jìn)基變量和出基變量并實(shí)施計(jì)算。 </p><p><b&

43、gt;　　5 應(yīng)用舉例</b></p><p>　　某運(yùn)輸問題的運(yùn)輸價(jià)格矩陣與產(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)榇嬖趦蓚€(gè)非基變量的檢驗(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)，故可以同時(shí)將取為進(jìn)基變量，取為出基變量，并實(shí)施計(jì)算，則有</p><p>　　=— ——— —————— </p><p>　　—— ————— =</p>&l

48、t;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)用價(jià)值。四川5.12大地震發(fā)生之后，

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

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

51、;　　用新的檢驗(yàn)方法進(jìn)行檢驗(yàn)</p><p>　　C= —————— ——————</p><p>　　— =</p><p>　　因?yàn)榇嬖趦蓚€(gè)非基變量的檢驗(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，：減2</b></p><p><b>　　：加2，：減2</b></p><p>　　得到新的基可行解：=12，=4，=8，=2，=14，=8 ，即由中隊(duì)向?yàn)?zāi)區(qū)運(yùn)送12噸物資，向運(yùn)送4噸物資；中隊(duì)向和分別運(yùn)送8噸和2噸物資；中隊(duì)向和分別運(yùn)送14噸和8噸物資。</p

53、><p>　　此時(shí)，總時(shí)間=246+2（-1）=244（小時(shí)）</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、，并且簡單介紹了其模型。然后通過如何判別一個(gè)運(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)價(jià)矩陣法對簡化非基變量的檢驗(yàn)數(shù)計(jì)算具有重要意義。該方法不僅每次只需進(jìn)行兩次矩陣變換就可以一

55、次性算出所有非基變量的檢驗(yàn)數(shù)，而且從上述算例及與其他大量運(yùn)籌學(xué)教材中的例題對比，該方法所得結(jié)果和用閉回路法或位勢法或其他方法所介紹的方法所得的結(jié)果是完全一致的，但該方法的優(yōu)越性是顯而易見的。但是本文研究的基礎(chǔ)是產(chǎn)銷平衡問題，即中隊(duì)可供應(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)解時(shí)，如果有某非基變量的檢驗(yàn)數(shù)等于零，則說明該運(yùn)輸問題有多重最優(yōu)解；二是當(dāng)運(yùn)輸問題某部分產(chǎn)地的產(chǎn)量和等于某一部分銷地的銷量和相等時(shí)，在迭代過程中有可能在某個(gè)格填入一個(gè)運(yùn)量時(shí)同時(shí)劃去一行和一列，出現(xiàn)退化（參見文獻(xiàn)[16]）。為了保證迭代，退化時(shí)應(yīng)在同時(shí)劃去的一行或一列中的某個(gè)格中填入數(shù)字0，表示這個(gè)格中的變量是取值為0 的基變量，使迭代過程中基可行解的分量恰好是（m+n-1）個(gè)。</p><

57、p><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é)報(bào),

58、2001,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]. 北京：人民郵電出版社,200

59、7,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é)報(bào),2001,3:70—74．</

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

61、t;/p><p>　　[12] 謬慧芬,邵小兵. 動(dòng)態(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é)報(bào),2009,24(9):71-73.</p><p>　　[14] 李榮鈞,鄺英強(qiáng).運(yùn)籌學(xué)[M].華南理工大學(xué)出版社,2003,3.&l

62、t;/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

63、 Transportation-production Problems[J]. Chin. Quart. J. of Math.2010, 25 (1): 52-59.</p><p><b>　　文獻(xiàn)綜述</b></p><p>　　運(yùn)輸問題的求解及其應(yīng)用 　</p><p>　　前言部分（說明寫作的目的，介紹有關(guān)概念、綜述范圍，扼

64、要說明有關(guān)主題爭論焦點(diǎn)）</p><p>　　眾所周知,現(xiàn)代交通運(yùn)輸事業(yè)的發(fā)展對人類社會(huì)的進(jìn)步與經(jīng)濟(jì)的發(fā)展是有著十分重要的意義的?？梢哉f,沒有通向資源與市場的運(yùn)輸設(shè)施、沒有科學(xué)而周密的運(yùn)輸規(guī)劃,不僅社會(huì)進(jìn)步與經(jīng)濟(jì)發(fā)展會(huì)受到嚴(yán)重制約,而且人們生活質(zhì)量的提高與消除貧困的目標(biāo)也往往難以得到真正的實(shí)現(xiàn)。當(dāng)然,不科學(xué)的運(yùn)輸規(guī)劃、運(yùn)輸方式與運(yùn)輸理念也會(huì)在加劇環(huán)境污染問題的同時(shí),造成稀缺資源的日益緊張和阻礙人們生活質(zhì)量的提高。

65、也正是有鑒于此,現(xiàn)階段積極構(gòu)建和推行運(yùn)輸問題的研究,無疑是有著極為重要的理論與實(shí)踐意義的。</p><p>　　通過文獻(xiàn)[1]我們了解到運(yùn)輸問題是一類具有特殊結(jié)構(gòu)的線性規(guī)劃問題。由于運(yùn)輸問題約束方程組的系數(shù)矩陣是完全么模的，即所有的子行列式為0或±1，存在著比單純形法更簡單的特殊解法。對于規(guī)模不太大的運(yùn)輸問題可用圖上作業(yè)法或表上作業(yè)法求解。這類問題的典型提法是，為了把某種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷地

66、，已知每個(gè)產(chǎn)地的供應(yīng)量和每個(gè)銷地的需求量，如何在許多可行的調(diào)運(yùn)方案中，確定一個(gè)總運(yùn)輸費(fèi)或總運(yùn)輸量最少的方案。</p><p>　　具有上述特點(diǎn)的線性規(guī)劃問題通常被稱為運(yùn)輸型問題?，F(xiàn)已發(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)計(jì)劃問

67、題，又稱日程計(jì)劃問題,簡稱CPS問題。其中一般運(yùn)輸問題、任務(wù)分配問題和生產(chǎn)計(jì)劃問題通常都可以用表上作業(yè)法求解，而網(wǎng)絡(luò)運(yùn)輸問題、最大流量問題和最短路徑問題一般可用圖上作業(yè)法或網(wǎng)絡(luò)技術(shù)求解。</p><p>　　文獻(xiàn)[2]中介紹運(yùn)輸問題的表上作業(yè)法求解。初始基本可行解的求法有三種：①左上角法。它的基本思想是給運(yùn)輸表中左上角的變量分配運(yùn)輸量以確定產(chǎn)銷關(guān)系。②最小元素法，或最小成本法。它的基本思想是就近供應(yīng)，即從運(yùn)輸表中

68、運(yùn)價(jià)最小的格子開始分配運(yùn)輸量以確定產(chǎn)銷關(guān)系。③元素差額法,又稱沃格爾近似法，簡稱VAM法。它是從運(yùn)輸表中各行和各列的最小元素和次小元素的差額來確定產(chǎn)銷關(guān)系。改進(jìn)初始基本可行解的方法有兩種：①閉回路法。這種方法需要對每一個(gè)空格尋找一條閉回路，并根據(jù)閉回路求出每個(gè)空格的檢驗(yàn)數(shù)。當(dāng)運(yùn)輸問題中m 和n 較大時(shí)，計(jì)算檢驗(yàn)數(shù)的工作量很大。②位勢法，或乘數(shù)法。先對初始調(diào)運(yùn)方案求出位勢，然后求各空格的檢驗(yàn)數(shù)。當(dāng)所有的檢驗(yàn)數(shù)均為非負(fù)時(shí)，就得到最優(yōu)方案。如

69、果出現(xiàn)負(fù)的檢驗(yàn)數(shù)，則從檢驗(yàn)數(shù)為負(fù)的空格出發(fā)，作閉回路，重新計(jì)算檢驗(yàn)數(shù)，作進(jìn)一步調(diào)整。用位勢法求檢驗(yàn)數(shù)就是對偶問題的表上作業(yè)法。</p><p>　　但是通過文獻(xiàn)[3]我們發(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>　?。?/p>

70、1）對運(yùn)輸問題中的中轉(zhuǎn)再分撥，其中轉(zhuǎn)的裝卸搬運(yùn)費(fèi)用，無論是求最小費(fèi)用最大流的優(yōu)化方法還是表上作業(yè)法求具有中轉(zhuǎn)站的運(yùn)輸問題最佳方案時(shí)，都沒有考慮此因素，但裝卸搬運(yùn)費(fèi)用及時(shí)間在物流費(fèi)用中占有一定的比重。</p><p>　　（2）多種運(yùn)輸方式的聯(lián)合運(yùn)輸問題，當(dāng)物資通過運(yùn)輸網(wǎng)絡(luò)從出發(fā)地運(yùn)往目的地時(shí)，由于各線路的不同特點(diǎn)，可能需要采用不同的運(yùn)輸方式，不同的運(yùn)輸方式所產(chǎn)生的費(fèi)用是不同的，但上述的優(yōu)化方法沒有考慮此因素。雖然

71、，人們對多式聯(lián)運(yùn)的優(yōu)化方法也進(jìn)行了一定的研究，但其方法也是有某些前提條件。</p><p>　?。?）對于物流系統(tǒng)中的配送問題，由于實(shí)際的配送問題，其配送方式有多種，按照物流據(jù)點(diǎn)的不同，可分為配送中心配送、倉庫配送、就站配送、就港配送、就廠配送等；按照配送貨物的品種和數(shù)量，可分為單一品種大批量配送、多品種小批量配送、配套成套配送等；按照配送時(shí)間和數(shù)量，可分為定時(shí)配送、定量配送、定時(shí)定量配送、不定時(shí)（及時(shí)）配送等；

72、按照配送時(shí)間和路線，可分為定時(shí)定路線配送、不定時(shí)定路線配送、定路線巡回配送等；按照配送用戶的范圍，可分為企業(yè)配送、行業(yè)配送、地區(qū)配送、城市配送等；按照配送經(jīng)營形式的不同，可分為銷售配送、供應(yīng)配送、銷售—供應(yīng)一體化配送、代理配送等；按照企業(yè)之間的關(guān)系，可分為共同配送、集團(tuán)配送、單獨(dú)配送等。尋找能綜合解決滿足所有條件的最佳配送方案的方法正是人們所期望的。</p><p>　?。?）對于新的運(yùn)輸網(wǎng)絡(luò)，只知道從各產(chǎn)地運(yùn)往

73、各銷地及可經(jīng)過的線路，這進(jìn)修求最佳方案，需要求多個(gè)指標(biāo)的最優(yōu)方案。如各地之間的單位物資的費(fèi)用（即單位運(yùn)價(jià)）、最大流量、最優(yōu)路線等。</p><p>　　因此對于復(fù)雜的運(yùn)輸問題的優(yōu)化，要根據(jù)具體情況，綜合應(yīng)用各種優(yōu)化技術(shù)求其最優(yōu)的調(diào)運(yùn)方案。</p><p>　　主題部分（闡明有關(guān)主題的歷史背景、現(xiàn)狀和發(fā)展方向，以及對這些問題的評述）</p><p>　　近兩年，物流已

74、成為當(dāng)今中國經(jīng)濟(jì)最熱門名詞之一。通過文獻(xiàn)[4]我們了解到運(yùn)輸在整個(gè)物流中占有很重要的地位，總成本占物流總成本的35％-50％左右，占商品價(jià)格的4％-10％。運(yùn)輸對物流總成本的節(jié)約具有舉足輕重的作用。會(huì)計(jì)學(xué)上將物流成本分為顯性成本和隱性成本。</p><p>　　在我國現(xiàn)行的物流運(yùn)輸方式中無論是自營物流，合營物流還是第三方物流，隱性成本占據(jù)了很重要的地位，這些隱性成本在物流運(yùn)輸過程中主要包括以下幾個(gè)方面：返程或起程

75、空駛：空車無貨載行駛，是不合理運(yùn)輸?shù)淖顕?yán)重形式。在實(shí)際運(yùn)輸組織中，必須調(diào)運(yùn)空車。但是，因調(diào)運(yùn)不當(dāng)貨源計(jì)劃不周，形成的空駛，是不合理運(yùn)輸?shù)谋憩F(xiàn)。造成空駛的不合理運(yùn)輸主要有以下幾種原因：依靠自備車送貨提貨，單程空駛的不合理運(yùn)輸。由于工作失誤或計(jì)劃不周，造成貨源不實(shí)，由于車輛過分專用，無法搭運(yùn)回程貨物。</p><p>　　對流運(yùn)輸：在同一線路上或平行線路上作相對方向的運(yùn)送，而與對方運(yùn)程的部分發(fā)生重疊交錯(cuò)的運(yùn)輸稱對流運(yùn)

76、輸。 </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)，同時(shí)又向外運(yùn)出。過遠(yuǎn)運(yùn)輸：是指調(diào)運(yùn)物資舍近求遠(yuǎn)，近處有資源不調(diào)而從遠(yuǎn)處調(diào)，這就造成可采取近程運(yùn)輸而未采取，拉長了貨物運(yùn)距的浪

77、費(fèi)現(xiàn)象。 </p><p>　　運(yùn)力選擇不當(dāng)：在于火車及大型船舶起運(yùn)及到達(dá)目的地的準(zhǔn)備、裝卸時(shí)間長，且機(jī)動(dòng)靈活性不足，在過近距離中利用，發(fā)揮不了運(yùn)速快的優(yōu)勢，延長運(yùn)輸時(shí)間。</p><p>　　因此，如何判別一個(gè)運(yùn)輸問題的調(diào)運(yùn)方案是否最優(yōu)至關(guān)重要。文獻(xiàn)[5]介紹到目前，通常采用閉回路法或位勢法來判別，但這兩種方法的計(jì)算量都非常大，而且都有其局限性。</p><p>

78、　　通過文獻(xiàn)[6-8]我們了解到閉回路法在求非基變量的檢驗(yàn)數(shù)時(shí)，需要先給每一個(gè)非基變量找到一個(gè)閉回路，然后再一一計(jì)算檢驗(yàn)數(shù)。當(dāng)產(chǎn)銷地點(diǎn)很多時(shí)，僅尋找閉回路就相當(dāng)麻煩，并且在當(dāng)前方案不是最優(yōu)解時(shí)，調(diào)整后的方案需要重新尋找所有非基變量的閉回路，并逐一計(jì)算新的檢驗(yàn)數(shù)，顯然計(jì)算量很大。</p><p>　　位勢法在求非基變量的檢驗(yàn)數(shù)時(shí)，需要先求解一個(gè)含有(m+n)個(gè)對偶變量和(m+n-1)個(gè)方程的線性方程組(此處以有m個(gè)

79、產(chǎn)地和n個(gè)銷地的平衡運(yùn)輸問題為例)，然后才能一一計(jì)算非基變量的檢驗(yàn)數(shù)以確定當(dāng)前方案是否最優(yōu)。當(dāng)產(chǎn)銷地點(diǎn)很多時(shí)，其計(jì)算量也是很大的，而且特別容易出錯(cuò)。若當(dāng)前方案不是最優(yōu)的，調(diào)整后的方案需要重新計(jì)算線性方程組和所有非基變量的檢驗(yàn)數(shù)。</p><p>　　其次本文還介紹了其他幾種常用的運(yùn)輸問題的判別法，但他們都有其局限性。</p><p>　　文獻(xiàn)[9]中矩陣法在第一步對運(yùn)價(jià)矩陣進(jìn)行konig變

80、換（指派問題的最優(yōu)解有這樣一個(gè)性質(zhì)，若從系數(shù)矩陣的一行列各元素中分別減去該行列的最小元素，得到新矩陣，那么以新矩陣為系數(shù)矩陣求得的最優(yōu)解和用原矩陣求得的最優(yōu)解相同．利用這個(gè)性質(zhì)，可使原系數(shù)矩陣變換為含有很多0元素的新矩陣，而最優(yōu)解保持不變．）的“造零”過程中，采用的是先將每一行的元素只是都減去該行中的基變量對應(yīng)元素中的最大運(yùn)價(jià)，然后每列的元素減去該列中基變量對應(yīng)元素中的最小值，以致“造零”速度較慢，因而計(jì)算量比較大。</p>

81、<p>　　文獻(xiàn)[10]中運(yùn)價(jià)矩陣法的缺陷主要在于為了判別調(diào)整后的方案是否達(dá)到最優(yōu)，需要對原始運(yùn)價(jià)矩陣重新進(jìn)行計(jì)算，導(dǎo)致計(jì)算量偏大。</p><p>　　文獻(xiàn)[11-12]中動(dòng)態(tài)規(guī)劃法中存在狀態(tài)變量必須滿足無后效性，并且只適用一些維數(shù)相當(dāng)?shù)偷膯栴}。</p><p>　　在文獻(xiàn)[13]受到文獻(xiàn)[8-12]的啟發(fā)，提出了一種新的更好的一次性算法，本文最這種方法進(jìn)行了探討，這種方法

82、可以一次性算出所有非基變量的檢驗(yàn)數(shù)，既避免了閉回路法中對所有非基變量檢驗(yàn)數(shù)的一一計(jì)算，又回避了位勢法中需要多次求解線性方程組以計(jì)算位勢的過程。同時(shí)，在當(dāng)前方案不是最優(yōu)解時(shí)，不需重新從第一步開始計(jì)算，只需在前一次檢驗(yàn)數(shù)矩陣的基礎(chǔ)上稍加修改即可一次完成方案調(diào)整后的檢驗(yàn)數(shù)的計(jì)算。</p><p>　　最后在文獻(xiàn)[14-15]中還介紹了運(yùn)輸問題在消防救援中的應(yīng)用，發(fā)現(xiàn)在實(shí)際應(yīng)用中，由于產(chǎn)銷不平衡，如供大于求和供不應(yīng)求兩類

83、，還有物資裝卸費(fèi)用等問題，都會(huì)使運(yùn)輸問題的求解出現(xiàn)誤差。</p><p>　　三．總結(jié)部分（將全文主題進(jìn)行扼要總結(jié)，提出自己的見解并對進(jìn)一步的發(fā)展方向做出預(yù)測）</p><p>　　本課題主要介紹了運(yùn)輸問題的求解及其應(yīng)用。</p><p>　　首先介紹了國內(nèi)的運(yùn)輸現(xiàn)狀，了解到我國目前還處于傳統(tǒng)的運(yùn)輸行業(yè)，要完成向現(xiàn)代運(yùn)輸行業(yè)的轉(zhuǎn)變需要解決一系列問題，而運(yùn)輸調(diào)運(yùn)方案的

84、不合理是傳統(tǒng)運(yùn)輸行業(yè)最大的弊病，也是造成運(yùn)輸成本浪費(fèi)的主要原因。</p><p>　　然后通過如何判別一個(gè)運(yùn)輸問題的調(diào)運(yùn)方案是否最優(yōu)，對通常采用的兩種閉回路法或位勢法做綜述整理,同時(shí)可以探討更好的一次性算法,既避免了閉回路法中對所有非基變量檢驗(yàn)數(shù)的一一計(jì)算,又回避了位勢法中需要多次求解線性方程組以計(jì)算位勢的過程。</p><p>　　通過對本課題的研究，我發(fā)現(xiàn)在實(shí)際運(yùn)輸問題中很難將運(yùn)輸過程

85、中所發(fā)生的費(fèi)用都考慮進(jìn)去，例如對運(yùn)輸問題中的中轉(zhuǎn)再分撥，其中轉(zhuǎn)的裝卸搬運(yùn)費(fèi)用。在以后我們可能會(huì)發(fā)現(xiàn)更有效更簡潔的方法。</p><p>　　參考文獻(xiàn)（根據(jù)文中參閱和引用的先后次序按序編排）</p><p>　　[1] 胡運(yùn)權(quán). 運(yùn)籌學(xué)(第三版)[M].北京:清華大學(xué)出版社,2007.4.</p><p>　　[2] 林同曾.運(yùn)籌學(xué)[M]

86、.北京:機(jī)械工業(yè)出版社,1986,6.　</p><p>　　[3] 云俊.運(yùn)輸問題優(yōu)化方法的綜合應(yīng)用[J].武漢理工大學(xué)學(xué)報(bào),2001,3:323-325.</p><p>　　[4] 張軍.我國物流運(yùn)輸?shù)碾[性成本及控制[J].水運(yùn)文獻(xiàn)信息,2006,2:25-26.</p><p>　　[5] Hamdy A.Taha. Opera

87、tions Research An Introduction(運(yùn)籌學(xué)導(dǎo)論)[M]. 北京：人民郵電出版社,2007,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．<

88、/p><p>　　[8]岳貴新．匈牙利方法在運(yùn)輸問題初始優(yōu)化解上的推廣[J]．沈陽工業(yè)學(xué)院學(xué)報(bào),2001,3:</p><p><b>　　70—74．</b></p><p>　　[9]王建平,李玉萍.運(yùn)輸問題中最優(yōu)調(diào)運(yùn)方案的檢驗(yàn)[J]．河南科學(xué),2007,3:367—371．</p><p>　　[10]孫嶙平.運(yùn)籌學(xué)[

89、M].北京:科學(xué)出版社,2005:52—68．</p><p>　　[11]孫曉燕,李自良,彭雄鳳,傅亞力,梁志強(qiáng).利用動(dòng)態(tài)規(guī)劃法求解運(yùn)輸問題的最短路徑[J]. 機(jī)械設(shè)計(jì)與制造,2010,2:223-224.</p><p>　　[12] 謬慧芬,邵小兵. 動(dòng)態(tài)規(guī)劃算法的原理及應(yīng)用［J］. 中國科技信息,2005,21:42.</p><p>　　[13] 

90、;李敏.運(yùn)輸問題中最優(yōu)調(diào)運(yùn)方案的新檢驗(yàn)法[J]. 荊楚理工學(xué)院學(xué)報(bào),2009,24(9):71-73. </p><p>　　[14] 李榮鈞,鄺英強(qiáng).運(yùn)籌學(xué)［M］.華南理工大學(xué)出版社,2003,3.</p><p>　　[15] 額爾登圖,運(yùn)輸問題在消防救援中的應(yīng)用[J].科技信息,2010,8:88.</p><p><b>　　開

91、題報(bào)告</b></p><p>　　運(yùn)輸問題的求解及其應(yīng)用</p><p>　　選題的背景、意義（所選課題的歷史背景、國內(nèi)外研究現(xiàn)狀和發(fā)展趨勢）</p><p>　　作為一個(gè)發(fā)展中國家，交通運(yùn)輸對我國經(jīng)濟(jì)、社會(huì)發(fā)展起著顯著的前導(dǎo)性作用。工農(nóng)業(yè)生產(chǎn)、人民生活以及國防建設(shè)的諸多方面都和交通運(yùn)輸業(yè)的發(fā)展有著緊密的關(guān)系。尤其在中國加入WTO以后，迅猛的經(jīng)濟(jì)發(fā)展讓

92、交通運(yùn)輸?shù)膲毫θ找婕哟螅煌ㄟ\(yùn)輸問題也越來越多的出現(xiàn)，對于運(yùn)輸問題的研究也越來越被重視。</p><p>　　由于經(jīng)濟(jì)的發(fā)展等原因，國外對于運(yùn)輸問題的研究已經(jīng)非常的深入，詳見文獻(xiàn)[2-4]。</p><p>　　1995年Saad N Aljarad和William R Black 用非集計(jì)模型分析沙特拉伯一巴林運(yùn)輸通道內(nèi)城間非工作出行的(non-business travel)運(yùn)輸方式選

93、擇。提出了兩個(gè)獨(dú)立的模型，即二項(xiàng)Logit模型和多項(xiàng)Logit模型。前者用于利雅得一巴林通道內(nèi)的運(yùn)輸方式選擇，后者用于沙特拉伯東部省份(達(dá)蘭、達(dá)曼、胡富夫等省)一巴林通道內(nèi)的運(yùn)輸方式選擇。同年，Chandra R. Bhat[3]對加拿大(Canada)的多倫多一蒙特利爾運(yùn)輸通道內(nèi)工作日的工作出行(weekday, business travel)進(jìn)行了研究，并且將用于計(jì)算出行者對運(yùn)輸方式(train, car, plan)選擇的式Lo

94、git模型(NL)進(jìn)行了改進(jìn)，提出協(xié)方差巢式Logit模型(COVNL). 1996年Hensher DAE4I提出采用異方差極值Logit模型(HEVL)對澳大利亞(Australia)的悉尼一堪培拉(Sydney-Canberra)通道內(nèi)的四種運(yùn)輸方式(car, plane, scheduled coach, nonscheduledcoach)所占的市場份額進(jìn)行了預(yù)測。但</p><p>　　1997年Hs

95、u C-I和Chung W-M提出在鐵路運(yùn)輸通道內(nèi)乘客如何選擇High speed rail(HSR), Conventional rail(CR)的分析模型。按照可達(dá)性(accessibility)將乘客分類，分別給出每種類型的乘客對運(yùn)輸方式選擇的計(jì)算模型。根據(jù)乘客的出行時(shí)間、時(shí)間價(jià)值、出行距離、票價(jià)以及HSR和CR的服務(wù)特點(diǎn)建立運(yùn)輸方式選擇模型。該模型的合理性在于將費(fèi)用轉(zhuǎn)化成時(shí)間，并給出了時(shí)間價(jià)值的計(jì)算公式。這樣做要比只以車內(nèi)時(shí)間和

96、車外時(shí)間為基礎(chǔ)利用多項(xiàng)Logit模型(MNL)或巢式Logit模型(NL)計(jì)算市場份額要合理，但是該方法在費(fèi)用和時(shí)間換算的過程中誤差很大。</p><p>　　2001年11，joon Chang博士在其博士論文中將Wardrop原理應(yīng)用到預(yù)測區(qū)域運(yùn)輸通道內(nèi)各運(yùn)輸方式所占的市場份額中，并針對韓國(Korea)京釜(Seoul-Busan)通道內(nèi)的四種運(yùn)輸方式(Air, High-speed rail , Conv

97、entional rail ,Highway)分別從用戶最優(yōu)和系統(tǒng)最優(yōu)的角度對其所占市場份額做了預(yù)測。并對傳統(tǒng)廣義出行費(fèi)用的求解做了改進(jìn)，這一點(diǎn)主要體現(xiàn)在對時(shí)間價(jià)值的確定問題上，對時(shí)間價(jià)值的求解摒棄了傳統(tǒng)方法，采用Wardrop原理并結(jié)合Dail的幾準(zhǔn)則來求解時(shí)間價(jià)值，得出了各種運(yùn)輸方式旅客時(shí)間價(jià)值的概率密度函數(shù)，使時(shí)間價(jià)值不再是常量，然后再利用Wardrop原理預(yù)測通道內(nèi)各運(yùn)輸方式的客運(yùn)量分擔(dān)率，但是在應(yīng)用該模型進(jìn)行遠(yuǎn)期預(yù)測時(shí)，體現(xiàn)不

98、出經(jīng)濟(jì)的發(fā)展和人們對價(jià)值觀念認(rèn)識的改變對時(shí)間價(jià)值函數(shù)的影響，進(jìn)而就影響了應(yīng)用該模型的可靠性。此外，在論文中采用的是理想交通條件下的Wardrop原理，體現(xiàn)不出不確定因素對客運(yùn)量分配的影響。</p><p>　　國外主要以運(yùn)輸問題求解算法為研究主體，以表上作業(yè)法、最短路法、最小費(fèi)用最大流以及智能算法等為代表；而國內(nèi)從算法、目標(biāo)函數(shù)、約束函數(shù)這三個(gè)角度進(jìn)行分類綜述。</p><p>　　但是都

99、存在由各種因素而導(dǎo)致的誤差。</p><p>　　隨著經(jīng)濟(jì)的發(fā)展需求，相信各國對運(yùn)輸問題的研究會(huì)更加深入，會(huì)有更加有效可行的方法被發(fā)現(xiàn)。</p><p>　　相關(guān)研究的最新成果及動(dòng)態(tài)</p><p>　　運(yùn)輸問題是一類具有特殊結(jié)構(gòu)的線性規(guī)劃問題。通過文獻(xiàn)[5]我們知道由于運(yùn)輸問題約束方程組的系數(shù)矩陣是完全么模的，即所有的子行列式為0或±1，存在著比單純形法

100、更簡單的特殊解法。對于規(guī)模不太大的運(yùn)輸問題可用圖上作業(yè)法或表上作業(yè)法求解。這類問題的典型提法是，為了把某種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷地，已知每個(gè)產(chǎn)地的供應(yīng)量和每個(gè)銷地的需求量，如何在許多可行的調(diào)運(yùn)方案中，確定一個(gè)總運(yùn)輸費(fèi)或總運(yùn)輸量最少的方案。</p><p>　　文獻(xiàn)[6-7]告訴我們運(yùn)輸問題可用表上作業(yè)法求解。初始基本可行解的求法有三種：①左上角法。它的基本思想是給運(yùn)輸表中左上角的變量分配運(yùn)輸量以確定產(chǎn)銷關(guān)

101、系。②小元素法，或最小成本法。它的基本思想是就近供應(yīng)，即從運(yùn)輸表中運(yùn)價(jià)最小的格子開始分配運(yùn)輸量以確定產(chǎn)銷關(guān)系。③元素差額法,又稱沃格爾近似法，簡稱VAM法。它是從運(yùn)輸表中各行和各列的最小元素和次小元素的差額來確定產(chǎn)銷關(guān)系。改進(jìn)初始基本可行解的方法有兩種：①閉回路法。這種方法需要對每一個(gè)空格尋找一條閉回路，并根據(jù)閉回路求出每個(gè)空格的檢驗(yàn)數(shù)。當(dāng)運(yùn)輸問題中m 和n 較大時(shí)，計(jì)算檢驗(yàn)數(shù)的工作量很大。②位勢法，或乘數(shù)法。先對初始調(diào)運(yùn)方案求出位勢，

102、然后求各空格的檢驗(yàn)數(shù)。當(dāng)所有的檢驗(yàn)數(shù)均為非負(fù)時(shí)，就得到最優(yōu)方案。如果出現(xiàn)負(fù)的檢驗(yàn)數(shù)，則從檢驗(yàn)數(shù)為負(fù)的空格出發(fā)，作閉回路，重新計(jì)算檢驗(yàn)數(shù)，作進(jìn)一步調(diào)整。用位勢法求檢驗(yàn)數(shù)就是對偶問題的表上作業(yè)法。</p><p>　　對于實(shí)際的運(yùn)輸問題，上述優(yōu)化方法很難將運(yùn)輸過程中所發(fā)生的費(fèi)用都考慮進(jìn)去，因此，如果教條地采用上述優(yōu)化方法直接進(jìn)行優(yōu)化，則很難保證此方案是真正的最佳方案。要根據(jù)具體情況，綜合應(yīng)用各種優(yōu)化技術(shù)求其最優(yōu)的調(diào)運(yùn)

103、方案。</p><p>　　課題的研究內(nèi)容及擬采取的研究方法（技術(shù)路線）、難點(diǎn)及預(yù)期達(dá)到的目標(biāo)</p><p>　?。?）研究內(nèi)容及研究方法</p><p>　　本課題主要探討了如何判別一個(gè)運(yùn)輸問題的調(diào)運(yùn)方案是最優(yōu)，對通常采用的兩種閉回路法或位勢法做綜述整理詳見文獻(xiàn)[8-9]，同時(shí)探討更好的一次性算法詳見文獻(xiàn)[10]，既避免了閉回路法中對所有非基變量檢驗(yàn)數(shù)的一一計(jì)算

104、,又回避了位勢法中需要多次求解線性方程組以計(jì)算位勢的過程。本課題的目標(biāo)就是利用已有或已得到的算法對實(shí)際問題進(jìn)行分析研究。</p><p><b>　?。?）研究難點(diǎn)</b></p><p>　　閉回路法、位勢法等方法計(jì)算量大，有缺陷，主要在于為了判別調(diào)整后的方案是否達(dá)到最優(yōu),需要對原始運(yùn)價(jià)矩陣重新進(jìn)行計(jì)算,導(dǎo)致計(jì)算量偏大。</p><p>　　

105、（3）預(yù)期達(dá)到的目標(biāo)</p><p>　　通過對本課題的研究,預(yù)期達(dá)到的目的如下：第一，熟悉高等代數(shù)及運(yùn)籌學(xué)的知識及其相關(guān)概念、性質(zhì)；第二，具有分析問題，解決問題的基本能力；第三， 會(huì)用相關(guān)的數(shù)學(xué)知識解決實(shí)際問題并對問題進(jìn)行求解；</p><p>　　論文詳細(xì)工作進(jìn)度和安排</p><p>　　第七學(xué)期第9周至第10周：確定論文題目；開始查閱文獻(xiàn)資料，收集

106、各種紙質(zhì)、電子文件信息、材料并對其進(jìn)行加工整理，形成系統(tǒng)材料；確定外文翻譯資料； </p><p>　　第七學(xué)期第11周至第12周：收集資料，閱讀相關(guān)文獻(xiàn)，分析資料，完成外文翻譯；對運(yùn)輸問題的背景和意義形成系統(tǒng)材料，并對運(yùn)輸問題的算法作系統(tǒng)整理完成外文翻譯；</p><p>　　第七學(xué)期第13周至第17周：認(rèn)真閱讀文獻(xiàn)資料，加以歸納總結(jié)，完成文獻(xiàn)綜述，深入分析運(yùn)輸問題的算法及其缺陷，建立研

107、究和解決問題的基本方案和技術(shù)路線，撰寫開題報(bào)告；</p><p>　　第七學(xué)期第18周：完成網(wǎng)上確認(rèn)；上傳外文翻譯，文獻(xiàn)綜述、開題報(bào)告. </p><p>　　第八學(xué)期第1周至第3周：全面開展課題研究，按照研究方案和路線撰寫論文，對運(yùn)輸問題的算法加以改進(jìn)并具體分析，并完成論文初稿； </p><p>　　第八學(xué)期第4周至第10周：進(jìn)入實(shí)習(xí)單位進(jìn)行畢業(yè)實(shí)習(xí)，