第5章物流系統(tǒng)規(guī)劃ppt課件

1、1第5章 物流系統(tǒng)規(guī)劃5.1 概述5.2 物流調(diào)運規(guī)劃5.3 物流分配規(guī)劃5.4 其它運用問題25.1 概述3一. 物流系統(tǒng)規(guī)劃概述物流系統(tǒng)規(guī)劃所關(guān)注的問題是如何合理、有效地利用或配置各種資源勞動力、資料、設(shè)備、資金，使實現(xiàn)預(yù)定目的所需的費用最小或資源最少，或者所獲得的收益最大。物流系統(tǒng)的規(guī)劃普通都可以用優(yōu)化模型來表達(dá)。其根本思想是在滿足一定的約束條件下，使預(yù)定的目的值到達(dá)最優(yōu)。物流系統(tǒng)規(guī)劃的數(shù)學(xué)根底主要是運籌學(xué)實際，常用的方法包括線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃等。4二. 物流系統(tǒng)規(guī)劃的目的義務(wù)提高物流系統(tǒng)的吞吐才干以順應(yīng)產(chǎn)量增長的要求；建立一個柔性的物流系統(tǒng)，以順應(yīng)產(chǎn)品經(jīng)常變化的情況；對消費過

2、程中能夠出現(xiàn)的各種不測情況或隨機變化做出及時的呼應(yīng)，堅持平衡消費；改善勞動條件，減輕勞動強度；對物流系統(tǒng)中的貨物進(jìn)展實時跟蹤；對物流系統(tǒng)的貨物進(jìn)展分類或選配，為隨后的處置(加工或包裝)提供方便條件。 5三. 評價物流系統(tǒng)規(guī)劃的主要目的經(jīng)濟(jì)性。包括初始投資、每年的運營費用、直接或間接的經(jīng)濟(jì)效益、投資回收期、全員勞動消費率等；可靠性。包括單個環(huán)節(jié)的可靠性和整個系統(tǒng)的可靠性技術(shù)、設(shè)備缺點率和排除缺點所需的時間；可維護(hù)性。維護(hù)保養(yǎng)所要求的技術(shù)程度、備件的供應(yīng)情況、所需貯藏的備件數(shù)量；靈敏性或柔性。順應(yīng)產(chǎn)品設(shè)計更改和產(chǎn)量變化的才干，物流系統(tǒng)各環(huán)節(jié)與消費節(jié)拍相匹配的才干，調(diào)整物流道路的能夠性；可擴(kuò)展性。在

3、物流系統(tǒng)的效力范圍和吞吐才干方面進(jìn)步擴(kuò)展的能夠性；平安性。包括產(chǎn)品的平安、人員的平安、以及正常運轉(zhuǎn)和事故形狀下的平安保證；勞動強度。需求勞動力的數(shù)量、勞動者的疲勞程度；易操作性。操作簡單、不易出錯，只需少量指令即可使設(shè)備和整個系統(tǒng)投入運轉(zhuǎn)；效力程度。對顧客的要求做出快速呼應(yīng)的才干；環(huán)境維護(hù)。符合環(huán)境維護(hù)條理的要求，對周圍環(huán)境的污染程度低。敏感性。對外界條件變動的敏感程度和順應(yīng)才干。6四. 物流系統(tǒng)規(guī)劃中的變量物流系統(tǒng)規(guī)劃中的控制要素分為兩類不可控要素：設(shè)計人員無法左右的種種前提條件?？煽匾兀嚎梢杂梢?guī)劃設(shè)計人員在一定范圍內(nèi)選取的變量。明確了物流系統(tǒng)中可控變量和不可控要素，就能知道加何去影響系統(tǒng)

4、的性能，到達(dá)所追求的目的。 物流系統(tǒng)的規(guī)劃普通是經(jīng)過調(diào)整可控變量察看系統(tǒng)性能的變化趨勢，從而選擇可控變量的最正確匹配，到達(dá)系統(tǒng)的最正確效果。 物流系統(tǒng)的功能除了受可控變量的影響外，還與不可控要素有親密的關(guān)系。通常，不可控要素不是非常確定的。75.2 物流系統(tǒng)調(diào)運規(guī)劃8一. 問題描畫調(diào)運規(guī)劃問題描畫 設(shè) 某種要調(diào)運的物資，有一組供應(yīng)點(產(chǎn)地或稱發(fā)點)m個，一組需求點(銷地或稱收點)n個，假設(shè)每個供應(yīng)點的供應(yīng)量及每個需求點的需求量都曾經(jīng)確定，即第i個產(chǎn)地有ai 單位的物資發(fā)出，第j個需求點需求收進(jìn)bj單位的物資；并且從每個產(chǎn)地到每一個銷地的單位運價是知的，假定把單位物資從第i個產(chǎn)地調(diào)運到第j個銷地

5、去的單位運價為cij 。調(diào)運規(guī)劃問題也叫運輸問題物資調(diào)運規(guī)劃的目的：制定一個合理的調(diào)運方案；確定m個產(chǎn)地與n個銷地之間的供需聯(lián)絡(luò)和數(shù)量的最優(yōu)搭配；確定詳細(xì)的運輸?shù)缆?，使總的運輸費用最低。9二. 確定產(chǎn)銷地之間的供需聯(lián)絡(luò)和收發(fā)量1. 數(shù)學(xué)模型 設(shè)供應(yīng)點為Ai，該供應(yīng)點的供應(yīng)量是ai，i=1,2,m； 設(shè)需求點為Bj，該需求點的需求量是bi，j1,2,n； cij為從第i個供應(yīng)點到第j個需求點的單位運價； 由供應(yīng)點Ai發(fā)往需求點Bj的物資調(diào)運量是xij單位。 假設(shè)m個供應(yīng)點的總供應(yīng)量等于n個需求點的總需求量，這樣，調(diào)運問題滿足供需平衡，稱為平衡運輸問題。這時，由各供應(yīng)點Ai調(diào)出的物資總量應(yīng)等于它的

