物流運(yùn)輸規(guī)劃(完)ppt課件

1、物流運(yùn)輸與配送管理實(shí)務(wù),主講：李 穎 鄭州大學(xué)西亞斯國際學(xué)院 商學(xué)院,第2章 物流運(yùn)輸規(guī)劃,本章知識(shí)結(jié)構(gòu),物流運(yùn)輸規(guī)劃,合理選擇運(yùn)輸方式,運(yùn)輸問題與線性規(guī)劃,旅行路線問題,小結(jié)與案例,圖論方法的應(yīng)用,各種運(yùn)輸方式的特點(diǎn),線性規(guī)劃模型及單純形法,旅行路線問題及求解,郵路問題、最小聯(lián)通問題及各自的求解方法,目前我國最常用的運(yùn)輸方式有哪些？,鐵路,按運(yùn)輸工具分,引言,每一個(gè)國家的經(jīng)濟(jì)地理環(huán)境和工業(yè)化程度不同，運(yùn)輸方式的構(gòu)成也有差異。例如，在缺乏河流的內(nèi)陸國家，就幾乎沒有水路運(yùn)輸；在工業(yè)化程度很低的國家，航空運(yùn)輸?shù)谋壤容^低。就近代運(yùn)輸業(yè)發(fā)展的一段歷史來看，船舶運(yùn)輸是較早使用的一種機(jī)械運(yùn)輸方式。180

2、7年，世界上第一艘輪船在北美哈德遜河下水，揭開了機(jī)械運(yùn)輸?shù)男录o(jì)元。其后，各種運(yùn)輸工具相繼問世。1825年，世界上第一條鐵路在英國正式通車，1861年，第一條輸油管道鋪設(shè)；1886年，以汽油為動(dòng)力的汽車在德國問世。到1903年第一架飛機(jī)飛上了藍(lán)天。在經(jīng)歷了整整一個(gè)世紀(jì)后，五種新型運(yùn)輸工具奠定了以五種運(yùn)輸方式為基本格局的運(yùn)輸業(yè)。,2.1 合理選擇運(yùn)輸方式 一、公路運(yùn)輸 設(shè)施：公路、公路車站和車輛。 優(yōu)點(diǎn)：對(duì)于小、中批量商品的近距離運(yùn)輸，運(yùn)費(fèi)較便宜，而且經(jīng)濟(jì)；可以做到“門到門”（doorto door)；包裝成本低。 缺點(diǎn)：運(yùn)輸能力低；單位運(yùn)費(fèi)高；易遭偷盜；加劇擁擠與污染,二、鐵路運(yùn)輸 設(shè)施：鐵路、

3、火車、車站及輔助設(shè)備 優(yōu)點(diǎn)：運(yùn)載能力較大，適用于大宗貨物的集中、迅速運(yùn) 輸；中、遠(yuǎn)距離運(yùn)輸時(shí)，運(yùn)費(fèi)比較便宜；受氣 候條件的影響較小；在軌道上運(yùn)輸，安全性好 缺點(diǎn)：靈活性差；對(duì)包裝的要求較高；基建成本大。,三、水上運(yùn)輸 設(shè)施：天然水道、港口和船舶。 優(yōu)點(diǎn)：高運(yùn)輸能力；低廉的單位運(yùn)費(fèi)。 缺點(diǎn)：速度慢；路線迂回；受天氣影響大，可靠性差,四、航空運(yùn)輸 設(shè)施：航空港、飛行器和航管設(shè)施。 優(yōu)點(diǎn)：速度快；受地形條件限制小。 缺點(diǎn)：運(yùn)輸成本高；運(yùn)載量有限；受氣候影響大。,五、管道運(yùn)輸 管道是一種集運(yùn)輸工具和運(yùn)輸線路于一身的運(yùn)輸方式。采用管道運(yùn)輸，貨物憑借高壓氣泵的壓力在管道內(nèi)移動(dòng)，到達(dá)目的地。 三種形式：液體

4、管道、氣體管道、漿質(zhì)管道。 優(yōu)點(diǎn)：可全天候工作；不需包裝；單向運(yùn)輸；單位運(yùn)營成本低。 缺點(diǎn)：貨物受限；機(jī)動(dòng)靈活性小，初期投資大。,各種交通運(yùn)輸方式的比較,在選擇運(yùn)輸工具的時(shí)候，主要考慮的因素：,運(yùn)輸數(shù)量： 1520噸以下的貨物，采用公路運(yùn)輸； 1520噸以上的貨物，采用鐵路運(yùn)輸； 數(shù)百噸以上的原材料之類的貨物，應(yīng)選擇水路運(yùn)輸。 運(yùn)輸價(jià)格： 運(yùn)輸速度 航空最快達(dá)到900 1000km/h； 鐵路80 250 km/h； 公路80 120km/h； 水路中的河運(yùn)820 km/h， 海運(yùn)每小時(shí)1030海里。,在選擇運(yùn)輸工具的時(shí)候，主要考慮的因素：,貨物性質(zhì) 運(yùn)輸距離： 200公里以內(nèi)，采用公路運(yùn)輸；

