匈牙利解法-物流產(chǎn)業(yè)大數(shù)據(jù)平臺課件

項目二運輸決策與優(yōu)化

能力目標：掌握運輸決策與優(yōu)化的技術(shù)

知識目標：掌握運輸方式選擇影響因素項目二運輸決策與優(yōu)化

能力目標：掌握運輸決策與優(yōu)化的技術(shù)1任務(wù)一運輸方式的選擇一、成本比較法(一)成本比較法如果不將運輸服務(wù)作為競爭手段，那么能使運輸服務(wù)的成本與運輸服務(wù)水平導致的相關(guān)間接庫存成本之間達到平衡的運輸服務(wù)就是最佳服務(wù)方案。因此最合理的應(yīng)該是，既能滿足顧客需求，又使總成本最低的服務(wù)。任務(wù)一運輸方式的選擇一、成本比較法2任務(wù)一運輸方式的選擇(二)考慮競爭因素的方法運輸方法的選擇如直接涉及到競爭優(yōu)勢，則應(yīng)采用考慮競爭因素的方法。當買方通過供應(yīng)渠道從若干個供應(yīng)商處購商品時，物流服務(wù)和價格就會影響到買方對供應(yīng)商的選擇。反之，供應(yīng)商也可以通過供應(yīng)渠道運輸方式的選擇控制物流服務(wù)的這些要素，影響買方的惠顧。

任務(wù)一運輸方式的選擇(二)考慮競爭因素的方法3任務(wù)二運輸路線的優(yōu)化技術(shù)一、表上作業(yè)法（1）表上作業(yè)法[例4-2]某公司下屬四個儲存某中物資的料庫，供應(yīng)五個工地的需要。四個料庫供應(yīng)量和五個工地的需求量以及由個料庫到各工地調(diào)運單位物資的運價見表4-6。任務(wù)二運輸路線的優(yōu)化技術(shù)一、表上作業(yè)法4任務(wù)二運輸路線的優(yōu)化技術(shù)解：1）運用表上作業(yè)法時，首先要列出被調(diào)運物資的調(diào)運物資初始表（簡稱供需平衡表）2）用矩陣對角法進行初步調(diào)整用任意兩個成矩形對角（其中有三處已初分）的運價之和與該矩形另外兩個對角的運價之和相比較任務(wù)二運輸路線的優(yōu)化技術(shù)5任務(wù)二運輸路線的優(yōu)化技術(shù)3）初始方案的檢驗與調(diào)整在制訂了初始調(diào)運方案之后，需要對它進行檢驗，如果判定初始調(diào)運方案不是最優(yōu)方案，需要對其進行調(diào)整直到獲得最優(yōu)調(diào)運方案。但是如何判定調(diào)運方案是不是最優(yōu)的呢？在此，引進最優(yōu)方案的數(shù)字表征——檢驗數(shù)的概念。①最優(yōu)方案的數(shù)字表征——檢驗數(shù)任務(wù)二運輸路線的優(yōu)化技術(shù)3）初始方案的檢驗與調(diào)整在6任務(wù)二運輸路線的優(yōu)化技術(shù)②用于求檢驗數(shù)的方法——位勢法③用霍撒克法則檢驗檢驗數(shù)Aij=Cij-（Ui+Vj）>=0，否則要進行調(diào)整。新方案是否是最優(yōu)方案，還需要對它進行檢驗。經(jīng)計算，該新方案的所有檢驗數(shù)都是非負的，說明這個方案已經(jīng)是最優(yōu)調(diào)運方案了。任務(wù)二運輸路線的優(yōu)化技術(shù)②用于求檢驗數(shù)的方法——位勢法7任務(wù)二運輸路線的優(yōu)化技術(shù)4）表上作業(yè)法基本步驟小結(jié)①列出調(diào)運物資的供需（產(chǎn)銷）平衡表及運價表。②按最小元素法建立初始調(diào)運方案。③采用位勢法計算初始方案每個空格的閉回路的檢驗數(shù)Cij。④檢查檢驗數(shù)，如所有Aij>=0，說明方案是最有的，已經(jīng)得到我們想要的方案，結(jié)束求解。⑤如果有某個或幾個Aij<0，則選擇負檢驗數(shù)中絕對值最大的閉回路進行調(diào)整，建立新的方案。⑥重復3—5步，直接獲得最優(yōu)調(diào)運方案。任務(wù)二運輸路線的優(yōu)化技術(shù)8任務(wù)二運輸路線的優(yōu)化技術(shù)二、匈牙利解法三家工廠A1、A2、A3生產(chǎn)需要某原材料，某供應(yīng)商在附近有4個儲存該物資的倉庫B1、B2、B3、B4，各點的需求量和供給量以及由倉庫到工廠調(diào)運該單位物資的運價見下表所示，該供應(yīng)商的目的是運輸費用最少，請問該如何做出決策？任務(wù)二運輸路線的優(yōu)化技術(shù)二、匈牙利解法9任務(wù)二運輸路線的優(yōu)化技術(shù)二、匈牙利解法解：1、運價表矩陣中分行分列減去最小運價，實現(xiàn)每行每列有“0”；0895-20231-17203-221011713429425