6、供應(yīng)量ai(i=1,2,m)；而每一個需求點Bj調(diào)入的物資總量應(yīng)等于它的需求量bj(j=1,2,n)。目的函數(shù)：約束條件10二. 確定產(chǎn)銷地之間的供需聯(lián)絡(luò)和收發(fā)量2. 模型求解用線性規(guī)劃方法求解如單純形法。用表上作業(yè)法求解針對這類問題的一種特殊解法3.表上作業(yè)法的主要步驟首先根據(jù)問題列出調(diào)運物資的供需平衡表以及運價表；其次確定一個初始的調(diào)運方案(當(dāng)然不一定就是最優(yōu)的方案)；然后根據(jù)一個斷定法那么，斷定初始方案能否為最優(yōu)方案。當(dāng)斷定初始方案不是最優(yōu)方案時，再對這個方案進(jìn)展調(diào)整。普通情況，每調(diào)整一次得到一個新的方案，而這個新方案的運費比前一個方案要少些，如此經(jīng)過幾次調(diào)整，就會得到最優(yōu)方案。11B1

7、B2B3B4供應(yīng)量(t)A1311310700A21928400A374105900需求量(t)3006005006002000工地料庫運價表5-1 某公司物資供應(yīng)情況表二. 確定產(chǎn)銷地之間的供需聯(lián)絡(luò)和收發(fā)量4. 表上作業(yè)法解題實例例題1 某公司下屬三個儲存某種物資的倉庫，供應(yīng)四個工地的需求。三個倉庫的供應(yīng)量和四個工地的需求量以及由各倉庫到各工地調(diào)運單位物資的運價(元噸)由表51給出，試求運輸費用最少的調(diào)運方案。12解：1列出物資調(diào)運平衡表和運價表 B1B2B3B4供應(yīng)量(t)A1700A2400A3900需求量(t)3006005006002000需供運價表5-2 供需平衡表表5-3 運價表

8、B1B2B3B4A1311310A21928A374105料庫運價工地平衡表中填入的數(shù)字表示供需點之間的調(diào)運量；空格表示雙方不發(fā)生調(diào)運關(guān)系平衡表和運價表是表上作業(yè)法的根本資料和運算的根據(jù)。表上作業(yè)法的本質(zhì)就是利用運價表在平衡表上進(jìn)展求解。 二. 確定產(chǎn)銷地之間的供需聯(lián)絡(luò)和收發(fā)量132編制初始調(diào)運方案 物資調(diào)運規(guī)劃其總的目的是尋求一個運輸費用最少的最優(yōu)調(diào)運方案。普通最優(yōu)方案是由初始方案經(jīng)過反復(fù)調(diào)整得到的。因此，編制出較好的初始調(diào)運方案非常重要。最好的調(diào)運方案是使運費最省的方案，因此可以用最小元素法來確定初始調(diào)運方案。所謂最小元素法，就是按運價表依次挑選運費少的供需點盡量優(yōu)先安排供應(yīng)的調(diào)運方法。二

9、. 確定產(chǎn)銷地之間的供需聯(lián)絡(luò)和收發(fā)量B1B2B3B4供應(yīng)量(t)A1700A2300400A3900需求量(t)3006005006002000需供運量供需平衡表 運價表B1B2B3B4A1311310A21928A374105料庫運價工地1 首先，在運價表內(nèi)找出最小的運價，對本例而言，方格(2，1)數(shù)值是1，最小，這樣，供應(yīng)點A2盡能夠地滿足B1工地的需求，于是在平衡表中有(2，1)300，即在空格(2，1)中填入數(shù)字300。 此時，由于工地B1曾經(jīng)全部得到滿足，不需求其他倉庫供應(yīng)給它了，運價表中的第一列數(shù)字己不起作用，因此將運價表第一列劃去，并標(biāo)注符號， B1B2B3B4供應(yīng)量(t)A17

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

11、0400A3600300900需求量(t)3006005006002000需供運價供需平衡表 運價表B1B2B3B4A1311310A21928A374105料庫運價工地12435仿照前面的方法，不斷作下去，就可得到如左圖所示的運價表和平衡表。 此時，在運價表中只需方格(1，4)處的運價沒有劃掉，B4尚有300t的需求，而A1剛好還有300t的物資可以供應(yīng)，為了滿足供需平衡，所以最后在平衡表上應(yīng)有(1，4)300。這樣就得到表56的初始調(diào)運方案。B1B2B3B4供應(yīng)量(t)A1400300700A2300100400A3600300900需求量(t)3006005006002000需供運量表5

12、-6 初始調(diào)運方案3524根據(jù)初始調(diào)運方案的運輸量和單位運價，可以計算初始調(diào)運方案的運輸費用為： S=1*300+4*600+3*400+2*100+10*300+5*300=8600(元)110價錢運量183初始方案的檢驗與調(diào)整1最優(yōu)方案的數(shù)字表征檢驗數(shù)相關(guān)概念 閉回路：對表上作業(yè)法的初始方案，從調(diào)運方案表上的一個空格出發(fā)，存在條且僅存在一條以該空格(用 xij 表示)為起點，以其他填有數(shù)字的點為其他頂點的閉合回路，簡稱閉回路。 每個頂點都是閉合回路的轉(zhuǎn)角點；閉合回路是一條封鎖折線，每一條邊 都是程度或垂直的；每一行(列)假設(shè)有閉合回路的頂點，那么必有兩個起點所在的行列除外。任一空格的閉合回