5、 200500公里的區(qū)域，采用鐵路運(yùn)輸； 500公里以上根據(jù)具體情況采用水路或 航空運(yùn)輸； 特別要求,運(yùn) 輸 方 式選擇 的原則,貴重或急需的貨物（數(shù)量不大）航空 短途公路 容易死亡、變質(zhì)的 活物、鮮貨物 長途且數(shù)量大鐵路 大宗、笨重的貨物（遠(yuǎn)距離運(yùn)輸）水運(yùn)或鐵路,選擇交通工具：,飛機(jī),選擇交通工具：,海輪,選擇交通工具：,江輪,選擇交通工具：,汽車,選擇交通工具：,火車,選擇運(yùn)輸方式,貴重或急需的貨物， 數(shù)量又不大的，多由 運(yùn)輸。,航空,選擇運(yùn)輸方式,容易死亡、變質(zhì)的， 活物、鮮貨，短程可由 運(yùn)輸。,公路,選擇運(yùn)輸方式,容易死亡、變質(zhì)的， 活物、鮮貨，遠(yuǎn)程而又?jǐn)?shù) 量大的可用 運(yùn)輸。,鐵路,選

6、擇運(yùn)輸方式,大宗笨重的貨物， 遠(yuǎn)距離運(yùn)輸，盡可能利 用 或 運(yùn)輸。,水運(yùn),鐵路,選擇運(yùn)輸方式,貨物和數(shù)量 起點(diǎn)至終點(diǎn) 鐵路公路 河運(yùn)海運(yùn) 航空,兩箱急救藥品 北京-拉薩,一噸活魚 密云水庫-北京,五十噸鋼材 上海-濟(jì)南,一萬噸海鹽 天津-上海,十萬噸大米 武漢-上海,例2.讀歐洲貨物四種運(yùn)輸方式運(yùn)費(fèi)與運(yùn)距相關(guān)曲線示意圖，回答問題。 運(yùn)距550千米時(shí)，最廉價(jià)的運(yùn)輸方式是_。 最昂貴的運(yùn)輸方式是_，它適合運(yùn)送的貨物特點(diǎn)是 _。,總運(yùn)價(jià),080550距離/千米,空運(yùn),公路,鐵路,水路,公路,鐵路,水運(yùn),空運(yùn),輕型、貴重、急需。,某公司有以下運(yùn)輸業(yè)務(wù)委托你公司進(jìn)行 托運(yùn)，請(qǐng)為其選擇合適的運(yùn)輸方式并說明

7、理由。 1.把兩箱急救藥和一批鮮花從廣州運(yùn)到北京。 2.把一批煤炭從山西運(yùn)到秦皇島。 3.把一批新鮮蔬菜從郊區(qū)運(yùn)到市區(qū)。 4.有一批鋼材，要從重慶運(yùn)到武漢。 5.有15萬噸石油需要從非洲運(yùn)到我國的上海。 6.把我國西部大量的天然氣運(yùn)到以上海為主的東部地區(qū)。,A公司首次承攬到三個(gè)集裝箱運(yùn)輸業(yè)務(wù)，時(shí)間較緊，從上海到大連鐵路1200公里，公路1500公里，水路1000公里。該公司自有10輛10噸普通卡車和一個(gè)自動(dòng)化立體倉庫，經(jīng)聯(lián)系附近一家聯(lián)運(yùn)公司雖無集裝箱卡車，但卻有專業(yè)人才和貨代經(jīng)驗(yàn)，只是要價(jià)比較高。至于零星集裝箱安排、落實(shí)車皮和船艙，A公司實(shí)在心中無底，你認(rèn)為采取什么措施比較穩(wěn)妥？,（1）自己購

