物流運輸規(guī)劃(完)

1、物流運輸與配送物流運輸與配送管理實務(wù)管理實務(wù)主講：李主講：李 穎穎鄭州大學西亞斯國際學院鄭州大學西亞斯國際學院商學院商學院第第2章章 物流運輸規(guī)劃物流運輸規(guī)劃本章知識結(jié)構(gòu)本章知識結(jié)構(gòu)物物流流運運輸輸規(guī)規(guī)劃劃合理選擇運輸方式合理選擇運輸方式運輸問題與線性規(guī)劃運輸問題與線性規(guī)劃 旅行路線問題旅行路線問題 小結(jié)與案例小結(jié)與案例 圖論方法的應(yīng)用圖論方法的應(yīng)用各種運輸方式的特點各種運輸方式的特點線性規(guī)劃模型及單純形法線性規(guī)劃模型及單純形法旅行路線問題及求解旅行路線問題及求解郵路問題、最小聯(lián)通問郵路問題、最小聯(lián)通問題及各自的求解方法題及各自的求解方法 目前我國最常用的運輸方式有哪些？目前我國最常用的運輸方

2、式有哪些？ 引言 每一個國家的經(jīng)濟地理環(huán)境和工業(yè)化程度不同，運輸方式的構(gòu)成也有差異。例如，在缺乏河流的內(nèi)陸國家，就幾乎沒有水路運輸；在工業(yè)化程度很低的國家，航空運輸?shù)谋壤容^低。就近代運輸業(yè)發(fā)展的一段歷史來看，船舶運輸是較早使用的一種機械運輸方式。1807年，世界上第一艘輪船在北美哈德遜河下水，揭開了機械運輸?shù)男录o元。其后，各種運輸工具相繼問世。1825年，世界上第一條鐵路在英國正式通車，1861年，第一條輸油管道鋪設(shè)；1886年，以汽油為動力的汽車在德國問世。到1903年第一架飛機飛上了藍天。在經(jīng)歷了整整一個世紀后，五種新型運輸工具奠定了以五種運輸方式為基本格局的運輸業(yè)。 2.1 合理選擇運

3、輸方式合理選擇運輸方式一、公路運輸一、公路運輸設(shè)施：公路、公路車站和車輛。設(shè)施：公路、公路車站和車輛。優(yōu)點優(yōu)點：對于小、中批量商品的近距離運輸，運費較便：對于小、中批量商品的近距離運輸，運費較便宜，而且經(jīng)濟；可以做到宜，而且經(jīng)濟；可以做到“門到門門到門”（doorto door)；包裝成本低。包裝成本低。缺點缺點：運輸能力低；單位運費高；易遭偷盜；加劇擁：運輸能力低；單位運費高；易遭偷盜；加劇擁擠與污染擠與污染二、鐵路運輸二、鐵路運輸設(shè)施：鐵路、火車、車站及輔助設(shè)備設(shè)施：鐵路、火車、車站及輔助設(shè)備優(yōu)點優(yōu)點：運載能力較大，適用于大宗貨物的集中、迅速運：運載能力較大，適用于大宗貨物的集中、迅速運

4、輸；中、遠距離運輸時，輸；中、遠距離運輸時，運費比較便宜；受氣運費比較便宜；受氣 候條件的影響較小候條件的影響較??；在軌道上運輸，安全性好；在軌道上運輸，安全性好缺點缺點：靈活性差；對包裝的要求較高；基建成本大。：靈活性差；對包裝的要求較高；基建成本大。 三、水上運輸三、水上運輸 設(shè)施：天然水道、港口和船舶。設(shè)施：天然水道、港口和船舶。優(yōu)點優(yōu)點：高運輸能力；：高運輸能力；低廉的單位運費低廉的單位運費。缺點缺點：速度慢；路線迂回；受天氣影響大，可靠性差：速度慢；路線迂回；受天氣影響大，可靠性差四、航空運輸四、航空運輸 設(shè)施：航空港、飛行器和航管設(shè)施。設(shè)施：航空港、飛行器和航管設(shè)施。 優(yōu)點優(yōu)點：速

5、度快速度快；受地形條件限制小。；受地形條件限制小。 缺點缺點：運輸成本高；運載量有限；受氣候影響大。：運輸成本高；運載量有限；受氣候影響大。 五、管道運輸五、管道運輸 管道是一種集運輸工具和運輸線路于一身的管道是一種集運輸工具和運輸線路于一身的運輸方式。采用管道運輸，貨物憑借高壓氣泵的運輸方式。采用管道運輸，貨物憑借高壓氣泵的壓力在管道內(nèi)移動，到達目的地。壓力在管道內(nèi)移動，到達目的地。 三種形式：液體管道、氣體管道、漿質(zhì)管道。三種形式：液體管道、氣體管道、漿質(zhì)管道。 優(yōu)點優(yōu)點：可全天候工作可全天候工作；不需包裝；單向運輸；單；不需包裝；單向運輸；單位運營成本低。位運營成本低。 缺點缺點：貨物受

6、限；機動靈活性小，初期投資大。：貨物受限；機動靈活性小，初期投資大。運輸方式運輸方式速速度度運運量量運價運價適合貨物適合貨物的特點的特點優(yōu)優(yōu) 點點缺缺 點點航空運輸航空運輸（飛機）最最快快少少最昂最昂貴貴貴重，急貴重，急需，時間需，時間要求緊要求緊速度快，包速度快，包裝簡單裝簡單運費高，有運費高，有重量限制重量限制水路運輸水路運輸（輪船）最最慢慢最最多多最便最便宜宜大宗貨物大宗貨物時間寬松時間寬松價格便宜價格便宜速度慢，受速度慢，受氣候影響大氣候影響大公路運輸公路運輸（汽車）較較慢慢較較少少較貴較貴靈活，量靈活，量少少,路程短路程短靈活，方便靈活，方便（door-to-door）裝載量小，裝載

7、量小，不適合長途不適合長途運輸。運輸。鐵路運輸鐵路運輸（火車）較較快快較較多多較便較便宜宜量大，時量大，時間較緊間較緊安全安全,可靠可靠中轉(zhuǎn)作業(yè)時中轉(zhuǎn)作業(yè)時間長間長管道運輸管道運輸（管道）連連續(xù)續(xù)大大便宜便宜氣體、液氣體、液體、連續(xù)體、連續(xù)性強性強貨損貨差少貨損貨差少，連續(xù)運輸，連續(xù)運輸適用產(chǎn)品較適用產(chǎn)品較少少各種交通運輸方式的比較各種交通運輸方式的比較 在選擇運輸工具的時候，主要考慮的因素：在選擇運輸工具的時候，主要考慮的因素：u運輸數(shù)量：運輸數(shù)量： 1520噸以下的貨物，采用公路運輸；噸以下的貨物，采用公路運輸； 1520噸以上的貨物，采用鐵路運輸；噸以上的貨物，采用鐵路運輸； 數(shù)百噸以上