13、路不僅是存在的，而且是獨一的。只需從空格出發(fā)，其他各轉(zhuǎn)角點所對應(yīng)的方格內(nèi)均填有數(shù)字時，所構(gòu)成的閉合回路，才是我們這里所說的閉回路 。二. 確定產(chǎn)銷地之間的供需聯(lián)絡(luò)和收發(fā)量19 空格(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供應(yīng)量(t)A1400300700A2300100400A3600300900需求量(t)3006005006002000需供二. 確定產(chǎn)銷地之間的供需聯(lián)絡(luò)和收發(fā)量20 檢驗數(shù)：調(diào)運方案的每個空格所

14、構(gòu)成的閉回路上，作單位物資的運量調(diào)整，總可以計算出相應(yīng)的運費是添加還是減少。我們把所計算出來的每條閉回路上調(diào)整單位運量而使運輸費用發(fā)生變化的增減值，稱其為檢驗數(shù)。假設(shè)檢驗數(shù)小于零，表示在該空格的閉回路上調(diào)整運量使運費減少；假設(shè)檢驗數(shù)大于零，那么表示在該空格的閉回路上調(diào)整運量會使運費添加。 最優(yōu)方案的斷定準(zhǔn)那么： 初始調(diào)運方案中，假設(shè)它一切的檢驗數(shù)都是非負(fù)的，那么這個初始調(diào)運方案一最優(yōu)。否那么。這一調(diào)運方案不一定是最優(yōu)的。 假設(shè)一切空格的檢驗數(shù)都小于零，那么假設(shè)再對調(diào)運方案進(jìn)展任何調(diào)整，都會添加運輸費用 二. 確定產(chǎn)銷地之間的供需聯(lián)絡(luò)和收發(fā)量2用位勢法求檢驗數(shù) 將初始調(diào)運方案中填有運量的方格對應(yīng)

15、的運價cij分解為兩部分，即： cij =ui+vj ,(對應(yīng)前面的例題，i=1,2,3; j=1,2,3,4) 其中ui和vj 分別為該方格對應(yīng)于i行和j列的位勢量.B1B2B3B4uiA1310U1=2A212U2=1A345U3=-3viv1=0v2=7v3=1v4=8需供C21=u2+v1=1C23=u2+v3=2C13=u1+v3=3C34=u3+v4=57個未知量，六個方程假定其中一個未知量為0恣意，如假定v1=0,那么可以根據(jù)左邊的方程解出全部未知量。位勢計算表第1步：求位勢量B1B2B3B4uiA129310U1=2A21829U2=1A3-34-25U3=-3viv1=0v2

16、=7v3=1v4=8需供準(zhǔn)檢驗數(shù)表按ui+vj求出各空格的位勢量，得到準(zhǔn)檢驗數(shù)表加方括號表示準(zhǔn)檢驗數(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步：求準(zhǔn)檢驗數(shù)B1B2B3B4A129310A21829A3-34-25第3步：求檢驗數(shù) 運價表B1B2B3B4A1311310A21928A374105 準(zhǔn)檢驗數(shù)表 利用運價表與準(zhǔn)檢驗數(shù)表求檢驗數(shù) 檢驗數(shù)表B1B2B3B4A112A21-1A3

17、1012“運價表 減 “準(zhǔn)檢驗數(shù)表檢驗結(jié)果：檢驗數(shù)出現(xiàn)負(fù)值，根據(jù)最優(yōu)方案判別準(zhǔn)那么，該方案不是最優(yōu)方案。3調(diào)整調(diào)運方案當(dāng)斷定一個初始調(diào)運方案不是最優(yōu)調(diào)運方案時，就要在檢驗數(shù)出現(xiàn)負(fù)值的該空格內(nèi)進(jìn)展調(diào)整。假設(shè)檢驗數(shù)是負(fù)值的空格不只一個時，普通選擇檢驗數(shù)為負(fù)值且絕對值最大的空格作為詳細(xì)的調(diào)整對象。X13400+100=500X14300-100=200X23100-100=0X240+100=100B1B2B3B4A1400300A2300100負(fù)A3600300調(diào)整過程：1作出負(fù)值所在空格的閉回路，本例為空格x24，閉回路如上圖所示。2沿閉回路在各奇數(shù)次轉(zhuǎn)角點中挑選運量的最小數(shù)值作為調(diào)整量。本例是

18、將x23方格的100作為調(diào)整量，將這個數(shù)填入空格x24內(nèi)，同時調(diào)整該閉回路中其他轉(zhuǎn)角點上的運量，使各行、列堅持原來的供需平衡這樣使得到一個新的調(diào)運方案。B1B2B3B4供應(yīng)量(t)A1500200700A23000100400A3600300900需求量(t)3006005006002000需供運量調(diào)整后的調(diào)運方案13524108B1B2B3B4A122A241A3912調(diào)整后的檢驗數(shù)經(jīng)過計算其檢驗數(shù)全部非負(fù)，此方案為最優(yōu)方案。運輸費用為：S3500十10200十8100十1300十4600十5300 8500(元) 該值小于初始調(diào)運方案的總運費。26(4)表上作業(yè)法根本步驟小結(jié)列出調(diào)運物資的

19、供需(產(chǎn)銷)平衡表及運價表；按最小元素法建立初始調(diào)運方案；采用位勢法計算初始方案每個空格的閉回路的檢驗數(shù)xij ；檢查檢驗數(shù)，假設(shè)一切xij =0，闡明方案是最優(yōu)的，曾經(jīng)得到我們想要的方案，終了求解；假設(shè)有某個或某幾個xij0，那么選擇負(fù)檢驗數(shù)中絕對值最大的閉回路進(jìn)展調(diào)整，建立新的方案；反復(fù)35步，直至獲得最優(yōu)調(diào)運方案。二. 確定產(chǎn)銷地之間的供需聯(lián)絡(luò)和收發(fā)量27(5)供需不平衡的物資調(diào)運問題經(jīng)過虛設(shè)一個供應(yīng)點或者需求點，將其轉(zhuǎn)化為平衡運輸問題求解。 供應(yīng)量大于需求量 引入一個虛設(shè)的需求點，令其的需求量等于實踐問題中供應(yīng)量與需求量之差，令其運價為0。 需求量大于供應(yīng)量 虛設(shè)一個供應(yīng)點。令這個虛設(shè)

20、的供應(yīng)點的供應(yīng)量等于實踐問題中需求量與供應(yīng)量的差額，運價為0。 二. 確定產(chǎn)銷地之間的供需聯(lián)絡(luò)和收發(fā)量28三. 運輸線路選擇運輸?shù)缆返倪x擇也是物資調(diào)運規(guī)劃的一個重要內(nèi)容。 運輸?shù)缆分苯佑绊懙竭\輸效果的好壞，關(guān)系著物資能否及時運到指定地點。當(dāng)單位輸運輸費用是以噸公里來計算時，運輸?shù)缆返拈L短就直接關(guān)系著運輸費用的多少。 本節(jié)采用圖上作業(yè)法來進(jìn)展運輸線路選擇。291. 交通表示圖的表示方法 交通表示圖用來闡明收發(fā)點的大致位置、收發(fā)量、交通道路長度的圖形。圖形表示方法：1發(fā)點產(chǎn)地或倉庫用符號 表示，里面的數(shù)字表示發(fā)貨量；2收點用需求地用符號 表示，里面的數(shù)字表示收貨量；3兩點間的連線為交通線，其長度記