8、買若干輛集裝箱卡車，然后組織運(yùn)輸。 （2）想法請(qǐng)鐵路部門安排運(yùn)輸 （3）水路最短，請(qǐng)航運(yùn)公司來解決運(yùn)輸 （4）聯(lián)運(yùn)公司雖無集卡，但可叫其租車完成此項(xiàng)運(yùn)輸 （5）沒有合適的運(yùn)輸工具，辭掉該項(xiàng)業(yè)務(wù),分析要點(diǎn)： 1）以請(qǐng)聯(lián)運(yùn)公司來承擔(dān)此項(xiàng)任務(wù)為好，比較穩(wěn)妥，聯(lián)運(yùn)公司是第三方物流服務(wù)企業(yè) 2）第三方物流服務(wù)供應(yīng)商，根據(jù)是夠擁有資產(chǎn)可分為資產(chǎn)基礎(chǔ)供應(yīng)商和非資產(chǎn)基礎(chǔ)供應(yīng)商。我們選擇的標(biāo)準(zhǔn)絕不是它有無實(shí)際的物流資產(chǎn)而是看專業(yè)人才和貨代經(jīng)驗(yàn)，有資產(chǎn)的物流供應(yīng)商價(jià)格可能低些，但靈活性差；而非資產(chǎn)基礎(chǔ)供應(yīng)商，則可根據(jù)不同需要“量體裁衣”，非常靈活,3）邀請(qǐng)第三方物流服務(wù)供應(yīng)商，應(yīng)該做好如下工作 （1）對(duì)該聯(lián)運(yùn)公司

9、做必要調(diào)查，看看信譽(yù)度如何。 （2）進(jìn)行必要的合同磋商，解決好合同的執(zhí)行標(biāo)準(zhǔn)、衡量標(biāo)準(zhǔn)、違約責(zé)任以及價(jià)格 （3）努力避免雙方合作失敗，既交貨又派專人關(guān)心 此事 （4）講明如果服務(wù)質(zhì)量好，可考慮長期合作的可能性。 其他方案欠穩(wěn)妥，無把握，風(fēng)險(xiǎn)很大,案例啟示： 企業(yè)生存與發(fā)展的不二法門就是盈利，但是對(duì)于企業(yè)即將開展的新業(yè)務(wù)或相關(guān)業(yè)務(wù)來說，盈利的同時(shí)，經(jīng)驗(yàn)和長期客戶的開發(fā)維護(hù)也是很重要的,6、幾種特殊的運(yùn)輸方式,1、集裝箱運(yùn)輸 1）概念 集裝箱是一個(gè)大型的、標(biāo)準(zhǔn)化的、能反復(fù)使用的載貨容器。 集裝箱運(yùn)輸就是以集裝箱作為一個(gè)貨物集合單元進(jìn)行運(yùn)輸?shù)囊环N運(yùn)輸方式。,標(biāo)準(zhǔn)集裝箱,側(cè)開門集裝箱,側(cè)開雙門集裝箱,

10、全側(cè)開門集裝箱,開頂散貨集裝箱,冷藏集裝箱,2）集裝箱運(yùn)輸?shù)膬?yōu)點(diǎn),提高裝卸效率，減輕勞動(dòng)強(qiáng)度 減少了裝卸所需要的時(shí)間和費(fèi)用，加速了車船周轉(zhuǎn) 保證貨物完整無損，避免貨損貨差 節(jié)省包裝費(fèi)用，簡化理貨手續(xù) 減少營運(yùn)費(fèi)用，降低運(yùn)輸成本,3）集裝箱運(yùn)輸?shù)娜毕?集裝箱運(yùn)輸需要大量的初始投資 建立新的管理體制、形成新的管理人員隊(duì)伍 增加了一些潛在的不安全因素,英國擱淺貨輪納波利號(hào)散落貨物,4）開展集裝箱運(yùn)輸?shù)臈l件,要有穩(wěn)定的貨源和經(jīng)濟(jì)腹地 要有良好的港口條件（深水港）和基礎(chǔ)設(shè)施（如裝卸） 較為發(fā)達(dá)的內(nèi)陸運(yùn)輸系統(tǒng) 高素質(zhì)的經(jīng)營管理者,2、托盤運(yùn)輸 1）概念： 托盤（ pallet）是用于集裝、堆放、搬運(yùn)和運(yùn)輸

