物流運輸規(guī)劃(完).課件

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

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

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

4、不需包裝；單向運輸；單位運營成本低。 缺點：貨物受限；機動靈活性小，初期投資大。運輸方式速度運量運價適合貨物的特點優(yōu) 點缺 點航空運輸（飛機）最快少最昂貴貴重，急需，時間要求緊速度快，包裝簡單運費高，有重量限制水路運輸（輪船）最慢最多最便宜大宗貨物時間寬松價格便宜速度慢，受氣候影響大公路運輸（汽車）較慢較少較貴靈活，量少,路程短靈活，方便（door-to-door）裝載量小，不適合長途運輸。鐵路運輸（火車）較快較多較便宜量大，時間較緊安全,可靠中轉(zhuǎn)作業(yè)時間長管道運輸（管道）連續(xù)大便宜氣體、液體、連續(xù)性強貨損貨差少，連續(xù)運輸適用產(chǎn)品較少各種交通運輸方式的比較 在選擇運輸工具的時候，主要考慮的因素

5、：運輸數(shù)量： 1520噸以下的貨物，采用公路運輸； 1520噸以上的貨物，采用鐵路運輸； 數(shù)百噸以上的原材料之類的貨物，應選擇水路運輸。運輸價格：運輸速度 航空最快達到900 1000km/h； 鐵路80 250 km/h； 公路80 120km/h； 水路中的河運820 km/h， 海運每小時1030海里。 在選擇運輸工具的時候，主要考慮的因素：貨物性質(zhì)運輸距離：200公里以內(nèi)，采用公路運輸；200500公里的區(qū)域，采用鐵路運輸；500公里以上根據(jù)具體情況采用水路或航空運輸； 特別要求運輸方 式選擇的原則貴重或急需的貨物（數(shù)量不大）航空 短途公路容易死亡、變質(zhì)的活物、鮮貨物 長途且數(shù)量大鐵路

6、大宗、笨重的貨物（遠距離運輸）水運或鐵路 選擇交通工具：想一想 從烏魯木齊到北京去開會，第二天必須趕到。飛機選擇交通工具：想一想 暑假從上海到大連旅游，選擇最經(jīng)濟的辦法。海輪選擇交通工具：想一想 從重慶到武漢，沿途觀賞三峽風光。江輪選擇交通工具：想一想 從拉薩到西寧，沿途參觀訪問。汽車選擇交通工具：想一想 從武漢到鄭州探親。火車選擇運輸方式 貴重或急需的貨物，數(shù)量又不大的，多由 運輸。航空選擇運輸方式 容易死亡、變質(zhì)的，活物、鮮貨，短程可由 運輸。公路選擇運輸方式 容易死亡、變質(zhì)的，活物、鮮貨，遠程而又數(shù)量大的可用 運輸。鐵路選擇運輸方式 大宗笨重的貨物，遠距離運輸，盡可能利用 或 運輸。水運

7、鐵路選擇運輸方式 貨物和數(shù)量 起點至終點 鐵路公路 河運海運 航空兩箱急救藥品 北京-拉薩一噸活魚 密云水庫-北京五十噸鋼材 上海-濟南一萬噸海鹽 天津-上海十萬噸大米 武漢-上海 例2.讀歐洲貨物四種運輸方式運費與運距相關曲線示意圖，回答問題。運距80千米時，最廉價的運輸方式是_。 80千米運距550千米時，最廉價的運輸方式是_。最昂貴的運輸方式是_，它適合運送的貨物特點是_?？傔\價080550距離/千米空運公路鐵路水路公路鐵路水運空運輕型、貴重、急需。 某公司有以下運輸業(yè)務委托你公司進行托運，請為其選擇合適的運輸方式并說明理由。 1.把兩箱急救藥和一批鮮花從廣州運到北京。 2.把一批煤炭從