21、在交通線旁邊。4物資調(diào)運的方向(流向)用符號 表示，并把 按物資調(diào)運方向畫在交通線的右邊，把調(diào)運物資的數(shù)量記在 的右邊，并加上括號，以表示和交通線長度區(qū)別。201520510物資調(diào)運交通流向圖202010201051510三. 運輸線路選擇302.圖上作業(yè)法目的：根據(jù)交通流向圖，找出運輸力量最小的方案。方法：消滅調(diào)運中的對流和迂回兩種不合理運輸。三. 運輸線路選擇311 對流 即同一物資在同一線路上的往返運輸。 如下面的圖， 將某物資10噸，從A1運到B2，而又有同樣的物資10噸，在同一期間從A2運到B1，于是A1A2間就出現(xiàn)了對流景象。 101010303040301010A1A2B1B2

22、假設(shè)從圖上看，對流可以了解為同一條交通線上，有兩條或兩條以上的物資調(diào)運方向。1010103030403010A1A2B1B210消除對流運力：30*10+20*10=600運力：30*10+40*10+40*10+30*10=1400三. 運輸線路選擇322迂回 迂回： 在交通圖成圈的時候，假設(shè)流向圖中內(nèi)圈流向的總長(簡稱內(nèi)流長)或外圈流向的總長(簡稱外流長)超越整個圈長的半，就稱為迂回運輸。 內(nèi)、外圈的概念：由于表示調(diào)運方向的箭頭，要按調(diào)運方向，畫在交通線的右邊，因此,流向圖中，有些流向就在圈外，稱為外圈流向；有些流向在圈內(nèi)，稱為內(nèi)圈流向。556千米AB5噸4千米556千米AB5噸4千米迂回

23、運輸無迂回運輸迂回運輸：運力 6*5=30噸.千米無迂回運輸：運力 4*5=20噸.千米三. 運輸線路選擇33例題，以下圖為一運輸交通圖該交通圖的運輸線路構(gòu)成圈。圈的總長=2+3+4+4=13內(nèi)圈長=4+3=7內(nèi)圈長大于總?cè)﹂L 的一半，為迂回運輸運力：3*30+4*20+4*10=210修正后：內(nèi)圈長=3外圈長=2+4=6內(nèi)圈長、外圈長都小于總?cè)﹂L的一半，不存在迂回運輸運力：2*10+3*20+4*30=200節(jié)省運力：210-200=101030305024320A1B2A24B130101030305024330A1B2A242010修正三. 運輸線路選擇34物資調(diào)運問題的圖上作業(yè)法消除運

24、輸過程中的對流和迂回，節(jié)省運輸力量。詳細(xì)步驟：先畫出一個沒有對流的運輸方案.再檢查有沒有迂回，假設(shè)沒有迂回，這方案就是最優(yōu)方案；假設(shè)有迂回，那么對方案進(jìn)展調(diào)整，直至消除迂回景象為止。在實踐的物資調(diào)運中，運輸線路可以分為兩種情況： 交通線路成圈 交通線路不成圈三. 運輸線路選擇3. 交通道路不成圈例題3 有某物資17萬噸，由A1，A2，A3，A4發(fā)出，發(fā)量分別為5，2，3，7(萬噸)，運往B1，B2，B3，B4，收量分別為8，1，3，5(萬噸)，收發(fā)量平衡，交通道路如圖58所示，問應(yīng)如何調(diào)運，才使運輸噸千米最小？5585A1B127313A2A3A4B2B3B4558A1B127313A2A3A

25、4B2B3B4交通線路圖調(diào)運流向圖解：該交通線路不成圈，只需求做一沒有對流的調(diào)運圖。方法：從各端點開場，由外到里，逐漸進(jìn)展各收發(fā)點之間的平衡2121754. 交通道路成圈例題4 有某物資7萬噸，由A1，A2，A3發(fā)出，發(fā)量分別為3，3，1(萬噸)，運往B1，B2，B3，B4，收量分別為2，3，1，1(萬噸)，收發(fā)量平衡，交通道路如圖510所示，問應(yīng)如何調(diào)運，才使運輸噸千米最??？113334B4A3213A1A2B1B3B2754324113334B4A3213A1A2B1B3B2754324解: (1)作一個沒有對流的流向圖。 方法：用“去線破圈的方法。去一線破一圈，有幾個圈去掉幾條線，把有圈

