《物流系統(tǒng)工程》第5章-1-物流系統(tǒng)規(guī)劃課件

第5章物流系統(tǒng)規(guī)劃5.1概述5.2物流調運規(guī)劃5.3物流分配規(guī)劃5.4其它應用問題1第5章物流系統(tǒng)規(guī)劃5.1概述15.1概述25.1概述2一.物流系統(tǒng)規(guī)劃概述物流系統(tǒng)規(guī)劃所關注的問題是如何合理、有效地利用或配置各種資源（勞動力、材料、設備、資金），使實現(xiàn)預定目標所需的費用最小（或資源最少），或者所獲得的收益最大。物流系統(tǒng)的規(guī)劃一般都可以用優(yōu)化模型來表達。其基本思想是在滿足一定的約束條件下，使預定的目標值達到最優(yōu)。物流系統(tǒng)規(guī)劃的數(shù)學基礎主要是運籌學理論，常用的方法包括線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃等。3一.物流系統(tǒng)規(guī)劃概述物流系統(tǒng)規(guī)劃所關注的問題是如何合理、有二.物流系統(tǒng)規(guī)劃的目標任務提高物流系統(tǒng)的吞吐能力以適應產(chǎn)量增長的要求；建設一個柔性的物流系統(tǒng)，以適應產(chǎn)品經(jīng)常變化的情況；對生產(chǎn)過程中可能出現(xiàn)的各種意外情況或隨機變化做出及時的響應，保持均衡生產(chǎn)；改善勞動條件，減輕勞動強度；對物流系統(tǒng)中的貨物進行實時跟蹤；對物流系統(tǒng)的貨物進行分類或選配，為隨后的處理(加工或包裝)提供方便條件。4二.物流系統(tǒng)規(guī)劃的目標任務提高物流系統(tǒng)的吞吐能力以適應產(chǎn)量三.評價物流系統(tǒng)規(guī)劃的主要指標經(jīng)濟性。包括初始投資、每年的運營費用、直接或間接的經(jīng)濟效益、投資回收期、全員勞動生產(chǎn)率等；可靠性。包括單個環(huán)節(jié)的可靠性和整個系統(tǒng)的可靠性技術、設備故障率和排除故障所需的時間；可維護性。維護保養(yǎng)所要求的技術水平、備件的供應情況、所需儲備的備件數(shù)量；靈活性或柔性。適應產(chǎn)品設計更改和產(chǎn)量變化的能力，物流系統(tǒng)各環(huán)節(jié)與生產(chǎn)節(jié)奏相匹配的能力，調整物流路線的可能性；可擴展性。在物流系統(tǒng)的服務范圍和吞吐能力方面進—步擴大的可能性；安全性。包括產(chǎn)品的安全、人員的安全、以及正常運行和事故狀態(tài)下的安全保障；勞動強度。需要勞動力的數(shù)量、勞動者的疲勞程度；易操作性。操作簡單、不易出錯，只需少量指令即可使設備和整個系統(tǒng)投入運行；服務水平。對顧客的要求做出快速響應的能力；環(huán)境保護。符合環(huán)境保護條理的要求，對周圍環(huán)境的污染程度低。敏感性。對外界條件變動的敏感程度和適應能力。5三.評價物流系統(tǒng)規(guī)劃的主要指標5四.物流系統(tǒng)規(guī)劃中的變量物流系統(tǒng)規(guī)劃中的控制因素分為兩類不可控因素：設計人員無法左右的種種前提條件。可控因素：可以由規(guī)劃設計人員在一定范圍內選取的變量。明確了物流系統(tǒng)中可控變量和不可控因素，就能知道加何去影響系統(tǒng)的性能，達到所追求的目標。物流系統(tǒng)的規(guī)劃一般是通過調整可控變量觀察系統(tǒng)性能的變化趨勢，從而選擇可控變量的最佳匹配，達到系統(tǒng)的最佳效果。物流系統(tǒng)的功能除了受可控變量的影響外，還與不可控因素有密切的關系。通常，不可控因素不是非常確定的。6四.物流系統(tǒng)規(guī)劃中的變量物流系統(tǒng)規(guī)劃中的控制因素分為兩類65.2物流系統(tǒng)調運規(guī)劃75.2物流系統(tǒng)調運規(guī)劃7一.問題描述調運規(guī)劃問題描述

設某種要調運的物資，有一組供應點(產(chǎn)地或稱發(fā)點)m個，一組需求點(銷地或稱收點)n個，如果每個供應點的供應量及每個需求點的需求量都已經(jīng)確定，即第i個產(chǎn)地有ai單位的物資發(fā)出，第j個需求點需要收進bj單位的物資；并且從每—個產(chǎn)地到每一個銷地的單位運價是已知的，假定把單位物資從第i個產(chǎn)地調運到第j個銷地去的單位運價為cij。調運規(guī)劃問題也叫運輸問題物資調運規(guī)劃的目的：制訂一個合理的調運方案；確定m個產(chǎn)地與n個銷地之間的供需聯(lián)系和數(shù)量的最優(yōu)搭配；確定具體的運輸路線，使總的運輸費用最低。8一.問題描述調運規(guī)劃問題描述8二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量1.數(shù)學模型設供應點為Ai，該供應點的供應量是ai，（i=1,2,…,m）；設需求點為Bj，該需求點的需求量是bi，（j＝1,2,…,n）；

cij為從第i個供應點到第j個需求點的單位運價；由供應點Ai發(fā)往需求點Bj的物資調運量是xij單位。假設m個供應點的總供應量等于n個需求點的總需求量，（這樣，調運問題滿足供需平衡，稱為平衡運輸問題）。這時，由各供應點Ai調出的物資總量應等于它的供應量ai(i=1,2,…,m)；而每一個需求點Bj調入的物資總量應等于它的需求量bj(j=1,2,…,n)。目標函數(shù)：約束條件9二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量1.數(shù)學模型約束條二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量2.模型求解用線性規(guī)劃方法求解（如單純形法）。用表上作業(yè)法求解（針對這類問題的一種特殊解法）3.表上作業(yè)法的主要步驟首先依據(jù)問題列出調運物資的供需平衡表以及運價表；其次確定一個初始的調運方案(當然不一定就是最優(yōu)的方案)；然后根據(jù)一個判定法則，判定初始方案是否為最優(yōu)方案。當判定初始方案不是最優(yōu)方案時，再對這個方案進行調整。一般情況，每調整一次得到一個新的方案，而這個新方案的運費比前一個方案要少些，如此經(jīng)過幾次調整，就會得到最優(yōu)方案。10二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量2.模型求解10B1B2B3B4供應量(t)A1311310700A21928400A374105900需求量(t)3006005006002000工地料庫運價表5-1某公司物資供應狀況表二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量4.表上作業(yè)法解題實例例題1某公司下屬三個儲存某種物資的倉庫，供應四個工地的需要。三個倉庫的供應量和四個工地的需求量以及由各倉庫到各工地調運單位物資的運價(元／噸)由表5—1給出，試求運輸費用最少的調運方案。11B1B2B3B4供應量(t)A1311310700A2192解：（1）列出物資調運平衡表和運價表

