管理數(shù)學(xué)方法在運(yùn)輸組織中的應(yīng)用

1、 物流運(yùn)輸管理物流運(yùn)輸管理第八章第八章 管理數(shù)學(xué)方法在運(yùn)輸組織管理數(shù)學(xué)方法在運(yùn)輸組織中的應(yīng)用中的應(yīng)用n第一節(jié)第一節(jié) 表上作業(yè)法表上作業(yè)法n第二節(jié)第二節(jié) 圖上作業(yè)法圖上作業(yè)法n第三節(jié)第三節(jié) 最短路線問(wèn)題最短路線問(wèn)題第一節(jié)第一節(jié) 表上作業(yè)法表上作業(yè)法n一、數(shù)學(xué)模型一、數(shù)學(xué)模型 例例1：給出一個(gè)物資調(diào)運(yùn)問(wèn)題，如下表所示，：給出一個(gè)物資調(diào)運(yùn)問(wèn)題，如下表所示，試用線性規(guī)劃法求解。試用線性規(guī)劃法求解。運(yùn)價(jià)運(yùn)價(jià) 銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地b1b2b3b4產(chǎn)量產(chǎn)量（t）a15310490a2169640a320105770銷(xiāo)量銷(xiāo)量（t）305080406060第一節(jié)第一節(jié) 表上作業(yè)法表上作業(yè)法二、表上作業(yè)法的步驟二、表

2、上作業(yè)法的步驟n1、確定初始基本可行解；、確定初始基本可行解；n2、求檢驗(yàn)數(shù)，判斷初始解是否最優(yōu)解；、求檢驗(yàn)數(shù)，判斷初始解是否最優(yōu)解；n3、若檢驗(yàn)數(shù)全非負(fù)，則初始解即最優(yōu)解，否則、若檢驗(yàn)數(shù)全非負(fù)，則初始解即最優(yōu)解，否則初始解不是最優(yōu)解，要進(jìn)行調(diào)整，得到新的可初始解不是最優(yōu)解，要進(jìn)行調(diào)整，得到新的可行解；行解；n4、重復(fù)、重復(fù)2、3兩步，經(jīng)有限次調(diào)整，得到最優(yōu)解。兩步，經(jīng)有限次調(diào)整，得到最優(yōu)解。 第一節(jié)第一節(jié) 表上作業(yè)法表上作業(yè)法三、確定初始基本可行解三、確定初始基本可行解n1、西北角法、西北角法n2、最小元素法、最小元素法n3、伏格爾法（、伏格爾法（vogel）最小元素法最小元素法n方法：列出

3、供需平衡表和運(yùn)價(jià)表。按運(yùn)價(jià)表方法：列出供需平衡表和運(yùn)價(jià)表。按運(yùn)價(jià)表依次挑選運(yùn)費(fèi)小的供需點(diǎn)盡量?jī)?yōu)先安排供應(yīng)。依次挑選運(yùn)費(fèi)小的供需點(diǎn)盡量?jī)?yōu)先安排供應(yīng)。（安排供應(yīng)后劃去運(yùn)價(jià)表中不起作用的運(yùn)價(jià)（安排供應(yīng)后劃去運(yùn)價(jià)表中不起作用的運(yùn)價(jià)并標(biāo)注，再在剩余未劃去的運(yùn)價(jià)中選取最小并標(biāo)注，再在剩余未劃去的運(yùn)價(jià)中選取最小的數(shù)值安排供應(yīng)，以此類(lèi)推。）的數(shù)值安排供應(yīng)，以此類(lèi)推。）例例2n某公司下屬三個(gè)儲(chǔ)存某種物資的料庫(kù)，供應(yīng)某公司下屬三個(gè)儲(chǔ)存某種物資的料庫(kù)，供應(yīng)四個(gè)工地的需要。三個(gè)料庫(kù)的供應(yīng)量和四個(gè)四個(gè)工地的需要。三個(gè)料庫(kù)的供應(yīng)量和四個(gè)工地的需求量以及各料庫(kù)到諸工地調(diào)運(yùn)單位工地的需求量以及各料庫(kù)到諸工地調(diào)運(yùn)單位物資的運(yùn)價(jià)