Aij=－2－1任務(wù)二運輸路線的優(yōu)化技術(shù)二、匈牙利解法10任務(wù)二運輸路線的優(yōu)化技術(shù)二、匈牙利解法2、按供求數(shù)量限制安排調(diào)運方案(只能安排在“0”運價上)，不能全部調(diào)運完成的話，需減去剩余運價中最小的運價，并還原非負的運價，實現(xiàn)每行每列有“0”，安排調(diào)運方案，如此反復直至求出最優(yōu)解。(0)4694003(0)67(0)3(0)5210故最優(yōu)調(diào)配方案為：B1B2B3B4A1(2)41011(7)6A21(3)54(2)1A39(4)3(2)55運輸費用=2*4+7*6+3*5+2*1+4*3+2*5=89元。任務(wù)二運輸路線的優(yōu)化技術(shù)二、匈牙利解法11任務(wù)二運輸路線的優(yōu)化技術(shù)三、圖上作業(yè)法[例]某公司下屬四個儲存某中物資的料庫，供應(yīng)五個工地的需要。四個料庫供應(yīng)量和五個工地的需求量以及由個料庫到各工地調(diào)運單位物資的運價見表。任務(wù)二運輸路線的優(yōu)化技術(shù)三、圖上作業(yè)法124353231800500400350300250需求量80030050200250丁600200400丙300300乙100100甲供應(yīng)量

EDCBA工地料庫43133522487877M+N-1=8用最小運費法確定初始方案4353231800500400350300250需求量8013435323V=88745U=V4=0300-150200250丁-62004003108丙-62130054乙-2-3-1-21000甲供應(yīng)量

EDCBA工地料庫43133522487877初始方案的檢驗與調(diào)整選擇負檢驗數(shù)中絕對值最大的閉回路進行調(diào)整

435323V=88745U=V4=0300-150200214初始方案的檢驗與調(diào)整①最優(yōu)方案的數(shù)字表征——檢驗數(shù)首先我們介紹閉回路的概念。從理論上得知（不予證明），對于表上作業(yè)法的初始方案來說，從調(diào)運方案上的一個空格出發(fā)，存在一條且僅存在一條以該空格（用Xij表示）為起點，以其他填有數(shù)字的點為其他頂點的閉合回路，簡稱閉合路。這個閉合路具有下列性質(zhì)：a.每個頂點都是轉(zhuǎn)角點。b.閉合回路是一條封閉折線，每一條邊都是水平或垂直的。c.每一行（列）若有閉合回路的頂點，則必有兩個。只有從空格出發(fā)，其余個轉(zhuǎn)角點多對應(yīng)的方格內(nèi)均填有數(shù)字時，所構(gòu)成的閉合回路，才是所說的閉回路。d.另外，過任一空格的閉合回路不僅是存在的，而且是唯一的。②用于求檢驗數(shù)的方法——位勢法設(shè)Cij（i=1，2，3，4；j=1，2，3，4，5），將初始調(diào)運方案中填有數(shù)值方格的Cij分解成兩部分：Cij=Ui+Vj。初始方案的檢驗與調(diào)整①最優(yōu)方案的數(shù)字表征——檢驗數(shù)首先我15435323V=88745U=V4=0200-150300250丁-62004003108丙-62130054乙-51002133甲供應(yīng)量

EDCBA工地料庫43133522487877初始方案的檢驗與調(diào)整435323V=88745U=V4=0200-150300216435323V=77745U=V4=0120050300250丁-5400200298丙-63230054乙-41002022甲供應(yīng)量

