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

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

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

3、=200t；a2=250t。三城市（B1,B2,B3）的日銷量分別為b1=100t，b2=150t，b3=200t。假定每t貨物的社會(huì)運(yùn)輸費(fèi)與出行公里線性有關(guān)，取cij代表煤礦i至城市j的最短距離。已知c11=90km，c12=70km，c13=100km，c21=80km，c22=65km，c23=80km。問如何安排運(yùn)輸時(shí)運(yùn)輸費(fèi)用最??？例現(xiàn)現(xiàn) 代代 物物 流流 學(xué)學(xué) 解：設(shè)xij為煤礦i 運(yùn)往城市j 的煤量，根據(jù)每個(gè)煤礦產(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目標(biāo)函數(shù)為：minz=90 x11+70 x12+100 x13+80 x21+65x22+80 x23?，F(xiàn)現(xiàn) 代代 物物 流流 學(xué)學(xué)1、列運(yùn)輸平衡表、列運(yùn)輸平衡表 列表時(shí)要求表內(nèi)供銷平衡，并將運(yùn)費(fèi)標(biāo)入表內(nèi)空格。需供B1B2B3供應(yīng)量A1x1190 x1270 x13100200A2x2180 x2265x2380250需求量100150200450現(xiàn)現(xiàn) 代代 物物 流流 學(xué)學(xué) 2、建立初始調(diào)運(yùn)方案、建立初始調(diào)運(yùn)方案 采用最小元素法，即在平衡表中挑取運(yùn)價(jià)最小或較小的供需點(diǎn)格子盡量?jī)?yōu)先分配的調(diào)運(yùn)方法。需供B1B2B3供應(yīng)量A1090702001002

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

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

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

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

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

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

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

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

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

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

15、物物 流流 學(xué)學(xué) 解解: 第一步第一步：令d(i,i)=，不存在通路的也記為，的距離陣，通常d(i,j)與d(j,i)不一定相同，即矩陣不一定對(duì)稱。 第二步第二步：對(duì)距離矩陣用匈牙利法求解，若得到無環(huán)路的路線，則就是最優(yōu)路線；如路線有環(huán)路，就不是最優(yōu)路線，但所走總距離給出了旅行商問題總距離的下界。現(xiàn)現(xiàn) 代代 物物 流流 學(xué)學(xué) 得不考慮環(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) 代代 物物 流流 學(xué)學(xué) 第三步第三步：出現(xiàn)環(huán)路時(shí)，打開節(jié)點(diǎn)個(gè)數(shù)最少的環(huán)路。即在此環(huán)路上考慮某段路線不通的各種情況，分別用匈牙利法求解，其中距離最短又無環(huán)路的路線即為最優(yōu)路線。 本例中，出現(xiàn)兩個(gè)環(huán)路， 1241和353，打開節(jié)點(diǎn)數(shù)少的環(huán)路，分別令d(3,5)=和d(5,3)=求解?，F(xiàn)現(xiàn) 代代 物物 流流 學(xué)學(xué)（1）當(dāng)d(3,5)=時(shí)，用匈牙利法求解。 可得無環(huán)路的最優(yōu)方案： 534125則，所走總距離為：1+4+2+1+4=12。21013334005042601013534015021402360411215457645126143623471現(xiàn)現(xiàn) 代代 物物

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

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

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

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

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

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