26、的交通圖，轉(zhuǎn)化為不成圈的交通圖。 技巧：普通先去掉長度最長的交通線，比如本例中去掉A1B4(7千米)，破A1B1B2A3B4圈；再去掉A3B3線(4千米)，破B2A2B3A3圈。這樣，原來有圈的交通圖，變成了不成圈的交通圖如圖511所示。從各個端點開場，做一個沒有對流的流向圖113334B4A3213A1A2B1B3B275432413121 (2)檢查有無迂回。 方法：對流向圖中的各圈進(jìn)展檢查，假設(shè)沒有迂回，那么這個初始方案就是最優(yōu)方案，假設(shè)其中某圈中有迂回，那么不是最優(yōu)方案，需求改良。113334B4A3213A1B1B3B275432413121A1B1B2A3B4總?cè)﹂L=7+3+4+4

27、+5=23外流長=5+4+3=12存在迂回，需求調(diào)整。B2A2B3A3總?cè)﹂L=4+3+2+4=13內(nèi)流長=3外流長=2不存在迂回，不需求調(diào)整A2113334B4A3213A1B1B3B27543241312A2調(diào)整方法：1在外圈的各流量中，減去外圈的最小流量1萬噸；2在內(nèi)圈的各流量中加上1萬噸，在此圈中，因無內(nèi)流量，故不加。3在無流量的線路上，新添加內(nèi)圈流量1萬噸。-1-1-1+1+11113334B4A3213A1B1B3B275432422A211A1B1B2A3B4總?cè)﹂L=7+3+4+4+5=23外流長=5內(nèi)流長=7+4=11不存在迂回。B2A2B3A3總?cè)﹂L=4+3+2+4=13內(nèi)流長

28、=3外流長=4+2=6不存在迂回此方案為最優(yōu)調(diào)運方案總運力：1*7+2*5+1*4+2*3+1*2=29萬噸千米141四. 最短路與最大流 1. 最短道路例題5 某家運輸公司簽定了一項運輸合同，要把A市的一批貨物運送到B市。該公司根據(jù)兩個城市之間可選擇的行車道路地圖，繪制了圖513的公路網(wǎng)絡(luò)。要求從交通網(wǎng)絡(luò)圖中，尋覓一條線路最短的運輸?shù)缆贰?A市4523769810B市100150175300275200175275200300200400250125100150 圖中 為結(jié)點，代表起點、目的地和與行車道路相交的其他城市，其中的數(shù)字為結(jié)點編號。箭頭為分支，代表兩個結(jié)點之間的公路，箭頭上標(biāo)明的數(shù)

29、字為運輸里程。公路網(wǎng)絡(luò)1解：從終點開場逐漸逆向推算。 (1)與終點10聯(lián)接的結(jié)點有兩個，即結(jié)點9和8； 從結(jié)點9到結(jié)點10只需一條線路，該線路為最短線路，長度100，記為：9-10100； 同樣，結(jié)點8到結(jié)點10的最短線路為150，記為8-10150； (2)結(jié)點6。與6聯(lián)接的只需一個結(jié)點9，6至9的最短里程為200。而9至終點10的最短里程為100因此6至終點10的最短里程為200十100300。記為：(6-9-10)300。 (3)結(jié)點5。與5聯(lián)接的結(jié)點有9、8兩個。 5至9再至終點的最短里程為400十100500， 5至8再至終點的最短里程為250十155400。 400500，所以5至

30、終點的最短里程為400，記為：(5-8-10)400。 (4) 結(jié)點7。至終點的最短里程為125十150275，記為：(7-8-10) 275。 1A市4523769810B市100150175275200175275200300200400250125100150300(5)結(jié)點4。與4聯(lián)接的結(jié)點有5、6、7三個。 結(jié)點4至6再到終點的最短里程為200十300=500； 結(jié)點4至5再到終點的最短里程為175十400575； 結(jié)點4至7再到終點的最短里程為275十275550。 三個里程中以500為最小，所以結(jié)點4至l 0的最短里程記為(46910) 500。(6)結(jié)點2和3。 用同樣的方法，

31、得到： 結(jié)點2到終點的最短里程為600。記為：(26910)600。 結(jié)點3到終點的最短里程為575。記為：(37810)575。 (5)最后看結(jié)點1。結(jié)點1可以經(jīng)過三個結(jié)點2、3、4銜接到終點。 結(jié)點1經(jīng)過結(jié)點2再到終點的最短里程100十600700，途徑為126910700； 結(jié)點1經(jīng)過結(jié)點4再到終點的最短里程150十500650，途徑為146910650； 結(jié)點1經(jīng)過結(jié)點3再到終點的最短里程175十575750，途徑為137810750。 以上三個里程中以650為最小，即A幣到B市的最短里程，對應(yīng)的最短道路為：146910。1A市4523769810B市10015017527520017

32、527520030020040025012510015030044最短道路法的運用物資的運輸?shù)缆返倪x擇物流渠道的設(shè)計電纜架設(shè)管道鋪設(shè)個人游覽中452. 最大流當(dāng)要把大量貨物運輸?shù)街付ǖ牡攸c時，有時會希望找到一條交通量最大的道路，以使貨物能在最短時間內(nèi)到達(dá)。這就是要在有一個起點和一個終點的網(wǎng)絡(luò)中，找出在一定時期內(nèi)，能在起點進(jìn)入，并經(jīng)過這個網(wǎng)絡(luò)，在終點輸出的最大流量問題。15234566433572起點終點1結(jié)點經(jīng)過才干交通線路46運輸網(wǎng)絡(luò)最大流量的計算 例題：某城市從北到南的交通，平常是利用85號公路進(jìn)展的。目前由于85號公路要進(jìn)展路面維修，車輛不能經(jīng)過。技術(shù)人員查明：在維修期間可以利用市區(qū)的其