B1B2B3B4供應量(t)A1700A2400A3900需求量(t)3006005006002000需供運價表5-2供需平衡表表5-3運價表

B1B2B3B4A1311310A21928A374105料庫運價工地平衡表中填入的數(shù)字表示供需點之間的調運量；空格表示雙方不發(fā)生調運關系平衡表和運價表是表上作業(yè)法的基本資料和運算的依據(jù)。表上作業(yè)法的實質就是利用運價表在平衡表上進行求解。二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量12解：（1）列出物資調運平衡表和運價表B1B2B3B4供應量（2）編制初始調運方案

物資調運規(guī)劃其總的目的是尋求一個運輸費用最少的最優(yōu)調運方案。一般最優(yōu)方案是由初始方案經(jīng)過反復調整得到的。因此，編制出較好的初始調運方案非常重要。最好的調運方案是使運費最省的方案，因此可以用最小元素法來確定初始調運方案。所謂最小元素法，就是按運價表依次挑選運費少的供——需點盡量優(yōu)先安排供應的調運方法。二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量13（2）編制初始調運方案物資調運規(guī)劃其總的目的是尋求一個運輸B1B2B3B4供應量(t)A1700A2300400A3900需求量(t)3006005006002000需供運量供需平衡表運價表

B1B2B3B4A1311310A21928A374105料庫運價工地1首先，在運價表內找出最小的運價，對本例而言，方格(2，1)數(shù)值是1，最小，這樣，供應點A2盡可能地滿足B1工地的需要，于是在平衡表中有(2，1)＝300，即在空格(2，1)中填入數(shù)字300。此時，由于工地B1已經(jīng)全部得到滿足，不需要其他倉庫供應給它了，運價表中的第一列數(shù)字己不起作用，因此將運價表第一列劃去，并標注符號①，14B1B2B3B4供應量(t)A1700A2300400A39B1B2B3B4供應量(t)A1700A2300100400A3900需求量(t)3006005006002000需供運量供需平衡表運價表

B1B2B3B4A1311310A21928A374105料庫運價工地12然后，在運價表未劃去的各行、列中，再選取一個最小的運價，本例，即(2，3)＝2最小，讓A2料庫盡量供應滿足B3工地的需要。由于A2庫儲量400t已供應給B1工地300t了，所以最多還能供給B3工地100t。于是在平衡表(2，3)空格填入100；相應地由于倉庫A2所儲物資已全部供應完畢，因此，在運價表中與A2同行的運價也不再起作用，所以也將它們劃去，并標注符號②。15B1B2B3B4供應量(t)A1700A2300100400B1B2B3B4供應量(t)A1400700A2300100400A3600300900需求量(t)3006005006002000需供運價供需平衡表運價表

B1B2B3B4A1311310A21928A374105料庫運價工地12435仿照前面的方法，一直作下去，就可得到如左圖所示的運價表和平衡表。此時，在運價表中只有方格(1，4)處的運價沒有劃掉，B4尚有300t的需求，而A1剛好還有300t的物資可以供應，為了滿足供需平衡，所以最后在平衡表上應有(1，4)＝300。這樣就得到表5—6的初始調運方案。16B1B2B3B4供應量(t)A1400700A2300100B1B2B3B4供應量(t)A1400300700A2300100400A3600300900需求量(t)3006005006002000需供運量表5-6初始調運方案3524根據(jù)初始調運方案的運輸量和單位運價，可以計算初始調運方案的運輸費用為：S=1*300+4*600+3*400+2*100+10*300+5*300=8600(元)110價格運量17B1B2B3B4供應量(t)A1400300700A2300（3）初始方案的檢驗與調整1）最優(yōu)方案的數(shù)字表征——檢驗數(shù)相關概念

閉回路：對表上作業(yè)法的初始方案，從調運方案表上的一個空格出發(fā)，存在—條且僅存在一條以該空格(用xij表示)為起點，以其他填有數(shù)字的點為其他頂點的閉合回路，簡稱閉回路。每個頂點都是閉合回路的轉角點；閉合回路是一條封閉折線，每一條邊都是水平或垂直的；每一行(列)若有閉合回路的頂點，則必有兩個（起點所在的行（列）除外）。任一空格的閉合回路不僅是存在的，而且是唯一的。只有從空格出發(fā)，其余各轉角點所對應的方格內均填有數(shù)字時，所構成的閉合回路，才是我們這里所說的閉回路。二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量18（3）初始方案的檢驗與調整1）最優(yōu)方案的數(shù)字表征——檢驗數(shù)二

空格(1，1)：(1，1)—(1，3)—(2，3)—(2，1)一(1，1)