8、的原材料之類的貨物，應(yīng)選擇水路運輸。數(shù)百噸以上的原材料之類的貨物，應(yīng)選擇水路運輸。u運輸價格：運輸價格：u運輸速度運輸速度 航空最快達到航空最快達到900 1000km/h； 鐵路鐵路80 250 km/h； 公路公路80 120km/h； 水路中的河運水路中的河運820 km/h， 海運每小時海運每小時1030海里。海里。 在選擇運輸工具的時候，主要在選擇運輸工具的時候，主要考慮的因素：考慮的因素：u貨物性質(zhì)貨物性質(zhì)u運輸距離：運輸距離：200公里以內(nèi)，采用公路運輸；公里以內(nèi)，采用公路運輸；200500公里的區(qū)域，采用鐵路運輸；公里的區(qū)域，采用鐵路運輸；500公里以上根據(jù)具體情況采用水路或公

9、里以上根據(jù)具體情況采用水路或航空運輸；航空運輸； u特別要求特別要求運運輸輸方方 式式選選擇擇的的原原則則貴重或急需的貨物（數(shù)量不大）貴重或急需的貨物（數(shù)量不大）航空航空 短途短途公路公路容易死亡、變質(zhì)的容易死亡、變質(zhì)的活物、鮮貨物活物、鮮貨物 長途且數(shù)量大長途且數(shù)量大鐵路鐵路大宗、笨重的貨物（遠距離運輸）大宗、笨重的貨物（遠距離運輸）水運或水運或鐵路鐵路 選擇交通工具：選擇交通工具： 從烏魯木齊到北京去開會，從烏魯木齊到北京去開會，第二天必須趕到。第二天必須趕到。飛機飛機選擇交通工具：選擇交通工具： 暑假從上海到大連旅游，暑假從上海到大連旅游，選擇最經(jīng)濟的辦法。選擇最經(jīng)濟的辦法。海輪海輪選擇

10、交通工具：選擇交通工具： 從重慶到武漢，沿途從重慶到武漢，沿途觀賞三峽風光。觀賞三峽風光。江輪江輪選擇交通工具：選擇交通工具： 從拉薩到西寧，沿途從拉薩到西寧，沿途參觀訪問。參觀訪問。汽車汽車選擇交通工具：選擇交通工具： 從武漢到鄭州探親。從武漢到鄭州探親?；疖嚮疖囘x擇運輸方式選擇運輸方式 貴重或急需的貨物，貴重或急需的貨物，數(shù)量又不大的，多由數(shù)量又不大的，多由 運輸。運輸。航空航空選擇運輸方式選擇運輸方式 容易死亡、變質(zhì)的，容易死亡、變質(zhì)的，活物、鮮貨，短程可由活物、鮮貨，短程可由 運輸。運輸。公路公路選擇運輸方式選擇運輸方式 容易死亡、變質(zhì)的，容易死亡、變質(zhì)的，活物、鮮貨，遠程而又數(shù)活物、

11、鮮貨，遠程而又數(shù)量大的可用量大的可用 運輸。運輸。鐵路鐵路選擇運輸方式選擇運輸方式 大宗笨重的貨物，大宗笨重的貨物，遠距離運輸，盡可能利遠距離運輸，盡可能利用用 或或 運輸。運輸。水運水運鐵路鐵路選擇運輸方式選擇運輸方式 貨物和數(shù)量貨物和數(shù)量 起點至終點起點至終點 鐵路公路鐵路公路 河運海運河運海運 航空航空兩箱急救藥品兩箱急救藥品 北京北京-拉薩拉薩一噸活魚一噸活魚 密云水庫密云水庫-北京北京五十噸鋼材五十噸鋼材 上海上海-濟南濟南一萬噸海鹽一萬噸海鹽 天津天津-上海上海十萬噸大米十萬噸大米 武漢武漢-上海上海 例例2.讀歐洲貨物四種運輸方式運費與運距相關(guān)曲線示意圖，讀歐洲貨物四種運輸方式運

12、費與運距相關(guān)曲線示意圖，回答問題?；卮饐栴}。運距運距80千米時，最廉價的運輸方式是千米時，最廉價的運輸方式是_。 80千米千米運距運距550千米時，最廉價的運輸方式是千米時，最廉價的運輸方式是_。最昂貴的運輸方式是最昂貴的運輸方式是_，它適合運送的貨物特點是它適合運送的貨物特點是_?？傔\價總運價080550距離距離/千米千米空運空運公路公路鐵路鐵路水路水路公路公路鐵路鐵路水運水運空運空運輕型、貴重、急需。輕型、貴重、急需。 某公司有以下運輸業(yè)務(wù)委托你公司進行某公司有以下運輸業(yè)務(wù)委托你公司進行托運，請為其選擇合適的運輸方式并說明理由。托運，請為其選擇合適的運輸方式并說明理由。 1.1.把兩箱急救

13、藥和一批鮮花從廣州運到北京。把兩箱急救藥和一批鮮花從廣州運到北京。 2.2.把一批煤炭從山西運到秦皇島。把一批煤炭從山西運到秦皇島。 3.3.把一批新鮮蔬菜從郊區(qū)運到市區(qū)。把一批新鮮蔬菜從郊區(qū)運到市區(qū)。 4.4.有一批鋼材，要從重慶運到武漢。有一批鋼材，要從重慶運到武漢。 5.5.有有1515萬噸石油需要從非洲運到我國的上海。萬噸石油需要從非洲運到我國的上海。 6.6.把我國西部大量的天然氣運到以上海為主的東把我國西部大量的天然氣運到以上海為主的東部地區(qū)。部地區(qū)。一批鮮花、一批鮮花、兩箱急救藥兩箱急救藥 廣州廣州北京北京 航空、鐵路航空、鐵路 航航 空空（速度快、保鮮）（速度快、保鮮）一批煤炭