8、山西運到秦皇島。 3.把一批新鮮蔬菜從郊區(qū)運到市區(qū)。 4.有一批鋼材，要從重慶運到武漢。 5.有15萬噸石油需要從非洲運到我國的上海。 6.把我國西部大量的天然氣運到以上海為主的東部地區(qū)。貨 物起始地點可選擇的運輸方式最佳方式及理由一批鮮花、兩箱急救藥 廣州北京 航空、鐵路 航 空（速度快、保鮮）一批煤炭山西秦皇島 鐵 路 鐵 路（路遠、運量大）新鮮蔬菜 郊區(qū)市區(qū) 鐵路、公路 公 路（方便、靈活）鋼 材重慶武漢水路、鐵路、公路 水 路（運量大，有河流，成本低） 15萬噸石油非洲上海水運+管道+公路水運+公路 水運+公路（實現(xiàn)門到門）天然氣 西部東部管 道 管道（特殊性） A公司首次承攬到三個集

9、裝箱運輸業(yè)務，時間較緊，從上海到大連鐵路1200公里，公路1500公里，水路1000公里。該公司自有10輛10噸普通卡車和一個自動化立體倉庫，經(jīng)聯(lián)系附近一家聯(lián)運公司雖無集裝箱卡車，但卻有專業(yè)人才和貨代經(jīng)驗，只是要價比較高。至于零星集裝箱安排、落實車皮和船艙，A公司實在心中無底，你認為采取什么措施比較穩(wěn)妥？（1）自己購買若干輛集裝箱卡車，然后組織運輸。（2）想法請鐵路部門安排運輸（3）水路最短，請航運公司來解決運輸（4）聯(lián)運公司雖無集卡，但可叫其租車完成此項運輸（5）沒有合適的運輸工具，辭掉該項業(yè)務分析要點：1）以請聯(lián)運公司來承擔此項任務為好，比較穩(wěn)妥，聯(lián)運公司是第三方物流服務企業(yè)2）第三方物流

10、服務供應商，根據(jù)是夠擁有資產(chǎn)可分為資產(chǎn)基礎供應商和非資產(chǎn)基礎供應商。我們選擇的標準絕不是它有無實際的物流資產(chǎn)而是看專業(yè)人才和貨代經(jīng)驗，有資產(chǎn)的物流供應商價格可能低些，但靈活性差；而非資產(chǎn)基礎供應商，則可根據(jù)不同需要“量體裁衣”，非常靈活3）邀請第三方物流服務供應商，應該做好如下工作（1）對該聯(lián)運公司做必要調(diào)查，看看信譽度如何。（2）進行必要的合同磋商，解決好合同的執(zhí)行標準、衡量標準、違約責任以及價格（3）努力避免雙方合作失敗，既交貨又派專人關心此事（4）講明如果服務質(zhì)量好，可考慮長期合作的可能性。其他方案欠穩(wěn)妥，無把握，風險很大案例啟示：企業(yè)生存與發(fā)展的不二法門就是盈利，但是對于企業(yè)即將開展的

11、新業(yè)務或相關業(yè)務來說，盈利的同時，經(jīng)驗和長期客戶的開發(fā)維護也是很重要的 6、幾種特殊的運輸方式 1、集裝箱運輸1）概念 集裝箱是一個大型的、標準化的、能反復使用的載貨容器。 集裝箱運輸就是以集裝箱作為一個貨物集合單元進行運輸?shù)囊环N運輸方式。標準集裝箱側(cè)開門集裝箱側(cè)開雙門集裝箱全側(cè)開門集裝箱開頂散貨集裝箱冷藏集裝箱2）集裝箱運輸?shù)膬?yōu)點 提高裝卸效率，減輕勞動強度 減少了裝卸所需要的時間和費用，加速了車船周轉(zhuǎn) 保證貨物完整無損，避免貨損貨差 節(jié)省包裝費用，簡化理貨手續(xù) 減少營運費用，降低運輸成本 3）集裝箱運輸?shù)娜毕?集裝箱運輸需要大量的初始投資 建立新的管理體制、形成新的管理人員隊伍 增加了一些