空格(3，1)：(3，I)—(2，1)—(2，3)—(1，3)一(1，4)—(3，4)—(3，1)對所有的空格，都可以用同樣的方法畫出一條閉回路。B1B2B3B4供應量(t)A1400300700A2300100400A3600300900需求量(t)3006005006002000需供二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量19空格(1，1)：(1，1)—(1，3)—(2，3)—(檢驗數(shù)：調運方案的每個空格所形成的閉回路上，作單位物資的運量調整，總可以計算出相應的運費是增加還是減少。我們把所計算出來的每條閉回路上調整單位運量而使運輸費用發(fā)生變化的增減值，稱其為檢驗數(shù)。如果檢驗數(shù)小于零，表示在該空格的閉回路上調整運量使運費減少；如果檢驗數(shù)大于零，則表示在該空格的閉回路上調整運量會使運費增加。

最優(yōu)方案的判定準則：初始調運方案中，如果它所有的檢驗數(shù)都是非負的，那么這個初始調運方案一最優(yōu)。否則。這一調運方案不一定是最優(yōu)的。

（如果所有空格的檢驗數(shù)都小于零，那么如果再對調運方案進行任何調整，都會增加運輸費用）二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量20檢驗數(shù)：調運方案的每個空格所形成的閉回路上，作單位物資的2）用位勢法求檢驗數(shù)將初始調運方案中填有運量的方格對應的運價cij分解為兩部分，即：cij=ui+vj,(對應前面的例題，i=1,2,3;j=1,2,3,4)其中ui和vj分別為該方格對應于i行和j列的位勢量.B1B2B3B4uiA1310U1=2A212U2=1A345U3=-3viv1=0v2=7v3=1v4=8需供C21=u2+v1=1C23=u2+v3=2C13=u1+v3=3……C34=u3+v4=57個未知量，六個方程假定其中一個未知量為0（任意），如假定v1=0,則可以根據(jù)左邊的方程解出全部未知量。位勢計算表第1步：求位勢量212）用位勢法求檢驗數(shù)將初始調運方案中填有運量的方格對B1B2B3B4uiA1[2][9]310U1=2A21[8]2[9]U2=1A3[-3]4[-2]5U3=-3viv1=0v2=7v3=1v4=8需供準檢驗數(shù)表按ui+vj求出各空格的位勢量，得到準檢驗數(shù)表（加方括號表示）準檢驗數(shù)計算過程空格（1，1）=u1+v1=2+0=2（3，1）=u3+v1=-3+0=-3（1，2）=u1+v2=2+7=9（2，2）=u2+v2=1+7=8（3，3）=u3+v3=-3+1=-2（2，4）=u2+v4=1+8=9第2步：求準檢驗數(shù)22B1B2B3B4uiA1[2][9]310U1=2A21[8B1B2B3B4A1[2][9]310A21[8]2[9]A3[-3]4[-2]5第3步：求檢驗數(shù)運價表B1B2B3B4A1311310A21928A374105準檢驗數(shù)表利用運價表與準檢驗數(shù)表求檢驗數(shù)檢驗數(shù)表B1B2B3B4A112A21-1A31012“運價表”減“準檢驗數(shù)表”檢驗結果：檢驗數(shù)出現(xiàn)負值，根據(jù)最優(yōu)方案判斷準則，該方案不是最優(yōu)方案。23B1B2B3B4A1[2][9]310A21[8]2[9]A3）調整調運方案當判定一個初始調運方案不是最優(yōu)調運方案時，就要在檢驗數(shù)出現(xiàn)負值的該空格內進行調整。如果檢驗數(shù)是負值的空格不只一個時，一般選擇檢驗數(shù)為負值且絕對值最大的空格作為具體的調整對象。X13400+100=500X14300-100=200X23100-100=0X240+100=100

B1B2B3B4A1

400300A2300

100

負A3

600

300調整過程：（1）作出負值所在空格的閉回路，本例為空格x24，閉回路如上圖所示。（2）沿閉回路在各奇數(shù)次轉角點中挑選運量的最小數(shù)值作為調整量。本例是將x23方格的100作為調整量，將這個數(shù)填入空格x24內，同時調整該閉回路中其他轉角點上的運量，使各行、列保持原來的供需平衡．這樣使得到一個新的調運方案。243）調整調運方案當判定一個初始調運方案不是最優(yōu)調運方案時，就B1B2B3B4供應量(t)A1500200700A23000100400A3600300900需求量(t)3006005006002000需供運量調整后的調運方案13524108B1B2B3B4A122A241A3912調整后的檢驗數(shù)通過計算其檢驗數(shù)全部非負，此方案為最優(yōu)方案。運輸費用為：S＝3×500十10×200十8×100十1×300十4×600十5×300＝8500(元)該值小于初始調運方案的總運費。25B1B2B3B4供應量(t)A1500200700A2300(4)表上作業(yè)法基本步驟小結①列出調運物資的供需(產(chǎn)銷)平衡表及運價表；②按最小元素法建立初始調運方案；③采用位勢法計算初始方案每個空格的閉回路的檢驗數(shù)xij；④檢查檢驗數(shù)，如果所有xij>=0，說明方案是最優(yōu)的，已經(jīng)得到我們想要的方案，結束求解；⑤如果有某個或某幾個xij<0，則選擇負檢驗數(shù)中絕對值最大的閉回路進行調整，建立新的方案；⑥重復3—5步，直至獲得最優(yōu)調運方案。二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量26(4)表上作業(yè)法基本步驟小結①列出調運物資的供需(產(chǎn)銷)平衡(5)供需不平衡的物資調運問題通過虛設一個供應點或者需求點，將其轉化為平衡運輸問題求解。①供應量大于需求量引入一個虛設的需求點，令其的需求量等于實際問題中供應量與需求量之差，令其運價為0。

②需求量大于供應量虛設一個供應點。令這個虛設的供應點的供應量等于實際問題中需求量與供應量的差額，運價為0。

二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量27(5)供需不平衡的物資調運問題通過虛設一個供應點或者需求點，三.運輸線路選擇運輸路線的選擇也是物資調運規(guī)劃的一個重要內容。

運輸路線直接影響到運輸效果的好壞，關系著物資能否及時運到指定地點。當單位輸運輸費用是以噸·公里來計算時，運輸路線的長短就直接關系著運輸費用的多少。本節(jié)采用圖上作業(yè)法來進行運輸線路選擇。28三.運輸線路選擇運輸路線的選擇也是物資調運規(guī)劃的一個重要內1.交通示意圖的表示方法

交通示意圖用來表明收發(fā)點的大致位置、收發(fā)量、交通路線長度的圖形。圖形表示方法：（1）發(fā)點（產(chǎn)地或倉庫）用符號表示，里面的數(shù)字表示發(fā)貨量；（2）收點用（需求地）用符號表示，里面的數(shù)字表示收貨量；（3）兩點間的連線為交通線，其長度記在交通線旁邊。（4）物資調運的方向(流向)用符號表示，并把按物資調運方向畫在交通線的右邊，把調運物資的數(shù)量記在的右邊，并加上括號，以表示和交通線長度區(qū)別。201520510物資調運交通流向圖20（20）102010（5）（15）（10）三.運輸線路選擇291.交通示意圖的表示方法201520510物資調運交通流向2.圖上作業(yè)法目的：根據(jù)交通流向圖，找出運輸力量最小的方案。方法：消滅調運中的對流和迂回兩種不合理運輸。三.運輸線路選擇302.圖上作業(yè)法三.運輸線路選擇30（1）對流

即同一物資在同一線路上的往返運輸。

如下面的圖，將某物資10噸，從A1運到B2，而又有同樣的物資10噸，在同一期間從A2運到B1，于是A1A2間就出現(xiàn)了對流現(xiàn)象。

10101030304030（10）（10）A1A2B1B2

如果從圖上看，對流可以理解為同一條交通線上，有兩條或兩條以上的物資調運方向。10101030304030（10）A1A2B1B2（10）消除對流運力：30*10+20*10=600運力：30*10+40*10+40*10+30*10=1400三.運輸線路選擇31（1）對流10101030304030（10）（10）A（2）迂回

迂回：在交通圖成圈的時候，如果流向圖中內圈流向的總長(簡稱內流長)或外圈流向的總長(簡稱外流長)超過整個圈長的—半，就稱為迂回運輸。

內、外圈的概念：由于表示調運方向的箭頭，要按調運方向，畫在交通線的右邊，因此,流向圖中，有些流向就在圈外，稱為外圈流向；有些流向在圈內，稱為內圈流向。556千米AB（5噸）4千米556千米AB（5噸）4千米迂回運輸無迂回運輸迂回運輸：運力6*5=30噸.千米無迂回運輸：運力4*5=20噸.千米三.運輸線路選擇32（2）迂回556千米AB（5噸）4千米556千米A例題，下圖為一運輸交通圖該交通圖的運輸線路構成圈。圈的總長=2+3+4+4=13內圈長=4+3=7內圈長大于總圈長的一半，為迂回運輸運力：3*30+4*20+4*10=210修改后：內圈長=3外圈長=2+4=6內圈長、外圈長都小于總圈長的一半，不存在迂回運輸運力：2*10+3*20+4*30=200節(jié)省運力：210-200=1010303050243（20）A1B2A24B1（30）（10）10303050243（30）A1B2A24（20）（10）修改三.運輸線路選擇33例題，下圖為一運輸交通圖該交通圖的運輸線路構成圈。10303物資調運問題的圖上作業(yè)法消除運輸過程中的對流和迂回，節(jié)省運輸力量。具體步驟：先畫出一個沒有對流的運輸方案.再檢查有沒有迂回，如果沒有迂回，這方案就是最優(yōu)方案；如果有迂回，則對方案進行調整，直至消除迂回現(xiàn)象為止。在實際的物資調運中，運輸線路可以分為兩種情況：交通線路成圈交通線路不成圈三.運輸線路選擇34物資調運問題的圖上作業(yè)法三.運輸線路選擇343.交通路線不成圈例題3有某物資17萬噸，由A1，A2，A3，A4發(fā)出，發(fā)量分別為5，2，3，7(萬噸)，運往B1，B2，B3，B4，收量分別為8，1，3，5(萬噸)，收發(fā)量平衡，交通路線如圖5—8所示，問應如何調運，才使運輸噸．千米最??？558（5）A1B127313A2A3A4B2B3B4558A1B127313A2A3A4B2B3B4交通線路圖調運流向圖解：該交通線路不成圈，只需要做一沒有對流的調運圖。方法：從各端點開始，由外到里，逐步進行各收發(fā)點之間的平衡（2）（1）（2）（1）（7）（5）353.交通路線不成圈例題3有某物資17萬噸，由A1，A4.交通路線成圈例題4有某物資7萬噸，由A1，A2，A3發(fā)出，發(fā)量分別為3，3，1(萬噸)，運往B1，B2，B3，B4，收量分別為2，3，1，1(萬噸)，收發(fā)量平衡，交通路線如圖5—10所示，問應如何調運，才使運輸噸．千米最小？113334B4A3213A1A2B1B3B2754324364.交通路線成圈例題4113334B4A3213A1A113334B4A3213A1A2B1B3B2754324解:(1)作一個沒有對流的流向圖。方法：用“去線破圈”的方法。去一線破一圈，有幾個圈去掉幾條線，把有圈的交通圖，轉化為不成圈的交通圖。技巧：一般先去掉長度最長的交通線，比如本例中去掉A1B4(7千米)，破A1B1B2A3B4圈；再去掉A3B3線(4千米)，破B2A2B3A3圈。這樣，原來有圈的交通圖，變成了不成圈的交通圖．如圖5—11所示。從各個端點開始，做一個沒有對流的流向圖113334B4A3213A1A2B1B3B2754324（1）（3）（1）（2）（1）37113334B4A3213A1A2B1B3B2754324解

(2)檢查有無迂回。

方法：對流向圖中的各圈進行檢查，如果沒有迂回，則這個初始方案就是最優(yōu)方案，如果其中某圈中有迂回，則不是最優(yōu)方案，需要改進。113334B4A3213A1B1B3B2754324（1）（3）（1）（2）（1）A1B1B2A3B4總圈長=7+3+4+4+5=23外流長=5+4+3=12存在迂回，需要調整。B2A2B3A3總圈長=4+3+2+4=13內流長=3外流長=2不存在迂回，不需要調整A238(2)檢查有無迂回。

方法：對流向圖中的各圈進行檢查，113334B4A3213A1B1B3B2754324（1）（3）（1）（2）A2調整方法：1）在外圈的各流量中，減去外圈的最小流量1萬噸；2）在內圈的各流量中加上1萬噸，在此圈中，因無內流量，故不加。3）在無流量的線路上，新添加內圈流量1萬噸。（-1）（-1）（-1）（+1）（+1）（1）39113334B4A3213A1B1B3B2754324（1）113334B4A3213A1B1B3B2754324（2）（2）A2（1）（1）A1B1B2A3B4總圈長=7+3+4+4+5=23外流長=5內流長=7+4=11不存在迂回。B2A2B3A3總圈長=4+3+2+4=13內流長=3外流長=4+2=6不存在迂回此方案為最優(yōu)調運方案總運力：1*7+2*5+1*4+2*3+1*2=29萬噸千米（1）40113334B4A3213A1B1B3B2754324（2）四.最短路與最大流

1.最短路線例題5某家運輸公司簽定了一項運輸合同，要把A市的一批貨物運送到B市。該公司根據(jù)兩個城市之間可選擇的行車路線地圖，繪制了圖5—13的公路網(wǎng)絡。要求從交通網(wǎng)絡圖中，尋找一條線路最短的運輸路線。1A市4523769810B市100150175300275200175275200300200400250125100150圖中為結點，代表起點、目的地和與行車路線相交的其他城市，其中的數(shù)字為結點編號。箭頭為分支，代表兩個結點之間的公路，箭頭上標明的數(shù)字為運輸里程。公路網(wǎng)絡141四.最短路與最大流1.最短路線1A市452376981解：從終點開始逐步逆向推算。(1)與終點10聯(lián)接的結點有兩個，即結點9和8；從結點9到結點10只有一條線路，該線路為最短線路，長度100，記為：（9-10）100；同樣，結點8到結點10的最短線路為150，記為（8-10）150；(2)結點6。與6聯(lián)接的只有一個結點9，6至9的最短里程為200。而9至終點10的最短里程為100．因此6至終點10的最短里程為200十100＝300。記為：(6-9-10)300。(3)結點5。與5聯(lián)接的結點有9、8兩個。5至9再至終點的最短里程為400十100＝500，5至8再至終點的最短里程為250十155＝400。400＜500，所以5至終點的最短里程為400，記為：(5-8-10)400。(4)結點7。至終點的最短里程為125十150＝275，記為：(7-8-10)275。

1A市4523769810B市10015017527520017527520030020040025012510015030042解：從終點開始逐步逆向推算。1A市4523769810B市1(5)結點4。與4聯(lián)接的結點有5、6、7三個。結點4至6再到終點的最短里程為200十300=500；結點4至5再到終點的最短里程為175十400＝575；結點4至7再到終點的最短里程為275十275＝550。三個里程中以500為最小，所以結點4至l0的最短里程記為(4—6—9—10)500。(6)結點2和3。用同樣的方法，得到：結點2到終點的最短里程為600。記為：(2—6—9—10)600。結點3到終點的最短里程為575。記為：(3—7—8—10)575。(5)最后看結點1。結點1可以通過三個結點2、3、4連接到終點。結點1通過結點2再到終點的最短里程100十600＝700，路徑為（1—2—6—9—10）700；結點1通過結點4再到終點的最短里程150十500＝650，路徑為（1—4—6—9—10）650；結點1通過結點3再到終點的最短里程175十575＝750，路徑為（1—3—7—8—10）750。以上三個里程中以650為最小，即A幣到B市的最短里程，對應的最短路線為：1—4—6—9—10。1A市4523769810B市10015017527520017527520030020040025012510015030043(5)結點4。與4聯(lián)接的結點有5、6、7三個。1A市4523最短路線法的應用物資的運輸路線的選擇物流渠道的設計電纜架設管道鋪設個人旅行中44最短路線法的應用442.最大流當要把大量貨物運輸?shù)街付ǖ牡攸c時，有時會希望找到一條交通量最大的路線，以使貨物能在最短時間內到達。這就是要在有一個起點和一個終點的網(wǎng)絡中，找出在一定時期內，能在起點進入，并通過這個網(wǎng)絡，在終點輸出的最大流量問題。15234566433572起點終點1結點通過能力交通線路452.最大流15234566433572起點終點1結點通過能運輸網(wǎng)絡最大流量的計算例題：某城市從北到南的交通，平時是利用85號公路進行的。目前因為85號公路要進行路面維修，車輛不能通過。技術人員查明：在維修期間可以利用市區(qū)的其它幾條路線通行，現(xiàn)在需要確定這幾條線路組成的交通網(wǎng)絡能否滿足每小時6000輛汽車的通過能力。15234566433572北南該市從北到南的臨時交通網(wǎng)絡如上圖所示，交通線路旁邊的數(shù)字表示單位時間內汽車的通過能力（每小時千輛）?，F(xiàn)在要求從結點1通過公路網(wǎng)到結點6的最大通過能力（最大流量）。846運輸網(wǎng)絡最大流量的計算15234566433572北南該市從計算方法（1）任意選擇一條從起點①到終點⑥的路線。例如，選擇路線1-2-5-6。首先找出這條路線上流量能力最小的支線。從圖上可以看出：5—6支線流量最小，其流量為2，表明沿“1-2-5-6”支線南駛的汽車，每小時的最大流量只能是2千輛，因為5-6支線限制了全線的車流量。其次把這條路線上每條支線的流量減去2。差值則表示該支線剩余的流量。將差值其寫在原來的流量能力的旁邊，并把原來的流量劃掉；把減數(shù)2寫在每條支線的終點，在減數(shù)2的右下角注上(1)，如2（1），表示第一條路線的流量能力為2千輛。標注方式如圖所示。15234566442335720北南2（1）2（1）2（1）47計算方法15234566442335720北南2(2)另選一條從起點1到終點6的路線，如：1-4-6。以該路線上最小的流量能力3為減數(shù)，減去各條支線上的流量。其差數(shù)、減數(shù)的記入方法同上。在差數(shù)3的右下角注上(2)，表示第二條路線的流量能力為3千輛。1523456644230357420北南2（1）2（1）2（1）3（2）3（2）48(2)另選一條從起點1到終點6的路線，如：1-4-6。152（3）再選一條從起點1到終點6的路線，如1-3-4-6。以該路線上最小的流量能力3為減數(shù)，減去各條支線上的流量，其差數(shù)、減數(shù)的記入方式同上。第三條路線的流量能力為3干輛（4）在剩下的流量圖中，已經(jīng)找不到一條完整的路線，滿足所有支路流量大于0的條件，因此能夠通行的交通路線已經(jīng)全部標出。（5）網(wǎng)絡的最大交通能力第一條線路1-2-5-6，流量2千輛/小時；第二條線路1-4-6，流量3千輛/小時；第三條線路1-3-4-6，流量3千輛/小時；該交通網(wǎng)絡的從北到南的最大通行流量為2+3+3=8千輛/小時。滿足每小時6000輛的通過能力。1522345664423030574120北南2（1）2（1）2（1）3（2）3（2）3（3）3（3）3（3）49（3）再選一條從起點1到終點6的路線，如1-3-4-6。15第5章物流系統(tǒng)規(guī)劃5.1概述5.2物流調運規(guī)劃5.3物流分配規(guī)劃5.4其它應用問題50第5章物流系統(tǒng)規(guī)劃5.1概述15.1概述515.1概述2一.物流系統(tǒng)規(guī)劃概述物流系統(tǒng)規(guī)劃所關注的問題是如何合理、有效地利用或配置各種資源（勞動力、材料、設備、資金），使實現(xiàn)預定目標所需的費用最?。ɑ蛸Y源最少），或者所獲得的收益最大。物流系統(tǒng)的規(guī)劃一般都可以用優(yōu)化模型來表達。其基本思想是在滿足一定的約束條件下，使預定的目標值達到最優(yōu)。物流系統(tǒng)規(guī)劃的數(shù)學基礎主要是運籌學理論，常用的方法包括線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃等。52一.物流系統(tǒng)規(guī)劃概述物流系統(tǒng)規(guī)劃所關注的問題是如何合理、有二.物流系統(tǒng)規(guī)劃的目標任務提高物流系統(tǒng)的吞吐能力以適應產(chǎn)量增長的要求；建設一個柔性的物流系統(tǒng)，以適應產(chǎn)品經(jīng)常變化的情況；對生產(chǎn)過程中可能出現(xiàn)的各種意外情況或隨機變化做出及時的響應，保持均衡生產(chǎn)；改善勞動條件，減輕勞動強度；對物流系統(tǒng)中的貨物進行實時跟蹤；對物流系統(tǒng)的貨物進行分類或選配，為隨后的處理(加工或包裝)提供方便條件。53二.物流系統(tǒng)規(guī)劃的目標任務提高物流系統(tǒng)的吞吐能力以適應產(chǎn)量三.評價物流系統(tǒng)規(guī)劃的主要指標經(jīng)濟性。包括初始投資、每年的運營費用、直接或間接的經(jīng)濟效益、投資回收期、全員勞動生產(chǎn)率等；可靠性。包括單個環(huán)節(jié)的可靠性和整個系統(tǒng)的可靠性技術、設備故障率和排除故障所需的時間；可維護性。維護保養(yǎng)所要求的技術水平、備件的供應情況、所需儲備的備件數(shù)量；靈活性或柔性。適應產(chǎn)品設計更改和產(chǎn)量變化的能力，物流系統(tǒng)各環(huán)節(jié)與生產(chǎn)節(jié)奏相匹配的能力，調整物流路線的可能性；可擴展性。在物流系統(tǒng)的服務范圍和吞吐能力方面進—步擴大的可能性；安全性。包括產(chǎn)品的安全、人員的安全、以及正常運行和事故狀態(tài)下的安全保障；勞動強度。需要勞動力的數(shù)量、勞動者的疲勞程度；易操作性。操作簡單、不易出錯，只需少量指令即可使設備和整個系統(tǒng)投入運行；服務水平。對顧客的要求做出快速響應的能力；環(huán)境保護。符合環(huán)境保護條理的要求，對周圍環(huán)境的污染程度低。敏感性。對外界條件變動的敏感程度和適應能力。54三.評價物流系統(tǒng)規(guī)劃的主要指標5四.物流系統(tǒng)規(guī)劃中的變量物流系統(tǒng)規(guī)劃中的控制因素分為兩類不可控因素：設計人員無法左右的種種前提條件?？煽匾蛩兀嚎梢杂梢?guī)劃設計人員在一定范圍內選取的變量。明確了物流系統(tǒng)中可控變量和不可控因素，就能知道加何去影響系統(tǒng)的性能，達到所追求的目標。物流系統(tǒng)的規(guī)劃一般是通過調整可控變量觀察系統(tǒng)性能的變化趨勢，從而選擇可控變量的最佳匹配，達到系統(tǒng)的最佳效果。物流系統(tǒng)的功能除了受可控變量的影響外，還與不可控因素有密切的關系。通常，不可控因素不是非常確定的。55四.物流系統(tǒng)規(guī)劃中的變量物流系統(tǒng)規(guī)劃中的控制因素分為兩類65.2物流系統(tǒng)調運規(guī)劃565.2物流系統(tǒng)調運規(guī)劃7一.問題描述調運規(guī)劃問題描述