14、一批煤炭山西山西秦皇島秦皇島 鐵鐵 路路 鐵鐵 路路（路遠、運量大）（路遠、運量大）新鮮蔬菜新鮮蔬菜 郊區(qū)郊區(qū)市區(qū)市區(qū) 鐵路、公路鐵路、公路 公公 路路（方便、靈活）（方便、靈活）鋼鋼 材材重慶重慶武漢武漢水路、鐵路、公路水路、鐵路、公路 水水 路路（運量大，有河流（運量大，有河流，成本低），成本低） 1515萬噸石油萬噸石油非洲非洲上海上海水運水運+管道管道+公路公路水運水運+公路公路 水運水運+公路公路（實現(xiàn)門到門）（實現(xiàn)門到門）天然氣天然氣 西部西部東部東部管管 道道 管道（特殊性）管道（特殊性） A公司首次承攬到三個集裝箱運輸業(yè)務(wù)，時公司首次承攬到三個集裝箱運輸業(yè)務(wù)，時間較緊，從上海到

15、大連鐵路間較緊，從上海到大連鐵路1200公里，公路公里，公路1500公里，水路公里，水路1000公里。該公司自有公里。該公司自有10輛輛10噸普通卡車和一個自動化立體倉庫，經(jīng)聯(lián)噸普通卡車和一個自動化立體倉庫，經(jīng)聯(lián)系附近一家聯(lián)運公司雖無集裝箱卡車，但卻系附近一家聯(lián)運公司雖無集裝箱卡車，但卻有專業(yè)人才和貨代經(jīng)驗，只是要價比較高。有專業(yè)人才和貨代經(jīng)驗，只是要價比較高。至于零星集裝箱安排、落實車皮和船艙，至于零星集裝箱安排、落實車皮和船艙，A公司實在心中無底，你認為采取什么措施比公司實在心中無底，你認為采取什么措施比較穩(wěn)妥？較穩(wěn)妥？（1）自己購買若干輛集裝箱卡車，然后組織）自己購買若干輛集裝箱卡車，然

16、后組織運輸。運輸。（2）想法請鐵路部門安排運輸）想法請鐵路部門安排運輸（3）水路最短，請航運公司來解決運輸）水路最短，請航運公司來解決運輸（4）聯(lián)運公司雖無集卡，但可叫其租車完成）聯(lián)運公司雖無集卡，但可叫其租車完成此項運輸此項運輸（5）沒有合適的運輸工具，辭掉該項業(yè)務(wù)）沒有合適的運輸工具，辭掉該項業(yè)務(wù)分析要點：分析要點：1）以請聯(lián)運公司來承擔此項任務(wù)為好，比較）以請聯(lián)運公司來承擔此項任務(wù)為好，比較穩(wěn)妥，聯(lián)運公司是第三方物流服務(wù)企業(yè)穩(wěn)妥，聯(lián)運公司是第三方物流服務(wù)企業(yè)2）第三方物流服務(wù)供應(yīng)商，根據(jù)是夠擁有資）第三方物流服務(wù)供應(yīng)商，根據(jù)是夠擁有資產(chǎn)可分為產(chǎn)可分為資產(chǎn)基礎(chǔ)供應(yīng)商資產(chǎn)基礎(chǔ)供應(yīng)商和和非資產(chǎn)

17、基礎(chǔ)供應(yīng)非資產(chǎn)基礎(chǔ)供應(yīng)商商。我們選擇的。我們選擇的標準絕不是它有無實際的物標準絕不是它有無實際的物流資產(chǎn)而是看專業(yè)人才和貨代經(jīng)驗流資產(chǎn)而是看專業(yè)人才和貨代經(jīng)驗，有資產(chǎn)，有資產(chǎn)的物流供應(yīng)商價格可能低些，但靈活性差；的物流供應(yīng)商價格可能低些，但靈活性差；而非資產(chǎn)基礎(chǔ)供應(yīng)商，則可根據(jù)不同需要而非資產(chǎn)基礎(chǔ)供應(yīng)商，則可根據(jù)不同需要“量體裁衣量體裁衣”，非常靈活，非常靈活3）邀請第三方物流服務(wù)供應(yīng)商，應(yīng)該做好如下工作）邀請第三方物流服務(wù)供應(yīng)商，應(yīng)該做好如下工作（1）對該聯(lián)運公司做必要調(diào)查，看看信譽度如何。）對該聯(lián)運公司做必要調(diào)查，看看信譽度如何。（2）進行必要的合同磋商，解決好合同的執(zhí)行標準、）進行必要的

18、合同磋商，解決好合同的執(zhí)行標準、衡量標準、違約責任以及價格衡量標準、違約責任以及價格（3）努力避免雙方合作失敗，既交貨又派專人關(guān)心）努力避免雙方合作失敗，既交貨又派專人關(guān)心此事此事（4）講明如果服務(wù)質(zhì)量好，可考慮長期合作的可能性。）講明如果服務(wù)質(zhì)量好，可考慮長期合作的可能性。其他方案欠穩(wěn)妥，無把握，風險很大其他方案欠穩(wěn)妥，無把握，風險很大案例啟示：案例啟示：企業(yè)生存與發(fā)展的不二法門就是盈利，但企業(yè)生存與發(fā)展的不二法門就是盈利，但是對于企業(yè)即將開展的新業(yè)務(wù)或相關(guān)業(yè)務(wù)是對于企業(yè)即將開展的新業(yè)務(wù)或相關(guān)業(yè)務(wù)來說，盈利的同時，經(jīng)驗和長期客戶的開來說，盈利的同時，經(jīng)驗和長期客戶的開發(fā)維護也是很重要的發(fā)維護

19、也是很重要的 6、幾種特殊的運輸方式幾種特殊的運輸方式 1、集裝箱運輸、集裝箱運輸1）概念）概念 集裝箱是一個集裝箱是一個大型的、標準化的、能反復大型的、標準化的、能反復使用使用的載貨容器。的載貨容器。 集裝箱運輸就是以集裝箱作為一個貨物集集裝箱運輸就是以集裝箱作為一個貨物集合單元進行運輸?shù)囊环N運輸方式。合單元進行運輸?shù)囊环N運輸方式。標準集裝箱標準集裝箱側(cè)開門集裝箱側(cè)開門集裝箱側(cè)開雙門集裝箱側(cè)開雙門集裝箱全側(cè)開門集裝箱全側(cè)開門集裝箱開頂散貨集裝箱開頂散貨集裝箱冷藏集裝箱冷藏集裝箱 提高裝卸效率，減輕勞動強度提高裝卸效率，減輕勞動強度 減少了裝卸所需要的時間和費用，加速了車船周轉(zhuǎn)減少了裝卸所需要