4、（元物資的運(yùn)價(jià)（元/噸）由表噸）由表1給出，試求運(yùn)輸費(fèi)給出，試求運(yùn)輸費(fèi)用最少的合理調(diào)運(yùn)方案。用最少的合理調(diào)運(yùn)方案。表表1：某公司物資供應(yīng)狀況表：某公司物資供應(yīng)狀況表運(yùn)價(jià)運(yùn)價(jià) 工地工地料庫(kù)料庫(kù)b1b2b3b4供應(yīng)量供應(yīng)量（t）a1311310700a21928400a374105900需求量需求量（t）300600500600西北角法西北角法b1b2b3b4供應(yīng)量供應(yīng)量（t）a1300400700a2200200400a3300600900需求量需求量（t）300600500600最小元素法最小元素法b1b2b3b4供應(yīng)量供應(yīng)量（t）a1400300700a2300100400a36003009

5、00需求量需求量（t）300600500600伏格爾法（伏格爾法（vogel）n1、計(jì)算出各行和各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)、計(jì)算出各行和各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差額；的差額；n2、從行和列差額中選出最、從行和列差額中選出最 （選：大或?。ㄟx：大或?。┱?，選擇它所在行或列中的最小元素，滿(mǎn)足者，選擇它所在行或列中的最小元素，滿(mǎn)足需要；需要；n3、對(duì)未劃去的再重復(fù)前兩步，直到解出初始、對(duì)未劃去的再重復(fù)前兩步，直到解出初始方案為止。方案為止。大伏格爾法伏格爾法b1b2b3b4供應(yīng)量供應(yīng)量（t）a1500200700a2300100400a3600300900需求量需求量（t）300600500600

6、第一節(jié)第一節(jié) 表上作業(yè)法表上作業(yè)法四、求檢驗(yàn)數(shù)四、求檢驗(yàn)數(shù)1、閉回路閉回路：以調(diào)運(yùn)方案表上的一個(gè)空格出發(fā)，存在：以調(diào)運(yùn)方案表上的一個(gè)空格出發(fā)，存在一條且僅一條以該空格（用一條且僅一條以該空格（用xij表示）為起點(diǎn)，以表示）為起點(diǎn)，以其他填有數(shù)字的點(diǎn)為其他頂點(diǎn)的閉合回路，稱(chēng)為其他填有數(shù)字的點(diǎn)為其他頂點(diǎn)的閉合回路，稱(chēng)為閉回路。它具有下列性質(zhì)：閉回路。它具有下列性質(zhì)：n每個(gè)頂點(diǎn)都是轉(zhuǎn)角點(diǎn)；每個(gè)頂點(diǎn)都是轉(zhuǎn)角點(diǎn)；n閉合回路是一條封閉折線，每一條邊都是水平或閉合回路是一條封閉折線，每一條邊都是水平或垂直的；垂直的；n每一行（列）若有閉合回路的頂點(diǎn)，則必有兩個(gè)。每一行（列）若有閉合回路的頂點(diǎn)，則必有兩個(gè)。以

7、上例最小元素法所得初始方案為例，找閉回路。以上例最小元素法所得初始方案為例，找閉回路。b1b2b3b4供應(yīng)量供應(yīng)量（t）a1400300700a2300100400a3600300900需求量需求量（t）300600500600第一節(jié)第一節(jié) 表上作業(yè)法表上作業(yè)法四、求檢驗(yàn)數(shù)四、求檢驗(yàn)數(shù)2、閉回路法、閉回路法求檢驗(yàn)數(shù)求檢驗(yàn)數(shù)檢驗(yàn)數(shù)：檢驗(yàn)數(shù)：每條閉回路上調(diào)整單位運(yùn)量而使運(yùn)輸費(fèi)每條閉回路上調(diào)整單位運(yùn)量而使運(yùn)輸費(fèi)用發(fā)生變化的增減值，稱(chēng)為檢驗(yàn)數(shù)。用發(fā)生變化的增減值，稱(chēng)為檢驗(yàn)數(shù)。n 如果檢驗(yàn)數(shù)小于零，表示在該空格的閉回路上如果檢驗(yàn)數(shù)小于零，表示在該空格的閉回路上調(diào)整運(yùn)量使運(yùn)費(fèi)減少；調(diào)整運(yùn)量使運(yùn)費(fèi)減少；n

