沈陽理工大學(xué)物流系統(tǒng)規(guī)劃設(shè)計課程設(shè)計運輸問題模型和求解方法的研究

1、 .摘 要運輸問題是運籌學(xué)的一個分支，是線性規(guī)劃的特殊形式。它研究的是如何在物資調(diào)運中，制定出一個由若干個產(chǎn)地將物資根據(jù)已知的運輸交通網(wǎng)運到各個銷售地的方案，使得總運費最小。運輸是整個物流活動中的核心，運輸管理是物流活動統(tǒng)籌規(guī)劃和管理的重要部分，對運輸環(huán)節(jié)進行規(guī)劃和優(yōu)化，對提高物流活動的效率有著重要意義。物流被稱為“第三利潤源泉”，而運輸成本又在整個物流成本中占得比例最大。合理的設(shè)計運輸方案，可以降低企業(yè)的物流成本，也就意味著增加了企業(yè)的利潤。本文通過對運輸問題模型和求解方法的研究，在產(chǎn)銷平衡的條件下，運用不同的方法：表上作業(yè)法、Vogel法和Excel軟件對運輸問題進行求解。運用表上作業(yè)法或

2、Vogel法的基本思路是：初始方案的確定最優(yōu)解的檢驗調(diào)運方案的調(diào)整。其求解步驟相對較為繁瑣，所以又介紹了Excel軟件的求解方法，該方法相對簡單，而且準確快速，但是轉(zhuǎn)換建模相對困難。總之，各種方法都有其優(yōu)點和缺點，在解決實際問題中，我們可以根據(jù)實際情況選擇一種或幾種方法進行求解。關(guān)鍵詞：線性規(guī)劃；運輸問題；表上作業(yè)法；Excel；Vogel法目 錄1 前言11.1 作業(yè)背景11.2 選題說明11.2.1 基本思路11.2.2 作業(yè)目標21.3 工作業(yè)績21.3.1 個人主要工作21.3.2 主要收獲21.3.3 自我評定31.3.4 小組成員任務(wù)分工情況32 物流運輸概述42.1 物流與運輸4

3、2.2.1 物流運輸?shù)母拍?2.2.2 運輸在物流中的地位42.2 運輸合理化42.2.1 不合理運輸42.2.2 影響運輸合理化的因素53 線性規(guī)劃與運輸問題63.1 線性規(guī)劃63.2 運輸問題74 運輸問題的求解方法104.1 單純形法104.2 表上作業(yè)法104.2.1 初始方案的確定114.2.2 最優(yōu)解的檢驗144.2.3 調(diào)運方案的改進154.3 Excel規(guī)劃求解方法165 某物流企業(yè)煤炭運輸項目方案求解20結(jié)束語22參考文獻2320 / 231 前言1.1 作業(yè)背景本文根據(jù)物流系統(tǒng)規(guī)劃與設(shè)計課程要求而做。課程作業(yè)要求如下：根據(jù)物流方案策劃與設(shè)計原理，根據(jù)所學(xué)的專業(yè)知識對一個具體

4、的物流項目進行規(guī)劃與設(shè)計。1.根據(jù)課程實踐時間選擇適當規(guī)模大小的設(shè)計課題。針對物流管理的具體特點，體現(xiàn)項目管理的思想，可由指導(dǎo)教師對學(xué)生進行分組（每組3-6人），一組一題，分工合作，共同完成（也可以選定某一物流項目或方案，獨立完成）。2.根據(jù)合理的進度安排，按照所學(xué)原理與實際案例，踏實地開展課程實踐活動。3.課程實踐過程中，根據(jù)選題的具體需求，在開發(fā)各環(huán)節(jié)中撰寫相關(guān)的技術(shù)文檔，最后要求提交詳細的課程實踐報告。4.重點放在方案的可行性與操作性上，容要有邏輯性，測算要準確。5.提供的方案要具有專業(yè)性，并經(jīng)教師和專家的檢查。1.2 選題說明運輸問題是線性規(guī)劃的一種特殊形式，運輸問題主要是解決這樣的問