11、的放置作為單元負(fù)荷的貨物和制品的水平平臺(tái)裝置。 托盤運(yùn)輸是貨物按照一定要求成組裝在一個(gè)標(biāo)準(zhǔn)托盤上組合成為一個(gè)運(yùn)輸單位并便于利用鏟車或托盤升降進(jìn)行裝卸、搬運(yùn)和堆存的一種運(yùn)輸方式，它是成組運(yùn)輸?shù)某跫?jí)形態(tài)。,2）托盤運(yùn)輸?shù)奶攸c(diǎn),（1）提高運(yùn)輸效率 搬運(yùn)或出入庫場都可用機(jī)械操作，減少貨物堆碼作業(yè)，從而有利于提高運(yùn)輸效率，縮短貨運(yùn)時(shí)間，減少勞動(dòng)強(qiáng)度。 （2）便于理貨，減少貨損貨差 以托盤為運(yùn)輸單位，貨物件數(shù)變少體積重量變大，而且每個(gè)托盤所裝數(shù)量相等。既便于點(diǎn)數(shù)、理貨交接，又可以減少貨損貨差事故。 （3）投資比較小，收效比較快。 （4）托盤的回收利用，組織工作難度較大，會(huì)浪費(fèi)一部分運(yùn)力。,3）托盤運(yùn)輸具有

12、一定的局限性，表現(xiàn)在以下幾方面： 1、托盤承運(yùn)的貨物范圍有限 最適合托盤運(yùn)輸?shù)呢浳锸窍溲b罐頭食品、硬紙盒裝的消費(fèi)品和袋及袋裝的貨物等比較小的包裝商品。 大的、形狀不一的家具、機(jī)械以及散裝冷凍等貨物，不適合于采用托盤進(jìn)行運(yùn)輸 2、托盤運(yùn)輸設(shè)備費(fèi)用減少，但要增加托盤運(yùn)輸費(fèi)用。同時(shí)，由于增加了托盤的重量和體積，相應(yīng)地減少了運(yùn)輸工具的載量。 3、托盤運(yùn)輸向成組運(yùn)輸前進(jìn)了一步，但它的效果還不足以改變傳統(tǒng)的流通方式，特別是不能滿足國際多式聯(lián)運(yùn)的要求。 例如，它不能像集裝箱那樣，可以密封越過國境或快速轉(zhuǎn)換各種運(yùn)輸方式。,4）采用托盤運(yùn)輸應(yīng)該注意的事項(xiàng),1、裝載托盤貨物的范圍有一定限制，不是所有貨物都可以用托

13、盤運(yùn)輸。 2、必須符合托盤積載的規(guī)定。 3、每一托盤貨載，必須捆扎牢固具有足夠的強(qiáng)度和穩(wěn)定，平衡。 既能夠承受一般海上風(fēng)險(xiǎn)，經(jīng)受裝卸操作和移動(dòng)，也能夠在其上面承受一定的壓力。 4、貨物以托盤運(yùn)輸時(shí)，必須在所有運(yùn)輸單證上注明“托盤運(yùn)輸”字樣。,3、散裝運(yùn)輸 1）含義： 散裝運(yùn)輸是指產(chǎn)品不帶包裝的運(yùn)輸，是用專用設(shè)備將產(chǎn)品直接由生產(chǎn)廠方送至用戶使用的運(yùn)輸方式。 2）優(yōu)點(diǎn)： ）節(jié)省包裝材料和費(fèi)用，減少貨損 ）減少工作環(huán)節(jié)，提高機(jī)械化、自動(dòng)化程度,4、國際多式聯(lián)運(yùn) 1）含義： 國際多式聯(lián)運(yùn)是指按照多式聯(lián)運(yùn)合同,以至少兩種不同的運(yùn)輸方式，由多式聯(lián)運(yùn)經(jīng)營人將貨物從一國境內(nèi)接管貨物的地點(diǎn)運(yùn)至另一國境內(nèi)指定交付

14、貨物的地點(diǎn)。,2）特征： （1）必須訂立多式聯(lián)運(yùn)合同 （1）多式聯(lián)運(yùn)合同：是指多式聯(lián)運(yùn)經(jīng)營人憑其收取全程運(yùn)費(fèi)，使用兩種或兩種以上不同運(yùn)輸工具，負(fù)責(zé)組織完成貨物全程運(yùn)輸?shù)暮贤?（2）托運(yùn)人只與MTO有業(yè)務(wù)和法律上的關(guān)系。（托運(yùn)人與各區(qū)段實(shí)際承運(yùn)人不發(fā)生任何業(yè)務(wù)和法律上的關(guān)系） （2）必須由多式聯(lián)運(yùn)經(jīng)營人對(duì)全程運(yùn)輸負(fù)責(zé) （3）必須是兩種或兩種以上不同運(yùn)輸方式組成的連貫運(yùn)輸。 （5）必須簽發(fā)多式聯(lián)運(yùn)單據(jù) （1）MTO在接管貨物后簽發(fā)多式聯(lián)運(yùn)單據(jù)（2）從發(fā)貨地到收貨地，一單到底（3）發(fā)貨人憑多式聯(lián)運(yùn)單據(jù)向銀行結(jié)匯。（4）收貨人憑多式聯(lián)運(yùn)單據(jù)向MTO或代理提貨。 （6）必須是單一的運(yùn)費(fèi)率,3）優(yōu)點(diǎn)：