20、的時間和費用，加速了車船周轉(zhuǎn) 保證貨物完整無損，避免貨損貨差保證貨物完整無損，避免貨損貨差 節(jié)省包裝費用，簡化理貨手續(xù)節(jié)省包裝費用，簡化理貨手續(xù) 減少營運費用，降低運輸成本減少營運費用，降低運輸成本 3 3）集裝箱運輸?shù)娜毕荩┘b箱運輸?shù)娜毕?集裝箱運輸需要大量的初始投資集裝箱運輸需要大量的初始投資 建立新的管理體制、形成新的管理人員隊伍建立新的管理體制、形成新的管理人員隊伍 增加了一些潛在的不安全因素增加了一些潛在的不安全因素 英國擱淺貨輪納波利號散落貨物 4）開展集裝箱運輸?shù)臈l件）開展集裝箱運輸?shù)臈l件 要有穩(wěn)定的貨源和經(jīng)濟腹地要有穩(wěn)定的貨源和經(jīng)濟腹地 要有良好的港口條件（深水港）和基礎(chǔ)設(shè)施

21、（如裝卸）要有良好的港口條件（深水港）和基礎(chǔ)設(shè)施（如裝卸） 較為發(fā)達的內(nèi)陸運輸系統(tǒng)較為發(fā)達的內(nèi)陸運輸系統(tǒng) 高素質(zhì)的經(jīng)營管理者高素質(zhì)的經(jīng)營管理者 2、托盤運輸托盤運輸 1）概念：概念： 托盤（托盤（ pallet）是用于集裝、堆放、搬運和運輸?shù)姆胖檬怯糜诩b、堆放、搬運和運輸?shù)姆胖米鳛閱卧摵傻呢浳锖椭破返乃狡脚_裝置。作為單元負荷的貨物和制品的水平平臺裝置。 托盤運輸是貨物按照托盤運輸是貨物按照一定要求成組一定要求成組裝在一個標準托盤裝在一個標準托盤上組合成為上組合成為一個運輸單位一個運輸單位并便于并便于利用鏟車或托盤利用鏟車或托盤升降進行裝升降進行裝卸、搬運和堆存的一種運輸方式，它是卸、搬運

22、和堆存的一種運輸方式，它是成組運輸?shù)某跫壭螒B(tài)成組運輸?shù)某跫壭螒B(tài)。 2）托盤運輸?shù)奶攸c）托盤運輸?shù)奶攸c （1）提高運輸效率提高運輸效率 搬運或出入庫場都可用機械操作，減少貨物堆碼作業(yè)，從而有利于提高運輸效率，縮短貨運時間，減少勞動強度。（2）便于理貨，減少貨損貨差便于理貨，減少貨損貨差 以托盤為運輸單位，貨物件數(shù)變少體積重量變大，而且每個托盤所裝數(shù)量相等。既便于點數(shù)、理貨交接，又可以減少貨損貨差事故。（3）投資比較小，收效比較快。）投資比較小，收效比較快。（4）托盤的回收利用，組織工作難度較大，會）托盤的回收利用，組織工作難度較大，會浪費一部分運力。浪費一部分運力。 3）托盤運輸具有一定的局限性

23、，表現(xiàn)在以下幾）托盤運輸具有一定的局限性，表現(xiàn)在以下幾方面：方面： 1、托盤承運的貨物范圍有限、托盤承運的貨物范圍有限 最適合托盤運輸?shù)呢浳锸窍溲b罐頭食品、硬紙盒裝的消費品和袋及袋裝的貨物等比較小的包裝商品。 大的、形狀不一的家具、機械以及散裝冷凍等貨物，不適合于采用托盤進行運輸 2、托盤運輸設(shè)備費用減少，但要增加托盤運、托盤運輸設(shè)備費用減少，但要增加托盤運輸費用。同時，由于增加了托盤的重量和體積輸費用。同時，由于增加了托盤的重量和體積，相應(yīng)地減少了運輸工具的載量。，相應(yīng)地減少了運輸工具的載量。 3、托盤運輸向成組運輸前進了一步，但它的、托盤運輸向成組運輸前進了一步，但它的效果還不足以改變傳統(tǒng)

24、的流通方式，特別是不效果還不足以改變傳統(tǒng)的流通方式，特別是不能滿足國際多式聯(lián)運的要求。能滿足國際多式聯(lián)運的要求。 例如，它不能像集裝箱那樣，可以密封越過國境或快速轉(zhuǎn)換各種運輸方式。 4）采用托盤運輸應(yīng)該注意的事項）采用托盤運輸應(yīng)該注意的事項 1、裝載托盤貨物的范圍有一定限制，不是所有貨、裝載托盤貨物的范圍有一定限制，不是所有貨物都可以用托盤運輸。物都可以用托盤運輸。 2、必須符合托盤積載的規(guī)定。、必須符合托盤積載的規(guī)定。 3、每一托盤貨載，必須捆扎牢固具有足夠的強度、每一托盤貨載，必須捆扎牢固具有足夠的強度和穩(wěn)定，平衡。和穩(wěn)定，平衡。 既能夠承受一般海上風險，經(jīng)受裝卸操作和移動，也能夠在其上面

25、承受一定的壓力。 4、貨物以托盤運輸時，必須在所有運輸單證上注、貨物以托盤運輸時，必須在所有運輸單證上注明明“托盤運輸托盤運輸”字樣字樣。 3、散裝運輸散裝運輸 1）含義含義： 散裝運輸是指產(chǎn)品不帶包裝的運輸，是用專用散裝運輸是指產(chǎn)品不帶包裝的運輸，是用專用設(shè)備將產(chǎn)品直接由生產(chǎn)廠方送至用戶使用的運輸方設(shè)備將產(chǎn)品直接由生產(chǎn)廠方送至用戶使用的運輸方式。式。 2）優(yōu)點）優(yōu)點： ）節(jié)省包裝材料和費用，減少貨損）節(jié)省包裝材料和費用，減少貨損 ）減少工作環(huán)節(jié)，提高機械化、自動化程度）減少工作環(huán)節(jié)，提高機械化、自動化程度 4、國際多式聯(lián)運、國際多式聯(lián)運 1 1）含義：）含義： 國際多式聯(lián)運是指按照國際多式聯(lián)