EDCBA工地料庫43133522487877經(jīng)計算，該新方案的所有檢驗數(shù)都是非負的，說明這個方案已經(jīng)是最優(yōu)調(diào)運方案了。435323V=77745U=V4=01200503002517圖上作業(yè)法【】有某物資7t，由A1，A2，A3發(fā)出，發(fā)量分別為3，3，1（t），運往收點B1，B2，B3，B4，收量分別為2，3，1，1（t），收發(fā)量平衡，交通圖如圖所示，問應(yīng)如何調(diào)運，才使t·km最小。。431213317354324圖上作業(yè)法【】有某物資7t，由A1，A2，A3發(fā)出，發(fā)量分別18圖上作業(yè)法解：①作一個沒有對流的流向圖，用“去線破圈”的方法，去一線破一圈，有幾個圈去掉幾條線，把有圈的交通圖，化為不成圈的交通圖。一般是去掉長度最長的交通線，比如，去掉Ａ1Ｂ4（7km），破A1B1B2A3B4圈，在去掉A3B3線（4km），破B2A2B3A3圈，這樣，原來有圈的交通圖，變成了不成圈的交通圖。圖上作業(yè)法解：①作一個沒有對流的流向圖，用“去線破圈”的方法193圖上作業(yè)法1213317354324312114②檢查有無迂回，方法水對流想圖中的各圈進行檢查，侃侃有無迂回。如果沒有迂回，即該圈總長的一半均大于內(nèi)流長和外流長，這個初始方案就是最優(yōu)方案，如果其中某一圈有迂回，這個方案就不是最優(yōu)方案，需要改進。在圖中，圈A1B1B2A3B4的總長為23km，外流長為5+4+3=12km，大于圈長的一半，因而需要調(diào)整。在看圈B2A2B3A3其總長為13km，圈中內(nèi)流長為3km，外流長為2km，都小于圈長的一半，因此此圈不必調(diào)整。3圖上作業(yè)法12133173543243121120圖上作業(yè)法然后先從各個端點開始，在圖上作一個沒有對流的流向圖。②檢查有無迂回，方法水對流想圖中的各圈進行檢查，侃侃有無迂回。如果沒有迂回，即該圈總長的一半均大于內(nèi)流長和外流長，這個初始方案就是最優(yōu)方案，如果其中某一圈有迂回，這個方案就不是最優(yōu)方案，需要改進。在圖中，圈A1B1B2A3B4的總長為23km，外流長為5+4+3=12km，大于圈長的一半，因而需要調(diào)整。在看圈B2A2B3A3其總長為13km，圈中內(nèi)流長為3km，外流長為2km，都小于圈長的一半，因此此圈不必調(diào)整。對圈A1B1B2A3B4的調(diào)整方法是：在外圈的個流量中，減去外圈的最小流量1t；然后在內(nèi)圈的個流量中加上1t，在此圈中，因無內(nèi)流量，所以無處可加；另外，在無流量的線段上，新添上內(nèi)圈流量1t，這樣得出新的流量圖。圖上作業(yè)法然后先從各個端點開始，在圖上作一個沒有對流的流向圖21對圈A1B1B2A3B4的調(diào)整方法是：在外圈的個流量中，減去外圈的最小流量1t；然后在內(nèi)圈的個流量中加上1t，在此圈中，因無內(nèi)流量，所以無處可加；另外，在無流量的線段上，新添上內(nèi)圈流量1t，這樣得出新的流量圖。方案調(diào)整1213317354324312114312133173543242121143對圈A1B1B2A3B4的調(diào)整方法是：在外圈的個流量中，減去22121331735432421211432121331735434231431在圈B2A2B3A3中外圈長為4+3=7大于圈長的一半，調(diào)整為內(nèi)圈加“1”外圈減“1”此時兩個圈都沒有迂回是最優(yōu)方案總的TKM為：7*1+2*5+1*4+3*2=27方案調(diào)整12133173543242121143212133173523圖上作業(yè)法新的流量圖中，在A1B1B2A3B4圈內(nèi)，內(nèi)流長為：4+7=11km，外流長為=5km，都不超過全圈長（23km）的一半，因此，這個流向圖沒有迂回現(xiàn)象，是本問題的最優(yōu)調(diào)運方案，總運輸力為27t·km。求解思路小結(jié)：流向劃右方，對流不應(yīng)當，內(nèi)流外流分開算，要求不過外圈長，如若超過外圈長，應(yīng)甩運量最小檔，反復求算最優(yōu)方。圖上作業(yè)法新的流量圖中，在A1B1B2A3B4圈內(nèi)，內(nèi)流長為24任務(wù)二運輸路線的優(yōu)化技術(shù)四、節(jié)約里程法配送路線是指各送貨車輛向各個客戶送貨時所要經(jīng)過的路線。配送路線合理與否對配送速度、成本、效益影響很大，采用科學的、合理的方法來優(yōu)化配送路線，是配送管理中非常重要的工作。任務(wù)二運輸路線的優(yōu)化技術(shù)四、節(jié)約里程法25任務(wù)二運輸路線的優(yōu)化技術(shù)2、配送路線優(yōu)化的方法（1）VSP網(wǎng)絡(luò)圖的原理在有很多配送去向的情況下，使用多少輛車，各輛車按照什么路線運行才能使整個運行距離最短，或使配送費用最低，這是配送路線優(yōu)化的問題。解決這一問題的最有代表性的方法是VSP（VehicleScheduingProgram）網(wǎng)絡(luò)圖。VSP可稱為車輛安排程序方法。