5、題：在物資進行調(diào)運時，有若干個產(chǎn)地，根據(jù)已知的交通運輸網(wǎng)，如何制定一個運輸方案，將這些物資運到各個銷售地，使得總運費最小。物流管理的本質(zhì)要求就是效，以最少的成本，實現(xiàn)最優(yōu)的服務(wù)，達到最佳的經(jīng)濟效益。物流被稱為“第三利潤源泉”，而運輸成本又在整個物流成本中占得比例最大。搞好物流管理，可以通過設(shè)計合理的運輸方案，使中間裝卸搬運、儲存費用降低、損失減少，在其他條件不變的情況下，降低物流成本，也就意味著擴大了企業(yè)的利潤空間，所以一個合理的、有效的運輸方案有著重要的意義。1.2.1 基本思路首先分析運輸與物流的關(guān)系與運輸在物流活動中的重要地位，引出為什么要研究運輸問題。然后探討運籌學(xué)中線性規(guī)劃方法在物流

6、運輸問題的中應(yīng)用，主要方法是基于單純形法的表上作業(yè)法和Vogel法，這兩種方法是單純形法的簡化方法，能夠幫助我們以圖表的形式快速求解出最優(yōu)的運輸方案，另外本文中還介紹了使用Excel求解線性規(guī)劃，它能幫助我們減少計算量，從而更加快速、準確的得到最優(yōu)解。最后根據(jù)上面介紹的方法對實際問題中的運輸案例進行算例演示，主要是建立模型，把不平衡問題轉(zhuǎn)化為產(chǎn)銷平衡的問題后運用表上作業(yè)法進行求解。1.2.2 作業(yè)目標通過對運籌學(xué)中線性規(guī)劃方法對物流運輸問題的應(yīng)用，熟練掌握表上作業(yè)法和Vogel法的計算方法、對給定方案最優(yōu)性的檢驗，以與對不是最優(yōu)方案進行優(yōu)化；并學(xué)會運用Excel工具建立模型進行線性規(guī)劃的求解。

7、能夠?qū)嶋H情況中各種不同的產(chǎn)銷不平衡問題進行建模，轉(zhuǎn)化為平衡的問題從而進行求解。1.3 工作業(yè)績1.3.1 個人主要工作本次課程設(shè)計是由我獨立完成的，主要進行了對運輸問題的線性規(guī)劃方法研究，包括前期的選題，查找和收集資料，根據(jù)以前學(xué)習(xí)過的運籌學(xué)基礎(chǔ)知識，掌握熟練運用表上作業(yè)法和Vogel這兩種方法，在學(xué)習(xí)的過程中對大量的運輸問題進行了演算；然后又自行學(xué)習(xí)了Excel軟件的線性規(guī)劃求解方法，對算例進行了反復(fù)的修改和試驗。最后又進行了多次的檢查和修改后撰寫成文。1.3.2 主要收獲最初因為自己對運籌學(xué)比較感興趣，所以選擇了運籌學(xué)中線性規(guī)劃在物流運輸問題中應(yīng)用這個選題方向。但在后來的資料查找與收集、

8、整理中才發(fā)現(xiàn)運輸問題是很復(fù)雜的，尤其在實際問題中涉與到很多的約束條件、多個目標函數(shù)要考慮。鑒于自習(xí)的學(xué)習(xí)和研究能力有限，并且在老師的指導(dǎo)建議下，最終縮小了圍，只對產(chǎn)銷平衡運輸問題和簡單的不平衡問題進行研究。從構(gòu)思到開始撰寫成文的過程中遇到了很多的困難，因為運用到了運籌學(xué)的相關(guān)知識，所以文中多次出現(xiàn)很多公式，以前又沒有接觸過在編寫的過程中遇到了許多問題，然后通過上網(wǎng)學(xué)習(xí)和同學(xué)間互相研究討教，運用MathType數(shù)學(xué)公式編輯器最終解決了這個難題。第4章是本文中最重要的部分，以案例為例具體介紹了表上作業(yè)法的計算步驟，在進行這部分的編寫時，我在以前學(xué)習(xí)過的運籌學(xué)基礎(chǔ)上又從新進行了一遍學(xué)習(xí)，在這一遍復(fù)習(xí)

9、的過程中對運籌學(xué)的知識又有了新的認識，熟練掌握了運用表上作業(yè)法和Vogel法求解物流運輸問題的方法。此外運用Excel軟件求解線性規(guī)劃問題對自己來說也是一個全新的學(xué)習(xí)過程，自己先在網(wǎng)上查找了相關(guān)的學(xué)習(xí)資料進行了學(xué)習(xí)，然后在計算機上輸入算例一點點進行試驗，開始因為地方的專業(yè)用語或表示方法看不懂和不會運用，在運行的過程中出現(xiàn)了很多錯誤以致無法運算或者無法得到最優(yōu)解。不過通過不斷的對比資料，一點點的摸索和反復(fù)的試驗，我最終掌握了Excel軟件求解線性規(guī)劃的方法。雖然學(xué)習(xí)新方法的過程是很費時費力的，但最后能夠掌握新的知識并運用它解決了一些問題后，感覺很有成功感。通過這次的課程設(shè)計，也使我對物流系統(tǒng)規(guī)劃