8、相反，如果檢驗(yàn)數(shù)大于零，則會(huì)使運(yùn)費(fèi)增加。相反，如果檢驗(yàn)數(shù)大于零，則會(huì)使運(yùn)費(fèi)增加。以上例最小元素法所得初始方案為例，求檢驗(yàn)數(shù)。以上例最小元素法所得初始方案為例，求檢驗(yàn)數(shù)。b1b2b3b4供應(yīng)量供應(yīng)量（t）a1400300700a2300100400a3600300900需求量需求量（t）300600500600第一節(jié)第一節(jié) 表上作業(yè)法表上作業(yè)法四、求檢驗(yàn)數(shù)四、求檢驗(yàn)數(shù)3、位勢(shì)法位勢(shì)法求檢驗(yàn)數(shù)求檢驗(yàn)數(shù)設(shè)設(shè)cij表示變量表示變量xij相應(yīng)的運(yùn)價(jià)，將初始調(diào)運(yùn)方案中相應(yīng)的運(yùn)價(jià)，將初始調(diào)運(yùn)方案中填有數(shù)值方格的填有數(shù)值方格的cij分解成兩部分：分解成兩部分：cij=ui+vj。其中，其中，ui和和vj分別稱(chēng)

9、為該方格對(duì)應(yīng)于分別稱(chēng)為該方格對(duì)應(yīng)于i行和行和j列的位列的位勢(shì)量。勢(shì)量。任意給定一個(gè)未知位勢(shì)量，計(jì)算出所有的任意給定一個(gè)未知位勢(shì)量，計(jì)算出所有的ui和和vj，那么空格處位勢(shì)為對(duì)應(yīng)的那么空格處位勢(shì)為對(duì)應(yīng)的ui和和vj之和，則空格處檢之和，則空格處檢驗(yàn)數(shù)為該處運(yùn)價(jià)與位勢(shì)之差，即驗(yàn)數(shù)為該處運(yùn)價(jià)與位勢(shì)之差，即cijuivj。第一節(jié)第一節(jié) 表上作業(yè)法表上作業(yè)法五、初始方案的調(diào)整五、初始方案的調(diào)整n1、閉回路法調(diào)整、閉回路法調(diào)整n在檢驗(yàn)數(shù)為負(fù)的空格，找到它的閉回路，從空在檢驗(yàn)數(shù)為負(fù)的空格，找到它的閉回路，從空格出發(fā)，奇數(shù)次轉(zhuǎn)角點(diǎn)（即偶數(shù)頂點(diǎn)）的最小格出發(fā)，奇數(shù)次轉(zhuǎn)角點(diǎn)（即偶數(shù)頂點(diǎn)）的最小調(diào)運(yùn)量為調(diào)整量?？崭?/p>