26、運是指按照多式聯(lián)運合同多式聯(lián)運合同,以以至少至少兩種不同的運輸方式兩種不同的運輸方式，由，由多式聯(lián)運經(jīng)營人多式聯(lián)運經(jīng)營人將貨物從將貨物從一國境內(nèi)一國境內(nèi)接管貨物的地點運至接管貨物的地點運至另一國境內(nèi)另一國境內(nèi)指定交付指定交付貨物的地點。貨物的地點。2）特征：）特征：（1）必須訂立多式聯(lián)運合同）必須訂立多式聯(lián)運合同（1）多式聯(lián)運合同：是指多式聯(lián)運經(jīng)營人憑其收取全程運費，使用兩種或兩種以上不同運輸工具，負責組織完成貨物全程運輸?shù)暮贤?。?）托運人只與MTO有業(yè)務(wù)和法律上的關(guān)系。（托運人與各區(qū)段實際承運人不發(fā)生任何業(yè)務(wù)和法律上的關(guān)系）（2）必須由多式聯(lián)運經(jīng)營人對全程運輸負責）必須由多式聯(lián)運經(jīng)營人對全

27、程運輸負責（3）必須是兩種或兩種以上不同運輸方式組成的連貫）必須是兩種或兩種以上不同運輸方式組成的連貫運輸。運輸。（5）必須簽發(fā)多式聯(lián)運單據(jù)）必須簽發(fā)多式聯(lián)運單據(jù)（1）MTO在接管貨物后簽發(fā)多式聯(lián)運單據(jù)（2）從發(fā)貨地到收貨地，一單到底（3）發(fā)貨人憑多式聯(lián)運單據(jù)向銀行結(jié)匯。（4）收貨人憑多式聯(lián)運單據(jù)向MTO或代理提貨。（6）必須是單一的運費率）必須是單一的運費率3）優(yōu)點：）優(yōu)點：（）手續(xù)簡便，可以做到一次性托運，一（）手續(xù)簡便，可以做到一次性托運，一次性付費，一次性投保，一單到底，統(tǒng)一次性付費，一次性投保，一單到底，統(tǒng)一理賠，全程負責理賠，全程負責（）安全可靠（）安全可靠（）統(tǒng)一理賠（）統(tǒng)一理賠

28、（）可以實現(xiàn)門門運輸（）可以實現(xiàn)門門運輸（）具有單一運費率（）具有單一運費率案例 2004年年10月月4日，原告日，原告A公司作為買方與溫公司作為買方與溫州市進出口公司州市進出口公司B簽訂一份售貨確認書，購買一簽訂一份售貨確認書，購買一批童裝，數(shù)量批童裝，數(shù)量500箱，總價為箱，總價為68180美元。美元。2005年年2月月11日，日，B公司以托運人身份將該批童裝裝公司以托運人身份將該批童裝裝于兩個于兩個20尺標箱內(nèi)，交由多式聯(lián)運經(jīng)營人尺標箱內(nèi)，交由多式聯(lián)運經(jīng)營人C承運承運。C公司簽發(fā)了號碼為公司簽發(fā)了號碼為RS95040的一式三份正的一式三份正本全程多式聯(lián)運提單。本全程多式聯(lián)運提單。 A公司

29、提貨時箱子外觀完好，打開箱子發(fā)現(xiàn)公司提貨時箱子外觀完好，打開箱子發(fā)現(xiàn)其中一個箱子是空的。另一個箱子貨物被擠壓而其中一個箱子是空的。另一個箱子貨物被擠壓而無法按正常價值出售。無法按正常價值出售。 問：多式聯(lián)運人是否承擔賠償責任。問：多式聯(lián)運人是否承擔賠償責任。解答：解答： 集裝箱貨物的真實性問題。根據(jù)國際集裝箱貨物的真實性問題。根據(jù)國際航運慣例，在集裝箱運輸方式中，由托運航運慣例，在集裝箱運輸方式中，由托運人負責裝箱的貨物，從裝箱托運后至交付人負責裝箱的貨物，從裝箱托運后至交付收貨人時的期間內(nèi)，如集裝箱箱體和封志收貨人時的期間內(nèi)，如集裝箱箱體和封志完好，貨物損壞或短缺，由托運人負責；完好，貨物損

30、壞或短缺，由托運人負責；如箱體損壞或封志破壞，箱內(nèi)貨物損壞或如箱體損壞或封志破壞，箱內(nèi)貨物損壞或短缺，由承運人負責。短缺，由承運人負責。 2.2 運輸問題與線性規(guī)劃運輸問題與線性規(guī)劃1、線性規(guī)劃模型及求解方法 1）線性規(guī)劃問題的數(shù)學表達式）線性規(guī)劃問題的數(shù)學表達式 線性規(guī)劃問題一般可以表示如下：線性規(guī)劃問題一般可以表示如下：稱為線性規(guī)劃問題的稱為線性規(guī)劃問題的標準形式標準形式（其中右端常數(shù)（其中右端常數(shù)b1，b2，bm0）。）。 ), 1(0), 1(. .)(min11njxmibxatsxcxfjnjijijnjjj變換一般變換一般LPLP為標準形式的方法：為標準形式的方法：（1 1）如果

31、原問題目標函數(shù)求極大值）如果原問題目標函數(shù)求極大值： 令令z1=z，轉(zhuǎn)化為求極小值。，轉(zhuǎn)化為求極小值。（2）若某個右端常數(shù)若某個右端常數(shù)bi0 則以則以1乘該約束兩端。乘該約束兩端。（3）若某約束為若某約束為“”型的不等式約束型的不等式約束， 則在左端加上一個非負變量，稱為松弛變量，使不則在左端加上一個非負變量，稱為松弛變量，使不等式化為等式；等式化為等式； 若某約束為若某約束為“”型型， 則在左端減去一個非負變量，稱為剩余變量，或者仍則在左端減去一個非負變量，稱為剩余變量，或者仍然稱為松弛變量，使不等式轉(zhuǎn)化為等式。（目標函數(shù)不變?nèi)环Q為松弛變量，使不等式轉(zhuǎn)化為等式。（目標函數(shù)不變（4）若某個若

32、某個xj的符號約束為的符號約束為xj0； 那么令那么令xj=xj，則，則xj0； 若某個若某個xj無符號限制無符號限制， 令令xj=xjxj，其中，其中xj0，xj0。（目標函數(shù)變）。（目標函數(shù)變） 2）單純形法）單純形法 單純形表單純形表jcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11mnmmnmaaaa1,11, 110010 0jijijcacj E單位陣單位陣 N非基陣非基陣基變量基變量XB非基變量非基變量XN檢驗數(shù)檢驗數(shù)基可行解基可行解 單純形法單純形法 單純形法的求解過程就是對單純形表的變換過程，其步單純形法的求解過程就是對單純形表的變換過程，其步