任務(wù)二運輸路線的優(yōu)化技術(shù)2、配送路線優(yōu)化的方法26任務(wù)二運輸路線的優(yōu)化技術(shù)(2)節(jié)約里程法的基本設(shè)定配送的是同一種貨物。各客戶的坐標及需求量均為已知。配送中心有足夠的運輸能力。任務(wù)二運輸路線的優(yōu)化技術(shù)(2)節(jié)約里程法的基本設(shè)定27任務(wù)二運輸路線的優(yōu)化技術(shù)節(jié)約里程法的計算【例】某配送中心A要向所在城市B，C，D，E，F(xiàn)，G共6個客戶點配送貨物，如圖所示。它們之間的距離（km）和每一處的配送貨物量（t）見表。運輸車輛有2.5t和4t兩種貨車，試確定配送路線。表配送距離和配送量任務(wù)二運輸路線的優(yōu)化技術(shù)節(jié)約里程法的計算表28BACDGEF212066991212241019圖配送點最短距離計算圖BACDGEF212066991212241019圖配送點29任務(wù)二運輸路線的優(yōu)化技術(shù)節(jié)約里程法的計算步驟（1）計算配送中心A到各配送點、各配送點之間的最短距離矩陣。（2）計算節(jié)約里程（3）節(jié)約里程排序（4）確定方案（5）改進方案任務(wù)二運輸路線的優(yōu)化技術(shù)節(jié)約里程法的計算步驟30任務(wù)二運輸路線的優(yōu)化技術(shù)解：計算配送中心A到各配送點、各配送點之間的最段距離。最短距離的計算方法：從終點開始逐步逆向推算。由于配送中心與各配送點只有一個結(jié)點，故它們之間的距離即為最短距離。因這些數(shù)據(jù)表中已知，所以只需要計算各客戶點之間的最短距離即可。即計算BD，BE，BF，BG，CE，CF，CG和DE的距離。以CE的計算為例：由圖所示，與終點E相聯(lián)結(jié)的有A，F(xiàn)，從C至E的最短距離為C-A-E，即12+20=32km。同理可求得其他各客戶之間的最短距離，見表。計算各配送點組合的節(jié)約里程數(shù)，并將之進行排序。節(jié)約里程數(shù)可由節(jié)約量的一般公式求得。如EG間的節(jié)約里程數(shù)為AE+AG-EG=20+21-1=40km。同理可求得其他各客戶之間的節(jié)約里程數(shù)，見表。任務(wù)二運輸路線的優(yōu)化技術(shù)解：31計算最短距離矩陣計算節(jié)約里程

計算最短距離矩陣計算節(jié)約里程