10、和運籌學(xué)的理論知識應(yīng)用到實踐有了更多的認識，自己得到了鍛煉，加強了自己學(xué)習(xí)和動手操作的能力，收獲很多。最后還要感老師和同學(xué)在課程設(shè)計中給予我的各種幫助和指導(dǎo)。1.3.3 自我評定R優(yōu) 良 中 與格 不與格1.3.4 小組成員任務(wù)分工情況學(xué)號任務(wù)備注2 物流運輸概述2.1 物流與運輸2.2.1 物流運輸?shù)母拍钗锪鞯倪\輸專指“物”的載運與輸送。它是在不同地域圍間（如兩個城市、兩個工廠之間，或一大企業(yè)相距較遠的兩車之間），以改變“物”的空間位置為目的的活動，是對“物”進行的空間位移。2.2.2 運輸在物流中的地位1.運輸是物流系統(tǒng)的基礎(chǔ)功能之一。物流系統(tǒng)是通過運輸來完成對客戶所需的原材料、半成品和制

11、成品的地理定位的。2.運輸合理化是物流系統(tǒng)合理化的關(guān)鍵。3.便利和可靠的運輸服務(wù)，是有效組織輸入和輸出物流的關(guān)鍵。同時，企業(yè)的工廠、倉庫與其供貨廠商和用戶之間的地理分布直接影響著物流的運輸作用。因此，運輸條件是企業(yè)選擇工廠、倉庫、配送中心等物流設(shè)施配置地點所要考慮的主要因素之一。4.運輸影響著物流的其它構(gòu)成因素。例如選擇的運輸方式?jīng)Q定著裝運貨物的包裝要求，使用不同類型的運輸工具決定其配套使用的裝卸搬運設(shè)備以與接收和發(fā)運站臺的設(shè)計等；企業(yè)庫存儲備量的大小，直接受運輸狀況的影響，發(fā)達的運輸系統(tǒng)能比較適量、快速和可靠地補充庫存，以減少不必要的儲備水平。5.運輸費用在物流費用中占有很大的比重。組織合理

12、運輸，以最小的費用，較快的時間，與時、準確，安全地將貨物從其產(chǎn)地送達銷地，是降低物流費用和提高經(jīng)濟效益的重要途徑之一。2.2 運輸合理化2.2.1 不合理運輸不合理運輸是在現(xiàn)有條件下可以達到的運輸水平而末達到，從而造成了運力浪費、運輸時間增加、運費超支等問題的運輸形式。不合理運輸?shù)闹饕问接校?.對流運輸。是指同一種貨物，或彼此間可以互相代用而又不影響管理、技術(shù)與效益的貨物，在同一線路上或平行線路上作相對方向的運送，而與對方運程的全部或一部分發(fā)生重疊交錯的運輸。2.迂回運輸。是舍近取遠的一種運輸，可以選取短距離進行運輸而卻選擇路程較長路線進行運輸?shù)囊环N不合理形式。3.重復(fù)運輸。本來可以直接將貨

13、物運到目的地，但是在未達目的地之處，或目的地之外的其它場所將貨卸下，再重復(fù)裝運送達目的地。3.倒流運輸。是指貨物從銷地或中轉(zhuǎn)地向產(chǎn)地或起運地回流的一種運輸現(xiàn)象。4.過遠運輸。是指調(diào)運物資舍近求遠，近處有資源不調(diào)而從遠處調(diào)，這就造成可采取近程運輸而未采取，拉長了貨物運距的浪費現(xiàn)象。5.運力選擇不當。是指沒有根據(jù)各種運輸工具的優(yōu)勢不正確地利用運輸工具造成的不合理現(xiàn)象。2.2.2 影響運輸合理化的因素影響物流運輸合理化的因素很多，起決定性作用的有以下五個方面因素：1.運輸距離。運輸過程中，運輸時間、運費等若干技術(shù)經(jīng)濟指標都與運距有一定的關(guān)系，運距長短與否是運輸是否合理的一個最基本的因素。2.運輸環(huán)節(jié)