33、它幾條道路通行，如今需求確定這幾條線路組成的交通網(wǎng)絡(luò)能否滿足每小時6000輛汽車的經(jīng)過才干。15234566433572北南該市從北到南的暫時交通網(wǎng)絡(luò)如上圖所示，交通線路旁邊的數(shù)字表示單位時間內(nèi)汽車的經(jīng)過才干每小時千輛。如今要求從結(jié)點1經(jīng)過公路網(wǎng)到結(jié)點6的最大經(jīng)過才干最大流量。8計算方法1恣意選擇一條從起點到終點的道路。例如，選擇道路1-2-5-6。首先找出這條道路上流量才干最小的支線。從圖上可以看出：56支線流量最小，其流量為2，闡明沿“1-2-5-6支線南駛的汽車，每小時的最大流量只能是2千輛，由于5-6支線限制了全線的車流量。其次把這條道路上每條支線的流量減去2。差值那么表示該支線剩余的

34、流量。將差值其寫在原來的流量才干的旁邊，并把原來的流量劃掉；把減數(shù)2寫在每條支線的終點，在減數(shù)2的右下角注上(1)，如21，表示第一條道路的流量才干為2千輛。標(biāo)注方式如下圖。15234566 44 233572 0北南212121(2)另選一條從起點1到終點6的道路，如：1-4-6。 以該道路上最小的流量才干3為減數(shù)，減去各條支線上的流量。其差數(shù)、減數(shù)的記入方法同上。在差數(shù)3的右下角注上(2)，表示第二條道路的流量才干為3千輛。15234566 44 23 0357 42 0北南21212132323再選一條從起點1到終點6的道路，如1-3-4-6。 以該道路上最小的流量才干3為減數(shù)，減去各條

35、支線上的流量，其差數(shù)、減數(shù)的記入方式同上。第三條道路的流量才干為3干輛4在剩下的流量圖中，曾經(jīng)找不到一條完好的道路，滿足一切支路流量大于0的條件，因此可以通行的交通道路曾經(jīng)全部標(biāo)出。5網(wǎng)絡(luò)的最大交通才干第一條線路1-2-5-6，流量2千輛/小時；第二條線路1-4-6，流量3千輛/小時；第三條線路1-3-4-6，流量3千輛/小時； 該交通網(wǎng)絡(luò)的從北到南的最大通行流量為2+3+3=8千輛/小時。滿足每小時6000輛的經(jīng)過才干。15 2234566 44 23 03 057 4 12 0北南2121213232333333505.3 物流分配規(guī)劃義務(wù)分配問題的數(shù)學(xué)模型用匈牙利法求解分配問題51一.

36、義務(wù)分配問題的數(shù)學(xué)模型在物流系統(tǒng)中或其它的管理任務(wù)中，管理人員經(jīng)常面臨的一個問題是：如何根據(jù)有限的資源(人力、物力、財力等)，進(jìn)展任務(wù)義務(wù)分配，以到達(dá)降低本錢或提高經(jīng)濟(jì)效益的目的。如：有A、B、C、D四門課程，上課的教師可以從甲、乙、丙、丁四名教師中選擇，不同的教師上不同的課程，其費用是不同的，并且規(guī)定，每人只講一門課程，每門課程只需求一人講授。問：如何安排，才干使總的上課費用最低？又如：運輸義務(wù)的分配問題。有n條航線的運輸義務(wù)指派給n艘船去完成，不同的船完成不同的航線其運輸本錢不同。要求每條船完成一條航線，并且一條航線只能由一條船去完成。如何分配義務(wù)，才干使總的費用最??？這類問題是常見的義務(wù)

37、分配問題，也叫指派問題，它的義務(wù)是如何進(jìn)展合理的義務(wù)分配，使總的費用最小。52一. 義務(wù)分配問題的數(shù)學(xué)模型以運輸問題的n項義務(wù)由n個司機去完成的情況為例，有n個司機被分配完成n項運輸義務(wù)，不同的司機完成義務(wù)某一項義務(wù)的費用都不一樣。要求每個司機完成其中一項義務(wù)，每個義務(wù)只能由一名司機完成，如何分配義務(wù)，才干使總的費用最??？ 令： cij表示第i個司機完成第j項義務(wù)的運輸本錢任務(wù)本錢或任務(wù)時間等價值系數(shù)； xij表示第i個司機去完成第j項義務(wù)，其值為1或0。當(dāng)其值為1時表示第i個司機被分配去完成第j項義務(wù)；其值為0時，表示第i個司機不被分配去完成第j項義務(wù)。53一. 義務(wù)分配問題的數(shù)學(xué)模型義務(wù)分

38、配問題屬于整數(shù)規(guī)劃問題，其變量xij的取值為整數(shù)，本例為0或1。義務(wù)分配問題可以用普通的整數(shù)規(guī)劃求解方法進(jìn)展求解。但是，整數(shù)規(guī)劃問題的求解也是非常困難的，到目前為止，還缺乏一致的求解方法。本書采用匈牙利法求解義務(wù)分配問題。54二. 匈牙利法求解分配問題可以證明，對于分配問題，在其費用矩陣Cij中，各行、各列均減去一個常數(shù)，Cij改動以后的最優(yōu)解，仍為原問題的最優(yōu)解。利用這個性質(zhì)，經(jīng)過對Cij的行、列進(jìn)展加減常數(shù)的計算，把一些矩陣元素變?yōu)?，在Cij為0的元素上進(jìn)展分解，就可得到原問題的最優(yōu)解。該方法運用了匈牙利數(shù)學(xué)家Konig矩陣性質(zhì)定理，因此這種方法被稱為匈牙利法。555.4 其他規(guī)劃問題選