32（3）節(jié)約里程排序（3）節(jié)約里程排序33任務(wù)二運輸路線的優(yōu)化技術(shù)EG節(jié)約里程最大，從表3-2中得知，它們的配送貨物量是：1．75+1．15=2．9t，在貨車載重限度內(nèi)，可以入選。FG的配送貨物量1．1t，正好可以與2．9t拼裝為一輛4t貨車的載運量，它們相互銜接成為一條路線AEGFA。全程為20+1+6+24=51km。因4t貨車已裝滿，所以應(yīng)考慮第二條配送路線。C，D配送貨物量是1．0+0．7=1．7t，在貨車載重限度內(nèi)，可以將B點的0．8t貨物集中在一起，拼裝為一輛2．5t貨車的載運量，形成第二條配送路線ABCDA或ADCBA，全程為9+9+10+12=40km。此案例的配送路線優(yōu)化后確定為二條，即AEGFA和ABCDA（ADCBA），總行程為51+40=91km，使用4t和2．5t的貨車各一輛。任務(wù)二運輸路線的優(yōu)化技術(shù)EG節(jié)約里程最大，從表3-2中得34BACDGEFA=4tB=2.5t92016612910任務(wù)二運輸路線的優(yōu)化技術(shù)BACDGEFA=4tB=2.5t92016612910任務(wù)35任務(wù)二運輸路線的優(yōu)化技術(shù)結(jié)論使用4t和2．5t的貨車各一輛總節(jié)約里程:(9+12+12+24+20+21)*2-91=105任務(wù)二運輸路線的優(yōu)化技術(shù)結(jié)論36任務(wù)三運輸合理化一、影響運輸合理化的因素1、運輸距離2、運輸環(huán)節(jié)3、運輸工具4、運輸時間5、運輸費用任務(wù)三運輸合理化一、影響運輸合理化的因素37任務(wù)三運輸合理化影響運輸合理化的外部因素1、政府。2、資源分布狀況。3、國民經(jīng)濟結(jié)構(gòu)的變化。4、運輸網(wǎng)布局的變化。5、運輸決策的參與者。任務(wù)三運輸合理化影響運輸合理化的外部因素38任務(wù)三運輸合理化二、不合理運輸?shù)谋憩F(xiàn)形式（一）空駛（二）對流運輸（三）迂回運輸（四）過遠運輸（五）重復運輸（六）無效運輸（七）運力選擇不當任務(wù)三運輸合理化二、不合理運輸?shù)谋憩F(xiàn)形式39任務(wù)三運輸合理化三、實現(xiàn)運輸合理化的有效措施（一）提高運輸工具實載率（二）減少動力投入，增加運輸能力（三）發(fā)展社會化運輸（四）開展中短距離鐵路公路分流，“以公代鐵”的運輸任務(wù)三運輸合理化三、實現(xiàn)運輸合理化的有效措施40任務(wù)三運輸合理化（五）盡量發(fā)展直達運輸（六）配載運輸（七）“四就”直撥運輸（八）發(fā)展特殊運輸技術(shù)和運輸工具依靠科技進步是實現(xiàn)運輸合理化的重要途徑。任務(wù)三運輸合理化（五）盡量發(fā)展直達運輸41項目二運輸決策與優(yōu)化

能力目標：掌握運輸決策與優(yōu)化的技術(shù)

知識目標：掌握運輸方式選擇影響因素項目二運輸決策與優(yōu)化

能力目標：掌握運輸決策與優(yōu)化的技術(shù)42任務(wù)一運輸方式的選擇一、成本比較法(一)成本比較法如果不將運輸服務(wù)作為競爭手段，那么能使運輸服務(wù)的成本與運輸服務(wù)水平導致的相關(guān)間接庫存成本之間達到平衡的運輸服務(wù)就是最佳服務(wù)方案。因此最合理的應(yīng)該是，既能滿足顧客需求，又使總成本最低的服務(wù)。任務(wù)一運輸方式的選擇一、成本比較法43任務(wù)一運輸方式的選擇(二)考慮競爭因素的方法運輸方法的選擇如直接涉及到競爭優(yōu)勢，則應(yīng)采用考慮競爭因素的方法。當買方通過供應(yīng)渠道從若干個供應(yīng)商處購商品時，物流服務(wù)和價格就會影響到買方對供應(yīng)商的選擇。反之，供應(yīng)商也可以通過供應(yīng)渠道運輸方式的選擇控制物流服務(wù)的這些要素，影響買方的惠顧。