14、。每增加一個運輸環(huán)節(jié)，勢必要增加運輸?shù)母綄倩顒樱缪b卸，搬運等，各項技術(shù)經(jīng)濟指標也會因此發(fā)生改變，因此減少運輸環(huán)節(jié)有一定的促進作用。3.運輸工具。各種運輸工具都有其優(yōu)勢領(lǐng)域，對運輸工具進行優(yōu)化選擇最大限度的發(fā)揮運輸工具的特點和作用，是運輸合理化的重要的一環(huán)。4.運輸時間。在全部物流時間中運輸時間占絕大部分，因此，運輸時間的縮短對整個流通時間的縮短起著決定性的作用。此外，縮短運輸時間，還能加速運輸工具的周轉(zhuǎn)，充分發(fā)揮運力的效能，不同程度地改善不合理的現(xiàn)象。5.運輸費用。運費在全部物流費用中占很大的比例，運費高底在很大程度上決定整個物流系統(tǒng)的競爭能力。實際上，運費的相對高低，無論對貨主還是對物流企

15、業(yè)都是運輸合理化的一個重要的指標。運費的高低也是各種合理化措施是否行之有效的最終判斷依據(jù)之一。3 線性規(guī)劃與運輸問題3.1 線性規(guī)劃經(jīng)營管理中如何有效地利用現(xiàn)有人力物力完成更多的任務(wù)，或在預(yù)定的任務(wù)目標下，如何耗用最少的人力物力去實現(xiàn)。這類統(tǒng)籌規(guī)劃的問題用數(shù)學(xué)語言表達，先根據(jù)問題要達到的目標選取適當?shù)淖兞?，問題的目標通過用變量的函數(shù)形式表示，對問題的限制條件用有關(guān)變量的等式或不等式表達。當變量連續(xù)取值，且目標函數(shù)和約束條件均為線性時，稱這類模型為線性規(guī)劃的模型。一般線性規(guī)劃問題的數(shù)學(xué)模型可表示為：（3.1）最早提出線性規(guī)劃想法的是法國數(shù)學(xué)家傅里葉和瓦萊.普森，分別于1832年和1911年獨立提

16、出的，但是那時并未引起注意。直到1939年，前聯(lián)數(shù)學(xué)家康托洛維奇在生產(chǎn)組織與計劃中的數(shù)學(xué)方法一書中，提出和研究了線性規(guī)劃問題，但也未引起重視。1947年，美國數(shù)學(xué)家丹澤格提出了一般的線性規(guī)劃數(shù)學(xué)模型和求解線性規(guī)劃問題的通用方法單純形法，為這門學(xué)科奠定了基礎(chǔ)。單純形法的提出，推動了最優(yōu)化理論的發(fā)展。1979年，前聯(lián)數(shù)學(xué)家哈奇揚提出了運用求解線性不等式組解線性規(guī)劃問題的橢球算法，并證明該算法是多項式時間算法。這算法的提出具有重要的意義，但其實際計算收斂速度極慢，實用效果比單純形法差。1984年，在美國貝爾實驗室工作的印度數(shù)學(xué)家卡瑪卡提出了求解線性規(guī)劃問題的投影尺度法，用這種方法求解線性規(guī)劃問題在變

17、量個數(shù)為5000時只要單純形法所用時間的1/50。這個多項式時間算法很有實用意義，這一算法的提出引起人們對點算法的關(guān)注，此后相繼出現(xiàn)了多種更為簡便實用的點算法。求解線性規(guī)劃是非常復(fù)雜和耗時的一件事，為了省時省力又準確的得出結(jié)果，人們把目光轉(zhuǎn)向了計算機求解，1952年，線性規(guī)劃問題第一次在計算機上獲得求解，這開始了人們對計算機求解線性規(guī)劃的探索，現(xiàn)在已經(jīng)有很多軟件可以進行線性規(guī)劃求解，如Excel、Lingo、Matlab等。3.2 運輸問題運輸問題發(fā)展于線性規(guī)劃問題，自從1939年提出了類似線性規(guī)劃的模型后，人們發(fā)現(xiàn)許多問題都屬于線性函數(shù)在約束條件下的最優(yōu)化問題，在1940年Hitchcock

18、提出運輸問題。運輸問題屬于線性規(guī)劃問題的特殊情況，既有線性規(guī)劃問題的共性，也有自身的特點和算法。運輸問題提出后，1958年Konterovich對運輸問題做了早期的研究。運輸問題的數(shù)學(xué)模型如下：已知某類物資有m個資源點（源點），=1，2，；其資源量分別為（=1，2，）；有n個需求點（終點），=1，2，；其需求量分別為（=1，2，）。從到運送單位貨物的運費為。若用表示從到運輸物資的數(shù)量，z為系統(tǒng)總運輸費用。在產(chǎn)銷平衡，即的條件下，要求得總運費最小的調(diào)運方案，可求解的數(shù)學(xué)模型：（3.2）但在現(xiàn)實生活中往往產(chǎn)銷是不平衡的，這就需要把產(chǎn)銷不平衡問題轉(zhuǎn)化為產(chǎn)銷平衡問題。當產(chǎn)大于銷時，即時，運輸問題的數(shù)學(xué)