10、加上調(diào)整量，其他格相調(diào)運(yùn)量為調(diào)整量?？崭窦由险{(diào)整量，其他格相應(yīng)調(diào)整。應(yīng)調(diào)整。例例3n某地區(qū)有某地區(qū)有3個(gè)煤礦，所產(chǎn)煤炭全部銷(xiāo)往個(gè)煤礦，所產(chǎn)煤炭全部銷(xiāo)往兩座火力發(fā)電廠。各礦產(chǎn)量、電廠需求兩座火力發(fā)電廠。各礦產(chǎn)量、電廠需求量及單位運(yùn)價(jià)表如表所示，問(wèn)如何安排量及單位運(yùn)價(jià)表如表所示，問(wèn)如何安排運(yùn)輸可使總運(yùn)費(fèi)最??？運(yùn)輸可使總運(yùn)費(fèi)最??？ 運(yùn)價(jià)運(yùn)價(jià) 電廠電廠煤礦煤礦b1b2煤產(chǎn)量煤產(chǎn)量a1355000a24211000a3698000需求量需求量1000014000例例4n用表上作業(yè)法求下表給出的運(yùn)輸問(wèn)題的最優(yōu)解，用表上作業(yè)法求下表給出的運(yùn)輸問(wèn)題的最優(yōu)解，并求最低運(yùn)費(fèi)為多少。并求最低運(yùn)費(fèi)為多少。運(yùn)價(jià)運(yùn)價(jià) 銷(xiāo)

11、地銷(xiāo)地產(chǎn)地產(chǎn)地甲甲乙乙丙丙丁丁產(chǎn)量產(chǎn)量（t）110671240021610599003541010400銷(xiāo)量銷(xiāo)量（t）500200400600第二節(jié)第二節(jié) 圖上作業(yè)法圖上作業(yè)法n利用表上作業(yè)法，可以確定物資的調(diào)運(yùn)方向，利用表上作業(yè)法，可以確定物資的調(diào)運(yùn)方向，即物資調(diào)運(yùn)的發(fā)點(diǎn)和收點(diǎn)，但實(shí)施運(yùn)輸方案時(shí)，即物資調(diào)運(yùn)的發(fā)點(diǎn)和收點(diǎn)，但實(shí)施運(yùn)輸方案時(shí)，還會(huì)遇到還會(huì)遇到運(yùn)輸路線的選擇問(wèn)題運(yùn)輸路線的選擇問(wèn)題。n在物資調(diào)運(yùn)中，把某項(xiàng)物資從各發(fā)點(diǎn)調(diào)到各收在物資調(diào)運(yùn)中，把某項(xiàng)物資從各發(fā)點(diǎn)調(diào)到各收點(diǎn)，調(diào)運(yùn)方案很多，我們要找出使用運(yùn)力最小點(diǎn)，調(diào)運(yùn)方案很多，我們要找出使用運(yùn)力最小的方案，即的方案，即消滅對(duì)流和迂回消滅對(duì)流

12、和迂回兩種不合理的運(yùn)輸。兩種不合理的運(yùn)輸。第二節(jié)第二節(jié) 圖上作業(yè)法圖上作業(yè)法一、交通圖一、交通圖1、交通圖的符號(hào)：、交通圖的符號(hào)：n發(fā)點(diǎn)用發(fā)點(diǎn)用“ ”表示，并將發(fā)貨量記在里面，收表示，并將發(fā)貨量記在里面，收點(diǎn)用點(diǎn)用“ ”表示，并將收貨量記在里面。兩點(diǎn)表示，并將收貨量記在里面。兩點(diǎn)間交通線的長(zhǎng)度記在交通線旁邊。間交通線的長(zhǎng)度記在交通線旁邊。2、調(diào)運(yùn)物資的流向圖：、調(diào)運(yùn)物資的流向圖：n物資調(diào)運(yùn)的方向（流向）用物資調(diào)運(yùn)的方向（流向）用“ ”表示，并把表示，并把“ ” 按調(diào)運(yùn)方向畫(huà)在交通線的按調(diào)運(yùn)方向畫(huà)在交通線的右邊右邊，把調(diào)，把調(diào)運(yùn)物資的數(shù)量記在運(yùn)物資的數(shù)量記在“ ”的右邊并的右邊并加上括號(hào)加上括號(hào)

13、。第二節(jié)第二節(jié) 圖上作業(yè)法圖上作業(yè)法二、圖上作業(yè)法二、圖上作業(yè)法1、對(duì)流運(yùn)輸、對(duì)流運(yùn)輸2、迂回運(yùn)輸、迂回運(yùn)輸n交通圖成圈時(shí)，由于表示調(diào)運(yùn)方向的箭頭要按交通圖成圈時(shí)，由于表示調(diào)運(yùn)方向的箭頭要按調(diào)運(yùn)方向，畫(huà)在交通線的右邊，因此，在流向調(diào)運(yùn)方向，畫(huà)在交通線的右邊，因此，在流向圖中有些流向就在圈內(nèi)，稱(chēng)為內(nèi)圈流向，有些圖中有些流向就在圈內(nèi)，稱(chēng)為內(nèi)圈流向，有些流向就在圈外，稱(chēng)為外圈流向。流向就在圈外，稱(chēng)為外圈流向。n如果流向圖中，內(nèi)圈流向的總長(zhǎng)或外圈流向的如果流向圖中，內(nèi)圈流向的總長(zhǎng)或外圈流向的總長(zhǎng)超過(guò)整個(gè)圈長(zhǎng)的一半，就稱(chēng)為迂回運(yùn)輸?？傞L(zhǎng)超過(guò)整個(gè)圈長(zhǎng)的一半，就稱(chēng)為迂回運(yùn)輸。n迂回運(yùn)輸?shù)恼{(diào)整：迂回運(yùn)輸?shù)恼{(diào)整

14、：n如果如果內(nèi)流長(zhǎng)內(nèi)流長(zhǎng)超過(guò)圈長(zhǎng)的一半，則在超過(guò)圈長(zhǎng)的一半，則在內(nèi)圈內(nèi)圈各流量各流量中減去中減去內(nèi)圈的最小內(nèi)圈的最小流量，在流量，在外圈外圈各流量中增加各流量中增加內(nèi)圈的最小內(nèi)圈的最小流量，同時(shí)在沒(méi)有流量的線段上新流量，同時(shí)在沒(méi)有流量的線段上新添添外圈外圈該最小流量。該最小流量。n反之同理。反之同理。第二節(jié)第二節(jié) 圖上作業(yè)法圖上作業(yè)法三、圖上作業(yè)法的步驟三、圖上作業(yè)法的步驟1、交通圖不含圈、交通圖不含圈n不出現(xiàn)對(duì)流即是最優(yōu)方案。不出現(xiàn)對(duì)流即是最優(yōu)方案。n方法：作一個(gè)沒(méi)有對(duì)流的流向圖，即由各端點(diǎn)方法：作一個(gè)沒(méi)有對(duì)流的流向圖，即由各端點(diǎn)開(kāi)始，開(kāi)始，由外向里由外向里，逐步進(jìn)行各收發(fā)點(diǎn)之間的收，逐步進(jìn)

15、行各收發(fā)點(diǎn)之間的收發(fā)平衡。發(fā)平衡。例例n有某物資有某物資17萬(wàn)噸，由萬(wàn)噸，由a1，a2，a3，a4發(fā)出，發(fā)出，發(fā)量分別為發(fā)量分別為5，2，3，7（單位：萬(wàn)噸），運(yùn)（單位：萬(wàn)噸），運(yùn)往往b1，b2，b3，b4，收量分別為，收量分別為8，1，3，5，收發(fā)量是平衡的，它的交通路線如圖所示，收發(fā)量是平衡的，它的交通路線如圖所示，問(wèn)應(yīng)如何調(diào)運(yùn)，才能使運(yùn)輸噸問(wèn)應(yīng)如何調(diào)運(yùn)，才能使運(yùn)輸噸千米最小。千米最小。52378135a1a2b1a3b2b3a4b4第二節(jié)第二節(jié) 圖上作業(yè)法圖上作業(yè)法2、交通圖含圈、交通圖含圈n第一步：第一步：“去線破圈去線破圈”，作一個(gè)沒(méi)有對(duì)流的流，作一個(gè)沒(méi)有對(duì)流的流向圖，形成初始方案。

16、向圖，形成初始方案。n第二步：檢查初始方案是否最優(yōu)（即有無(wú)迂第二步：檢查初始方案是否最優(yōu)（即有無(wú)迂回）?；兀?。n第三步：如有迂回，如果第三步：如有迂回，如果內(nèi)流長(zhǎng)內(nèi)流長(zhǎng)超過(guò)圈長(zhǎng)的一超過(guò)圈長(zhǎng)的一半，則在半，則在內(nèi)圈內(nèi)圈各流量中減去各流量中減去內(nèi)圈的最小內(nèi)圈的最小流量，流量，在在外圈外圈各流量中增加各流量中增加內(nèi)圈的最小內(nèi)圈的最小流量，同時(shí)在流量，同時(shí)在沒(méi)有流量的線段上新添沒(méi)有流量的線段上新添外圈外圈該最小流量。該最小流量。 。n第四步：重復(fù)上述兩步，直至得出最優(yōu)方案。第四步：重復(fù)上述兩步，直至得出最優(yōu)方案。例：交通圖含圈的圖上作業(yè)法例：交通圖含圈的圖上作業(yè)法abe-20cdihgf(45)(23

17、)(25)(36)(23)(13)(127)(29)+20-30+60-30-50+20+100-70(18)交通圖含圈的圖上作業(yè)法交通圖含圈的圖上作業(yè)法1 、去線破圈、去線破圈 先去掉先去掉ab段，形成一個(gè)初始段，形成一個(gè)初始的調(diào)運(yùn)方案的調(diào)運(yùn)方案abe-20cdihgf(45)(23)(25)(36)(23)(13)(127)(29)+20-30+60-30-50+20+100-70(18)交通圖含圈的圖上作業(yè)法交通圖含圈的圖上作業(yè)法2、檢驗(yàn)、檢驗(yàn) 圈周長(zhǎng)圈周長(zhǎng)/2=36+23+18+25+23+45=170/2=85 外圈長(zhǎng)外圈長(zhǎng)=45+25+18+23=111 內(nèi)圈長(zhǎng)內(nèi)圈長(zhǎng)=23 外圈長(zhǎng)

18、大于圓圈周長(zhǎng)外圈長(zhǎng)大于圓圈周長(zhǎng)/2abe-20cdihgf(45)(23)(25)(36)(23)(13)(127)(29)+20-30+60-30-50+20+100-70(18)n3、調(diào)整、調(diào)整 選取外圈流向線中最小流量選取外圈流向線中最小流量a-i的的“20”，所以應(yīng)，所以應(yīng)在外圈的各段流向線上均減去在外圈的各段流向線上均減去“20”，同時(shí)在內(nèi)圈的，同時(shí)在內(nèi)圈的各段流向線及原來(lái)沒(méi)有流向線的各段流向線及原來(lái)沒(méi)有流向線的ab段分別加上段分別加上“20”，這樣就形成了一個(gè)新的調(diào)撥方案。這樣就形成了一個(gè)新的調(diào)撥方案。abe-20cdihgf(45)(23)(25)(36)(23)(13)(127

19、)(29)+20-30+60-30-50+20+100-70(18)abe-20cdihgf(45)(23)(25)(36)(23)(13)(127)(29)+20-30+60-30-50+20+100-70(18)計(jì)算：例：設(shè)有計(jì)算：例：設(shè)有a1a1、a2a2、a3a3三個(gè)配送點(diǎn)分別有化肥三個(gè)配送點(diǎn)分別有化肥40t40t、30t30t、30t30t，需送往四個(gè)客戶(hù)點(diǎn)，需送往四個(gè)客戶(hù)點(diǎn)b1b1、b2b2、b3b3、b4b4，而且已，而且已知各配送點(diǎn)和客戶(hù)點(diǎn)的地理位置及它們之間的道路通阻知各配送點(diǎn)和客戶(hù)點(diǎn)的地理位置及它們之間的道路通阻情況，可據(jù)此制出相應(yīng)的交通圖，如圖情況，可據(jù)此制出相應(yīng)的交通圖

20、，如圖11-211-2所示。所示。第三節(jié)第三節(jié) 最短路線問(wèn)題最短路線問(wèn)題n例：選擇從例：選擇從a點(diǎn)到點(diǎn)到e點(diǎn)的最短路線。點(diǎn)的最短路線。ab1b2b3c1c2c3d1d2e36477456534236534方法：動(dòng)態(tài)規(guī)劃的逆序遞推法方法：動(dòng)態(tài)規(guī)劃的逆序遞推法k=1k=2k=3k=4n例：某家運(yùn)輸公司簽訂了一項(xiàng)運(yùn)輸合同，要把例：某家運(yùn)輸公司簽訂了一項(xiàng)運(yùn)輸合同，要把a(bǔ)市的一批貨物運(yùn)到市的一批貨物運(yùn)到b市。該公司根據(jù)可選擇的市。該公司根據(jù)可選擇的行車(chē)路線的地圖繪制了公路網(wǎng)絡(luò)如下圖，如何行車(chē)路線的地圖繪制了公路網(wǎng)絡(luò)如下圖，如何選擇運(yùn)輸路線，才能使總路程最短？選擇運(yùn)輸路線，才能使總路程最短？1243657

21、9810100150175300275200175275200300200400250125100150a市市b市市最大流問(wèn)題最大流問(wèn)題n當(dāng)我們要把貨物運(yùn)輸?shù)街付ǖ牡攸c(diǎn)時(shí)，有時(shí)當(dāng)我們要把貨物運(yùn)輸?shù)街付ǖ牡攸c(diǎn)時(shí)，有時(shí)會(huì)希望找到一條會(huì)希望找到一條交通量最大交通量最大的路線，以使貨的路線，以使貨物能在物能在最短時(shí)間內(nèi)到達(dá)最短時(shí)間內(nèi)到達(dá)。n這就要在有一個(gè)起點(diǎn)和一個(gè)終點(diǎn)的網(wǎng)絡(luò)中，這就要在有一個(gè)起點(diǎn)和一個(gè)終點(diǎn)的網(wǎng)絡(luò)中，找出在一定時(shí)期內(nèi)，能在起點(diǎn)進(jìn)入，并通過(guò)找出在一定時(shí)期內(nèi)，能在起點(diǎn)進(jìn)入，并通過(guò)這個(gè)網(wǎng)絡(luò)，在終點(diǎn)輸出的最大流量問(wèn)題。這個(gè)網(wǎng)絡(luò)，在終點(diǎn)輸出的最大流量問(wèn)題。例題：例題：n美國(guó)北卡羅來(lái)納州杜哈姆市周?chē)?/p>

