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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、找出最小運(yùn)價(jià)為1，先將a2的產(chǎn)品供應(yīng)給b1。因 ，即a2 除滿足b1的全部需要外，還多出1噸產(chǎn)品。在表4.2的（a2，b1）的交叉格處填上3，同時(shí)把表4.2中的b1列劃掉；表4.2銷地產(chǎn)地b1b2b3b4產(chǎn)量（噸）a13113107a2319284a3741059銷量（噸）365620第二步：在表4.2中找出沒有劃掉的最小的運(yùn)價(jià)2，把a(bǔ)2多余的1噸供應(yīng)給b3，并在表4.3（a2，b3）交叉格中填上1，同時(shí)把表4.3的a2行劃掉；表4.3銷地產(chǎn)地b1b2b3b4產(chǎn)量（噸）a13113107a23191284a3741059銷量（噸）365620第三步：同樣在表4.3中找出沒有劃掉的最小的運(yùn)價(jià)3，

24、因?yàn)閍2已經(jīng)供應(yīng)1噸給b3，所以a1供應(yīng)4噸給b3，并在表4.4（a1，b3）交叉格中填上4，同時(shí)把表4.4的b3列劃掉；表4.4銷地產(chǎn)地b1b2b3b4產(chǎn)量（噸）a131143107a23191284a3741059銷量（噸）365620第四步：在表4.4中找出沒有劃掉的最小的運(yùn)價(jià)4，把 a3的6噸供應(yīng)給b2，并在表4.5（a3，b2）交叉格中填上6，同時(shí)把表4.5的b2列劃掉；表4.5銷地產(chǎn)地b1b2b3b4產(chǎn)量（噸）a131143107a23191284a376410359銷量（噸）365620第五步：在表4.5中找出沒有劃掉的最小的運(yùn)價(jià)5，由于a3一共生產(chǎn)9噸，把 6噸供應(yīng)給了b2，剩

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

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

27、00007a219281116a37410512兩最小元素之差251321321212表4.9 vogel法運(yùn)輸方案銷地產(chǎn)地b1b2b3b4產(chǎn)量（噸）a1527a2314a3639銷量（噸）365620總運(yùn)費(fèi)=31+64+53+210+18+35=85元4.2.2 最優(yōu)解的檢驗(yàn)最優(yōu)解的判別方法是計(jì)算空格的檢驗(yàn)數(shù)。運(yùn)輸問題的目標(biāo)函數(shù)是要求實(shí)現(xiàn)最小化，所以當(dāng)時(shí)，為最優(yōu)解。求空格檢驗(yàn)的方法有兩種：閉回路法和位勢(shì)法，本文采用的是閉回路法。閉回路法的步驟是在初始解方案的計(jì)算表上，從每一空格出發(fā)找一條閉回路，即以某一個(gè)空格為起點(diǎn)，水平或垂直向前劃，當(dāng)碰到一個(gè)數(shù)字格時(shí)可以轉(zhuǎn)90后，繼續(xù)前進(jìn)，直到回到原點(diǎn)為止