15、（）手續(xù)簡便，可以做到一次性托運(yùn)，一次性付費(fèi)，一次性投保，一單到底，統(tǒng)一理賠，全程負(fù)責(zé) （）安全可靠 （）統(tǒng)一理賠 （）可以實(shí)現(xiàn)門門運(yùn)輸 （）具有單一運(yùn)費(fèi)率,案例,2004年10月4日，原告A公司作為買方與溫州市進(jìn)出口公司B簽訂一份售貨確認(rèn)書，購買一批童裝，數(shù)量500箱，總價(jià)為68180美元。2005年2月11日，B公司以托運(yùn)人身份將該批童裝裝于兩個(gè)20尺標(biāo)箱內(nèi)，交由多式聯(lián)運(yùn)經(jīng)營人C承運(yùn)。C公司簽發(fā)了號(hào)碼為RS95040的一式三份正本全程多式聯(lián)運(yùn)提單。 A公司提貨時(shí)箱子外觀完好，打開箱子發(fā)現(xiàn)其中一個(gè)箱子是空的。另一個(gè)箱子貨物被擠壓而無法按正常價(jià)值出售。 問：多式聯(lián)運(yùn)人是否承擔(dān)賠償責(zé)任。,解答：

16、 集裝箱貨物的真實(shí)性問題。根據(jù)國際航運(yùn)慣例，在集裝箱運(yùn)輸方式中，由托運(yùn)人負(fù)責(zé)裝箱的貨物，從裝箱托運(yùn)后至交付收貨人時(shí)的期間內(nèi)，如集裝箱箱體和封志完好，貨物損壞或短缺，由托運(yùn)人負(fù)責(zé)；如箱體損壞或封志破壞，箱內(nèi)貨物損壞或短缺，由承運(yùn)人負(fù)責(zé)。,2.2 運(yùn)輸問題與線性規(guī)劃 1、線性規(guī)劃模型及求解方法 1）線性規(guī)劃問題的數(shù)學(xué)表達(dá)式 線性規(guī)劃問題一般可以表示如下：,稱為線性規(guī)劃問題的標(biāo)準(zhǔn)形式（其中右端常數(shù)b1，b2，bm0）。,變換一般LP為標(biāo)準(zhǔn)形式的方法： （1）如果原問題目標(biāo)函數(shù)求極大值：,令z1=z，轉(zhuǎn)化為求極小值。 （2）若某個(gè)右端常數(shù)bi0 則以1乘該約束兩端。 （3）若某約束為“”型的不等式約束

17、， 則在左端加上一個(gè)非負(fù)變量，稱為松弛變量，使不等式化為等式； 若某約束為“”型， 則在左端減去一個(gè)非負(fù)變量，稱為剩余變量，或者仍然稱為松弛變量，使不等式轉(zhuǎn)化為等式。（目標(biāo)函數(shù)不變 （4）若某個(gè)xj的符號(hào)約束為xj0； 那么令xj=xj，則xj0； 若某個(gè)xj無符號(hào)限制， 令xj=xjxj，其中xj0，xj0。（目標(biāo)函數(shù)變）,2）單純形法 單純形表,E 單位陣,N 非基陣,基變量XB,非基變量XN,檢驗(yàn)數(shù),基可行解,單純形法 單純形法的求解過程就是對(duì)單純形表的變換過程，其步驟為： （1）求初始基可行解，列出初始單純形表 （2）最優(yōu)性檢驗(yàn)： 若所有檢驗(yàn)數(shù) ，則表中基可行解即為最優(yōu)解，計(jì)算結(jié)束；

18、若存在 ，則選最大者 所對(duì)應(yīng)的變量 為入基變量，轉(zhuǎn)步驟（3） （3）檢查單純形表的第K列。 若無正值，則為無界解； 若有一個(gè)以上的正值，按最小比值法 確定出基變量 （4）用對(duì)角頂點(diǎn)法對(duì)單純形表進(jìn)行變換 （5）返回步驟（2）進(jìn)行迭代,對(duì)角頂點(diǎn)法： 如下圖所示，矩形的四個(gè)頂點(diǎn)分別對(duì)應(yīng)四個(gè)元素：D1、D2、D3、D4，若D1為需要變換的元素，它的對(duì)角元素是交叉元素D3 ，另兩個(gè)對(duì)角元素為D2和D4 。 對(duì)角頂點(diǎn)法就是：第i行第j列的元素新值D1為舊值D1減去兩個(gè)對(duì)角元素D2、 D4乘積除以交叉元素D3所得的值 即： D1= D1- D2 * D4 / D3,D4,D1,D3,主列,j列,i行,主行,

