第12章貨物運輸?shù)膬?yōu)化求解

1、 主要內(nèi)容主要內(nèi)容：產(chǎn)銷運輸問題，分配運輸問題，網(wǎng)絡流問題，送貨集貨問題的模型建立、求解過程。 重點掌握重點掌握：產(chǎn)銷運輸問題，分配運輸問題，網(wǎng)絡流問題，送貨集貨問題模型建立、最優(yōu)解求取?，F(xiàn)現(xiàn) 代代 物物 流流 學學 第一節(jié) 產(chǎn)銷運輸問題 第二節(jié) 分配運輸問題 第三節(jié) 網(wǎng)絡流問題 第四節(jié) 送貨集貨問題現(xiàn)現(xiàn) 代代 物物 流流 學學 12.1.1 產(chǎn)銷平衡的運輸問題產(chǎn)銷平衡的運輸問題 12.1.1.1 模型分析模型分析 某種物資有m個產(chǎn)地A1,A2,Am，其供應量分為a1,a2,am；有n個銷地B1,B2,Bn，其銷量分為b1,b2,bn；產(chǎn)地物資供應量總和等于銷地物資銷量（需求量）總和；從產(chǎn)地A

2、i到銷地Bj的物資量和單位物資運價分別為xij,cij，求此時調(diào)運物資最佳方案?，F(xiàn)現(xiàn) 代代 物物 流流 學學對此問題可有下述線性規(guī)劃模型：對此問題可有下述線性規(guī)劃模型：minjijijxcz11min. .tsnjiijax1), 1(mimijijbx1), 1(njnjmiijab110ijx), 1;, 1(njmi現(xiàn)現(xiàn) 代代 物物 流流 學學 12.1.1.2 表上作業(yè)法求解表上作業(yè)法求解 根據(jù)上述模型的特殊結構而建立的表上作業(yè)法比起用單純形法要簡單得多。其思路為：由初始運輸方案開始，通過檢驗、改進，最后獲得最優(yōu)運輸方案。 設有兩個煤礦供應三個城市用煤，煤礦A1和A2的日產(chǎn)量分別為a1

3、=200t；a2=250t。三城市（B1,B2,B3）的日銷量分別為b1=100t，b2=150t，b3=200t。假定每t貨物的社會運輸費與出行公里線性有關，取cij代表煤礦i至城市j的最短距離。已知c11=90km，c12=70km，c13=100km，c21=80km，c22=65km，c23=80km。問如何安排運輸時運輸費用最??？例現(xiàn)現(xiàn) 代代 物物 流流 學學 解：設xij為煤礦i 運往城市j 的煤量，根據(jù)每個煤礦產(chǎn)煤總量和城市的用煤總量，xij (i=1,2; j=1,2,3)必須滿足下列條件：x11+x12+x13=200 x21+x22+x23=250 x11+x21=100

4、x12+x22=150 x13+x23=200目標函數(shù)為：minz=90 x11+70 x12+100 x13+80 x21+65x22+80 x23?，F(xiàn)現(xiàn) 代代 物物 流流 學學1、列運輸平衡表、列運輸平衡表 列表時要求表內(nèi)供銷平衡，并將運費標入表內(nèi)空格。需供B1B2B3供應量A1x1190 x1270 x13100200A2x2180 x2265x2380250需求量100150200450現(xiàn)現(xiàn) 代代 物物 流流 學學 2、建立初始調(diào)運方案、建立初始調(diào)運方案 采用最小元素法，即在平衡表中挑取運價最小或較小的供需點格子盡量優(yōu)先分配的調(diào)運方法。需供B1B2B3供應量A1090702001002

5、00A2100801506580250需求量100150200450現(xiàn)現(xiàn) 代代 物物 流流 學學 3、方案的檢驗和調(diào)整、方案的檢驗和調(diào)整 （1）閉回路。從調(diào)運方案的任意空格出發(fā)，沿水平方向或垂直方向前進，而遇到填有數(shù)字的方格，折轉(zhuǎn)90o前進，當然可以直接穿過數(shù)字格和空格，但只能遇有數(shù)字的格才能折轉(zhuǎn)，只能水平、垂直方向前進，不能對角線移動，這樣經(jīng)過多次折轉(zhuǎn)直到回到原來出發(fā)的空格，形成一條閉回路。 （2）位勢法檢驗 由方案表列出檢驗表。表中行列數(shù)與方案表一樣，運價在每一格的右上角，原方案表中的空格填寫檢驗數(shù)，原方案表中的數(shù)字格為檢驗表的空格，原方案表中的供應量、需求量寫行與列的位勢，稱為行或列位勢

6、格?，F(xiàn)現(xiàn) 代代 物物 流流 學學需供B1B2B3uiA10907020010090A210080150658080vj0-1510位 勢 表 求檢驗數(shù)。若空格位于第i行第j列，則其檢驗數(shù)ij按下式求出： ij=cij-ui-vj 求位勢。記第i行位勢為ui，第j列位勢為vj，通常可任選一格填0作為該格的位勢。而其他格位勢可由則可求得：cij=ui+vj。現(xiàn)現(xiàn) 代代 物物 流流 學學需供B1B2B3uiA190-57010090A28065-108080vj0-1510檢 驗 數(shù) 表 由上表可知，存在負的檢驗數(shù)，表明不是最優(yōu)的，需要進行調(diào)整。現(xiàn)現(xiàn) 代代 物物 流流 學學 （3）調(diào)整運輸方案 確定

7、閉回路。在需調(diào)整的運輸方案表上選取對應的檢驗數(shù)為負的且絕對值最大的格為檢驗格，從檢驗格出發(fā)在運輸方案表上作閉回路。需供B1B2B3供應量A109070200100200A2100801506580250需求量100150200450閉 回 路 表現(xiàn)現(xiàn) 代代 物物 流流 學學 在閉回路上做運輸量最大的調(diào)整，得出新的運輸方案。從空格開始，沿閉回路在格偶數(shù)格中挑選運量最小的作為調(diào)整量，調(diào)整閉回路各點的運輸量。需供B1B2B3供應量A11009070100100200A2801506510080250需求量100150200450新運輸方案1表現(xiàn)現(xiàn) 代代 物物 流流 學學 由于上表中有負檢驗數(shù)，故需繼

8、續(xù)進行調(diào)整，得新運輸方案表。需供B1B2B3供應量A11009010070100200A280506520080250需求量100150200450新運輸方案2表現(xiàn)現(xiàn) 代代 物物 流流 學學對新運輸方案表進行檢驗。需供B1B2B3uiA190701510090A2-580658085vj0-20-5新運輸方案2檢驗表現(xiàn)現(xiàn) 代代 物物 流流 學學繼續(xù)進行調(diào)整。需供B1B2B3供應量A1509015070100200A250806520080250需求量100150200450新運輸方案3表現(xiàn)現(xiàn) 代代 物物 流流 學學 此時，檢驗數(shù)全是正數(shù)，因此運輸方案3表中的運輸方案為最優(yōu)方案。需供B1B2B3

9、uiA190701010090A2805658080vj0-200新運輸方案3檢驗表現(xiàn)現(xiàn) 代代 物物 流流 學學 12.1.2 產(chǎn)銷不平衡時的運輸問題產(chǎn)銷不平衡時的運輸問題 njmiijab11 2、銷大于產(chǎn)的運輸問題 對于銷量大于產(chǎn)量，即 的運輸問題，必然有一些銷地不能得到滿足，發(fā)生缺貨，此時引入虛擬供應點，并設其相應運價為0。這樣，就可以用產(chǎn)銷平衡的表上作業(yè)法求解銷大于產(chǎn)的運輸問題。njmiijab11 1、產(chǎn)大于銷的運輸問題 對于產(chǎn)量大于銷量，即 的運輸問題，必然有些產(chǎn)地的產(chǎn)品不能安排運輸，此時引入虛擬需求點，令其需量等于總供量與總需量之差，并設其相應運價為0。這樣，就可以用表上作業(yè)法求

10、解產(chǎn)大于銷的運輸問題。現(xiàn)現(xiàn) 代代 物物 流流 學學 12.2.1 模型分析模型分析 某材料廠有B1、B2、B3三臺叉車可分配給A1、A2、A3三個倉庫進行搬運作業(yè)，其中任一叉車都可以再任一倉庫進行搬運工作，只是搬運作業(yè)費不同，各臺叉車相應作業(yè)費cij，如表所示，要求一臺叉車只分配給一個倉庫使用，試求搬運作業(yè)費用最小的分配方案。現(xiàn)現(xiàn) 代代 物物 流流 學學效率矩陣表171922B3242015B2353125B1A3A2A1倉庫 cij叉車根據(jù)問題引入變量xij，并按以下規(guī)定取值：項任務個單位不去完成第第項任務個單位被分配去完成第第jijixij01其中，i=1,2,n；j= 1,2,n?，F(xiàn)現(xiàn)

11、代代 物物 流流 學學當問題要求極小時，有數(shù)學模型：ninjijijxcz11min. .ts), 2 , 1(1), 2 , 1(111nixnjxnjijniij現(xiàn)現(xiàn) 代代 物物 流流 學學 12.2.2 匈牙利算法匈牙利算法 匈牙利算法的主要依據(jù)主要依據(jù)：在效率矩陣的任何行或列中，加上或減去同一常數(shù)，并不改變最優(yōu)分配。利用此性質(zhì)，可使原效率矩陣變換為含有很多0元素的新效率矩陣，找出在其中的位于不同行、列的n個獨立的0元素，將其取值為1，其他元素取值為0，即的原分配問題的最優(yōu)解?，F(xiàn)現(xiàn) 代代 物物 流流 學學 效率矩陣為： 1724351920312215251007801270007180

12、1127010171915172435192031221525例題第一步：變換效率舉陣，使其每一行和每一列都至少有一個0元素。現(xiàn)現(xiàn) 代代 物物 流流 學學7801270 第二步：試求最優(yōu)分配方案。 從1行開始，依次檢查各行，找出只有一個未標記的0元素的行，并講該元素用“ ”表示，與該元素同行同列的其他0元素則用“”表示。對應的任務僅由所對應的單位去完成，此單位不再去完成其他任務，這項任務也不再由其他單位完成。 依次檢查各列，找出只有一個未標記的0元素的列，并講該元素用“ ”表示，與該元素同行同列的其他0元素則用“”表示。 重復上述步驟，直到效率矩陣中沒有未標記的0元素?，F(xiàn)現(xiàn) 代代 物物 流流

13、學學78012700第三步：繼續(xù)調(diào)整效率矩陣。 對每一個 元素畫一條水平線或垂直線，使這些線覆蓋所有0元素。 在直線不穿過的所有元素中找到最小元素。 在沒有水平線的各行減去此最小元素，有垂直線的各列加上此最小元素，得到新的效率矩陣。-1-1067001800現(xiàn)現(xiàn) 代代 物物 流流 學學已經(jīng)得3個0元素，故得最優(yōu)分配方案為：A1B1，A2B2，A3B3則，根據(jù)原效率矩陣，3叉車總搬運作業(yè)費為：25+20+17=60（元）0670180第四步：回第二步，直到求出最優(yōu)分配方案?，F(xiàn)現(xiàn) 代代 物物 流流 學學 Qbi12.2.3 巡回運輸問題（旅行商問題） 在單網(wǎng)點配送中，物流網(wǎng)點向所屬用戶送貨，各用戶

14、的需求量bi（i=1,2,3,n），貨車載重量為Q，若滿足 ，則該網(wǎng)點只需一輛貨車即可。顯然，這種情況下使費用最省的方案是合理安排貨車訪問各用戶的順序，使貨車的巡回路線的總距離最短，這也就是旅行商問題?，F(xiàn)現(xiàn) 代代 物物 流流 學學 已知5用戶間距離如表，其中d(i,j)=表示從第i個用戶到第j個用戶是沒有意義的，用戶1為物流網(wǎng)點所在位置，如果只考慮將每個用戶都當作一個達到用戶，則對每個出發(fā)用戶都要選擇一個到達用戶，爾每個到達用戶只能有一個出發(fā)用戶到達該地，將問題變成了一個分配問題，可用匈牙利算法求解。到達出發(fā)123451234521171655764443253416用戶間距表例題現(xiàn)現(xiàn) 代代

15、物物 流流 學學 解解: 第一步第一步：令d(i,i)=，不存在通路的也記為，的距離陣，通常d(i,j)與d(j,i)不一定相同，即矩陣不一定對稱。 第二步第二步：對距離矩陣用匈牙利法求解，若得到無環(huán)路的路線，則就是最優(yōu)路線；如路線有環(huán)路，就不是最優(yōu)路線，但所走總距離給出了旅行商問題總距離的下界?，F(xiàn)現(xiàn) 代代 物物 流流 學學 得不考慮環(huán)路下的最優(yōu)方案：12，24，41，35，53 則，所走總距離為：1+3+1+1+4=10 可以看出上述路線存在環(huán)路，不是原問題的最優(yōu)路線，但給出了原問題的下界10。1013534005204226010135340015021402360411215457645

16、1126143623471現(xiàn)現(xiàn) 代代 物物 流流 學學 第三步第三步：出現(xiàn)環(huán)路時，打開節(jié)點個數(shù)最少的環(huán)路。即在此環(huán)路上考慮某段路線不通的各種情況，分別用匈牙利法求解，其中距離最短又無環(huán)路的路線即為最優(yōu)路線。 本例中，出現(xiàn)兩個環(huán)路， 1241和353，打開節(jié)點數(shù)少的環(huán)路，分別令d(3,5)=和d(5,3)=求解。現(xiàn)現(xiàn) 代代 物物 流流 學學（1）當d(3,5)=時，用匈牙利法求解。 可得無環(huán)路的最優(yōu)方案： 534125則，所走總距離為：1+4+2+1+4=12。21013334005042601013534015021402360411215457645126143623471現(xiàn)現(xiàn) 代代 物物

17、流流 學學（2）當d(5, 3)=時，用匈牙利法求解。 可得無環(huán)路的最優(yōu)方案： 12, 21, 35, 43, 54則，所走總距離為：1+2+1+4+5=13。3002504015211023300025340015021402360511215576451126143623471現(xiàn)現(xiàn) 代代 物物 流流 學學 可以看到，上述方案出現(xiàn)環(huán)路121和354 3，如果打開環(huán)路求解，其總距離一定不小于13，而已經(jīng)得到總距離為12的路線，故不必再作計算。因此得上述旅行上的最優(yōu)路線為： 534125；總距離為：12?，F(xiàn)現(xiàn) 代代 物物 流流 學學12.2.4 旅行商問題的神經(jīng)網(wǎng)絡求解旅行商問題的神經(jīng)網(wǎng)絡求解1

18、、連續(xù)Hopfield神經(jīng)網(wǎng)絡模型TijUjj+-vj-vjvi-vi+-uiciRiIiIiji（a）Hopfield神經(jīng)元現(xiàn)現(xiàn) 代代 物物 流流 學學（b）Hopfield神經(jīng)網(wǎng)絡v1+-+-+-v1v2-v2v3-v3123I1I2I3現(xiàn)現(xiàn) 代代 物物 流流 學學 設有n個神經(jīng)元互連，則可用下述非線性微分方程描述：)()()()()(1iiiiinijijiiugtvIRtutvTdttducninjniniviiijiijidvvgRIvvvTE111101)(121上式可以定義系統(tǒng)的能量函數(shù)為：現(xiàn)現(xiàn) 代代 物物 流流 學學ninjniiijiijIvvvTE111210dtdEt 可

19、以證明，對于該能量函數(shù)，恒有 ，即當 ，網(wǎng)絡達到穩(wěn)定。應用網(wǎng)絡的這一特性，可以進行優(yōu)化問題的求解。求解時，只需將優(yōu)化問題的目標函數(shù)轉(zhuǎn)化成能量函數(shù)的形式，然后應用上述微分方程運算到網(wǎng)絡收斂即可。通常在用Hopfield神經(jīng)網(wǎng)絡求解實際問題時，一般忽略能量式中得積分項，將能量函數(shù)簡化為下式，以便目標函數(shù)的映射。 現(xiàn)現(xiàn) 代代 物物 流流 學學 12.3.1 網(wǎng)絡最大流問題網(wǎng)絡最大流問題 1、問題的提出 已知連接產(chǎn)地V1與銷地Vn的交通網(wǎng)，每一弧（Vi,Vj）代表從Vi到Vj的運輸線，產(chǎn)品經(jīng)由Vi輸送到Vj，弧旁括號外的數(shù)字cij為弧的容量，括號內(nèi)的數(shù)字xij為Vi到Vj的貨運量，要求合理安排xij，

20、使V1到Vn的貨運量最大?，F(xiàn)現(xiàn) 代代 物物 流流 學學ijx 2、尋求最大流的標號法 對于包含n個頂點V1,V2,Vn的網(wǎng)絡流，V1為發(fā)點，Vn為收點，各段?。╒i,Vj）上容量為cij，設 是一個可行流，判斷它是否最大流及對它進行調(diào)整，關鍵在于求出其增廣鏈，標號法就是基于此來尋求最大流的。 3、最小費用最大流問題 解最小費用最大流問題的基本思想是，通過已知的由V1到收點Vn的最小費用流x，尋求其對應的最小費用增廣鏈，沿此增廣鏈去調(diào)整x，實現(xiàn)最大流?，F(xiàn)現(xiàn) 代代 物物 流流 學學 第三步：重復第二步，直到所有的頂點都標號為止，每個頂點標號內(nèi)的第二個數(shù)字即為V1到該頂點得最短距離，運用反向追蹤可找

21、出此最短路徑。)(min1,1ijijijWLL4、最短路徑問題Dijkstra算法如下：第一步：給發(fā)點V1以標號（1,0），L11=0。第二步：從以標號頂點出發(fā)，找出與這些頂點Vi相鄰所有頂點，若 ，則對Vj標號為（i,L1j）現(xiàn)現(xiàn) 代代 物物 流流 學學 12.4.1 模型分析模型分析 送貨問題，是指在中心倉庫中，需要向幾個分倉庫送貨，每個分倉庫對貨物由一定的需求，運送貨物的車輛在中心倉庫裝滿貨后發(fā)出，把貨送到各分倉庫卸貨，完成任務后返回中心倉庫，求滿足貨運需求的費用最小的車輛行駛路線?，F(xiàn)現(xiàn) 代代 物物 流流 學學 Kknikrrrrkknkkknkiiknsignccimize11) )