22、從北到南的美國(guó)北卡羅來(lái)納州杜哈姆市周?chē)鷱谋钡侥系慕煌?，平時(shí)是利用交通，平時(shí)是利用85號(hào)公路通行的。后來(lái)，號(hào)公路通行的。后來(lái)，有兩個(gè)星期因?yàn)橛袃蓚€(gè)星期因?yàn)?5號(hào)公路要進(jìn)行路面維修，號(hào)公路要進(jìn)行路面維修，車(chē)輛不能行駛，因而北卡羅來(lái)納州公路委員車(chē)輛不能行駛，因而北卡羅來(lái)納州公路委員會(huì)的工程技術(shù)人員需要查明，穿過(guò)杜哈姆市會(huì)的工程技術(shù)人員需要查明，穿過(guò)杜哈姆市區(qū)的幾條路線，是不是有把握讓每小時(shí)區(qū)的幾條路線，是不是有把握讓每小時(shí)6000輛汽車(chē)穿過(guò)，這些汽車(chē)在正常情況下，是利輛汽車(chē)穿過(guò)，這些汽車(chē)在正常情況下，是利用用85號(hào)公路南駛的。號(hào)公路南駛的。n下圖標(biāo)出了穿過(guò)該市從北往南的幾條路線。下圖標(biāo)出了穿過(guò)該市從