19、模型變?yōu)椋?.3）由于產(chǎn)大于銷，所以多余的產(chǎn)品就要考慮在產(chǎn)地就地儲存的問題，設(shè)是產(chǎn)地的儲存量，有令，當，時，當，時，將其代入(3.3)得：（3.4）其中，這就轉(zhuǎn)化成了一個平衡的運輸問題。當銷大于產(chǎn)時，也可以轉(zhuǎn)化成為一個產(chǎn)銷平衡問題，產(chǎn)大于銷是假設(shè)多增設(shè)一個銷售點，該銷地的銷量為，相應(yīng)的運價變?yōu)?。同樣，當銷大于產(chǎn)時也可以用同樣的方法進行轉(zhuǎn)換，這時假設(shè)多增加一個產(chǎn)地，其產(chǎn)量為，相應(yīng)的運價為，然后轉(zhuǎn)化成產(chǎn)銷平衡問題。4 運輸問題的求解方法4.1 單純形法在運輸問題的解法中最好最有效的方法是單純形法，單純形法求解線性規(guī)劃的思路：先找出一個基本可行解，對它進行鑒別，看其是否是最優(yōu)解；若不是，則按照一定的

20、法則轉(zhuǎn)換到另一改進的基本可行解，再進行鑒別；若仍不是，則再轉(zhuǎn)換，按此重復(fù)進行。單純形法的計算步驟如下：第一步：求出線性規(guī)劃的初始基可行解，列出初始單純形表；第二步：進行最優(yōu)性檢驗。如果所有檢驗數(shù)都小于等于零，則基可行解就是最優(yōu)解，否則進行下一步； 第三步：從一個基可行解轉(zhuǎn)換到另一個目標函數(shù)值更大的基可行解，列出新的單純形表；第四步：重復(fù)第二、三步一直到計算終止。4.2 表上作業(yè)法表上作業(yè)法是單純形法在求解運輸問題時的一種簡化方法，其實質(zhì)仍是單純形法，其一般思路是：初始方案的確定最優(yōu)解的檢驗調(diào)運方案的調(diào)整。分析實際問題列出產(chǎn)銷平衡表與單位運價表確定初始調(diào)運方案（最小元素法或Vogel法）求檢驗數(shù)

21、（閉回路法或位勢法）得到最優(yōu)方案算出總的運價是所有檢驗數(shù)>=0否找出絕對值最大的負檢驗數(shù)用閉回路調(diào)整，得出新的調(diào)運方案圖4.1 表上作業(yè)法計算步驟在用表上作業(yè)法求解運輸問題時，首先給出一個初始方案，一般來說，這個方案不會是最好的，因此需要給出一個判別準則，并對初始方案進行調(diào)整、改進，一直到求得最優(yōu)方案為止。下面以一個案例對表上作業(yè)法的求解進行介紹。案例：某公司經(jīng)銷某種產(chǎn)品，它下設(shè)三個加工廠，有四個銷售點，各加工廠每日的產(chǎn)量與各銷售點每日銷量、各加工廠到銷售點的單位產(chǎn)品的運價如表4.1所示，問該公司應(yīng)如何調(diào)運產(chǎn)品，在滿足各銷售點需求量的前提下，使得總運費最少。表4.1 產(chǎn)銷平衡表與單位運價

22、表銷地產(chǎn)地B1B2B3B4產(chǎn)量（噸）A13113107A219284A3741059銷量（噸）3656204.2.1 初始方案的確定初始方案的確定就是初始基可行解的確定。產(chǎn)銷平衡的運輸問題總是存在可行解。因為所以必存在可行解：0 =1，2， =1，2，又因為0min（，）故產(chǎn)銷平衡的運輸問題必存在最優(yōu)解。確定初始基可行解的方法很多，常用的求解方法一般有：最小元素法和Vogel法，簡單又盡可能接近最優(yōu)解的方法是Vogel法。1.最小元素法最小元素法的基本方法就是就近供應(yīng)，即從單位運價表中最小的運價開始確定供銷關(guān)系，然后依次類推，一直到給出全部方案為止。其步驟如下：第一步：在表4.1找出最小運價為