19、D2,若對(duì)第i行第j列的元素7進(jìn)行變換，則變換過程為： 變換后第i行第j列的元素為： 7-3*2/8=25/4,3,2,7,8,主列,j列,i行,主行,變換單純形表： 首先，將 行的元素除以交叉元素， 即 變換后的交叉元素 然后，其他行的元素（除k列）按對(duì)角頂點(diǎn)法變換 最后，把k列（不含交叉）元素變?yōu)?，即 單純形變換結(jié)束,例：求解下列線性規(guī)劃問題,解：加入變量 ，則問題變換為如下形式,3 0 -1 0 0 M M 0 4 1 1 1 1 0 0 0 M 1 -2 1 -1 0 -1 1 0 M 9 0 3 1 0 0 0 1 10M -2M 4M 1 0 -M 0 0 -3,正檢驗(yàn)數(shù)中最大者

20、對(duì)應(yīng)的列為主列,主元素化為1, 向量 換入, 換出,4 1 3,表1：列初始單純形表 （單位矩陣對(duì)應(yīng)的變量為基變量）,最小的值對(duì)應(yīng)的行為主行,3 0 -1 0 0 M M 0 4 1 1 1 1 0 0 0 M 1 -2 1 -1 0 -1 1 0 M 9 0 3 1 0 0 0 1 10M -2M 4M 1 0 -M 0 0 -3,變換為：4-1*1=3,3,1 -2 1 -1 0 -1 1 0,6,變換為： 9-1*3=6,變換為： 1-1*(-2)=3,3,變換為： 1-1*(-1)=2,2,變換為： 1-1*0=1,1,變換為： 0-1*(-1)=1,1,變換為： 0-1*1=-1,-

21、1,變換為： 0-1*0=0,0,變換為： 0-(-2)*3=6,6,變換為： 1-(-1)*3=4,4,變換為： 0-0*3=0,0,變換為： 0-(-1)*3=3,3,變換為： 0-1*3=-3,-3,變換為： 1-0*3=1,1,6M 6M 4M 4M 0 3M -4M 0 -3 +1,0,0,0,3 0 -1 0 0 M M 0 3 3 0 2 1 1 -1 0 0 1 -2 1 -1 0 -1 1 0 M 6 6 0 4 0 3 -3 1 6M 6M 0 1+4M 0 3M -4M 0 -3,正檢驗(yàn)數(shù)中最大者對(duì)應(yīng)的列為主列,主元素化為1, 向量 換入, 換出,1 - 1,表2：換基

22、（對(duì)角頂點(diǎn)法，主列化為單位向量，主元為1）,最小的值對(duì)應(yīng)的行為主行,3 0 -1 0 0 M M 0 0 0 0 0 1 -1/2 -1/2 -1/2 0 3 0 1 1/3 0 0 0 1/3 3 1 1 0 2/3 0 1/2 -1/2 1/6 3 0 0 3 0 3/2 -M -M -3/2 +1/2,正檢驗(yàn)數(shù)中最大者對(duì)應(yīng)的列為主列,主元素化為1, 向量 換入, 換出,- 9 3/2,表3：換基 （對(duì)角頂點(diǎn)法，主列化為單位向量，主元為1）,最小的值對(duì)應(yīng)的行為主行,3 0 -1 0 0 M M 0 0 0 0 0 1 -1/2 1/2 -1/2 0 5/2 -1/2 1 0 0 -1/4

23、1/4 1/4 -1 3/2 3/2 0 1 0 3/4 -3/4 1/4 -3/2 -9/2 0 0 0 -3/4 -M -M +3/4 -1/4,表4：換基 （對(duì)角頂點(diǎn)法，主列化為單位向量，主元為1）,最優(yōu)解為X=(0,5/2,3/2) 目標(biāo)函數(shù)值Z=-3/2,2、運(yùn)輸問題的最優(yōu)解 運(yùn)輸問題的求解方法有多種，例如線性規(guī)劃方法、表上作業(yè)法、圖上作業(yè)法等。 1）運(yùn)輸問題 典型背景單一物資運(yùn)輸調(diào)度問題 設(shè)某種物品有: m個(gè)產(chǎn)地： 產(chǎn)量： n個(gè)銷地： 銷量： 從產(chǎn)地 到銷地 的單位運(yùn)價(jià)是 。 求總運(yùn)費(fèi)最小的調(diào)度方案。,產(chǎn)地,銷地,運(yùn)輸問題的原始條件可以用“運(yùn)輸表”表示，運(yùn)輸表有一定的格式，圖下圖所

