第三章 配送方案的優(yōu)化

第三章配送方案的優(yōu)化第一節(jié)配送優(yōu)化1、配送優(yōu)化定義：按照貨物的特點合理流向以及運輸條件，走最少的里程，經(jīng)最少的環(huán)節(jié)，用最少的運力，花最少的費用，以最短的時間，把貨物運到目的地。2、優(yōu)化配送的意義（1）有利于物資產(chǎn)品迅速地從生產(chǎn)地向消費地轉(zhuǎn)移，加速資金的周轉(zhuǎn)，提高企業(yè)資金的使用效率。（2）縮短運輸時間，加快物流速度。（3）節(jié)約運輸費用，降低物流成本。（4）節(jié)約運力，緩解運力緊張的狀況，節(jié)約能源。3、不合理配送的概念在組織貨物運輸過程中，違反貨物流通規(guī)律，不按照經(jīng)濟區(qū)域和貨物自然流向組織貨物調(diào)運，在各運輸方式間或在同一運輸方式線路上，發(fā)生相同或可替代產(chǎn)品的對流，或相向運輸、重復(fù)運輸以及過遠運輸、迂回運輸?shù)冗`反各種運輸合理分工原則，而造成不必要的貨物周轉(zhuǎn)或裝卸工作量，浪費運力，增加運輸費用的運輸。4、不合理運輸?shù)谋憩F(xiàn)（1）返程或起程空駛。因調(diào)運不當、貨源計劃不周而形成的空駛是不合理運輸最嚴重的表現(xiàn)形式。造成空駛的原因有：能利用社會化的運輸體系不利用，卻依靠自備車送貨，則往往出現(xiàn)單程實車、單程空駛現(xiàn)象。由于工作失誤或計劃不周，造成貨源不實，車輛空去空回。由于車輛過于專用，無法搭運回程貨物，只能單程實車，單程空駛。（2）對流運輸。對流運輸指的是同種貨物以不同的發(fā)送點同時或先后作面對面的運輸，并且彼此重復(fù)對方旅程的全部或一部分。10301010B1A1A2B2304030(10)(10)10301010B1A1A2B2304030(10)(10)調(diào)整前有對流的配送調(diào)整后無對流的配送（3）迂回運輸。在貨物發(fā)點與收點之間有兩條以上的同類交通線可以采用時，未能利用最短路徑的運輸。556km4km5噸556km4km5噸迂回運輸105030302443（10）（30）（20）迂回運輸無迂回運輸105030302443（20）（30）（10）無迂回運輸重要原則：環(huán)狀線路上，收點與發(fā)點的貨物行走公路數(shù)，不應(yīng)超過整個環(huán)狀路線長度的一半。（4）過遠運輸。調(diào)運物資舍近求遠的現(xiàn)象。（5）運力選擇不當。即運輸工具沒有正確的利用所造成的不合理現(xiàn)象。棄水走陸。鐵路、大型船舶的過近運輸。運輸工具承載能力選擇不當。出現(xiàn)大馬拉小車，小驢拉大車。（6）托運方式不當。本應(yīng)采用直運而采用了轉(zhuǎn)運。5、合理配送的途徑（1）、減少運輸次數(shù)，縮短運輸距離。如在煤炭基地建發(fā)電廠，在林業(yè)基地建木材加工廠。（如福建泰寧）

企業(yè)往往其廠址選擇有以下幾種類型：靠近原料供應(yīng)靠近市場動力指向型廉價勞動力指向型技術(shù)指向型（2）提高運輸工具的實載率。充分利用專業(yè)運輸隊伍。充分獲取和利用相關(guān)信息，如貨源信息、道路交通狀況、天氣預(yù)報、同行業(yè)運輸狀況信息等。采取盒裝整車運輸方式。即零擔拼整車中轉(zhuǎn)運輸，主要用于雜貨運輸。5、優(yōu)化配送的途徑（3）周密進行運輸系統(tǒng)設(shè)計運輸與原料采購的配合、運輸與產(chǎn)品銷售的配合、運輸與倉庫的合理設(shè)計、運輸網(wǎng)絡(luò)的合理布局。（4）科學選擇運輸方式，避免動力閑置浪費。鐵路、水路的經(jīng)濟運輸里程在200-300km以上，適合“重、厚、長、大”的貨物。公路的經(jīng)濟運輸里程在300km以下，適合“輕、薄、短、小”貨物（5）、采用四就直撥運輸

這種方式是指物流經(jīng)理在組織貨物調(diào)運的過程中，以當?shù)厥a(chǎn)或外地到達的貨物不運進批發(fā)站倉庫，運用直撥的方法，把貨物直接分撥給基層批發(fā)、零售中間環(huán)節(jié)。該種方式可以減少一道中間環(huán)節(jié)，在時間和各方面起到雙重的經(jīng)濟效益。四就直撥的主要形式含義具體方式就廠直播物流部門從工廠收購產(chǎn)品，在經(jīng)廠驗收后，不經(jīng)過倉庫和不必要的轉(zhuǎn)運環(huán)節(jié)，直接調(diào)撥給銷售部門或直接送到車站碼頭運往目的地廠場際直撥、廠店直撥、廠批直撥用工廠專用線、碼頭直接發(fā)送就車站直撥物流部門對外地到達車站的貨物，經(jīng)交接驗收后，直接分撥給各個銷售部門直接運往市內(nèi)各銷售部門直接運往外埠要貨單位就倉庫直撥在發(fā)貨時越過逐級的層層調(diào)撥，省略不必要中間環(huán)節(jié)，直接從倉庫撥給銷售部門對需要儲存保管的貨物就倉庫直撥對常年生產(chǎn)、常年銷售貨物就倉庫直撥對季節(jié)生產(chǎn)、常年銷售貨物就倉庫直撥就車船過載對外地用車、船運入的貨物，經(jīng)交接驗收后，不在車站或碼頭停放，不入庫，隨即通過其它運輸工具直接運至銷售部門就火車直接裝汽車就船直接裝火車或汽車就大船過駁小船第二節(jié)物流配送網(wǎng)絡(luò)布局優(yōu)化1、配送網(wǎng)絡(luò)布局的定義：根據(jù)物資的供需情況，運輸條件，自然狀況等因素，來合理布置物流節(jié)點的位置、規(guī)模和供貨范圍。2、配送網(wǎng)絡(luò)布局的步驟（1）找出物流配送網(wǎng)絡(luò)規(guī)劃的約束條件。（2）依據(jù)約束條件構(gòu)造模型；（3）將模型轉(zhuǎn)變成數(shù)學模型求出可行解；（4）依據(jù)一定判斷標準對可行解進行排序，求出較于滿意解。例如:某企業(yè)打算在南昌或沈陽設(shè)立分公司（也許在兩個城市都設(shè)立分公司）增加市場份額，同時計劃在新設(shè)立分公司城市最多建一個配送中心，也可以不建配送中心，總的預(yù)算費用不得超過20萬。求如何規(guī)劃使的企業(yè)總凈現(xiàn)值最大。決策編號問題決策變量凈現(xiàn)值（萬元）所需資金（萬元）1是否在南昌設(shè)分公司X118122是否在沈陽設(shè)分公司X21063是否在南昌設(shè)立配送中心X312104是否在武漢設(shè)立配送中心X484

abcdefgh12345789610111214133、備選地址的選擇原則（1）用戶滿意原則（2）有利于運輸合理化（3）費用最小原則（4）動態(tài)性原則（5）戰(zhàn)略性原則4、網(wǎng)點布局的常用方法（1）解析方法（2）模擬方法（3）啟發(fā)式方法（迭代法）5、一元網(wǎng)點布局問題[1]因素評分法。步驟如下：

給出備選地點。列出影響選址的各個因素。給出各因素的分值范圍。由專家對各備選點就各因素評分。將每一個地點因素的得分相加，求出總分后加以比較，得分最多的地點中選?？紤]因素分值范圍區(qū)域內(nèi)貨物需要量大小0~400周圍的輔助服務(wù)設(shè)施0~330運輸條件0~200配送服務(wù)的輻射區(qū)域范圍0~100生活條件0~100出貨0~100與顧客距離0~100勞動力獲取0~30勞動力成本0~20氣候0~50供應(yīng)商情況0~200進貨0~100工會環(huán)境0~50稅收0~50國家激勵措施/法律0~50土地成本0~50公用事業(yè)費0~10適時管理要求0~50影響選址的每個因素及其分值范圍[2]重心法將配送系統(tǒng)的資源點和需求點看成是分布在某一平面范圍的物體系統(tǒng)，各資源點與需求點的物流量可分別看成是物體的重量，物體系統(tǒng)的重心將作為配送中心的最佳位置。如果（Xi,Yi)表示個點的坐標，Wi表示各點的運量，Ci表示各點的運輸費率，則重心的坐標為：

X0=（X1W1C1+``+XiWiCi）/（W1C1+`+WiCi）