23、1，先將A2的產(chǎn)品供應(yīng)給B1。因>，即A2 除滿足B1的全部需要外，還多出1噸產(chǎn)品。在表4.2的（A2，B1）的交叉格處填上3，同時把表4.2中的B1列劃掉；表4.2銷地產(chǎn)地B1B2B3B4產(chǎn)量（噸）A13113107A2319284A3741059銷量（噸）365620第二步：在表4.2中找出沒有劃掉的最小的運價2，把A2多余的1噸供應(yīng)給B3，并在表4.3（A2，B3）交叉格中填上1，同時把表4.3的A2行劃掉；表4.3銷地產(chǎn)地B1B2B3B4產(chǎn)量（噸）A13113107A23191284A3741059銷量（噸）365620第三步：同樣在表4.3中找出沒有劃掉的最小的運價3，因為A2

24、已經(jīng)供應(yīng)1噸給B3，所以A1供應(yīng)4噸給B3，并在表4.4（A1，B3）交叉格中填上4，同時把表4.4的B3列劃掉；表4.4銷地產(chǎn)地B1B2B3B4產(chǎn)量（噸）A131143107A23191284A3741059銷量（噸）365620第四步：在表4.4中找出沒有劃掉的最小的運價4，把 A3的6噸供應(yīng)給B2，并在表4.5（A3，B2）交叉格中填上6，同時把表4.5的B2列劃掉；表4.5銷地產(chǎn)地B1B2B3B4產(chǎn)量（噸）A131143107A23191284A376410359銷量（噸）365620第五步：在表4.5中找出沒有劃掉的最小的運價5，由于A3一共生產(chǎn)9噸，把 6噸供應(yīng)給了B2，剩下的3噸

25、全部供應(yīng)給B4，并在表4.6（A3，B4）交叉格中填上3，同時把表4.6的A3行劃掉；表4.6銷地產(chǎn)地B1B2B3B4產(chǎn)量（噸）A131143107A23191284A376410359銷量（噸）365620第六步：在表4.6中只剩下運價10沒有劃掉，由于A1一共生產(chǎn)7噸，把 4噸供應(yīng)給了B3，剩下的3噸全部供應(yīng)給B4，并在表4.6（A1，B4）交叉格中填上3，同時把表4.6的B4列劃掉。到此已經(jīng)把產(chǎn)地的產(chǎn)品全部分配到各銷地，并得出表4.7運輸方案，同時得出總運費為86元。表4.7 最小元素法運輸方案銷地產(chǎn)地B1B2B3B4產(chǎn)量（噸）A1311433107A23191284A376410359

26、銷量（噸）365620總運費=4×3+3×10+3×1+1×2+6×4+3×5=86元2.Vogel法Vogel法的基本思路是：產(chǎn)品如果不能按最小運費就近供應(yīng)，就考慮次小運費，會產(chǎn)生一個差額，差額越大，說明不能按最小運費調(diào)運時，運費增加就越多，因而對差額最大處采用最小運費調(diào)運。Vogel法的求解步驟是從運價表上分別找出每行與每列的最小的兩個元素之差，再從差值最大的行或列中找出最小運價確定供需關(guān)系和供應(yīng)數(shù)量。當產(chǎn)地或銷地中有一方數(shù)量上供應(yīng)完畢或得到滿足時，劃去運價表中對應(yīng)的行或列，在重復(fù)上述步驟。求解過程與結(jié)果見下表：表4.8 Voge

27、l法計算過程銷地產(chǎn)地B1B2B3B4兩最小元素之差219281116A37410512兩最小元素之差251321321212表4.9 Vogel法運輸方案銷地產(chǎn)地B1B2B3B4產(chǎn)量（噸）A1527A2314A3639銷量（噸）365620總運費=3×1+6×4+5×3+2×10+1×8+3×5=85元4.2.2 最優(yōu)解的檢驗最優(yōu)解的判別方法是計算空格的檢驗數(shù)。運輸問題的目標函數(shù)是要現(xiàn)最小化，所以當時，為最優(yōu)解。求空格檢驗的方法有兩種：閉回路法和位勢法，本文采用的是閉回路法。閉回路法的步驟是在初始解方案的計算