24、示,運(yùn)輸問題的數(shù)學(xué)模型,由某一產(chǎn)地運(yùn)往各個(gè)銷地的物品數(shù)量之和等于該產(chǎn)地的產(chǎn)量,由各產(chǎn)地運(yùn)往某一銷地的物品數(shù)量之和等于該銷地的銷量,變量非負(fù)條件,目標(biāo)函數(shù)表示運(yùn)輸總費(fèi)用，求極小化,如果 ，即供應(yīng)量等于總需求量，稱該運(yùn) 輸問題為產(chǎn)銷平衡問題。數(shù)學(xué)模型為：,反之稱為產(chǎn)銷不平衡問題： 如果 ，即供應(yīng)量大于總需求量，可增加一個(gè)虛構(gòu)銷售地，令其需求量為 ，數(shù)學(xué)模型為：,如果 ，即供應(yīng)量小于總需求量，可增加一個(gè)虛構(gòu)生產(chǎn)地，令其需求量為 ，數(shù)學(xué)模型為：,2.3 旅行路線問題 1、旅行路線問題表述 一個(gè)有N個(gè)城市組成的一般網(wǎng)絡(luò)，已知任意兩城市之間的直達(dá)距離，尋找一條旅行路線，使其最終回歸到出發(fā)城市，而且每個(gè)城市

25、剛好經(jīng)過一次，問如何規(guī)劃路線才能使總的旅行距離最短？,2、問題求解 1）窮舉法 列出所有可能存在的路線，計(jì)算所有路線的距離，進(jìn)行比較，找出最短的那條路線就是最佳路線，這種方法稱為“窮舉法” 原理：旅行路線問題是從一結(jié)點(diǎn)出發(fā)，經(jīng)過N-1個(gè)結(jié)點(diǎn)后再回到出發(fā)點(diǎn)。N-1個(gè)結(jié)點(diǎn)有（N-1）！種排列方法，因此，旅行路線也有（N-1）！種。只要找出N-1個(gè)結(jié)點(diǎn)的所有排列，計(jì)算所有路線的長度，就能找到最佳路線。,例子：設(shè)從A點(diǎn)出發(fā)，經(jīng)過所有的城市，最終回到A點(diǎn)，求最佳路線。已知各點(diǎn)間的距離 d(A,B)=3，d(A,C)=5，d(A,D)=1，d(A,E)=4，d(B,E)=2，d(B,D)=6,，d(B,C

26、)=1，d(C,E)=4，d(C,D)=5，d(D,E)=6。,A,B,C,D,E,此處，N=5，則（N-1）！=4！=24 則所有的排列方式為： BCDE BCED BDCE BDEC BECD BEDC CBDE CBED CDBE CDEB CEBD CEDB DBCE DBEC DCBE DCEB DEBC DECB EBCD EBDC ECBD ECDB EDBC EDCB 可以計(jì)算每一條線路的距離，找其中最小的即 BCDE=19 BCED=15 BDCE=22 BDEC=24 BECD=15 BEDC=21 CBDE=22 CBED=15 CDBE=22 CDEB=21 CEBD=

27、18 CEDB=24 DBCE=16 DBEC=18 DCBE=13 DCEB=15 DEBC=15 DECB=15 EBCD=13 EBDC=22 ECBD=16 ECDB=22 EDBC=22 EDCB=19 從上述數(shù)據(jù)可知，路線ADCBEA和AEBCDA是最佳路線,2.4 圖論方法的應(yīng)用 1、圖論的基本知識(shí) 圖論是數(shù)學(xué)的一個(gè)分支,以圖為研究對(duì)象。 這種圖由若干給定的點(diǎn)和連接兩點(diǎn)的線構(gòu)成,借以描述某些事物之間的關(guān)系。用點(diǎn)代表事物,用連接兩點(diǎn)的線表示兩個(gè)事物之間具有特定關(guān)系。,（1）圖論的起源 圖論起源于18世紀(jì),追朔到1736年瑞士數(shù)學(xué)家歐拉出版第一本圖論著作,提出和解決著名哥尼斯堡七橋問