12、潛在的不安全因素 英國擱淺貨輪納波利號散落貨物 4）開展集裝箱運輸?shù)臈l件 要有穩(wěn)定的貨源和經(jīng)濟腹地 要有良好的港口條件（深水港）和基礎設施（如裝卸） 較為發(fā)達的內(nèi)陸運輸系統(tǒng) 高素質(zhì)的經(jīng)營管理者 2、托盤運輸 1）概念： 托盤（ pallet）是用于集裝、堆放、搬運和運輸?shù)姆胖米鳛閱卧摵傻呢浳锖椭破返乃狡脚_裝置。 托盤運輸是貨物按照一定要求成組裝在一個標準托盤上組合成為一個運輸單位并便于利用鏟車或托盤升降進行裝卸、搬運和堆存的一種運輸方式，它是成組運輸?shù)某跫壭螒B(tài)。 2）托盤運輸?shù)奶攸c （1）提高運輸效率 搬運或出入庫場都可用機械操作，減少貨物堆碼作業(yè)，從而有利于提高運輸效率，縮短貨運時間，減

13、少勞動強度。（2）便于理貨，減少貨損貨差 以托盤為運輸單位，貨物件數(shù)變少體積重量變大，而且每個托盤所裝數(shù)量相等。既便于點數(shù)、理貨交接，又可以減少貨損貨差事故。（3）投資比較小，收效比較快。（4）托盤的回收利用，組織工作難度較大，會浪費一部分運力。 3）托盤運輸具有一定的局限性，表現(xiàn)在以下幾方面： 1、托盤承運的貨物范圍有限 最適合托盤運輸?shù)呢浳锸窍溲b罐頭食品、硬紙盒裝的消費品和袋及袋裝的貨物等比較小的包裝商品。 大的、形狀不一的家具、機械以及散裝冷凍等貨物，不適合于采用托盤進行運輸 2、托盤運輸設備費用減少，但要增加托盤運輸費用。同時，由于增加了托盤的重量和體積，相應地減少了運輸工具的載量。

14、3、托盤運輸向成組運輸前進了一步，但它的效果還不足以改變傳統(tǒng)的流通方式，特別是不能滿足國際多式聯(lián)運的要求。 例如，它不能像集裝箱那樣，可以密封越過國境或快速轉(zhuǎn)換各種運輸方式。 4）采用托盤運輸應該注意的事項 1、裝載托盤貨物的范圍有一定限制，不是所有貨物都可以用托盤運輸。 2、必須符合托盤積載的規(guī)定。 3、每一托盤貨載，必須捆扎牢固具有足夠的強度和穩(wěn)定，平衡。 既能夠承受一般海上風險，經(jīng)受裝卸操作和移動，也能夠在其上面承受一定的壓力。 4、貨物以托盤運輸時，必須在所有運輸單證上注明“托盤運輸”字樣。 3、散裝運輸 1）含義： 散裝運輸是指產(chǎn)品不帶包裝的運輸，是用專用設備將產(chǎn)品直接由生產(chǎn)廠方送至

15、用戶使用的運輸方式。 2）優(yōu)點： ）節(jié)省包裝材料和費用，減少貨損 ）減少工作環(huán)節(jié)，提高機械化、自動化程度 4、國際多式聯(lián)運 1）含義： 國際多式聯(lián)運是指按照多式聯(lián)運合同,以至少兩種不同的運輸方式，由多式聯(lián)運經(jīng)營人將貨物從一國境內(nèi)接管貨物的地點運至另一國境內(nèi)指定交付貨物的地點。2）特征：（1）必須訂立多式聯(lián)運合同（1）多式聯(lián)運合同：是指多式聯(lián)運經(jīng)營人憑其收取全程運費，使用兩種或兩種以上不同運輸工具，負責組織完成貨物全程運輸?shù)暮贤＃?）托運人只與MTO有業(yè)務和法律上的關系。（托運人與各區(qū)段實際承運人不發(fā)生任何業(yè)務和法律上的關系）（2）必須由多式聯(lián)運經(jīng)營人對全程運輸負責（3）必須是兩種或兩種以上不