28、表上，從每一空格出發(fā)找一條閉回路，即以某一個空格為起點，水平或垂直向前劃，當碰到一個數(shù)字格時可以轉(zhuǎn)90°后，繼續(xù)前進，直到回到原點為止。在例題中用最小元素法求出的初始解表4.7中，從任意一個空格出發(fā)，如（A1，B1），若讓A1調(diào)運1噸產(chǎn)品給B1，為了保持產(chǎn)銷平衡，則在（A1，B3）處減少1噸，（A2，B3）處增加1噸，（A2，B1）處減少1噸，構(gòu)成了一個閉回路。這一閉回路增加的運費為：（+1）×3+（-1）×3+（+1）×2+（-1）×1=1（元），。這1就是空格（A1，B1）的檢驗數(shù)，同理可以找出所有空格的檢驗數(shù)，結(jié)果如下表：表4.10 檢驗

29、數(shù)表空格閉回路檢驗數(shù)（A1，B1）（A1，B1）（A1，B3）（A2，B3）（A2，B1）（A1，B1）1（A1，B2）（A1，B2）（A1，B4）（A3，B4）（A3，B2）（A1，B2）2（A2，B2）（A2，B2）（A2，B3）（A1，B3）（A1，B4）（A3，B4）（A3，B2）（A2，B2）1（A2，B4）（A2，B4）（A2，B3）（A1，B3）（A1，B4）（A2，B4）-1（A3，B1）（A3，B1）（A3，B4）（A1，B4）（A1，B3）（A2，B3）（A2，B1）（A3，B1）10（A3，B3）（A3，B3）（A3，B4）（A1，B4）（A1，B3）（A3，B3）12當

30、檢驗數(shù)存在負數(shù)時，說明原方案不是最優(yōu)解，需要改進。4.2.3 調(diào)運方案的改進在進行最優(yōu)解檢驗時，若出現(xiàn)負檢驗數(shù)，表明沒有得出最優(yōu)解，方案需要進行改進，本文采用改進的方法是閉回路調(diào)整法。閉回路調(diào)整法的思路是：以負檢驗數(shù)的空格為調(diào)入格，當負檢驗數(shù)為兩個或兩個以上時，一般選最小的負檢驗數(shù)，以它相對應(yīng)的非基變量為換入變量。由表4.10可知，空格（A2，B4）的檢驗數(shù)為負，所以以該空格為調(diào)入格見表4.11，在該空格中調(diào)入量是以閉回路上具有（-1）的數(shù)字格中的最小者，即min（1，3）=1，然后按閉回路上的正、負號，進行加減得到調(diào)整方案，見表4.12，此時的總運費為85元。表4.11 方案調(diào)整銷地產(chǎn)地B1

31、B2B3B4產(chǎn)量（噸）A14（+1）3（-1）7A231（-1） (+1)4A3639銷量（噸）3656表4.12 改進后的運輸方案銷地產(chǎn)地B1B2B3B4產(chǎn)量（噸）A1527A2314A3639銷量（噸）3656總運費=3×1+6×4+5×3+2×10+1×8+3×5=85（元）對此調(diào)整后的方案再次用閉回路法進行檢驗，得出的檢驗數(shù)如下：表4.13 改進后的檢驗數(shù)表空格閉回路檢驗數(shù)（A1，B1）（A1，B1）（A1，B3）（A2，B3）（A2，B1）（A1，B1）0（A1，B2）（A1，B2）（A1，B4）（A3，B4）（A3，B2）

32、（A1，B2）2（A2，B2）（A2，B2）（A2，B3）（A1，B3）（A1，B4）（A3，B4）（A3，B2）（A2，B2）2（A2，B4）（A2，B4）（A2，B3）（A1，B3）（A1，B4）（A2，B4）1（A3，B1）（A3，B1）（A3，B4）（A1，B4）（A1，B3）（A2，B3）（A2，B1）（A3，B1）9（A3，B3）（A3，B3）（A3，B4）（A1，B4）（A1，B3）（A3，B3）12表中的所有檢驗數(shù)都是非負數(shù)，說明表4.12的結(jié)果是最優(yōu)解。同時也說明Vogel法給出的初始解比最小元素法給出的初始解更接近最優(yōu)解。4.3 Excel規(guī)劃求解方法在進行運輸問題求解時，