39、址問題貨物裝配問題物流效力系統(tǒng)中的配置問題56一. 選址問題物流調(diào)運規(guī)劃問題，是一種有固定發(fā)點、固定收點和固定道路的運輸規(guī)劃問題。還有一類運輸問題，他的收貨點和發(fā)貨點是待定的，這就是選址問題。這類問題在物流系統(tǒng)規(guī)劃中經(jīng)常遇到。選址問題要思索多種要素，本節(jié)只討論選址問題中的物流問題。分為兩個問題：單一地址選址方法；圖上作業(yè)法。571. 單一地址選址方法 建立一個新工廠或倉庫，應(yīng)合理選擇廠址或庫址。所謂選址問題，就是從多個候選廠址中選取一個最優(yōu)地址建廠，使物流費用到達(dá)最低。 問題描畫：假設(shè)廠址候選地點有s個，分別用D1,D2,Ds表示；原資料、燃料、零配件的供應(yīng)地有m個，分別用A1,A2,Am表示

40、，其供應(yīng)量分別用P1,P2,Pm表示；產(chǎn)品銷售地有n個，分別用B1,B2,Bn表示，其銷售量分別為Q1,Q2,Qn表示。設(shè)cij為供應(yīng)地Ai到候選廠址Dj的單位運輸本錢；djk為候選廠址Dj到銷售地Bk的單位運輸本錢；設(shè)選址變量為xj(j=1,2,s)，其中：xj=0或1，1表示在Dj點建廠，0表示不在Dj點建廠。單一選址問題是一種線性規(guī)劃問題,并且變量的取值為0或1，屬于整數(shù)規(guī)劃問題。單一地址的選址模型的求解方法比較簡單從目的函數(shù)表達(dá)式的右邊可以看出：經(jīng)過計算模型中括號內(nèi)的算式值，就可以確定運輸本錢最小的方案。當(dāng)要選定的地址不是單一的，而是多個時，問題不再屬于線性規(guī)劃問題。612. 圖上作業(yè)

41、法 對于運輸?shù)缆凡缓芈返倪x址問題，可用圖上作業(yè)法求解。 下面以一個實踐例子來闡明圖上作業(yè)法的選址問題： 例題8 假定有六個礦井產(chǎn)量分別為5000噸、6000噸、7000噸、2000噸、4000噸和3000噸，運輸?shù)缆啡缦聢D，這些礦石要經(jīng)過加工后才干轉(zhuǎn)運到其他地方。這些礦井之間道路不含回路，欲選擇一個礦井，在此礦井上建立一個加工廠，使各礦井到工廠的運輸總費用最低。 為了便于分析，用一個新的圖來替代原圖，新圖圈內(nèi)數(shù)字表示礦井編號，產(chǎn)量記在圈的旁邊，道路交叉點看作產(chǎn)量為零的礦井，把那些只需一條道路銜接的礦井稱為端點。首先計算這些礦井的總產(chǎn)量，本例為27000噸。然后分析各端點，都沒有超越總產(chǎn)量的一

42、半，因此把各端點的數(shù)量合并到前一站，即 和 的數(shù)量合并到；把的數(shù)量合并到 ；把 的數(shù)量合并到 ，如以下圖所示。3561100090007000各端點都合并到前一站后， 和變成了圖中的端點。對它們進(jìn)展分析其數(shù)量都不超越總產(chǎn)量的一半，所以他們不是最正確點。再把它們合并到前一站，即把和的數(shù)量合并到 。那么 的數(shù)量為27000，超越總量的一半，所以是最正確點。結(jié)論：加工廠應(yīng)建在第5號礦井。 63二. 貨物裝配 貨物配裝的目的是在車輛載分量為額定值的情況下，合理進(jìn)展貨物的安排，使車輛裝載貨物的價值最大如：分量最大、運費最低等。 641. 運用動態(tài)規(guī)劃解裝貨問題 設(shè)貨車的載分量上限為G，用于運送n種不同的

43、貨物，貨物的分量分別為W1，W2，.，Wn，每一種貨物對應(yīng)于一個價值系數(shù)，分別用P1，P2，.，Pn表示，它表示價值、運費或分量等。設(shè)Xk表示第k種貨物的裝入數(shù)量，貨物配裝問題的數(shù)學(xué)模型可以表示為： 可以把裝入一件貨物作為一個階段，把裝貨問題看作動態(tài)規(guī)劃問題。普通情況下，動態(tài)規(guī)劃問題的求解過程是從最后一個階段開場由后向前進(jìn)展的。由于裝入貨物的先后次序不影響裝貨問題的最優(yōu)解。所以我們的求解過程可以從第一階段開場，由前向后逐漸進(jìn)展。求解過程：1裝入第1種貨物X1件，其最大價值為 其中：X1表示第1種貨物的裝載數(shù)量；其取值范圍：0X1 G/W1 ，方括號表示取整； P1：第1種貨物的價值系數(shù)分量、運

44、費、價值等； f1(W)：第一種貨物的價值。 (2)裝入第2種貨物X2件，其最大價值為 其中：X2表示第2種貨物的裝載數(shù)量； 其取值范圍：0X2 G/W2 ； P2：第2種貨物的價值系數(shù)分量、運費、價值等； ：第一種貨物的分量； ：第一種貨物的價值。3裝入第3種貨物X3件，其最大價值為 其中：X3表示第3種貨物的裝載數(shù)量； 其取值范圍：0X3 G/W3； P3：第3種貨物的價值系數(shù)；(n) 裝入第n種貨物Xn件，其最大價值為 其中：Xn表示第n種貨物的裝載數(shù)量； 其取值范圍：0Xn G/Wn ； Pn：第n種貨物的價值系數(shù)；例題9 載分量為8t的載重汽車，運輸4種機電產(chǎn)品，產(chǎn)品分量分別為3噸、