設某種要調運的物資，有一組供應點(產(chǎn)地或稱發(fā)點)m個，一組需求點(銷地或稱收點)n個，如果每個供應點的供應量及每個需求點的需求量都已經(jīng)確定，即第i個產(chǎn)地有ai單位的物資發(fā)出，第j個需求點需要收進bj單位的物資；并且從每—個產(chǎn)地到每一個銷地的單位運價是已知的，假定把單位物資從第i個產(chǎn)地調運到第j個銷地去的單位運價為cij。調運規(guī)劃問題也叫運輸問題物資調運規(guī)劃的目的：制訂一個合理的調運方案；確定m個產(chǎn)地與n個銷地之間的供需聯(lián)系和數(shù)量的最優(yōu)搭配；確定具體的運輸路線，使總的運輸費用最低。57一.問題描述調運規(guī)劃問題描述8二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量1.數(shù)學模型設供應點為Ai，該供應點的供應量是ai，（i=1,2,…,m）；設需求點為Bj，該需求點的需求量是bi，（j＝1,2,…,n）；

cij為從第i個供應點到第j個需求點的單位運價；由供應點Ai發(fā)往需求點Bj的物資調運量是xij單位。假設m個供應點的總供應量等于n個需求點的總需求量，（這樣，調運問題滿足供需平衡，稱為平衡運輸問題）。這時，由各供應點Ai調出的物資總量應等于它的供應量ai(i=1,2,…,m)；而每一個需求點Bj調入的物資總量應等于它的需求量bj(j=1,2,…,n)。目標函數(shù)：約束條件58二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量1.數(shù)學模型約束條二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量2.模型求解用線性規(guī)劃方法求解（如單純形法）。用表上作業(yè)法求解（針對這類問題的一種特殊解法）3.表上作業(yè)法的主要步驟首先依據(jù)問題列出調運物資的供需平衡表以及運價表；其次確定一個初始的調運方案(當然不一定就是最優(yōu)的方案)；然后根據(jù)一個判定法則，判定初始方案是否為最優(yōu)方案。當判定初始方案不是最優(yōu)方案時，再對這個方案進行調整。一般情況，每調整一次得到一個新的方案，而這個新方案的運費比前一個方案要少些，如此經(jīng)過幾次調整，就會得到最優(yōu)方案。59二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量2.模型求解10B1B2B3B4供應量(t)A1311310700A21928400A374105900需求量(t)3006005006002000工地料庫運價表5-1某公司物資供應狀況表二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量4.表上作業(yè)法解題實例例題1某公司下屬三個儲存某種物資的倉庫，供應四個工地的需要。三個倉庫的供應量和四個工地的需求量以及由各倉庫到各工地調運單位物資的運價(元／噸)由表5—1給出，試求運輸費用最少的調運方案。60B1B2B3B4供應量(t)A1311310700A2192解：（1）列出物資調運平衡表和運價表