22、 1(min)1()1(. .tskkinikrbd1Kk, 2 , 1lnk0Kk, 2 , 1Kkkln1kkikiknilrrR,12, 2 , 121kkRR21kk 其他011) 1(kknnsign其中，現(xiàn)現(xiàn) 代代 物物 流流 學學12.4.2 掃描法求解掃描法求解（1）在地圖或方格圖中確定所有分倉庫的位置。（2）自中心倉庫始沿任一方向向外劃一條直線。（3）沿順時針或逆時針方向旋轉(zhuǎn)該直線直到與某分倉庫相交，相交時考慮在線路上增加該分倉庫運貨任務時，是否會超過車輛的載貨容量（顯示雍容量最大的車輛），如果不會，線路增加該分倉庫，并繼續(xù)旋轉(zhuǎn)直線到下一分倉庫。否則執(zhí)行步驟（4）。（4）構成一條送貨線路?，F(xiàn)現(xiàn) 代代 物物 流流 學學（5）從不包含在上一條線路中的分倉庫開始，繼續(xù)旋轉(zhuǎn)直線，繼續(xù)步驟（3），直到所有得分倉庫的送貨任務都已安排在不同線路中。（6）應用TSP問題的求解算法，排定各線路中分倉庫的先后順序，使各線路的路徑最短。現(xiàn)現(xiàn) 代代 物物 流流 學學 12.4.3 節(jié)約節(jié)約法求解法求解 在對多個分倉庫進行送貨時，將其中能取得最大“節(jié)約里程”的兩個分倉庫合并在一條線路上，進行巡回送貨，能夠獲得最大的里程節(jié)約。同時，在不超過運輸車輛載貨容量的條件下，設法使這條選定的巡回路線，盡可能將其他分倉庫按其所能取得“節(jié)約里程”的打下納入