23、北往南的幾條路線。結(jié)點(diǎn)旁邊的數(shù)字表明以每小時(shí)千輛汽車(chē)為單結(jié)點(diǎn)旁邊的數(shù)字表明以每小時(shí)千輛汽車(chē)為單位的該行車(chē)道的流量能力。位的該行車(chē)道的流量能力。計(jì)算方法：計(jì)算方法：n1、任意選擇一條從起點(diǎn)、任意選擇一條從起點(diǎn)1到終點(diǎn)到終點(diǎn)6的路線，首的路線，首先找出這條路線上流量能力最小的支線，即先找出這條路線上流量能力最小的支線，即為該路線的最大流量。把它記在每條支線的為該路線的最大流量。把它記在每條支線的終點(diǎn)并在右下角標(biāo)注，如：終點(diǎn)并在右下角標(biāo)注，如：2（1） 。其次把這。其次把這條路線上的每條支線的流量能力減去該數(shù)，條路線上的每條支線的流量能力減去該數(shù)，差數(shù)表示該支線剩余的流量能力。將其寫(xiě)在差數(shù)表示該支線剩余的流量能力。將其寫(xiě)在原來(lái)的流量能力的旁邊，并把原流量劃掉。原來(lái)的流量能力的旁邊，并把原流量劃掉。n2、重新選擇，重復(fù)上述操作。直至沒(méi)有可行、重新選擇，重復(fù)上述操作。直至沒(méi)有可行路線為止。路線為止。思考題n已知運(yùn)輸問(wèn)題的產(chǎn)銷(xiāo)平衡表、單位運(yùn)