28、題。 圖論不僅在許多領(lǐng)域,如計(jì)算機(jī)科學(xué),運(yùn)籌學(xué),心理學(xué)等方面得到了廣泛的應(yīng)用,而且學(xué)科本身也獲得長足發(fā)展,形成了擬陣?yán)碚?超圖理論,代數(shù)圖論,拓?fù)鋱D論等新分支,哥尼斯堡七橋(Knigsberg Bridges)問題,在哥尼斯堡，有七座橋?qū)⑵杖R格爾河中的兩個(gè)島及島與河岸聯(lián)結(jié)起來。問題是要從這四塊陸地中的任何一塊開始通過每一座橋正好一次，再回到起點(diǎn)。 歐拉(Euler)解決了這個(gè)問題。四塊被分開的區(qū)域作為點(diǎn)，連結(jié)它們的橋作為邊將問題用圖表示,（2）圖的基本概念 定義1：圖由點(diǎn)集 和 中元素的無序?qū)Φ囊粋€(gè)集合 所構(gòu)成的二元組，記為 ，中的元素 叫做頂點(diǎn)， 中的元素 叫做邊。 一條邊的兩個(gè)端點(diǎn)如果相同

29、，稱此邊為環(huán)（自回路）。 兩個(gè)點(diǎn)之間多于一條邊的，稱為多重邊。 定義2： 頂點(diǎn)的次：以點(diǎn) 為端點(diǎn)的邊數(shù)叫做點(diǎn) 的次，記作 簡記為 。邊 為環(huán)，邊 為多重邊,次為奇數(shù)的點(diǎn)稱為奇點(diǎn)； 次為偶數(shù)的點(diǎn)稱為偶點(diǎn)； 任何圖中，次為奇數(shù)的頂點(diǎn)必為偶數(shù)個(gè)。 定義3： 鏈：網(wǎng)絡(luò)圖 ，若圖 中某些點(diǎn)與邊的交替序列可以 排成 的形式，且 ，則 稱這個(gè)點(diǎn)邊序列為連接 和 的一條鏈，鏈長為 。 定義4：網(wǎng)絡(luò)圖 中，連接 和 的一條鏈，當(dāng) 和 是同一 個(gè)點(diǎn)時(shí)，稱此鏈為圈 定義5：一個(gè)圖中任意兩點(diǎn)間至少有一條鏈相連，則稱此圖為 連通圖。,2、郵路問題及求解方法 （1）問題表述 中國郵遞員問題（CPPChinese post

30、man problem） 一名郵遞員負(fù)責(zé)投遞某一地區(qū)的郵件。如何為他（她）設(shè)計(jì)一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？ 由于這一問題是我國管梅谷教授1960年首先提出的，所以國際上稱之為中國郵遞員問題。,解法思想： 要把所有路段都走遍，即：一筆畫出經(jīng)過所有路段的連線，這個(gè)連線就是一個(gè)可行解，而總長度最短的連線就是最優(yōu)解。,（2）求解方法 中國郵路問題用圖論的語言描述就是： 給定一個(gè)連通圖G，每邊有非負(fù)權(quán)l(xiāng)(e),要求一條回路過每邊至少一次，且滿足總權(quán)最小。,求解步驟： 1）找出圖中的奇點(diǎn)和偶點(diǎn)。 A、E、I、L、N是偶點(diǎn)，B、C、D、G、H、J、K、M為奇

31、點(diǎn)。 2）奇點(diǎn)個(gè)數(shù)為偶數(shù)個(gè)，因此可兩兩配對(duì)，如D-J、K-G、C-M、B-H。在配對(duì)的兩點(diǎn)之間添加一條弧，使得到的新圖上沒有奇點(diǎn)，如下圖所示：,A,B,C,D,E,G,H,I,L,M,N,2,2,2,2,1,1,1,1,1,1,1,3,2,2,2,2,1,K,J,3)調(diào)整添弧，使每個(gè)圈的添弧總長度不大于圈長度的一半 先看B-C-I-H圈，整圈的總長度為6，而添弧長度為 ，超過整圈長度的一半，需要調(diào)整。 調(diào)整方法：去掉原來的添弧，在未添弧的路段上添弧 即：去掉弧B-H、H-I、C-I，在路段B-C上添弧，如圖所示,K,2,1,A,B,C,D,E,G,H,I,L,M,N,2,2,2,1,1,1,1,1,1,1,3,2,2,2,2,J,4）繼續(xù)檢查調(diào)整 再看圈I-K-N-M，添弧部分的長度為 ，而整圈長度為 ，超過整圈的一半，要繼續(xù)