B1B2B3B4供應量(t)A1700A2400A3900需求量(t)3006005006002000需供運價表5-2供需平衡表表5-3運價表

B1B2B3B4A1311310A21928A374105料庫運價工地平衡表中填入的數(shù)字表示供需點之間的調運量；空格表示雙方不發(fā)生調運關系平衡表和運價表是表上作業(yè)法的基本資料和運算的依據(jù)。表上作業(yè)法的實質就是利用運價表在平衡表上進行求解。二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量61解：（1）列出物資調運平衡表和運價表B1B2B3B4供應量（2）編制初始調運方案

物資調運規(guī)劃其總的目的是尋求一個運輸費用最少的最優(yōu)調運方案。一般最優(yōu)方案是由初始方案經(jīng)過反復調整得到的。因此，編制出較好的初始調運方案非常重要。最好的調運方案是使運費最省的方案，因此可以用最小元素法來確定初始調運方案。所謂最小元素法，就是按運價表依次挑選運費少的供——需點盡量優(yōu)先安排供應的調運方法。二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量62（2）編制初始調運方案物資調運規(guī)劃其總的目的是尋求一個運輸B1B2B3B4供應量(t)A1700A2300400A3900需求量(t)3006005006002000需供運量供需平衡表運價表

B1B2B3B4A1311310A21928A374105料庫運價工地1首先，在運價表內找出最小的運價，對本例而言，方格(2，1)數(shù)值是1，最小，這樣，供應點A2盡可能地滿足B1工地的需要，于是在平衡表中有(2，1)＝300，即在空格(2，1)中填入數(shù)字300。此時，由于工地B1已經(jīng)全部得到滿足，不需要其他倉庫供應給它了，運價表中的第一列數(shù)字己不起作用，因此將運價表第一列劃去，并標注符號①，63B1B2B3B4供應量(t)A1700A2300400A39B1B2B3B4供應量(t)A1700A2300100400A3900需求量(t)3006005006002000需供運量供需平衡表運價表