33、驟為：驟為：（1）求初始基可行解，列出初始單純形表）求初始基可行解，列出初始單純形表（2）最優(yōu)性檢驗：）最優(yōu)性檢驗： 若所有檢驗數(shù)若所有檢驗數(shù) ，則表中基可行解即為最優(yōu)解，計算，則表中基可行解即為最優(yōu)解，計算結(jié)束；結(jié)束； 若存在若存在 ，則選最大者，則選最大者 所對應(yīng)的變量所對應(yīng)的變量 為入基變量，為入基變量，轉(zhuǎn)步驟（轉(zhuǎn)步驟（3）（3）檢查單純形表的第）檢查單純形表的第K列。列。 若無正值，則為無界解；若無正值，則為無界解； 若有一個以上的正值，按最小比值法若有一個以上的正值，按最小比值法 確定出基變量確定出基變量（4）用對角頂點法對單純形表進行變換）用對角頂點法對單純形表進行變換（5）返回步

34、驟（）返回步驟（2）進行迭代）進行迭代 0j0jkkxlklikikiabaab0minlx 對角頂點法：對角頂點法： 如下圖所示，矩形的四個頂點分別對應(yīng)四個元素：如下圖所示，矩形的四個頂點分別對應(yīng)四個元素：D1、D2、D3、D4，若，若D1為需要變換的元素，它的對角元素是交叉為需要變換的元素，它的對角元素是交叉元素元素D3 ，另兩個對角元素為，另兩個對角元素為D2和和D4 。 對角頂點法就是：第對角頂點法就是：第i行第行第j列的元素新值列的元素新值D1為舊值為舊值D1減去兩個對角元素減去兩個對角元素D2、 D4乘積除以交叉元素乘積除以交叉元素D3所得的值所得的值 即：即： D1= D1- D

35、2 * D4 / D3D4D1D3主列主列j列列i行行主行主行D2 若對第對第i行第行第j列的元素列的元素7進行變換，則變進行變換，則變換過程為：換過程為： 變換后第變換后第i行第行第j列的元素為：列的元素為： 7-3*2/8=25/43278主列主列j列列i行行主行主行 變換單純形表：變換單純形表： 首先，將首先，將 行的元素除以交叉元素，行的元素除以交叉元素， 即即 變換后的交叉元素變換后的交叉元素 然后，其他行的元素（除然后，其他行的元素（除k列）按對角頂點法變列）按對角頂點法變換換 最后，把最后，把k列（不含交叉）元素變?yōu)榱校ú缓徊妫┰刈優(yōu)?，即，即 單純形變換結(jié)束單純形變換結(jié)束