45、3噸、4噸、5噸，試問如何配裝才干充分利用貨車的運載才干?解： 第一步，按照前面的公式，分成四個階段計算每一階段的價值。 計算結(jié)果以表格表示如下：貨物裝配例題載分量件數(shù)價值(分量)載分量第2種貨物的件數(shù)第1種貨物的分量價值計算價值Max載分量第3種貨物的件數(shù)第1、2種貨物的分量價值計算價值Max第二步：尋覓最優(yōu)方案。尋覓最優(yōu)解方案的次序與計算順序相反，由第4階段向第1階段進(jìn)展。從價值最大的裝載情況，逐漸向前尋覓最優(yōu)方案。1在第4階段計算表中，在載分量為8時，價值(本例為載分量)最大值f4(W)8，對應(yīng)兩組數(shù)據(jù)(加*號的數(shù)據(jù))： 1X40； 2X41； 先看X41時的情況： 當(dāng)X41時，即第4種

46、貨物裝入1件(5噸)，表中第3列數(shù)字表示其他種類貨物的裝載量。當(dāng)X41時，其他3種貨物裝載量為3噸；2按相反方向，在第3階段計算表中，查W=3噸時，得到最大價值f3(W)3，對應(yīng)的X3=0。查表中第3列數(shù)字，W=3，X3=0時，其他兩類貨物裝入分量3；3在第2階段計算表中，查W=3，f2(W)=3對應(yīng)兩組數(shù)據(jù)： 1X2=0； 2) X2=1； 即 當(dāng)X2 =1或0時，其他(第1種)貨物裝載量為3或0；4查第1階段計算表， 1當(dāng)W3時，對應(yīng)X1=1； 2當(dāng)W0時，對應(yīng)X1=0；根據(jù)當(dāng)前面的尋覓過程，可以得到兩組最優(yōu)解： 第一組：X1=1，X2=0，X3=0，X4=1； 第二組：X1=0，X2=1

47、，X3=0，X4=1；這兩組最優(yōu)解的實踐載分量為： 第一組：X1 * 3 + X4 * 5 = 1*3+1*5 = 8 第二組：X2 * 3 + X4 * 5 = 1*3+1*5 = 8 前面的最優(yōu)方案是在第四階段取X41時得出的方案。 假設(shè)在第4階段計算表中取X40，那么其他種類的貨物裝載量W - W4X4=8； 在第3階段計算表中，查W=8一欄，f3(w)=8對應(yīng)X32，再仿照前面的方法，可以得到第3組最優(yōu)解： 第三組：X1=0，X2=0，X3=2，X4=0； 裝載量為：X3 * 2 = 2*4 = 8以上三組裝載方案，都最大限制地發(fā)揚了車輛的載重才干，都是最優(yōu)方案。最終的最優(yōu)裝載方案為：

48、 第一組：X1=1，X2=0，X3=0，X4=1； 第二組：X1=0，X2=1，X3=0，X4=1； 第三組：X1=0，X2=0，X3=2，X4=0；762. 種類混裝問題在實踐的物流過程中，儲運倉庫(或貨運車站)要把客戶所需的貨物組成整車，運往各地。不同客戶的貨物，要分別在一站或多站卸貨。在裝貨、運輸和卸貨過程中，為了減少裝卸、運輸過程中出現(xiàn)過失，普通要按照種類、外形、顏色、規(guī)格、到達(dá)地點，把貨物分為假設(shè)干類，在裝車時分別進(jìn)展處置。這就是種類混裝問題。設(shè)裝車的貨物可以分為1類，2類，m類。共有N件(捆)待運貨物，其中1類貨物有N1件(捆)，它們的分量分別G11，G12，G1N1；2類貨物有N

49、2件(捆)，它們的分量分別為G21，G22，G2N2；第s類貨物共有Ns件，它們的分量分別為Gs1，Gs2，GsNs；以此類推，可以看出：貨物總的件數(shù)： 其中，Ns：第s類貨物的件數(shù)； m：貨物的種類數(shù)； N：貨物的總件數(shù)； 設(shè)： 種類混裝問題要求同一貨車內(nèi)每類貨物至多裝入一件捆，同一客戶的多件同類貨物可記作一件捆。在這樣的假設(shè)條件下，可以把種類混裝問題的數(shù)學(xué)模型表示如下：該數(shù)學(xué)模型的目的是對合理進(jìn)展分類后的貨物進(jìn)展裝載，使實踐載分量G的值最大。該數(shù)學(xué)模型屬于整數(shù)規(guī)劃的問題，可以用單純形法進(jìn)展求解。其中m：貨物的類別數(shù)；Nr：第r類貨物的件數(shù)；Grs：第r類第s件貨物的分量；G0：貨車載分量的上限。 圖5-20表示8件貨物分為4類，在圖中同一列的方框表示同一類貨物，方框內(nèi)的數(shù)字(符號)表示貨物分量。 上述種類混裝問題就是在網(wǎng)絡(luò)中自右向左尋覓一條道路，使道路所經(jīng)過的方框中的分量之和到達(dá)最大，但又不超越貨車的載分量的上限Go。這種問題可以用窮舉法求解，即比較各條道路的載分量從而求出不超越Go的最大裝載量的道路；也可以將四類貨物看作4個階段，將上述問題化為動態(tài)規(guī)劃問題求解。下面引見動態(tài)規(guī)劃的解