16、同運輸方式組成的連貫運輸。（5）必須簽發(fā)多式聯(lián)運單據(jù)（1）MTO在接管貨物后簽發(fā)多式聯(lián)運單據(jù)（2）從發(fā)貨地到收貨地，一單到底（3）發(fā)貨人憑多式聯(lián)運單據(jù)向銀行結匯。（4）收貨人憑多式聯(lián)運單據(jù)向MTO或代理提貨。（6）必須是單一的運費率3）優(yōu)點：（）手續(xù)簡便，可以做到一次性托運，一次性付費，一次性投保，一單到底，統(tǒng)一理賠，全程負責（）安全可靠（）統(tǒng)一理賠（）可以實現(xiàn)門門運輸（）具有單一運費率案例 2004年10月4日，原告A公司作為買方與溫州市進出口公司B簽訂一份售貨確認書，購買一批童裝，數(shù)量500箱，總價為68180美元。2005年2月11日，B公司以托運人身份將該批童裝裝于兩個20尺標箱內(nèi)，交

17、由多式聯(lián)運經(jīng)營人C承運。C公司簽發(fā)了號碼為RS95040的一式三份正本全程多式聯(lián)運提單。 A公司提貨時箱子外觀完好，打開箱子發(fā)現(xiàn)其中一個箱子是空的。另一個箱子貨物被擠壓而無法按正常價值出售。 問：多式聯(lián)運人是否承擔賠償責任。解答： 集裝箱貨物的真實性問題。根據(jù)國際航運慣例，在集裝箱運輸方式中，由托運人負責裝箱的貨物，從裝箱托運后至交付收貨人時的期間內(nèi)，如集裝箱箱體和封志完好，貨物損壞或短缺，由托運人負責；如箱體損壞或封志破壞，箱內(nèi)貨物損壞或短缺，由承運人負責。 2.2 運輸問題與線性規(guī)劃1、線性規(guī)劃模型及求解方法 1）線性規(guī)劃問題的數(shù)學表達式 線性規(guī)劃問題一般可以表示如下：稱為線性規(guī)劃問題的標

18、準形式（其中右端常數(shù)b1，b2，bm0）。 變換一般LP為標準形式的方法：（1）如果原問題目標函數(shù)求極大值： 令z1=z，轉(zhuǎn)化為求極小值。（2）若某個右端常數(shù)bi0 則以1乘該約束兩端。（3）若某約束為“”型的不等式約束， 則在左端加上一個非負變量，稱為松弛變量，使不等式化為等式； 若某約束為“”型， 則在左端減去一個非負變量，稱為剩余變量，或者仍然稱為松弛變量，使不等式轉(zhuǎn)化為等式。（目標函數(shù)不變（4）若某個xj的符號約束為xj0； 那么令xj=xj，則xj0； 若某個xj無符號限制， 令xj=xjxj，其中xj0，xj0。（目標函數(shù)變） 2）單純形法 單純形表 E單位陣 N非基陣基變量XB非

19、基變量XN檢驗數(shù)基可行解 單純形法 單純形法的求解過程就是對單純形表的變換過程，其步驟為：（1）求初始基可行解，列出初始單純形表（2）最優(yōu)性檢驗： 若所有檢驗數(shù) ，則表中基可行解即為最優(yōu)解，計算結束； 若存在 ，則選最大者 所對應的變量 為入基變量，轉(zhuǎn)步驟（3）（3）檢查單純形表的第K列。 若無正值，則為無界解； 若有一個以上的正值，按最小比值法 確定出基變量（4）用對角頂點法對單純形表進行變換（5）返回步驟（2）進行迭代 對角頂點法： 如下圖所示，矩形的四個頂點分別對應四個元素：D1、D2、D3、D4，若D1為需要變換的元素，它的對角元素是交叉元素D3 ，另兩個對角元素為D2和D4 。 對角

20、頂點法就是：第i行第j列的元素新值D1為舊值D1減去兩個對角元素D2、 D4乘積除以交叉元素D3所得的值 即： D1= D1- D2 * D4 / D3D4D1D3主列j列i行主行D2 若對第i行第j列的元素7進行變換，則變換過程為： 變換后第i行第j列的元素為： 7-3*2/8=25/43278主列j列i行主行 變換單純形表： 首先，將 行的元素除以交叉元素， 即 變換后的交叉元素 然后，其他行的元素（除k列）按對角頂點法變換 最后，把k列（不含交叉）元素變?yōu)?，即 單純形變換結束 例：求解下列線性規(guī)劃問題解：加入變量 ，則問題變換為如下形式 3 0 -1 0 0 M M 0 4 1 1 1