任務(wù)一運輸方式的選擇(二)考慮競爭因素的方法44任務(wù)二運輸路線的優(yōu)化技術(shù)一、表上作業(yè)法（1）表上作業(yè)法[例4-2]某公司下屬四個儲存某中物資的料庫，供應(yīng)五個工地的需要。四個料庫供應(yīng)量和五個工地的需求量以及由個料庫到各工地調(diào)運單位物資的運價見表4-6。任務(wù)二運輸路線的優(yōu)化技術(shù)一、表上作業(yè)法45任務(wù)二運輸路線的優(yōu)化技術(shù)解：1）運用表上作業(yè)法時，首先要列出被調(diào)運物資的調(diào)運物資初始表（簡稱供需平衡表）2）用矩陣對角法進行初步調(diào)整用任意兩個成矩形對角（其中有三處已初分）的運價之和與該矩形另外兩個對角的運價之和相比較任務(wù)二運輸路線的優(yōu)化技術(shù)46任務(wù)二運輸路線的優(yōu)化技術(shù)3）初始方案的檢驗與調(diào)整在制訂了初始調(diào)運方案之后，需要對它進行檢驗，如果判定初始調(diào)運方案不是最優(yōu)方案，需要對其進行調(diào)整直到獲得最優(yōu)調(diào)運方案。但是如何判定調(diào)運方案是不是最優(yōu)的呢？在此，引進最優(yōu)方案的數(shù)字表征——檢驗數(shù)的概念。①最優(yōu)方案的數(shù)字表征——檢驗數(shù)任務(wù)二運輸路線的優(yōu)化技術(shù)3）初始方案的檢驗與調(diào)整在47任務(wù)二運輸路線的優(yōu)化技術(shù)②用于求檢驗數(shù)的方法——位勢法③用霍撒克法則檢驗檢驗數(shù)Aij=Cij-（Ui+Vj）>=0，否則要進行調(diào)整。新方案是否是最優(yōu)方案，還需要對它進行檢驗。經(jīng)計算，該新方案的所有檢驗數(shù)都是非負的，說明這個方案已經(jīng)是最優(yōu)調(diào)運方案了。任務(wù)二運輸路線的優(yōu)化技術(shù)②用于求檢驗數(shù)的方法——位勢法48任務(wù)二運輸路線的優(yōu)化技術(shù)4）表上作業(yè)法基本步驟小結(jié)①列出調(diào)運物資的供需（產(chǎn)銷）平衡表及運價表。②按最小元素法建立初始調(diào)運方案。③采用位勢法計算初始方案每個空格的閉回路的檢驗數(shù)Cij。④檢查檢驗數(shù)，如所有Aij>=0，說明方案是最有的，已經(jīng)得到我們想要的方案，結(jié)束求解。⑤如果有某個或幾個Aij<0，則選擇負檢驗數(shù)中絕對值最大的閉回路進行調(diào)整，建立新的方案。⑥重復3—5步，直接獲得最優(yōu)調(diào)運方案。任務(wù)二運輸路線的優(yōu)化技術(shù)49任務(wù)二運輸路線的優(yōu)化技術(shù)二、匈牙利解法三家工廠A1、A2、A3生產(chǎn)需要某原材料，某供應(yīng)商在附近有4個儲存該物資的倉庫B1、B2、B3、B4，各點的需求量和供給量以及由倉庫到工廠調(diào)運該單位物資的運價見下表所示，該供應(yīng)商的目的是運輸費用最少，請問該如何做出決策？任務(wù)二運輸路線的優(yōu)化技術(shù)二、匈牙利解法50任務(wù)二運輸路線的優(yōu)化技術(shù)二、匈牙利解法解：1、運價表矩陣中分行分列減去最小運價，實現(xiàn)每行每列有“0”；0895-20231-17203-221011713429425

Aij=－2－1任務(wù)二運輸路線的優(yōu)化技術(shù)二、匈牙利解法51任務(wù)二運輸路線的優(yōu)化技術(shù)二、匈牙利解法2、按供求數(shù)量限制安排調(diào)運方案(只能安排在“0”運價上)，不能全部調(diào)運完成的話，需減去剩余運價中最小的運價，并還原非負的運價，實現(xiàn)每行每列有“0”，安排調(diào)運方案，如此反復直至求出最優(yōu)解。(0)4694003(0)67(0)3(0)5210故最優(yōu)調(diào)配方案為：B1B2B3B4A1(2)41011(7)6A21(3)54(2)1A39(4)3(2)55運輸費用=2*4+7*6+3*5+2*1+4*3+2*5=89元。任務(wù)二運輸路線的優(yōu)化技術(shù)二、匈牙利解法52任務(wù)二運輸路線的優(yōu)化技術(shù)三、圖上作業(yè)法[例]某公司下屬四個儲存某中物資的料庫，供應(yīng)五個工地的需要。四個料庫供應(yīng)量和五個工地的需求量以及由個料庫到各工地調(diào)運單位物資的運價見表。任務(wù)二運輸路線的優(yōu)化技術(shù)三、圖上作業(yè)法534353231800500400350300250需求量80030050200250丁600200400丙300300乙100100甲供應(yīng)量

EDCBA工地料庫43133522487877M+N-1=8用最小運費法確定初始方案4353231800500400350300250需求量8054435323V=88745U=V4=0300-150200250丁-62004003108丙-62130054乙-2-3-1-21000甲供應(yīng)量

EDCBA工地料庫43133522487877初始方案的檢驗與調(diào)整選擇負檢驗數(shù)中絕對值最大的閉回路進行調(diào)整