36、l1, 3 , 2 , 1mnjaaalkljlj1lkaliaik , 0 例：求解下列線性規(guī)劃問題例：求解下列線性規(guī)劃問題3 , 2 , 1, 093124. .3)(min3232132131jxxxxxxxxxtsxxxfj7 , 2 , 1, 093124. .003)(min732653214321765431jxxxxxxxxxxxxxt sMxMxxxxxxfj解：加入變量解：加入變量 ，則問題變換為如下形式，則問題變換為如下形式7654,xxxx5 , 2 , 1, 093124. .003)(min32532143215431jxxxxxxxxxxxt sxxxxxfj 3

37、 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 正檢驗數(shù)中最大者對正檢驗數(shù)中最大者對應(yīng)的列為主列應(yīng)的列為主列主元素化為主元素化為1, 向量向量換入換入, 換出換出 jcBCBXb764xxx1x2x3x4x5x6x7x 4 1 32x6xminmax表表1：列初始單純形表：列初始單純形表 （單位矩陣對應(yīng)的變量為基變量）（單位矩陣對應(yīng)的變量為基變量）最小的值對應(yīng)最小的值對應(yīng)的行為主行的行為主行 3 0 -1 0 0 M M 0 4 1 1 1 1 0 0

38、 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 jcBCBXb764xxx1x2x3x4x5x6x7xminmax變換為：4-1*1=33 1 -2 1 -1 0 -1 1 06變換為：9-1*3=6變換為：1-1*(-2)=33變換為：1-1*(-1)=22變換為：1-1*0=11變換為：0-1*(-1)=11變換為：0-1*1=-1-1變換為：0-1*0=00變換為：0-(-2)*3=66變換為：1-(-1)*3=44變換為：0-0*3=00變換為：0-(-1)*3=33變換為：0-1*3=-3-3變換為

39、：1-0*3=116M 6M 4M 4M 0 3M -4M 0 -3 +1000 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 正檢驗數(shù)中最大者對正檢驗數(shù)中最大者對應(yīng)的列為主列應(yīng)的列為主列主元素化為1, 向量換入, 換出 jcBCBXb724xxx1x2x3x4x5x6x7x 1 - 11x7xminmax表表2：換基：換基（對角頂點法，主列化為單位向量，主元為（對角頂點法，主列化為單位向量，主元為1）最小的值對應(yīng)最小的值對應(yīng)的行為主行的行

40、為主行 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 正檢驗數(shù)中最大者對正檢驗數(shù)中最大者對應(yīng)的列為主列應(yīng)的列為主列主元素化為1, 向量換入, 換出 jcBCBXb124xxx1x2x3x4x5x6x7x - 9 3/23x1xminmax表表3：換基：換基（對角頂點法對角頂點法，主列化為單位向量，主元為主列化為單位向量，主元為1 1）最小的值對應(yīng)最小的值對應(yīng)的行為主行的行為主行 3 0 -1 0 0

41、M M 0 0 0 0 0 1 -1/2 1/2 -1/2 0 5/2 -1/2 1 0 0 -1/4 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 jcBCBXb324xxx1x2x3x4x5x6x7xmaxmax表表4：換基：換基（對角頂點法，主列化為單位向量，主元為對角頂點法，主列化為單位向量，主元為1 1）最優(yōu)解為X=(0,5/2,3/2)目標函數(shù)值Z=-3/2 2、運輸問題的最優(yōu)解、運輸問題的最優(yōu)解 運輸問題的求解方法有多種，例如線性規(guī)劃方法、表上運輸問題的求解方法有多種，例如線性

42、規(guī)劃方法、表上作業(yè)法、圖上作業(yè)法等。作業(yè)法、圖上作業(yè)法等。1）運輸問題）運輸問題 典型背景典型背景單一物資運輸調(diào)度問題單一物資運輸調(diào)度問題 設(shè)某種物品有設(shè)某種物品有: m個產(chǎn)地：個產(chǎn)地： 產(chǎn)量：產(chǎn)量： n個銷地：個銷地： 銷量：銷量： 從產(chǎn)地從產(chǎn)地 到銷地到銷地 的單位運價是的單位運價是 。 求總運費最小的調(diào)度方案。求總運費最小的調(diào)度方案。nBBB,21mAAA,21maaa,21nbbb,21iAjBijc產(chǎn)量產(chǎn)量銷量銷量1A2AmA1B2BnB產(chǎn)地產(chǎn)地銷地銷地nb1b2b1a2ama11c21c1mc12c22c2mcnc1nc2mnc 運輸問題的原始條件可以用運輸問題的原始條件可以用“運

43、輸表運輸表”表表示，運輸表有一定的格式，圖下圖所示示，運輸表有一定的格式，圖下圖所示 njmixnjbxmiaxxcxfijjmiijinjijminjijij,2,1,2,1,0,2,1,2,1,min1111）（運輸問題的數(shù)學模型運輸問題的數(shù)學模型由某一產(chǎn)地運往各個銷地的物由某一產(chǎn)地運往各個銷地的物品數(shù)量之和等于該產(chǎn)地的產(chǎn)量品數(shù)量之和等于該產(chǎn)地的產(chǎn)量由各產(chǎn)地運往某一銷地的物品由各產(chǎn)地運往某一銷地的物品數(shù)量之和等于該銷地的銷量數(shù)量之和等于該銷地的銷量變量非負條件變量非負條件目標函數(shù)表示運輸總費目標函數(shù)表示運輸總費用，求極小化用，求極小化jiba如果如果 ，即供應(yīng)量等于總需求量，稱該運，即供應(yīng)

44、量等于總需求量，稱該運輸問題為產(chǎn)銷平衡問題。數(shù)學模型為：輸問題為產(chǎn)銷平衡問題。數(shù)學模型為： njmixnjbxmiaxxcxfijjmiijinjijminjijij,2,1,2,1,0,2,1,2,1,min1111）（ 反之稱為反之稱為產(chǎn)銷不平衡問題產(chǎn)銷不平衡問題： 如果如果 ，即供應(yīng)量大于總需求量，可增加一，即供應(yīng)量大于總需求量，可增加一個虛構(gòu)銷售地，令其需求量為個虛構(gòu)銷售地，令其需求量為 ，數(shù)學，數(shù)學模型為：模型為：jibajinbab1 njmixnjbxmiaxxcxfijjmiijinjijminjijij,2,1,2,1,0,2,1,2,1,min1111）（11,2,1,2,

45、1,0,2,1,2,1,min111111 njmixnjbxmiaxxcxfijjmiijinjijminjijij）（ 如果如果 ，即供應(yīng)量小于總需求量，可增加一，即供應(yīng)量小于總需求量，可增加一個虛構(gòu)生產(chǎn)地，令其需求量為個虛構(gòu)生產(chǎn)地，令其需求量為 ，數(shù)學模，數(shù)學模型為：型為：jibaijmaba1 njmixnjbxmiaxxcxfijjmiijinjijminjijij,2,1,2,1,0,2,1,2,1,min1111）（ njmixnjbxmiaxxcxfijjmiijinjijminjijij,2,11,2,1,0,2,1,1,2,1,min111111）（ 2.3 旅行路線問題旅

46、行路線問題1、旅行路線問題表述、旅行路線問題表述 一個有一個有N個城市組成的一般網(wǎng)絡(luò)，已知任意兩個城市組成的一般網(wǎng)絡(luò)，已知任意兩城市之間的直達距離，尋找一條旅行路線，使其最城市之間的直達距離，尋找一條旅行路線，使其最終回歸到出發(fā)城市，而且每個城市剛好經(jīng)過一次，終回歸到出發(fā)城市，而且每個城市剛好經(jīng)過一次，問如何規(guī)劃路線才能使總的旅行距離最短？問如何規(guī)劃路線才能使總的旅行距離最短？ 2、問題求解、問題求解 1）窮舉法）窮舉法 列出所有可能存在的路線，計算所有路線的距離，進列出所有可能存在的路線，計算所有路線的距離，進行比較，找出最短的那條路線就是最佳路線，這種方法稱為行比較，找出最短的那條路線就是

47、最佳路線，這種方法稱為“窮舉法窮舉法” 原理：原理：旅行路線問題是從一結(jié)點出發(fā)，經(jīng)過旅行路線問題是從一結(jié)點出發(fā)，經(jīng)過N-1個結(jié)點后再回個結(jié)點后再回到出發(fā)點。到出發(fā)點。N-1個結(jié)點有（個結(jié)點有（N-1）！種排列方法，因此，旅）！種排列方法，因此，旅行路線也有（行路線也有（N-1）！種。只要找出）！種。只要找出N-1個結(jié)點的所有排列，個結(jié)點的所有排列，計算所有路線的長度，就能找到最佳路線。計算所有路線的長度，就能找到最佳路線。例子：設(shè)從例子：設(shè)從A點出發(fā)，經(jīng)過所有的城市，最終回到點出發(fā)，經(jīng)過所有的城市，最終回到A點，求最點，求最佳路線。已知各點間的距離佳路線。已知各點間的距離 d(A,B)=3，d

48、(A,C)=5，d(A,D)=1，d(A,E)=4，d(B,E)=2，d(B,D)=6,，d(B,C)=1，d(C,E)=4，d(C,D)=5，d(D,E)=6。 ABCDE 此處，此處，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可以計算每一條線路的距離，找其中最小的即可以計算每一條線路的距離，找其中最小的即BCD

49、E=19 BCED=15 BDCE=22 BDEC=24 BECD=15BEDC=21 CBDE=22 CBED=15 CDBE=22 CDEB=21 CEBD=18 CEDB=24 DBCE=16 DBEC=18 DCBE=13DCEB=15 DEBC=15 DECB=15 EBCD=13 EBDC=22ECBD=16 ECDB=22 EDBC=22 EDCB=19從上述數(shù)據(jù)可知，路線從上述數(shù)據(jù)可知，路線ADCBEA和和AEBCDA是最佳路線是最佳路線 2.4 圖論方法的應(yīng)用圖論方法的應(yīng)用 1、圖論的基本知識、圖論的基本知識 圖論圖論是數(shù)學的一個分支是數(shù)學的一個分支, ,以圖為研究對象。以圖

50、為研究對象。 這種圖由若干給定的這種圖由若干給定的點點和連接兩點的和連接兩點的線線構(gòu)成構(gòu)成, ,借以描述某些事物之間的關(guān)系借以描述某些事物之間的關(guān)系。用點代表事物。用點代表事物, ,用用連接兩點的線表示兩個事物之間具有特定關(guān)系。連接兩點的線表示兩個事物之間具有特定關(guān)系。 （1 1）圖論的起源）圖論的起源 圖論起源于圖論起源于1818世紀世紀, ,追朔到追朔到17361736年瑞士數(shù)學家年瑞士數(shù)學家歐拉出版第一本圖論著作歐拉出版第一本圖論著作, ,提出和解決著名提出和解決著名哥尼斯哥尼斯堡七橋堡七橋問題問題。 圖論不僅在許多領(lǐng)域圖論不僅在許多領(lǐng)域, ,如計算機科學如計算機科學, ,運籌學運籌學,

51、 ,心理學等方面得到了廣泛的應(yīng)用心理學等方面得到了廣泛的應(yīng)用, ,而且學科本身也而且學科本身也獲得長足發(fā)展獲得長足發(fā)展, ,形成了擬陣理論形成了擬陣理論, ,超圖理論超圖理論, ,代數(shù)圖代數(shù)圖論論, ,拓撲圖論等新分支拓撲圖論等新分支哥尼斯堡七橋哥尼斯堡七橋(Knigsberg Bridges)問題問題 在哥尼斯堡，有七座橋?qū)⑵杖R格爾河中的兩個島及島與在哥尼斯堡，有七座橋?qū)⑵杖R格爾河中的兩個島及島與河岸聯(lián)結(jié)起來。問題是要從這四塊陸地中的任何一塊開始通河岸聯(lián)結(jié)起來。問題是要從這四塊陸地中的任何一塊開始通過每一座橋正好一次，再回到起點。過每一座橋正好一次，再回到起點。 歐歐拉拉(Euler)解決了