21、 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ù)中最大者對應的列為主列主元素化為1, 向量換入, 換出 4 1 3表1：列初始單純形表 （單位矩陣對應的變量為基變量）最小的值對應的行為主行 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=33 1 -2 1 -1 0 -1 1 06變換為：9-1*3=6變換為：1-1*(-2)

22、=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變換為：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ù)中最大者對應的列為

23、主列主元素化為1, 向量換入, 換出 1 - 1表2：換基（對角頂點法，主列化為單位向量，主元為1）最小的值對應的行為主行 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ù)中最大者對應的列為主列主元素化為1, 向量換入, 換出 - 9 3/2表3：換基（對角頂點法，主列化為單位向量，主元為1）最小的值對應的行為主行 3 0 -1 0 0 M M 0 0 0 0 0 1 -1/2 1/2 -1/2

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

25、運輸表”表示，運輸表有一定的格式，圖下圖所示運輸問題的數(shù)學模型由某一產(chǎn)地運往各個銷地的物品數(shù)量之和等于該產(chǎn)地的產(chǎn)量由各產(chǎn)地運往某一銷地的物品數(shù)量之和等于該銷地的銷量變量非負條件目標函數(shù)表示運輸總費用，求極小化如果 ，即供應量等于總需求量，稱該運輸問題為產(chǎn)銷平衡問題。數(shù)學模型為： 反之稱為產(chǎn)銷不平衡問題： 如果 ，即供應量大于總需求量，可增加一個虛構銷售地，令其需求量為 ，數(shù)學模型為： 如果 ，即供應量小于總需求量，可增加一個虛構生產(chǎn)地，令其需求量為 ，數(shù)學模型為： 2.3 旅行路線問題1、旅行路線問題表述 一個有N個城市組成的一般網(wǎng)絡，已知任意兩城市之間的直達距離，尋找一條旅行路線，使其最終回

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

27、,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可以計算每一條線路的距離，找其中最小的即BCDE=19 BCED=15 BDCE=22 BDEC=24 BECD=15BEDC=21 CBDE=22 CBED=15 CDBE=22 CDEB=21

28、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ù)可知，路線ADCBEA和AEBCDA是最佳路線 2.4 圖論方法的應用 1、圖論的基本知識 圖論是數(shù)學的一個分支,以圖為研究對象。 這種圖由若干給定的點和連接兩點的線構成,借以描述某些事物之間的關系。用點代表事物,用連接兩點的線表示兩個事物之間具有特定關系。 （1）圖論的起源 圖論起源于18世紀,追朔到1736年瑞士數(shù)學家歐拉出版第一本圖論著作,提出和解決著名哥尼斯堡七

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

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

31、roblem） 一名郵遞員負責投遞某一地區(qū)的郵件。如何為他（她）設計一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？ 由于這一問題是我國管梅谷教授1960年首先提出的，所以國際上稱之為中國郵遞員問題。 解法思想： 要把所有路段都走遍，即：一筆畫出經(jīng)過所有路段的連線，這個連線就是一個可行解，而總長度最短的連線就是最優(yōu)解。ABCDEGHILMN22221111111322221K（2）求解方法 中國郵路問題用圖論的語言描述就是： 給定一個連通圖G，每邊有非負權l(xiāng)(e),要求一條回路過每邊至少一次，且滿足總權最小。 求解步驟：1）找出圖中的奇點和偶點。A、E、I、L、N是偶點，B、C、D、G、H、J、K、M為奇點。2）奇點個數(shù)為偶數(shù)個，因此可兩兩配對，如D-J、K-G、C-M、B-H。在配對的兩點之間添加一條弧，使得到的新圖上沒有奇點，如下圖所示：ABCDEGHILMN22221111111322221KJ3)調(diào)整添弧，使每個圈的添弧總長度不大于圈長度的一半先看B-C-I-H圈，整圈的總長度為6，而添弧長度為 ，超過