B1B2B3B4A1311310A21928A374105料庫運價工地12然后，在運價表未劃去的各行、列中，再選取一個最小的運價，本例，即(2，3)＝2最小，讓A2料庫盡量供應滿足B3工地的需要。由于A2庫儲量400t已供應給B1工地300t了，所以最多還能供給B3工地100t。于是在平衡表(2，3)空格填入100；相應地由于倉庫A2所儲物資已全部供應完畢，因此，在運價表中與A2同行的運價也不再起作用，所以也將它們劃去，并標注符號②。64B1B2B3B4供應量(t)A1700A2300100400B1B2B3B4供應量(t)A1400700A2300100400A3600300900需求量(t)3006005006002000需供運價供需平衡表運價表

B1B2B3B4A1311310A21928A374105料庫運價工地12435仿照前面的方法，一直作下去，就可得到如左圖所示的運價表和平衡表。此時，在運價表中只有方格(1，4)處的運價沒有劃掉，B4尚有300t的需求，而A1剛好還有300t的物資可以供應，為了滿足供需平衡，所以最后在平衡表上應有(1，4)＝300。這樣就得到表5—6的初始調運方案。65B1B2B3B4供應量(t)A1400700A2300100B1B2B3B4供應量(t)A1400300700A2300100400A3600300900需求量(t)3006005006002000需供運量表5-6初始調運方案3524根據(jù)初始調運方案的運輸量和單位運價，可以計算初始調運方案的運輸費用為：S=1*300+4*600+3*400+2*100+10*300+5*300=8600(元)110價格運量66B1B2B3B4供應量(t)A1400300700A2300（3）初始方案的檢驗與調整1）最優(yōu)方案的數(shù)字表征——檢驗數(shù)相關概念

閉回路：對表上作業(yè)法的初始方案，從調運方案表上的一個空格出發(fā)，存在—條且僅存在一條以該空格(用xij表示)為起點，以其他填有數(shù)字的點為其他頂點的閉合回路，簡稱閉回路。每個頂點都是閉合回路的轉角點；閉合回路是一條封閉折線，每一條邊都是水平或垂直的；每一行(列)若有閉合回路的頂點，則必有兩個（起點所在的行（列）除外）。任一空格的閉合回路不僅是存在的，而且是唯一的。只有從空格出發(fā)，其余各轉角點所對應的方格內均填有數(shù)字時，所構成的閉合回路，才是我們這里所說的閉回路。二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量67（3）初始方案的檢驗與調整1）最優(yōu)方案的數(shù)字表征——檢驗數(shù)二