28、。在例題中用最小元素法求出的初始解表4.7中，從任意一個(gè)空格出發(fā)，如（a1，b1），若讓a1調(diào)運(yùn)1噸產(chǎn)品給b1，為了保持產(chǎn)銷平衡，則在（a1，b3）處減少1噸，（a2，b3）處增加1噸，（a2，b1）處減少1噸，構(gòu)成了一個(gè)閉回路。這一閉回路增加的運(yùn)費(fèi)為：（+1）3+（-1）3+（+1）2+（-1）1=1（元），。這1就是空格（a1，b1）的檢驗(yàn)數(shù)，同理可以找出所有空格的檢驗(yàn)數(shù)，結(jié)果如下表：表4.10 檢驗(yàn)數(shù)表空格閉回路檢驗(yàn)數(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

29、（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當(dāng)檢驗(yàn)數(shù)存在負(fù)數(shù)時(shí)，說明原方案不是最優(yōu)解，需要改進(jìn)。4.2.3 調(diào)運(yùn)方案的改進(jìn)在進(jìn)行最優(yōu)解檢驗(yàn)時(shí)，若出現(xiàn)負(fù)檢驗(yàn)數(shù)，表明沒有得出最優(yōu)解，方案需要進(jìn)行改進(jìn)，本文采用改進(jìn)的方法是閉回路調(diào)整法。閉回路調(diào)

30、整法的思路是：以負(fù)檢驗(yàn)數(shù)的空格為調(diào)入格，當(dāng)負(fù)檢驗(yàn)數(shù)為兩個(gè)或兩個(gè)以上時(shí)，一般選最小的負(fù)檢驗(yàn)數(shù)，以它相對(duì)應(yīng)的非基變量為換入變量。由表4.10可知，空格（a2，b4）的檢驗(yàn)數(shù)為負(fù)，所以以該空格為調(diào)入格見表4.11，在該空格中調(diào)入量是以閉回路上具有（-1）的數(shù)字格中的最小者，即min（1，3）=1，然后按閉回路上的正、負(fù)號(hào)，進(jìn)行加減得到調(diào)整方案，見表4.12，此時(shí)的總運(yùn)費(fèi)為85元。表4.11 方案調(diào)整銷地產(chǎn)地b1b2b3b4產(chǎn)量（噸）a14（+1）3（-1）7a231（-1） (+1)4a3639銷量（噸）3656表4.12 改進(jìn)后的運(yùn)輸方案銷地產(chǎn)地b1b2b3b4產(chǎn)量（噸）a1527a2314a36

31、39銷量（噸）3656總運(yùn)費(fèi)=31+64+53+210+18+35=85（元）對(duì)此調(diào)整后的方案再次用閉回路法進(jìn)行檢驗(yàn)，得出的檢驗(yàn)數(shù)如下：表4.13 改進(jìn)后的檢驗(yàn)數(shù)表空格閉回路檢驗(yàn)數(shù)（a1，b1）（a1，b1）（a1，b3）（a2，b3）（a2，b1）（a1，b1）0（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）2（a2，b4）（a2，b4）（a2，b3）（a1，b3）（a1，b4）（a2，b4）1（a3，b1）（a3，b1）（a3，b4）（a1

32、，b4）（a1，b3）（a2，b3）（a2，b1）（a3，b1）9（a3，b3）（a3，b3）（a3，b4）（a1，b4）（a1，b3）（a3，b3）12表中的所有檢驗(yàn)數(shù)都是非負(fù)數(shù)，說明表4.12的結(jié)果是最優(yōu)解。同時(shí)也說明vogel法給出的初始解比最小元素法給出的初始解更接近最優(yōu)解。4.3 excel規(guī)劃求解方法在進(jìn)行運(yùn)輸問題求解時(shí)，傳統(tǒng)的解法是表上作業(yè)法，雖然表上作業(yè)法已經(jīng)是最簡單的，但是在求解過程中還是會(huì)消耗大量的時(shí)間，特別是大規(guī)模的運(yùn)輸問題，表上作業(yè)法就顯得很復(fù)雜。隨著計(jì)算機(jī)的出現(xiàn)，人們開始嘗試用計(jì)算機(jī)對(duì)運(yùn)輸問題進(jìn)行求解，至今已經(jīng)有很多軟件是針對(duì)線性規(guī)劃而設(shè)計(jì)的，如excel的規(guī)劃求解，

33、以及專業(yè)的求解工具lingo等。excel的“規(guī)劃求解”功能強(qiáng)大，它可以實(shí)現(xiàn)對(duì)有多個(gè)決策變量的線性規(guī)劃問題的求解，回避了用線性規(guī)劃專業(yè)軟件求解時(shí)對(duì)操作者的專業(yè)要求，同時(shí)也克服了筆算的缺點(diǎn)，其操作方法簡單、方便、快捷，大大提高了計(jì)算的效率與準(zhǔn)確性。excel與專業(yè)軟件相比，有以下特點(diǎn)：1、excel軟件方便易學(xué)，大部分人都比較熟悉，容易掌握；2、能用表格簡單直觀地體現(xiàn)數(shù)學(xué)模型；3、excel具有大量的內(nèi)建函數(shù)，通過設(shè)置參數(shù)，就能進(jìn)行復(fù)雜的計(jì)算，建模過程簡單；4、excel軟件具有強(qiáng)大的數(shù)據(jù)分析功能。excel求解的步驟如下（以4.2中案例為例）：1.創(chuàng)建表格圖4.1 創(chuàng)建表格2.建立目標(biāo)函數(shù)和約

34、束條件目標(biāo)函數(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+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 約束條件和目標(biāo)函數(shù)3.設(shè)置規(guī)劃

35、求解參數(shù)圖4.3 規(guī)劃求解參數(shù)4. 設(shè)置規(guī)劃求解選項(xiàng)圖4.4 規(guī)劃求解選項(xiàng)圖5.規(guī)劃求解結(jié)果圖4.5 規(guī)劃求解6. 計(jì)算結(jié)果圖4.6 excel求解的結(jié)果由圖4.6計(jì)算結(jié)果可知，運(yùn)用excel求解的結(jié)果和用表上作業(yè)法求得的結(jié)果是一致的。5 某物流企業(yè)煤炭運(yùn)輸項(xiàng)目方案求解案例：某物流企業(yè)承包了一個(gè)冬季供暖的煤炭運(yùn)輸項(xiàng)目，有a、b、c三個(gè)煤礦為、四個(gè)地區(qū)供應(yīng)冬季的用煤。已知各煤礦的年產(chǎn)量及從各煤礦到各地區(qū)單位煤炭的運(yùn)輸費(fèi)用如表5.1所示，設(shè)計(jì)一個(gè)使總運(yùn)費(fèi)最節(jié)省的煤炭調(diào)撥方案。表5.1銷地煤礦產(chǎn)量（萬噸）a1613221750b1413191560c19202350最低需求（萬噸）最高需求（萬噸）3

36、050707003010不限分析：實(shí)際問題中的運(yùn)輸問題一般都是產(chǎn)銷不平衡的問題，根據(jù)表5.1中數(shù)據(jù)，總產(chǎn)量為50+60+50=160萬噸，四個(gè)地區(qū)的最低需求為30+70+10=110萬噸，最高需求為無限。根據(jù)現(xiàn)有產(chǎn)量，第個(gè)地區(qū)每年最多能分配到60萬噸，此時(shí)最高需求為50+70+30+60=210萬噸110萬噸。為了使產(chǎn)銷平衡，需要設(shè)一個(gè)虛擬的煤礦d，并設(shè)其年產(chǎn)量為50萬噸。由于各地的需求分最低和最高兩種，以第個(gè)地區(qū)為例，最低需求30萬噸是必須滿足的條件，所以不可以由虛擬煤礦d供應(yīng)，可令對(duì)應(yīng)的運(yùn)價(jià)為無限大的正數(shù)（極為m），而其余的20萬噸是可以滿足也可以不滿足的，所以這部分可以由d供應(yīng)，對(duì)應(yīng)運(yùn)價(jià)為0。根據(jù)上述分析可寫出產(chǎn)銷平衡表5.2和單位運(yùn)價(jià)表5.3表5.2 產(chǎn)銷平衡表銷地煤礦*產(chǎn)量（萬噸）a50b60c50d50銷量（萬噸）302070301050210表5.3 單位運(yùn)價(jià)表銷地煤礦*產(chǎn)量（萬噸）a16161322171750b14141319151560c19192023mm50dm0m0m050銷量（萬噸）302070301050210按照4.2節(jié)中介紹的表上作業(yè)法求得案例的最