435323V=88745U=V4=0300-150200255初始方案的檢驗與調(diào)整①最優(yōu)方案的數(shù)字表征——檢驗數(shù)首先我們介紹閉回路的概念。從理論上得知（不予證明），對于表上作業(yè)法的初始方案來說，從調(diào)運方案上的一個空格出發(fā)，存在一條且僅存在一條以該空格（用Xij表示）為起點，以其他填有數(shù)字的點為其他頂點的閉合回路，簡稱閉合路。這個閉合路具有下列性質(zhì)：a.每個頂點都是轉(zhuǎn)角點。b.閉合回路是一條封閉折線，每一條邊都是水平或垂直的。c.每一行（列）若有閉合回路的頂點，則必有兩個。只有從空格出發(fā)，其余個轉(zhuǎn)角點多對應(yīng)的方格內(nèi)均填有數(shù)字時，所構(gòu)成的閉合回路，才是所說的閉回路。d.另外，過任一空格的閉合回路不僅是存在的，而且是唯一的。②用于求檢驗數(shù)的方法——位勢法設(shè)Cij（i=1，2，3，4；j=1，2，3，4，5），將初始調(diào)運方案中填有數(shù)值方格的Cij分解成兩部分：Cij=Ui+Vj。初始方案的檢驗與調(diào)整①最優(yōu)方案的數(shù)字表征——檢驗數(shù)首先我56435323V=88745U=V4=0200-150300250丁-62004003108丙-62130054乙-51002133甲供應(yīng)量

EDCBA工地料庫43133522487877初始方案的檢驗與調(diào)整435323V=88745U=V4=0200-150300257435323V=77745U=V4=0120050300250丁-5400200298丙-63230054乙-41002022甲供應(yīng)量

EDCBA工地料庫43133522487877經(jīng)計算，該新方案的所有檢驗數(shù)都是非負的，說明這個方案已經(jīng)是最優(yōu)調(diào)運方案了。435323V=77745U=V4=01200503002558圖上作業(yè)法【】有某物資7t，由A1，A2，A3發(fā)出，發(fā)量分別為3，3，1（t），運往收點B1，B2，B3，B4，收量分別為2，3，1，1（t），收發(fā)量平衡，交通圖如圖所示，問應(yīng)如何調(diào)運，才使t·km最小。。431213317354324圖上作業(yè)法【】有某物資7t，由A1，A2，A3發(fā)出，發(fā)量分別59圖上作業(yè)法解：①作一個沒有對流的流向圖，用“去線破圈”的方法，去一線破一圈，有幾個圈去掉幾條線，把有圈的交通圖，化為不成圈的交通圖。一般是去掉長度最長的交通線，比如，去掉Ａ1Ｂ4（7km），破A1B1B2A3B4圈，在去掉A3B3線（4km），破B2A2B3A3圈，這樣，原來有圈的交通圖，變成了不成圈的交通圖。圖上作業(yè)法解：①作一個沒有對流的流向圖，用“去線破圈”的方法603圖上作業(yè)法1213317354324312114②檢查有無迂回，方法水對流想圖中的各圈進行檢查，侃侃有無迂回。如果沒有迂回，即該圈總長的一半均大于內(nèi)流長和外流長，這個初始方案就是最優(yōu)方案，如果其中某一圈有迂回，這個方案就不是最優(yōu)方案，需要改進。在圖中，圈A1B1B2A3B4的總長為23km，外流長為5+4+3=12km，大于圈長的一半，因而需要調(diào)整。在看圈B2A2B3A3其總長為13km，圈中內(nèi)流長為3km，外流長為2km，都小于圈長的一半，因此此圈不必調(diào)整。3圖上作業(yè)法12133173543243121161圖上作業(yè)法然后先從各個端點開始，在圖上作一個沒有對流的流向圖。②檢查有無迂回，方法水對流想圖中的各圈進行檢查，侃侃有無迂回。如果沒有迂回，即該圈總長的一半均大于內(nèi)流長和外流長，這個初始方案就是最優(yōu)方案，如果其中某一圈有迂回，這個方案就不是最優(yōu)方案，需要改進。在圖中，圈A1B1B2A3B4的總長為23km，外流長為5+4+3=12km，大于圈長的一半，因而需要調(diào)整。在看圈B2A2B3A3其總長為13km，圈中內(nèi)流長為3km，外流長為2km，都小于圈長的一半，因此此圈不必調(diào)整。對圈A1B1B2A3B4的調(diào)整方法是：在外圈的個流量中，減去外圈的最小流量1t；然后在內(nèi)圈的個流量中加上1t，在此圈中，因無內(nèi)流量，所以無處可加；另外，在無流量的線段上，新添上內(nèi)圈流量1t，這樣得出新的流量圖。圖上作業(yè)法然后先從各個端點開始，在圖上作一個沒有對流的流向圖62對圈A1B1B2A3B4的調(diào)整方法是：在外圈的個流量中，減去外圈的最小流量1t；然后在內(nèi)圈的個流量中加上1t，在此圈中，因無內(nèi)流量，所以無處可加；另外，在無流量的線段上，新添上內(nèi)圈流量1t，這樣得出新的流量圖。方案調(diào)整1213317354324312114312133173543242121143對圈A1B1B2A3B4的調(diào)整方法是：在外圈的個流量中，減去63121331735432421211432121331735434231431在圈B2A2B3A3中外圈長為4+3=7大于圈長的一半，調(diào)整為內(nèi)圈加“1”外圈減“1”此時兩個圈都沒有迂回是最優(yōu)方案總的TKM為：7*1+2*5+1*4+3*2=27方案調(diào)整12133173543242121143212133173564圖上作業(yè)法新的流量圖中，在A1B1B2A3B4圈內(nèi)，內(nèi)流長為：4+7=11km，外流長為=5km，都不超過全圈長（23km）的一半，因此，這個流向圖沒有迂回現(xiàn)象，是本問題的最優(yōu)調(diào)運方案，總運輸力為27t·km。求解思路小結(jié)：流向劃右方，對流不應(yīng)當，內(nèi)流外流分開算，要求不過外圈長，如若超過外圈長，應(yīng)甩運量最小檔，反復求算最優(yōu)方。圖上作業(yè)法新的流量圖中，在A1B1B2A3B4圈內(nèi)，內(nèi)流長為65任務(wù)二運輸路線的優(yōu)化技術(shù)四、節(jié)約里程法配送路線是指各送貨車輛向各個客戶送貨時所要經(jīng)過的路線。配送路線合理與否對配送速度、成本、效益影響很大，采用科學的、合理的方法來優(yōu)化配送路線，是配送管理中非常重要的工作。任務(wù)二運輸路線的優(yōu)化技術(shù)四、節(jié)約里程法66任務(wù)二運輸路線的優(yōu)化技術(shù)2、配送路線優(yōu)化的方法（1）VSP網(wǎng)絡(luò)圖的原理在有很多配送去向的情況下，使用多少輛車，各輛車按照什么路線運行才能使整個運行距離最短，或使配送費用最低，這是配送路線優(yōu)化的問題。解決這一問題的最有代表性的方法是VSP（VehicleScheduingProgram）網(wǎng)絡(luò)圖。VSP可稱為車輛安排程序方法。