33、傳統(tǒng)的解法是表上作業(yè)法，雖然表上作業(yè)法已經(jīng)是最簡單的，但是在求解過程中還是會消耗大量的時間，特別是大規(guī)模的運輸問題，表上作業(yè)法就顯得很復(fù)雜。隨著計算機的出現(xiàn)，人們開始嘗試用計算機對運輸問題進行求解，至今已經(jīng)有很多軟件是針對線性規(guī)劃而設(shè)計的，如Excel的規(guī)劃求解，以與專業(yè)的求解工具Lingo等。Excel的“規(guī)劃求解”功能強大，它可以實現(xiàn)對有多個決策變量的線性規(guī)劃問題的求解，回避了用線性規(guī)劃專業(yè)軟件求解時對操作者的專業(yè)要求，同時也克服了筆算的缺點，其操作方法簡單、方便、快捷，大大提高了計算的效率與準確性。Excel與專業(yè)軟件相比，有以下特點：1、Excel軟件方便易學(xué)，大部分人都比較熟悉，容易

34、掌握；2、能用表格簡單直觀地體現(xiàn)數(shù)學(xué)模型；3、Excel具有大量的建函數(shù)，通過設(shè)置參數(shù)，就能進行復(fù)雜的計算，建模過程簡單；4、Excel軟件具有強大的數(shù)據(jù)分析功能。Excel求解的步驟如下（以4.2中案例為例）：1.創(chuàng)建表格圖4.1 創(chuàng)建表格2.建立目標函數(shù)和約束條件目標函數(shù)：C10=SUMPRODUCT(B2:E2，B3:E3)+SUMPRODUCT(B4:E4，B5:E5)+ SUMPRODUCT(B6:E6，B7:E7)約束條件：B8=SUM（B3+B5+B7）；C8=SUM（C3+C5+C7）；D8=SUM（D3+D5+D7）；E8=SUM（E3+E5+E7）；F3=SUM（B3+C3

35、+D3+E3）；F5=SUM（B5+C5+D5+E5）；F7=SUM（B7+C7+D7+E7）；B3:E30；B5:E50；B7:E70；B8=B9；C8=C9；D8=D9；E8=E9；F3=G3；F5=G5；F7=G7；圖4.2 約束條件和目標函數(shù)3.設(shè)置規(guī)劃求解參數(shù)圖4.3 規(guī)劃求解參數(shù)4. 設(shè)置規(guī)劃求解選項圖4.4 規(guī)劃求解選項圖5.規(guī)劃求解結(jié)果圖4.5 規(guī)劃求解6. 計算結(jié)果圖4.6 Excel求解的結(jié)果由圖4.6計算結(jié)果可知，運用Excel求解的結(jié)果和用表上作業(yè)法求得的結(jié)果是一致的。5 某物流企業(yè)煤炭運輸項目方案求解案例：某物流企業(yè)承包了一個冬季供暖的煤炭運輸項目，有A、B、C三個煤

36、礦為、四個地區(qū)供應(yīng)冬季的用煤。已知各煤礦的年產(chǎn)量與從各煤礦到各地區(qū)單位煤炭的運輸費用如表5.1所示，設(shè)計一個使總運費最節(jié)省的煤炭調(diào)撥方案。表5.1銷地煤礦產(chǎn)量（萬噸）A1613221750B1413191560C19202350最低需求（萬噸）最高需求（萬噸）3050707003010不限分析：實際問題中的運輸問題一般都是產(chǎn)銷不平衡的問題，根據(jù)表5.1中數(shù)據(jù)，總產(chǎn)量為50+60+50=160萬噸，四個地區(qū)的最低需求為30+70+10=110萬噸，最高需求為無限。根據(jù)現(xiàn)有產(chǎn)量，第個地區(qū)每年最多能分配到60萬噸，此時最高需求為50+70+30+60=210萬噸>110萬噸。為了使產(chǎn)銷平衡，需

37、要設(shè)一個虛擬的煤礦D，并設(shè)其年產(chǎn)量為50萬噸。由于各地的需求分最低和最高兩種，以第個地區(qū)為例，最低需求30萬噸是必須滿足的條件，所以不可以由虛擬煤礦D供應(yīng)，可令對應(yīng)的運價為無限大的正數(shù)（極為M），而其余的20萬噸是可以滿足也可以不滿足的，所以這部分可以由D供應(yīng)，對應(yīng)運價為0。根據(jù)上述分析可寫出產(chǎn)銷平衡表5.2和單位運價表5.3表5.2 產(chǎn)銷平衡表銷地煤礦*產(chǎn)量（萬噸）A50B60C50D50銷量（萬噸）302070301050210表5.3 單位運價表銷地煤礦*產(chǎn)量（萬噸）A16161322171750B14141319151560C19192023MM50DM0M0M050銷量（萬噸）302070301050210按照4.2節(jié)中介紹的表上作業(yè)法求得案例的最優(yōu)方案如表5.4所示表5.4 最優(yōu)方案銷地煤礦*