空格(1，1)：(1，1)—(1，3)—(2，3)—(2，1)一(1，1)

空格(3，1)：(3，I)—(2，1)—(2，3)—(1，3)一(1，4)—(3，4)—(3，1)對所有的空格，都可以用同樣的方法畫出一條閉回路。B1B2B3B4供應量(t)A1400300700A2300100400A3600300900需求量(t)3006005006002000需供二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量68空格(1，1)：(1，1)—(1，3)—(2，3)—(檢驗數(shù)：調運方案的每個空格所形成的閉回路上，作單位物資的運量調整，總可以計算出相應的運費是增加還是減少。我們把所計算出來的每條閉回路上調整單位運量而使運輸費用發(fā)生變化的增減值，稱其為檢驗數(shù)。如果檢驗數(shù)小于零，表示在該空格的閉回路上調整運量使運費減少；如果檢驗數(shù)大于零，則表示在該空格的閉回路上調整運量會使運費增加。

最優(yōu)方案的判定準則：初始調運方案中，如果它所有的檢驗數(shù)都是非負的，那么這個初始調運方案一最優(yōu)。否則。這一調運方案不一定是最優(yōu)的。

（如果所有空格的檢驗數(shù)都小于零，那么如果再對調運方案進行任何調整，都會增加運輸費用）二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量69檢驗數(shù)：調運方案的每個空格所形成的閉回路上，作單位物資的2）用位勢法求檢驗數(shù)將初始調運方案中填有運量的方格對應的運價cij分解為兩部分，即：cij=ui+vj,(對應前面的例題，i=1,2,3;j=1,2,3,4)其中ui和vj分別為該方格對應于i行和j列的位勢量.B1B2B3B4uiA1310U1=2A212U2=1A345U3=-3viv1=0v2=7v3=1v4=8需供C21=u2+v1=1C23=u2+v3=2C13=u1+v3=3……C34=u3+v4=57個未知量，六個方程假定其中一個未知量為0（任意），如假定v1=0,則可以根據(jù)左邊的方程解出全部未知量。位勢計算表第1步：求位勢量702）用位勢法求檢驗數(shù)將初始調運方案中填有運量的方格對B1B2B3B4uiA1[2][9]310U1=2A21[8]2[9]U2=1A3[-3]4[-2]5U3=-3viv1=0v2=7v3=1v4=8需供準檢驗數(shù)表按ui+vj求出各空格的位勢量，得到準檢驗數(shù)表（加方括號表示）準檢驗數(shù)計算過程空格（1，1）=u1+v1=2+0=2（3，1）=u3+v1=-3+0=-3（1，2）=u1+v2=2+7=9（2，2）=u2+v2=1+7=8（3，3）=u3+v3=-3+1=-2（2，4）=u2+v4=1+8=9第2步：求準檢驗數(shù)71B1B2B3B4uiA1[2][9]310U1=2A21[8B1B2B3B4A1[2][9]310A21[8]2[9]A3[-3]4[-2]5第3步：求檢驗數(shù)運價表B1B2B3B4A1311310A21928A374105準檢驗數(shù)表利用運價表與準檢驗數(shù)表求檢驗數(shù)檢驗數(shù)表B1B2B3B4A112A21-1A31012“運價表”減“準檢驗數(shù)表”檢驗結果：檢驗數(shù)出現(xiàn)負值，根據(jù)最優(yōu)方案判斷準則，該方案不是最優(yōu)方案。72B1B2B3B4A1[2][9]310A21[8]2[9]A3）調整調運方案當判定一個初始調運方案不是最優(yōu)調運方案時，就要在檢驗數(shù)出現(xiàn)負值的該空格內進行調整。如果檢驗數(shù)是負值的空格不只一個時，一般選擇檢驗數(shù)為負值且絕對值最大的空格作為具體的調整對象。X13400+100=500X14300-100=200X23100-100=0X240+100=100

B1B2B3B4A1

400300A2300

100

負A3

600

300調整過程：（1）作出負值所在空格的閉回路，本例為空格x24，閉回路如上圖所示。（2）沿閉回路在各奇數(shù)次轉角點中挑選運量的最小數(shù)值作為調整量。本例是將x23方格的100作為調整量，將這個數(shù)填入空格x24內，同時調整該閉回路中其他轉角點上的運量，使各行、列保持原來的供需平衡．這樣使得到一個新的調運方案。733）調整調運方案當判定一個初始調運方案不是最優(yōu)調運方案時，就B1B2B3B4供應量(t)A1500200700A23000100400A3600300900需求量(t)3006005006002000需供運量調整后的調運方案13524108B1B2B3B4A122A241A3912調整后的檢驗數(shù)通過計算其檢驗數(shù)全部非負，此方案為最優(yōu)方案。運輸費用為：S＝3×500十10×200十8×100十1×300十4×600十5×300＝8500(元)該值小于初始調運方案的總運費。74B1B2B3B4供應量(t)A1500200700A2300(4)表上作業(yè)法基本步驟小結①列出調運物資的供需(產(chǎn)銷)平衡表及運價表；②按最小元素法建立初始調運方案；③采用位勢法計算初始方案每個空格的閉回路的檢驗數(shù)xij；④檢查檢驗數(shù)，如果所有xij>=0，說明方案是最優(yōu)的，已經(jīng)得到我們想要的方案，結束求解；⑤如果有某個或某幾個xij<0，則選擇負檢驗數(shù)中絕對值最大的閉回路進行調整，建立新的方案；⑥重復3—5步，直至獲得最優(yōu)調運方案。二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量75(4)表上作業(yè)法基本步驟小結①列出調運物資的供需(產(chǎn)銷)平衡(5)供需不平衡的物資調運問題通過虛設一個供應點或者需求點，將其轉化為平衡運輸問題求解。①供應量大于需求量引入一個虛設的需求點，令其的需求量等于實際問題中供應量與需求量之差，令其運價為0。

②需求量大于供應量虛設一個供應點。令這個虛設的供應點的供應量等于實際問題中需求量與供應量的差額，運價為0。

二.確定產(chǎn)銷地之間的供需聯(lián)系和收發(fā)量76(5)供需不平衡的物資調運問題通過虛設一個供應點或者需求點，三.運輸線路選擇運輸路線的選擇也是物資調運規(guī)劃的一個重要內容。

運輸路線直接影響到運輸效果的好壞，關系著物資能否及時運到指定地點。當單位輸運輸費用是以噸·公里來計算時，運輸路線的長短就直接關系著運輸費用的多少。本節(jié)采用圖上作業(yè)法來進行運輸線路選擇。77三.運輸線路選擇運輸路線的選擇也是物資調運規(guī)劃的一個重要內1.交通示意圖的表示方法

交通示意圖用來表明收發(fā)點的大致位置、收發(fā)量、交通路線長度的圖形。圖形表示方法：（1）發(fā)點（產(chǎn)地或倉庫）用符號表示，里面的數(shù)字表示發(fā)貨量；（2）收點用（需求地）用符號表示，里面的數(shù)字表示收貨量；（3）兩點間的連線為交通線，其長度記在交通線旁邊。（4）物資調運的方向(流向)用符號表示，并把按物資調運方向畫在交通線的右邊，把調運物資的數(shù)量記在的右邊，并加上括號，以表示和交通線長度區(qū)別。201520510物資調運交通流向圖20（20）102010（5）（15）（10）三.運輸線路選擇781.交通示意圖的表示方法201520510物資調運交通流向2.圖上作業(yè)法目的：根據(jù)交通流向圖，找出運輸力量最小的方案。方法：消滅調運中的對流和迂回兩種不合理運輸。三.運輸線路選擇792.圖上作業(yè)法三.運輸線路選擇30（1）對流

即同一物資在同一線路上的往返運輸。

如下面的圖，將某物資10噸，從A1運到B2，而又有同樣的物資10噸，在同一期間從A2運到B1，于是A1A2間就出現(xiàn)了對流現(xiàn)象。

10101030304030（10）（10）A1A2B1B2

如果從圖上看，對流可以理解為同一條交通線上，有兩條或兩條以上的物資調運方向。10101030304030（10）A1A2B1B2（10）消除對流運力：30*10+20*10=600運力：30*10+40*10+40*10+30*10=1400三.運輸線路選擇80（1）對流10101030304030（10）（10）A（2）迂回

迂回：在交通圖成圈的時候，如果流向圖中內圈流向的總長(簡稱內流長)或外圈流向的總長(簡稱外流長)超過整個圈長的—半，就稱為迂回運輸。

內、外圈的概念：由于表示調運方向的箭頭，要按調運方向，畫在交通線的右邊，因此,流向圖中，有些流向就在圈外，稱為外圈流向；有些流向在圈內，稱為內圈流向。556千米AB（5噸）4千米556千米AB（5噸）4千米迂回運輸無迂回運輸迂回運輸：運力6*5=30噸.千米無迂回運輸：運力4*5=20噸.千米三.運輸線路選擇81（2）迂回556千米AB（5噸）4千米556千米A例題，下圖為一運輸交通圖該交通圖的運輸線路構成圈。圈的總長=2+3+4+4=13內圈長=4+3=7內圈長大于總圈長的一半，為迂回運輸運力：3*30+4*20+4*10=210修改后：內圈長=3外圈長=2+4=6內圈長、外圈長都小于總圈長的一半，不存在迂回運輸運力：2*10+3*20+4*30=200節(jié)省運力：210-200=1010303050243（20）A1B2A24B1（30）（10）10303050243（30）A1B2A24（20）（10）修改三.運輸線路選擇82例題，下圖為一運輸交通圖該交通圖的運輸線路構成圈。10303物資調運問題的圖上作業(yè)法消除運輸過程中的對流和迂回，節(jié)省運輸力量。具體步驟：先畫出一個沒有對流的運輸方案.再檢查有沒有迂回，如果沒有迂回，這方案就是最優(yōu)方案；如果有迂回，則對方案進行調整，直至消除迂回現(xiàn)象為止。在實際的物資調運中，運輸線路可以分為兩種情況：交通線路成圈交通線路不成圈三.運輸線路選擇83物資調運問題的圖上作業(yè)法三.運輸線路選擇343.交通路線不成圈例題3有某物資17萬噸，由A1，A2，A3，A4發(fā)出，發(fā)量分別為5，2，3，7(萬噸)，運往B1，B2，B3，B4，收量分別為8，1，3，5(萬噸)，收發(fā)量平衡，交通路線如圖5—8所示，問應如何調運，才使運輸噸．千米最??？558（5）A1B127313A2A3A4B2B3B4558A1B127313A2A3A4B2B3B4交通線路圖調運流向圖解：該交通線路不成圈，只需要做一沒有對流的調運圖。方法：從各端點開始，由外到里，逐步進行各收發(fā)點之間的平衡（2）（1）（2）（1）（7）（5）843.交通路線不成圈例題3有某物資17萬噸，由A1，A4.交通路線成圈例題4有某物資7萬噸，由A1，A2，A3發(fā)出，發(fā)量分別為3，3，1(萬噸)，運往B1，B2，B3，B4，收量分別為2，3，1，1(萬噸)，收發(fā)量平衡，交通路線如圖5—10所示，問應如何調運，才使運輸噸．千米最?。?13334B4A3213A1A2B1B3B2754324854.交通路線成圈例題4113334B4A3213A1A113334B4A3213A1A2B1B3B2754324解:(1)作一個沒有對流的流向圖。方法：用“去線破圈”的方法。去一線破一圈，有幾個圈去掉幾條線，把有圈的交通圖，轉化為不成圈的交通圖。技巧：一般先去掉長度最長的交通線，比如本例中去掉A1B4(7千米)，破A1B1B2A3B4圈；再去掉A3B3線(4千米)，破B2A2B3A3圈。這樣，原來有圈的交通圖，變成了不成圈的交通圖．如圖5—11所示。從各個端點開始，做一個沒有對流的流向圖113334B4A3213A1A2B1B3B2754324（1）（3）（1）（2）（1）86113334B4A3213A1A2B1B3B2754324解

(2)檢查有無迂回。

方法：對流向圖中的各圈進行檢查，如果沒有迂回，則這個初始方案就是最優(yōu)方案，如果其中某圈中有迂回，則不是最優(yōu)方案，需要改進。113334B4A3213A1B1B3B2754324（1）（3）（1）（2）（1）A1B1B2A3B4總圈長=7+3+4+4+5=23外流長=5+4+3=12存在迂回，需要調整。B2A2B3A3總圈長=4+3+2+4=13內流長=3外流長=2不存在迂回，不需要調整A287(2)檢查有無迂回。

方法：對流向圖中的各圈進行檢查，113334B4A3213A1B1B3B2754324（1）（3）（1）（2）A2調整方法：1）在外圈的各流量中，減去外圈的最小流量1萬噸；2）在內圈的各流量中加上1萬噸，在此圈中，因無內流量，故不加。3）在無流量的線路上，新添加內圈流量1萬噸。（-1）（-1）（-1）（+1）（+1）（1）88113334B4A3213A1B1B3B2754324（1）113334B4A3213A1B1B3B2754324（2）（2）A2（1）（1）A1B1B2A3B4總圈長=7+3+4+4+5=23外流長=5內流長=7+4=11不存在迂回。B2A2B3A3總圈長=4+3+2+4=13內流長=3外流長=4+2=6不存在迂回此方案為最優(yōu)調運方案總運力：1*7+2*5+1*4+2*3+1*2=29萬噸千米（1）89113334B4A3213A1B1B3B2754324（2）四.最短路與最大流

1.最短路線例題5某家運輸公司簽定了一項運輸合同，要把A市的一批貨物運送到B市。該公司根據(jù)兩個城市之間可選擇的行車路線地圖，繪制了圖5—13的公路網(wǎng)絡。要求從交通網(wǎng)絡圖中，尋找一條線路最短的運輸路線。1A市4523769810B市1001501753002