任務(wù)二運輸路線的優(yōu)化技術(shù)2、配送路線優(yōu)化的方法67任務(wù)二運輸路線的優(yōu)化技術(shù)(2)節(jié)約里程法的基本設(shè)定配送的是同一種貨物。各客戶的坐標及需求量均為已知。配送中心有足夠的運輸能力。任務(wù)二運輸路線的優(yōu)化技術(shù)(2)節(jié)約里程法的基本設(shè)定68任務(wù)二運輸路線的優(yōu)化技術(shù)節(jié)約里程法的計算【例】某配送中心A要向所在城市B，C，D，E，F(xiàn)，G共6個客戶點配送貨物，如圖所示。它們之間的距離（km）和每一處的配送貨物量（t）見表。運輸車輛有2.5t和4t兩種貨車，試確定配送路線。表配送距離和配送量任務(wù)二運輸路線的優(yōu)化技術(shù)節(jié)約里程法的計算表69BACDGEF212066991212241019圖配送點最短距離計算圖BACDGEF212066991212241019圖配送點70任務(wù)二運輸路線的優(yōu)化技術(shù)節(jié)約里程法的計算步驟（1）計算配送中心A到各配送點、各配送點之間的最短距離矩陣。（2）計算節(jié)約里程（3）節(jié)約里程排序（4）確定方案（5）改進方案任務(wù)二運輸路線的優(yōu)化技術(shù)節(jié)約里程法的計算步驟71任務(wù)二運輸路線的優(yōu)化技術(shù)解：計算配送中心A到各配送點、各配送點之間的最段距離。最短距離的計算方法：從終點開始逐步逆向推算。由于配送中心與各配送點只有一個結(jié)點，故它們之間的距離即為最短距離。因這些數(shù)據(jù)表中