Y0=（Y1W1C1+``+YiWiCi）/（W1C1+`+WiCi）ANBQ例題1假設(shè)某家電集團在P1地生產(chǎn)冰箱，在P2地生產(chǎn)洗衣機，在P3地生產(chǎn)空調(diào)，在P4地生產(chǎn)小家電，假設(shè)各生產(chǎn)地的運輸費率相同，各工廠所在地與某城市中心的距離和每年產(chǎn)量如下。求配送中心的位置工廠所在地P1P2P3P4X1Y1X2Y2X3Y3X4Y4距離市中心的坐標距離（千米）2070606020205020年運輸量2000120010002500例題2假設(shè)配送中心有三家主要客戶A、B、C，位置如下圖，其中配送中心到A的運輸量為100單位，運費為10元/單位，到B的運輸量為200單位，運費為8元/單位，到C的運輸量為150單位，運費為10元/單位，求最佳的配送中心點。A（5，20）C（20，5）P（X，Y）B（25，25）(3)微分法

彌補重心法的不足，采取逐次迭代而形成滿意結(jié)果。6、多元網(wǎng)點布局問題有m個資源點Ai（i=1,2，····，m），各點的資源量為ai；有n個需求點Bj（j=1,2，···，n），各點的需求量為bj；有q個可能設(shè)置網(wǎng)點的備選地址Dk（k=1,2，·····，q）。需求點可以從設(shè)置的網(wǎng)點進貨，也可以從資源點直接進貨。第三節(jié)貨物配裝優(yōu)化最大化的利用運輸工具的運輸力。1、貨物配裝時應(yīng)該注意的問題外觀、形狀易混淆的貨物應(yīng)該分開擺放重不壓輕；后送先裝；有氣味揮發(fā)和吸收的貨物應(yīng)分開裝；將易散發(fā)粉塵和清潔貨物分開裝；滲水貨物與易受潮貨物分開裝；包裝不同貨物應(yīng)分開裝；有銳角的貨物應(yīng)該加上外框，以免碰撞受損；圓狀易滾動貨物應(yīng)放直；貨物之間，貨物與車輛之間應(yīng)加上襯墊；注意貨車開門處的貨物穩(wěn)固；注意貨車的重心平穩(wěn)，及注意貨車的裝貨高度；危險品在運輸中出現(xiàn)問題的處置方式爆炸品：迅速轉(zhuǎn)移至安全場所修理或更換包裝，對漏灑的物品及時用水濕潤，灑些鋸屑或棉絮等松軟物，輕輕收集。

壓縮氣體或易揮發(fā)液體：打開車門、庫門，并移到通風場所。液氨漏氣可浸入水中，其他劇毒氣體應(yīng)浸入石灰水中。

自燃品或遇水燃燒品：黃磷灑落后要迅速浸入水中，金屬鈉、鉀等必須浸入盛有煤油或無水液體石蠟的鐵桶中。

易燃品：將滲漏部位朝上。對漏灑物用干燥的黃沙、干土覆蓋后清理。

毒害品：迅速用沙土掩蓋，疏散人員，請衛(wèi)生防疫部門協(xié)助處理。

腐蝕品：用沙土覆蓋，清掃后用清水沖洗干凈。

放射品：迅速遠離放射源，保護好現(xiàn)場，請衛(wèi)生防疫部門指導(dǎo)處理。

2、配裝方法與數(shù)學模型（1）原始手工經(jīng)驗配載即按照配裝工人的日常經(jīng)驗實施配裝。往往簡要考慮車輛的容量與載重要求。

（一）、基本概念

1、階段：把一個問題的過程，恰當?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便于按一定的次序去求解。描述階段的變量稱為階段變量。階段的劃分，一般是根據(jù)時間和空間的自然特征來進行的，但要便于問題轉(zhuǎn)化為多階段決策。年、月、路段（2）動態(tài)規(guī)劃方法

AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514階段(stage)n:也就是作出決策的若干輪次。n=1、2、3、4、5。1階段2階段3階段4階段5階段AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975142、狀態(tài)：表示每個階段開始所處的自然狀況或客觀條件。通常一個階段有若干個狀態(tài)，描述過程狀態(tài)的變量稱為狀態(tài)變量，記為Sn

S1={A}，S2={B1,B2,B3}，S3={C1,C2,C3}，S4={D1,D2,D3}，S5={E1,E2}。階段的起點。AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975143、決策(decision)dn：從一個階段某狀態(tài)演變到下一個階段某狀態(tài)的選擇。一階段所有的決策構(gòu)成決策集，記為Dn(Sn)。

階段的終點。

D1(S1)={d1(A)}={B1,B2,B3}=S2，

D2(S2)={d2(B1),d2(B2),d2(B3)}={C1,C2;C1,C2,C3;C2,C3}={C1,C2,C3}=S3，

D3(S3)={d3(C1),d3(C2),d3(C3)}={D1,D2;D1,D2,D3;D1,D2,D3}={D1,D2,D3}=S4，

D4(S4)={d4(D1),d4(D2),d4(D3)}={E1,E2;E1,E2;E1,E2}={E1,E2}=S5，

D5(S5)={d5(E1),d5(E2)}={F;F}={F}。AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975144、策略(policy)：全過程中各個階段的決策dn組成的有序總體{dn}.

如AB2

C1

D1

E2

F

上例從AF共有38種走法，即有38條路線，38個策略。5、子策略(sub-policy)

：剩下的n個階段構(gòu)成n子過程，相應(yīng)的決策系列叫n子策略。如

C1

D1

E2

FAB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975146、狀態(tài)轉(zhuǎn)移方程當?shù)贙階段處于狀態(tài)sk時，若選用決策dk,則下一階段即第K+1階段所處狀態(tài)sk+1便唯一確定，此事記之為：

sk+1=dk（sk）/uk

（sk）AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514

7、指標函數(shù)和最優(yōu)值函數(shù)：用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標，為指標函數(shù)。指標函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)。在不同的問題中，指標函數(shù)的含義是不同的，它可能是距離、利潤、成本、產(chǎn)量或資源消耗等。動態(tài)規(guī)劃模型的指標函數(shù)，應(yīng)具有可分離性，并滿足遞推關(guān)系。

最優(yōu)值函數(shù)Z=opt[v1(s1,u1)*

*vn(sn,un)]。其中：opt為max或min，*為運算符號。指標函數(shù)

1、動態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫出基本的遞推關(guān)系式和恰當?shù)倪吔鐥l件（簡稱基本方程）。要做到這一點，就必須將問題的過程分成幾個相互聯(lián)系的階段，恰當?shù)倪x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個大問題轉(zhuǎn)化成一組同類型的子問題，然后逐個求解。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進行，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。（二）、動態(tài)規(guī)劃的基本思想例題：設(shè)國家撥給60萬元投資，供四個工廠擴建使用，每個工廠擴建后的利潤與投資額的大小有關(guān)，投資后的利潤函數(shù)如下表所示。投資利潤0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570解：依據(jù)題意，是要求f4(60)

。按順序解法計算。第一階段：求f1(x)。顯然有f1(x)＝g1(x)，得到下表

投資利潤0102030405060f1(x)＝

g1(x)0205065808585最優(yōu)策略0102030405060第二階段：求f2(x)。此時需考慮第一、第二個工廠如何進行投資分配，以取得最大的總利潤。最優(yōu)策略為（40，20），此時最大利潤為120萬元。同理可求得其它f2(x)

的值。投資利潤0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570最優(yōu)策略為（30，20），此時最大利潤為105萬元。投資利潤0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570最優(yōu)策略為（20，20），此時最大利潤為90萬元。最優(yōu)策略為（20，10），此時最大利潤為70萬元。投資利潤0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570最優(yōu)策略為（10，0）或（0，10），此時最大利潤為20萬元。

f2(0)

＝0。最優(yōu)策略為（0，0），最大利潤為0萬元。得到下表最優(yōu)策略為（20，0），此時最大利潤為50萬元。投資利潤0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570

投資利潤0102030405060f2(x)020507090105120最優(yōu)策略(0,0)(10,0)(0,10)(20,0)(20,10)(20,20)(30,20)(40,20)第三階段：求f3(x)。此時需考慮第一、第二及第三個工廠如何進行投資分配，以取得最大的總利潤。最優(yōu)策略為（20，10，30），最大利潤為155萬元。投資利潤0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570投資利潤0102030405060f2(x)020507090105120最優(yōu)策略(0,0)(10,0)(0,10)(20,0)(20,10)(20,20)(30,20)(40,20)F3(60)

投資利潤0102030405060f3(x)0256085110135155最優(yōu)策略(0,0,0)(0,0,10)(0,0,20)(0,0,30)(20,0,20)(20,0,30)(20,10,30)第四階段：求f4(60)。即問題的最優(yōu)策略。最優(yōu)策略為（20，0，30，10），最大利潤為160萬元。投資利潤0102030405060f3(x)0256085110135155最優(yōu)策略(0,0,0)(0,0,10)(0,0,20)(0,0,30)(20,0,20)(20,0,30)(20,10,30)投資利潤0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570練習：某公司打算在3個不同的地區(qū)設(shè)置4個銷售點，根據(jù)市場部門估計，在不同地區(qū)設(shè)置不同數(shù)量的銷售點每月可得到的利潤如表所示。試問在各地區(qū)如何設(shè)置銷售點可使每月總利潤最大。地區(qū)銷售點01234123000161210251714302116322217x1=2，x2=1，x3=1，f3(4)=47

有一個徒步旅行者，其可攜帶物品重量的限度為a公斤，設(shè)有n

種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（作用），問此人應(yīng)如何選擇攜帶的物品（各幾件），使所起作用（使用價值）最大？物品

12…j…n重量（公斤/件）

a1a2…

aj

…

an每件使用價值

c1c2…cj

…

cn（三）（背包問題）

（用于解決車輛運輸過程中容量有限的問題）設(shè)xj

為第j種物品的裝件數(shù)（非負整數(shù)）則問題的數(shù)學模型如下：用動態(tài)規(guī)劃方法求解，按可裝入物品的n種類型劃分n個階段，令

fk(y)=總重量不超過

y公斤，包中只裝有前k種物品時的最大使用價值。其中y≥0，k

＝1,2,…,n。所以問題就是求fn(a)

1其遞推關(guān)系式為：當k=1時，有：例題：求下面背包問題的最優(yōu)解物品123重量（公斤）325使用價值8512解：a＝5

，問題是求f3(5)物品123重量（公斤）325使用價值8512物品123重量（公斤）325使用價值8512物品123重量（公斤）325使用價值8512物品123重量（公斤）325使用價值8512所以，最優(yōu)解為X＝（1,1,0），最優(yōu)值為Z=13。練習1：某廠生產(chǎn)三種產(chǎn)品，各種產(chǎn)品重量與利潤的關(guān)系如表所示。現(xiàn)將此三種產(chǎn)品運往市場出售，運輸能力總重量不超過6噸，問如何安排運輸，使總利潤最大？種類123重量（噸）234單件利潤（元）80130180最優(yōu)方案：X1

=（0.2.0）X2=（1.0.1）Z=260練習2：求下列問題的最優(yōu)解

X=(2.1.0)

最優(yōu)值為

Z=13四、集裝箱問題

d0:集裝箱寬

h0：集裝箱長

li:貨箱長度

hi:貨箱高度例：某運輸問題的資料如下：單位銷地運價產(chǎn)地產(chǎn)量2910291342584257銷量3846第四節(jié)物資調(diào)度優(yōu)化

數(shù)學模型的一般形式

已知資料如下：單位銷地運價產(chǎn)地B1B2B3B4產(chǎn)量A1C11C12C13C14a1A2C21C22C23C24a2A3C31C32C33C34a3銷量b1b2b3b4當產(chǎn)銷平衡時，其模型如下：當產(chǎn)大于銷時，其模型是：當產(chǎn)小于銷時，其模型是：

⑷.重復(fù)⑵.⑶，直到找到最優(yōu)解為止。步驟：

⑴.找出初始基本可行解（初始調(diào)運方案，一般m+n-1個數(shù)字格），用西北角法、最小元素法、伏格爾法；

⑵.求出各非基變量的檢驗數(shù)，判別是否達到最優(yōu)解。如果是停止計算，否則轉(zhuǎn)入下一步，用位勢法計算；

⑶.改進當前的基本可行解（確定換入、換出變量），用閉合回路法調(diào)整；表上作業(yè)法例一、某運輸資料如下表所示：單位銷地運價產(chǎn)地產(chǎn)量311310719284741059銷量36561、求初始方案：

⑴.西北角法（或左上角法）：此法是純粹的人為的規(guī)定，沒有理論依據(jù)和實際背景，但它易操作。如圖：單位銷地運價產(chǎn)地B1B2B3B4產(chǎn)量A1347A2224A3369銷量3656總的運輸費用＝（3×3）＋（4×11）＋（2×9）＋（2×2）＋（3×10）＋（6×5）＝135元B1B2B3B4產(chǎn)量A17A2

4A39銷量3656311310192741058341633

⑵.最小元素法：基本思想是就近供應(yīng)，即從運價最小的地方開始供應(yīng)（調(diào)運），然后次小，直到最后供完為止?？偟倪\輸費用＝（3×1）＋（6×4）＋（4×3）＋（1×2）＋（3×10）＋（3×5）＝86元B1B2B3B4產(chǎn)量A17A2

4A39銷量3656

20311310192741058

（3）伏格爾法：一產(chǎn)地的產(chǎn)品假如不能按最小運費就近供應(yīng)，就應(yīng)考慮次小運費;這就有一個差額,差額越大，說明不能按最小運費調(diào)運時，運費增加越多。因此，差額越大，越要按最小運費調(diào)運。行差額列差額12345123450007

11161225136213

3

212312521總的運輸費用＝（3×1）＋（6×4）＋（5×3）＋（1×8）＋（2×10）＋（3×5）＝85元

最優(yōu)解判斷法則σij≥0（因為目標函數(shù)要求最小化）

表格中有調(diào)運量的地方為基變量，空格處為非基變量?；兞康臋z驗數(shù)σij＝0，非基變量的檢驗數(shù)σij≥0。

σij<0表示運費減少，σij>0表示運費增加。2、最優(yōu)解的判別（檢驗數(shù)的求法）：

⑴.閉合回路法：

B1B2B3B4產(chǎn)量A17A24A39銷量3656313463（＋1）（＋1）（－1）（－1）①②③③

計算如下：空格處（A1

B1

）＝

(1×3)＋｛(－1)×3｝＋(1×2)＋｛(－1)×1｝＝1

此數(shù)即為該空格處的檢驗數(shù)。1B1B2B3B4產(chǎn)量A17A24A39銷量3656313631241131045計算如下：空格處（A1

B2）＝

(1×11)＋｛(－1)×10｝＋(1×5)＋｛(－1)×4｝＝2

此數(shù)即為該空格處的檢驗數(shù)。（+1）（-1）（-1）（+1）B1B2B3B4產(chǎn)量A17A24A39銷量36563136312-1431028計算如下：空格處（A2B4）＝

(1×8)＋｛(－1)×10｝＋(1×3)＋｛(－1)×2｝＝-1

此數(shù)即為該空格處的檢驗數(shù)。B1B2B3B4產(chǎn)量A17A24A39銷量365631363121-14451032計算如下：空格處（A2

B2）＝(1×9)＋｛(－1)×4｝＋(1×5)＋｛(－1)×10｝＋(1×3)＋｛(－1)×2｝＝1

此數(shù)即為該空格處的檢驗數(shù)。9B1B2B3B4產(chǎn)量A17A24A39銷量365631363121-11243105計算如下：空格處（A3B3）＝

(1×10)＋｛(－1)×5｝＋(1×10)＋｛(－1)×3｝＝12

此數(shù)即為該空格處的檢驗數(shù)。10B1B2B3B4產(chǎn)量A17A24A39銷量365631363121-1121047123105計算如下：空格處（A3B1）＝(1×7)＋｛(－1)×1｝＋(1×2)＋｛(－1)×3｝＋(1×10)＋｛(－1)×5｝＝10

此數(shù)即為該空格處的檢驗數(shù)。B1B2B3B4產(chǎn)量A17A24A39銷量365600000121-112100

檢驗數(shù)中有負數(shù)，說明原方案不是最優(yōu)解。

運輸問題的約束條件共有m+n個，其中：m是產(chǎn)地產(chǎn)量的限制；n是銷地銷量的限制。

由單純形法可知，基變量的σij＝

0∴cij－(ui+vj)＝0因此ui

,vj可以求出。⑵.位勢法B1B2B3B4產(chǎn)量A17A2

4A39銷量3656311310192741058341633

原運輸圖接上例：B1B2B3B4A1310u1A212u2A345u3v1v2v3v4成本表B1B2B3B4A1293100A21829－1A3－34－25－529310

u2+v1=1

u2+v3=2

u3+v2=4u1+v4=10

u1+v3=3u3+v4=5

令：u1＝0u1＝0v1＝2u2＝－1v2＝9u3＝－5v3＝3v4＝10(ui+vj)按σij=cij－(ui+vj)

計算檢驗數(shù)，并以σij≥0

檢驗，或用(ui+vj)

－cij

≤0檢驗。B1B2B3B4A1311310A21928A374105cijB1B2B3B4A129310A21829A3－34-25(ui+vj)－B1B2B3B4A11200A2010－1A3100120＝表中還有負數(shù)，說明還未得到最優(yōu)解，應(yīng)繼續(xù)調(diào)整。σij

——閉合回路調(diào)整法接上例：B1B2B3B4產(chǎn)量A17A24A39銷量36563134633、解改進的方法-1B1B2B3B4產(chǎn)量A1527A2314A3639銷量36566563銷量9A34A27A1產(chǎn)量B4B3B2B1313463（＋1）（＋1）（－1）（－1）改進后的運輸方案B1B2B3B4A10200A20210A390120經(jīng)檢驗所有σij≥0,得到最優(yōu)解，最小運費

=(3×5)＋(2×10)＋(1×3)＋(8×1)＋(4×6)＋(5×3)=850v4v3v2v1u354A3u281A2u1103A1B4B3B2B1成本表10393－55－24－2A3－28171A2010393A1B4B3B2B1(ui+vj)uivjB1B2B3B4A1311310A21928A374105Cij所有σij≥0,得到最優(yōu)解，最小運費

=(2×3)＋(5×3)＋(1×1)＋(3×8)＋(6×4)＋(3×5)=85B1B2B3B4產(chǎn)量A10527A2314A3639銷量3656(+2)(-2)(-2)(+2)B1B2B3B4產(chǎn)量A1257A2134A3639銷量3656另一運輸方案

⑴.無窮多最優(yōu)解：產(chǎn)銷平衡的運輸問題必定存最優(yōu)解。如果非基變量的σij＝0，則該問題有無窮多最優(yōu)解。如上例：（1.1）中的檢驗數(shù)是0，經(jīng)過調(diào)整，可得到另一個最優(yōu)解。

⑵.退化：表格中一般要有(m+n-1)個數(shù)字格。但有時，在分配運量時則需要同時劃去一行和一列，這時需要補一個0，以保證有(m+n-1)個數(shù)字格。一般可在劃去的行和列的任意空格處加一個0即可。4、表上作業(yè)法計算中的問題例1：B1B2B3B4A178143A226355A3142782176213552682176

例2：B1B2B3A11221A23132A32314124B1B2B3A111A222A344124000

1、產(chǎn)大于銷：模型方法是先將原問題變成平衡問題，需假設(shè)一個銷地(Bn+1)(實際上考慮產(chǎn)地的存量)，三、產(chǎn)銷不平衡的運輸問題及其求解方法模型為：

2、銷大于產(chǎn)：同樣假設(shè)一個產(chǎn)地即可，變化同上。單位運價表中的單位運價為B1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5

A121134070A210359050A378120702030406040B1B2B3B4B5

A170A250A370203040604040303020302020用最小元素法求初始方案例題：（產(chǎn)大于銷的情況）已知某運輸問題的資料如下表所示B1B2B3B4發(fā)量A1265315A2132112A3327413收量1013125

1、表中的發(fā)量、收量單位為：噸，運價單位為：元/噸試求出最優(yōu)運輸方案.練習：

2、如將A2的發(fā)量改為17，其它資料不變，試求最優(yōu)調(diào)運方案。B1B2B3B4發(fā)量A112315A210212A313013收量1013125B1B2B3B4發(fā)量A1265315A2132112A3327413收量1013125解：1、用最小元素法求初始方案最小運費

=(12×5)＋(3×3)＋(10×1)＋(2×1)＋(13×2)=107B1B2B3B4A153A211A3242、用位勢法判斷：B1B2B3B4ui

A153u1A211u2A324u3vj

v1v2v3v4成本表

u1+v3=5u2+v4=1u1+v4=3u3+v2=2u2+v1=1u3+v4=4

令：u1＝0u1＝0v1＝3u2＝－2v2＝1u3＝1v3＝5v4＝3B1B2B3B4ui

A1530A211－2A3241vj

3153B1B2B3B4ui

A131530A21－131－2A342641vj

3153(ui+vj)B1B2B3B4A12653A21321A33274B1B2B3B4A13153A21－131A34264cij－B1B2B3B4A1－1500A204－10A3－1010＝表中還有負數(shù)，說明沒有得到最優(yōu)解，調(diào)整運輸方案。σij(ui+vj)B1B2B3B4A1123A2102A3130B1B2B3B4A1105A2102A3130＋2＋2－2－2新的運送方案B1B2B3B4A153A212A324新的成本表B1B2B3B4ui

A141530A21－220－3A352641vj

4153(ui+vj)1

總的運費105元/噸B1B2B3B4A14153A21－220A35264B1B2B3B4A12653A21321A33274－＝B1B2B3B4A1－2500A20501A3－2010表中還有負數(shù)，說明沒有得到最優(yōu)解，繼續(xù)調(diào)整運輸方案。cij(ui+vj)1

(σij)1

013A3210A2510A1B4B3B2B13512vj

14623A3－302－2－1A203512A1ui

B4B3B2B1(ui+vj)2

42A32A2352A1B4B3B2B1新的成本表013A312A25010A1B4B3B2B1新的運送方案總的運費85元/噸B1B2B3B4A12653A21321A33274cijB1B2B3B4A12153A2－1－220A33264(ui+vj)2

－＝B1B2B3B4A10500A22501A30010

(σij)2

表中沒有負數(shù)，說明已經(jīng)得到最優(yōu)解。但有無窮多最優(yōu)解。0013A312A25010A1B4B3B2B1最終的運送方案總的運輸費用＝（10×2）＋（5×3）＋（12×2）＋（13×2）＝85元B1B2B3B4B5發(fā)量A110515A2102517A313013收量10131255B1B2B3B4B5發(fā)量A12653015A21321017A33274013收量10131255（第2小題）B1B2B3B4B5A150A2121A324B1B2B3B4B5ui

A150u1A2121u2A324u3vj

v1v2v3v4v5成本表

u1+v3=5u2+v3=2u1+v5=0u2+v4=1u2+v1=1u3+v2=2u3+v4=4令：u1＝0u1＝0v1＝4u2＝-3v2＝2u3＝0v3＝5v4＝4v5＝0B1B2B3B4B5ui

A1425400A21-121-3-3A3425400vj

42540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5

A1-240-10A204004A3-10200σij505B45121310收量1313A317210A215510A1發(fā)量B5B3B2B1B1B2B3B4B5發(fā)量A1100515A212517A313013收量10131255B1B2B3B4B5A1250A221A324B1B2B3B4B5ui

A1250u1A221u2A324u3vj

v1v2v3v4v5成本表

u1+v1=2u2+v4=1u1+v3=5u3+v2=2u1+v5=0u3+v4=4u2+v3=2令：u1＝0u1＝0v1＝2u2＝-3v2＝2u3＝0v3＝5v4＝4v5＝0B1B2B3B4B5ui

A1225400A2-1-121-3-3A3225400vj

22540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5

A1040-10A224004A310200σijB1B2B3B4B5發(fā)量A1100515A212517A313013收量10131255B1B2B3B4B5發(fā)量A1100515A212517A313013收量10131255B1B2B3B4B5發(fā)量A110515A212517A31313收量10131255C=75已知資料如下表所示，問如何供電能使總的輸電費用為最??？發(fā)電廠發(fā)電量A1700A2200A3100城市需電量B1500B2250B3100B4150電力供需表B1B2B3B4A110523A24312A35634單位輸電費用作業(yè)：B1B2B3B4A1A2A3初始方案10010050250400100B1B2B3B4A110523A24312A35634單位輸電費用發(fā)電廠發(fā)電量A1700A2200A3100城市需電量B1500B2250B3100B4150電力供需表B1B2B3B4A11053A212A35B1B2B3B4ui

A1105230A29412-1A350-3-2-5vj

10523B1B2B3B4ui

A10000A2-5-100A30666vj

σij成本表-(ui+vj)

=cij

(ui+vj)

A3A2A1B4B3B2B1初始方案10010050250400100B1B2B3B4A110523A24312A35634cijB1B2B3B4A140025050A2100100A3100B1B2B3B4A1300250150A2100100A3100B1B2B3B4A11053A241A35成本表B1B2B3B4ui

A1105730A24-11-3-6A3502-2-5vj

10573

(ui+vj)

調(diào)運方案B1B2B3B4ui

A100-50A20405A30616vj

σij-(ui+vj)

=cijB1B2B3B4A1300250150A2100100A3100B1B2B3B4A1200250100150A2200A3100B1B2B3B4A110523A24A35成本表調(diào)運方案B1B2B3B4ui

A1105230A24-1-4-3-6A350-3-2-5vj

10523

(ui+vj)

B1B2B3B4ui

A10000A20455A30666vj

σij-(ui+vj)

=cijB1B2B3B4A1200250100150A2200A3100C=5200試用表上作業(yè)法求最優(yōu)解20060554540銷量758779A3704635A2556263A1產(chǎn)量B4B3B2B1銷地產(chǎn)地B1B2B3B4產(chǎn)量A140

15

55A2

45

2570A3

403575銷量40455560200最小總費用為945。第五節(jié)線路優(yōu)化1、一對一的運輸2、一對多的運輸3、多對多的運輸1、一對一的運輸一個供貨點對另一個點運輸送貨常常描述為物品由一個點經(jīng)過若干個階段且每個階段都有若干個點后到達另一終點的運輸。（1）有序經(jīng)過若干個階段（各階段點不相連情況）（2）不好劃分階段情況。例如、從A

地到D

地要鋪設(shè)一條煤氣管道,其中需經(jīng)過兩級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。問應(yīng)該選擇什么路線，使總距離最短？AB1B2C1C2C3D24333321114（1）有序經(jīng)過若干階段的情況AB1B2C1C2C3D24333321114

從最終狀態(tài)開始,自右至左,逆著決策次序進行計算(故名逆推法),每次在已知某階段初所處狀態(tài)的條件下,推算應(yīng)選取什么決策，階段末應(yīng)處于什么狀態(tài),使從所處狀態(tài)出發(fā)到最終狀態(tài)的各決策構(gòu)成該所處狀態(tài)的最優(yōu)（后部）子策略。算完后再從初始狀態(tài)到最終狀態(tài)順序找最優(yōu)策略。逆推法：解：整個計算過程分三個階段，從最后一個階段開始。第三階段（C→D）：C

有三條路線到終點D

。

AB1B2C1C2C3D24333321114DC1C2C3顯然有f0(D

)

=0;f1(C1)

=1；

f1(C2)

=3；

f1(C3)

=4

第一階段第二階段第三階段

d(B1,C1)+f1(C1)

3+1f2(B1)=mind(B1,C2

)+f1(C2)

=min3+3

d(B1,C3)+f1(C3)1+44=min6=45第二階段（B→C）：B到C

有六條路線。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為B1→C1→D)

d(B2,C1)+f1(C1)

2+1f2(B2)=mind(B2,C2

)+f1(C2)

=min3+3

d(B2,C3)+f1(C3)1+43=min6=35AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為B2→C1→D)第一階段（

A→B

）：A到B有二條路線。

f3(A)1=d(A,B1)＋f2(B1)＝2＋4＝6

f3(A)2=d(A,B2)＋f2(B2)＝4＋3＝7∴f3(A)

=min=min｛6,7｝=6d(A,B1)＋f2(B1)d(A,B2)＋f2(B2)(最短路線為A→B1→C1→D)AB1B2C1C2C3D24333321114DC1C2C3B1B2AAB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路線為A→B1→C1→D

路長為6練習：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最優(yōu)路線為：A→B1→C2→D1→E2→F2→G

路長＝18用逆推法求從A到G的最短路徑3第一階段第二階段第三階段第四階段第五階段第六階段k=5，出發(fā)點E1、E2、E3d5(E1)=F1E1F1GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643d5(E2)=F2E2F2Gk=6,F1Gf6(F1)=4F2G

,f6(F2)=34d5(E3)=F2E3F2Gk=4，f4(D1)=7d4(D1)=E2D1E2F2Gf4(D2)=6d4(D2)=E2D2E2F2Gf4(D3)=8d4(D3)=E2D3E2F2Gf3(C1)=13d3(C1)=D1C1D1E2F2Gf3(C2)=10d3(C2)=D1C2D1E2F2Gf3(C3)=9d3(C3)=D1C3D1E2F2Gf3(C4)=12d3(C4)=D3C4D3E2F2Gk=3,AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643k=2,f2(B1)=13d2(B1)=C2B1C2D1E2F2Gf2(B2)=16d2(B2)=C3B2C3D1E2F2G

=minf1(A)=mind1(A,B1)+f2(B1)d1(A,B2)+f2(B2)5+133+16=18k=1,AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643d1(A)=B1d2(B1)=C2d3(C2)=D1d4(D1)=E2d5(E1)=F1E1F1Gd5(E2)=F2E2F2Gd5(E3)=F2E3F2G759

d5(E2)=F2d6(F2)=G最優(yōu)策略AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643

一般提法為：設(shè)為連通圖，圖中各邊有權(quán)（表示之間沒有邊），為圖中任意兩點，求一條路，使它為從到的所有路中總權(quán)最短。即：最小。(一)、狄克斯屈拉(Dijkstra)算法適用于wij≥0，給出了從vs到任意一個點vj的最短路。（2）、無序經(jīng)過若干各點的情況算法步驟：1.給始點vs以P標號