52、這個問題。四塊被分開的區(qū)域作為點，解決了這個問題。四塊被分開的區(qū)域作為點，連結(jié)它們的橋作為邊將問題用圖表示連結(jié)它們的橋作為邊將問題用圖表示（2）圖的基本概念）圖的基本概念 定義定義1：圖圖由點集由點集 和和 中元素的無序?qū)Φ囊粋€集合中元素的無序?qū)Φ囊粋€集合 所構(gòu)成的二元組，記為所構(gòu)成的二元組，記為 ，中的元素，中的元素 叫做頂點，叫做頂點， 中的元素中的元素 叫做邊。叫做邊。 一條邊的兩個端點如果相同，稱此邊為一條邊的兩個端點如果相同，稱此邊為環(huán)環(huán)（自回路）。（自回路）。 兩個點之間多于一條邊的，稱為兩個點之間多于一條邊的，稱為多重邊多重邊。 定義定義2： 頂點的次頂點的次：以點：以點 為端點

53、的邊數(shù)叫做點為端點的邊數(shù)叫做點 的次，記作的次，記作 簡記為簡記為 。邊。邊 為環(huán)，邊為環(huán)，邊 為多重邊為多重邊 ivV keE EVG,VEivkeVvv)deg(v)(vd4)(1)(1)(4)(4321vdvdvdvd5e43,ee 次為奇數(shù)的點稱為次為奇數(shù)的點稱為奇點奇點； 次為偶數(shù)的點稱為次為偶數(shù)的點稱為偶點偶點； 任何圖中，次為奇數(shù)的頂點必為偶數(shù)個。任何圖中，次為奇數(shù)的頂點必為偶數(shù)個。定義定義3： 鏈鏈：網(wǎng)絡(luò)圖：網(wǎng)絡(luò)圖 ，若圖，若圖 中某些點與邊的交替序列可中某些點與邊的交替序列可以以排成排成 的形式，且的形式，且 ，則，則稱這個點邊序列為連接稱這個點邊序列為連接 和和 的一條鏈，

54、鏈長為的一條鏈，鏈長為 。定義定義4：網(wǎng)絡(luò)圖：網(wǎng)絡(luò)圖 中，連接中，連接 和和 的一條鏈，當?shù)囊粭l鏈，當 和和 是同一是同一 個點時，稱此鏈為個點時，稱此鏈為圈圈定義定義5：一個圖中任意兩點間至少有一條鏈相連，則稱此圖為：一個圖中任意兩點間至少有一條鏈相連，則稱此圖為 連通圖連通圖。EVG,kkkiiiiiiivevevev,12110Gktvvetttiii, 1,10ivkivkG0ivkiv0ivkiv 2、郵路問題及求解方法、郵路問題及求解方法 （1）問題表述）問題表述 中國郵遞員問題（中國郵遞員問題（CPPChinese postman problem） 一名郵遞員負責投遞某一地區(qū)的郵

55、件。如何為他（她）一名郵遞員負責投遞某一地區(qū)的郵件。如何為他（她）設(shè)計一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條設(shè)計一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？街道至少一次，最后返回郵局）？ 由于這一問題是我國管梅谷教授由于這一問題是我國管梅谷教授1960年首先提出的，年首先提出的，所以國際上稱之為中國郵遞員問題。所以國際上稱之為中國郵遞員問題。 解法思想：解法思想： 要把所有路段都走遍，即：要把所有路段都走遍，即：一筆畫出經(jīng)過所有路段的一筆畫出經(jīng)過所有路段的連線，這個連線就是一個連線，這個連線就是一個可行解，而總長度最短的可行解，而總長度最短的連線就是

56、最優(yōu)解。連線就是最優(yōu)解。ABCDEGHILMN22221111111322221K（2）求解方法）求解方法 中國郵路問題用圖論的語言描述就是：中國郵路問題用圖論的語言描述就是： 給定一個連通圖給定一個連通圖G，每邊有非負權(quán)，每邊有非負權(quán)l(xiāng)(e),要求一條回路過每要求一條回路過每邊至少一次，且滿足總權(quán)最小。邊至少一次，且滿足總權(quán)最小。 求解步驟：求解步驟：1）找出圖中的奇點和偶點找出圖中的奇點和偶點。A、E、I、L、N是偶點，是偶點，B、C、D、G、H、J、K、M為奇點。為奇點。2）奇點個數(shù)為偶數(shù)個，因此可兩兩配對奇點個數(shù)為偶數(shù)個，因此可兩兩配對，如，如D-J、K-G、C-M、B-H。在配對的兩點之間添加一條弧，使得到的新圖上沒有。在配對的兩點之間添加一條弧，使得到的新圖上沒有奇點，如下圖所示：奇點，如下圖所示：ABCDEGHILMN22221111111322221KJ3)調(diào)