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

1、物流系統(tǒng)規(guī)劃物流系統(tǒng)規(guī)劃15.3 物流分配規(guī)劃物流分配規(guī)劃q任務(wù)分配問題的數(shù)學模型任務(wù)分配問題的數(shù)學模型q用匈牙利法求解分配問題用匈牙利法求解分配問題第第5章章 物流系統(tǒng)規(guī)劃物流系統(tǒng)規(guī)劃2一一. 任務(wù)分配問題的數(shù)學模型任務(wù)分配問題的數(shù)學模型q在物流系統(tǒng)中或其它的管理工作中，管理人員經(jīng)常面臨的一個問題是：如何根據(jù)有限的資源(人力、物力、財力等)，進行工作任務(wù)分配，以達到降低成本或提高經(jīng)濟效益的目的。如：v 有A、B、C、D四門課程，上課的老師可以從甲、乙、丙、丁四名老師中選擇，不同的老師上不同的課程，其費用是不同的，并且規(guī)定，每人只講一門課程，每門課程只需要一人講授。問：如何安排，才能使總的上課

2、費用最低？v 又如：運輸任務(wù)的分配問題。有n條航線的運輸任務(wù)指派給n艘船去完成，不同的船完成不同的航線其運輸成本不同。要求每條船完成一條航線，并且一條航線只能由一條船去完成。如何分配任務(wù)，才能使總的費用最?。縬這類問題是常見的任務(wù)分配問題，也叫指派問題，它的任務(wù)是如何進行合理的任務(wù)分配，使總的費用最小。第第5章章 物流系統(tǒng)規(guī)劃物流系統(tǒng)規(guī)劃3一一. 任務(wù)分配問題的數(shù)學模型任務(wù)分配問題的數(shù)學模型q以運輸問題的n項任務(wù)由n個司機去完成的情況為例，有n個司機被分配完成n項運輸任務(wù)，不同的司機完成任務(wù)某一項任務(wù)的費用都不一樣。要求每個司機完成其中一項任務(wù)，每個任務(wù)只能由一名司機完成，如何分配任務(wù)，才能使

3、總的費用最??？ 1011. .1111或ijniijnjijniniijijxxxtsxcMinZ 令： cij表示第i個司機完成第j項任務(wù)的運輸成本（工作成本或工作時間等價值系數(shù)）； xij表示第i個司機去完成第j項任務(wù)，其值為1或0。q當其值為1時表示第i個司機被分配去完成第j項任務(wù)；q其值為0時，表示第i個司機不被分配去完成第j項任務(wù)。第第5章章 物流系統(tǒng)規(guī)劃物流系統(tǒng)規(guī)劃4一一. 任務(wù)分配問題的數(shù)學模型任務(wù)分配問題的數(shù)學模型q任務(wù)分配問題屬于整數(shù)規(guī)劃問題，其變量xij的取值為整數(shù)，（本例為0或1）。q任務(wù)分配問題可以用一般的整數(shù)規(guī)劃求解方法進行求解。但是，整數(shù)規(guī)劃問題的求解也是非常困難的

4、，到目前為止，還缺乏統(tǒng)一的求解方法。q本書采用匈牙利法求解任務(wù)分配問題。第第5章章 物流系統(tǒng)規(guī)劃物流系統(tǒng)規(guī)劃5二二. 匈牙利法求解分配問題匈牙利法求解分配問題q可以證明，對于分配問題，在其費用矩陣Cij中，各行、各列均減去一個常數(shù)，Cij改變以后的最優(yōu)解，仍為原問題的最優(yōu)解。q利用這個性質(zhì)，通過對Cij的行、列進行加減常數(shù)的計算，把一些矩陣元素變?yōu)?，在Cij為0的元素上進行分解，就可得到原問題的最優(yōu)解。q該方法應(yīng)用了匈牙利數(shù)學家Konig矩陣性質(zhì)定理，因此這種方法被稱為匈牙利法。物流系統(tǒng)規(guī)劃物流系統(tǒng)規(guī)劃65.4 其他規(guī)劃問題其他規(guī)劃問題q選址問題選址問題q貨物裝配問題貨物裝配問題q物流服務(wù)系

5、統(tǒng)中的配置問題物流服務(wù)系統(tǒng)中的配置問題第第5章章 物流系統(tǒng)規(guī)劃物流系統(tǒng)規(guī)劃7一一. 選址問題選址問題q物流調(diào)運規(guī)劃問題，是一種有固定發(fā)點、固定收點和固定道路的運輸規(guī)劃問題。q還有一類運輸問題，他的收貨點和發(fā)貨點是待定的，這就是選址問題。這類問題在物流系統(tǒng)規(guī)劃中經(jīng)常遇到。q選址問題要考慮多種因素，本節(jié)只討論選址問題中的物流問題。分為兩個問題：v單一地址選址方法；v圖上作業(yè)法。第第5章章 物流系統(tǒng)規(guī)劃物流系統(tǒng)規(guī)劃81. 單一地址選址方法單一地址選址方法 建立一個新工廠（或倉庫），應(yīng)合理選擇廠址（或庫址）。所謂選址問題，就是從多個候選廠址中選取一個最優(yōu)地址建廠，使物流費用達到最低。 問題描述問題描述

6、：假設(shè)廠址候選地點有s個，分別用D1,D2,Ds表示；原材料、燃料、零配件的供應(yīng)地有m個，分別用A1,A2,Am表示，其供應(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點建廠。011minDBDDc運輸DA11111111jkj1jji或以表示為：選址問題的數(shù)學模型可為：所有候選地的運輸成本費用為：到所有的銷售地的運輸候選地的運輸費用為：到銷

7、售地從候選地的運輸費用為：所有的供應(yīng)點到候選地費用為：點的到候選地從供應(yīng)點jsjjjsjnkkjkmiiijsjnkjkjkmijiijnkjkjkjkjkmijiijjiijxxs.t.x)QdPc(Z)xQdxPc(xQdxQdxPcxPq單一選址問題是一種線性規(guī)劃問題,并且變量的取值為0或1，屬于整數(shù)規(guī)劃問題。q單一地址的選址模型的求解方法比較簡單從目標函數(shù)表達式的右邊可以看出：通過計算模型中通過計算模型中括號內(nèi)的算式值，就能夠確定運輸成本最小的方括號內(nèi)的算式值，就能夠確定運輸成本最小的方案。案。q當要選定的地址不是單一的，而是多個時，問題不再屬于線性規(guī)劃問題。第第5章章 物流系統(tǒng)規(guī)劃物

8、流系統(tǒng)規(guī)劃122. 2. 圖上作業(yè)法圖上作業(yè)法 對于運輸路線不含回路的選址問題，可用圖上作業(yè)法求解。 下面以一個實際例子來說明圖上作業(yè)法的選址問題： 例題8 假定有六個礦井產(chǎn)量分別為5000噸、6000噸、7000噸、2000噸、4000噸和3000噸，運輸路線如圖所示，這些礦石要經(jīng)過加工后才能轉(zhuǎn)運到其他地方。這些礦井之間道路不含回路，欲選擇一個礦井，在此礦井上建立一個加工廠，使各礦井到工廠的運輸總費用最低。 為了便于分析，用一個新的圖來代替原圖，新圖圈內(nèi)數(shù)字表示礦井編號，產(chǎn)量記在圈的旁邊，道路交叉點看作產(chǎn)量為零的礦井，把那些只有一條道路連接的礦井稱為端點。q首先計算這些礦井的總產(chǎn)量，本例為2

9、7000噸。q然后分析各端點，都沒有超過總產(chǎn)量的一半，因此把各端點的數(shù)量合并到前一站，即 和 的數(shù)量合并到；把的數(shù)量合并到 ；把 的數(shù)量合并到 ，如下圖所示。3561100090007000q各端點都合并到前一站后， 和變成了圖中的端點。對它們進行分析其數(shù)量都不超過總產(chǎn)量的一半，所以他們不是最佳點。q再把它們合并到前一站，即把和的數(shù)量合并到 。則 的數(shù)量為27000，超過總量的一半，所以是最佳點。q結(jié)論：加工廠應(yīng)建在第5號礦井。 第第5章章 物流系統(tǒng)規(guī)劃物流系統(tǒng)規(guī)劃14二二. 貨物裝配貨物裝配 貨物配裝的目的是在車輛載重量為額定值的情況下，合理進行貨物的安排，使車輛裝載貨物的價值最大（如：重量

10、最大、運費最低等）。 第第5章章 物流系統(tǒng)規(guī)劃物流系統(tǒng)規(guī)劃151. 運用動態(tài)規(guī)劃解裝貨問題運用動態(tài)規(guī)劃解裝貨問題 設(shè)貨車的載重量上限為G，用于運送n種不同的貨物，貨物的重量分別為W1，W2，.，Wn，每一種貨物對應(yīng)于一個價值系數(shù)，分別用P1，P2，.，Pn表示，它表示價值、運費或重量等。設(shè)Xk表示第k種貨物的裝入數(shù)量，貨物配裝問題的數(shù)學模型可以表示為： ),.,1(0. .)(max11nkXGXWtsXPxfkknkknkkkq可以把裝入一件貨物作為一個階段，把裝貨問題看作動態(tài)規(guī)劃問題。一般情況下，動態(tài)規(guī)劃問題的求解過程是從最后一個階段開始由后向前進行的。由于裝入貨物的先后次序不影響裝貨問題

11、的最優(yōu)解。所以我們的求解過程可以從第一階段開始，由前向后逐步進行。q求解過程：（1）裝入第1種貨物X1件，其最大價值為 111max)(XPWf其中：X1表示第1種貨物的裝載數(shù)量；其取值范圍：0X1 G/W1 ，方括號表示取整； P1：第1種貨物的價值系數(shù)（重量、運費、價值等）； f1(W)：第一種貨物的價值。 (2)裝入第2種貨物X2件，其最大價值為 其中：X2表示第2種貨物的裝載數(shù)量； 其取值范圍：0X2 G/W2 ； P2：第2種貨物的價值系數(shù)（重量、運費、價值等）； ：第一種貨物的重量； ：第一種貨物的價值。（3）裝入第3種貨物X3件，其最大價值為 其中：X3表示第3種貨物的裝載數(shù)量；

12、 其取值范圍：0X3 G/W3； P3：第3種貨物的價值系數(shù)；)(max)(221222XWWfXPwf22XWW )(221XWWf)(max)(332333XWWfXPwf(n) 裝入第n種貨物Xn件，其最大價值為 其中：Xn表示第n種貨物的裝載數(shù)量； 其取值范圍：0Xn G/Wn ； Pn：第n種貨物的價值系數(shù)；)(max)(1nnnnnnXWWfXPwf例題9 載重量為8t的載重汽車，運輸4種機電產(chǎn)品，產(chǎn)品重量分別為3噸、3噸、4噸、5噸，試問如何配裝才能充分利用貨車的運載能力?解： 第一步，按照前面的公式，分成四個階段計算每一階段的價值。第一步，按照前面的公式，分成四個階段計算每一階

13、段的價值。 計算結(jié)果以表格表示如下：貨物裝配例題載重量件數(shù)價值(重量)載重量第2種貨物的件數(shù)第1種貨物的重量價值計算價值Max載重量第3種貨物的件數(shù)第1、2種貨物的重量價值計算價值Max第二步：尋找最優(yōu)方案。第二步：尋找最優(yōu)方案。尋找最優(yōu)解方案的次序與計算順序相反，由第4階段向第1階段進行。從價值最大的裝載情況，逐步向前尋找最優(yōu)方案。（1）在第4階段計算表中，在載重量為8時，價值(本例為載重量)最大值f4(W)8，對應(yīng)兩組數(shù)據(jù)(加*號的數(shù)據(jù))： 1）X40； 2）X41； 先看X41時的情況： 當X41時，即第4種貨物裝入1件(5噸)，表中第3列數(shù)字表示其余種類貨物的裝載量。當當X41時，其他

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

15、4=1； 第二組：X1=0，X2=1，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時得出的方案。 如果在第4階段計算表中取X X4 40 0，則其余種類的貨物裝載量W - W4X4=8； 在第3階段計算表中，查W=8一欄，f3(w)=8對應(yīng)X32，再仿照前面的方法，可以得到第3組最優(yōu)解： 第三組：X X1 1=0=0，X X2 2=0=0，X X3 3=2=2，X X4 4=0=0； 裝載量為：X3 * 2 = 2*4

16、= 8以上三組裝載方案，都最大限度地發(fā)揮了車輛的載重能力，都是最優(yōu)方案。最終的最優(yōu)裝載方案為： 第一組：X X1 1=1=1，X X2 2=0=0，X X3 3=0=0，X X4 4=1=1； 第二組：X X1 1=0=0，X X2 2=1=1，X X3 3=0=0，X X4 4=1=1； 第三組：X X1 1=0=0，X X2 2=0=0，X X3 3=2=2，X X4 4=0=0；第第5章章 物流系統(tǒng)規(guī)劃物流系統(tǒng)規(guī)劃272. 2. 品種混裝問題品種混裝問題在實際的物流過程中，儲運倉庫(或貨運車站)要把客戶所需的貨物組成整車，運往各地。不同客戶的貨物，要分別在一站或多站卸貨。在裝貨、運輸和卸

17、貨過程中，為了減少裝卸、運輸過程中出現(xiàn)差錯，一般要按照品種、形狀、顏色、規(guī)格、到達地點，把貨物分為若干類，在裝車時分別進行處理。這就是品種混裝問題。q設(shè)裝車的貨物可以分為1類，2類，m類。共有N件(捆)待運貨物，其中1類貨物有N1件(捆)，它們的重量分別G11，G12，G1N1；2類貨物有N2件(捆)，它們的重量分別為G21，G22，G2N2；第s類貨物共有Ns件，它們的重量分別為Gs1，Gs2，GsNs；以此類推，可以看出：貨物總的件數(shù)： 其中，Ns：第s類貨物的件數(shù)； m：貨物的種類數(shù)； N：貨物的總件數(shù)； 設(shè)： 品種混裝問題要求同一貨車內(nèi)每類貨物至多裝入一件（捆），同一客戶的多件同類貨物

18、可記作一件（捆）。在這樣的假設(shè)條件下，可以把品種混裝問題的數(shù)學模型表示如下：msNNmss,.,2, 11件貨物不裝入類第第件貨物裝入類第第srsrXrs01該數(shù)學模型的目的是對合理進行分類后的貨物進行裝載，使實際載重量G的值最大。該數(shù)學模型屬于整數(shù)規(guī)劃的問題，可以用單純形法進行求解。mrNsrsrsmsrsmrNsrsrsrrGXGmrXtsXGG110111,.,2 , 11. .max其中m：貨物的類別數(shù)；Nr：第r類貨物的件數(shù)；Grs：第r類第s件貨物的重量；G0：貨車載重量的上限。 圖5-20表示8件貨物分為4類，在圖中同一列的方框表示同一類貨物，方框內(nèi)的數(shù)字(符號)表示貨物重量。

19、上述品種混裝問題就是在網(wǎng)絡(luò)中自右向左尋找一條路線，使路線所經(jīng)品種混裝問題就是在網(wǎng)絡(luò)中自右向左尋找一條路線，使路線所經(jīng)過的方框中的重量之和達到最大，但又不超過貨車的載重量的上限過的方框中的重量之和達到最大，但又不超過貨車的載重量的上限GoGo。v 這種問題可以用窮舉法求解，即比較各條路線的載重量從而求出不超過Go的最大裝載量的路線；v 也可以將四類貨物看作4個階段，將上述問題化為動態(tài)規(guī)劃問題求解。下面介紹動態(tài)規(guī)劃的解法。 例題10 貨車載重量上限Go50；第1類貨物2件，G11=20，G12=11；第2類貨物1件，G21=13；第3類貨物3件，G316，G3211，G338；第4類貨物2件，G4

20、119，G4217。19176118132011 計算過程見表5-3134，分成四個階段進行?？裳b重量實裝重量剩余容量第1階段的可裝容量W值對應(yīng)第2階段的剩余容量W-G 尋找最優(yōu)解的次序與計算順序相反，從第一階段計算表開始，直到第四階段。 要使裝載量達到最大，對應(yīng)的剩余余量應(yīng)當最小。要使裝載量達到最大，對應(yīng)的剩余余量應(yīng)當最小。 （1）在第一階段計算表中，余量W-G1的最小值為零，為最好的方案，此時，對應(yīng)的實際裝載量G1為20，可裝載容量W值為20。 （2）第一階段的可裝載容量W=20為第二階段的剩余裝載容量，即W-G2的值為20，從表中可以看出第二階段的剩余裝載容量為20的實際裝載方式有兩種，

21、分別是： G2=0 和 G2=13 對應(yīng)的可裝容量分別為W=20和33。 （3）第二階段的可裝容量W=20和33為第三階段的剩余裝載容量，查表可得： 對應(yīng)于剩余可裝載容量為20的實際裝載量為G3=11,可裝載容量為W=31。 對應(yīng)于剩余可裝載容量為33的實際裝載量為G3=0,可裝載容量為W=33。 （4）同理可得第四階段的G4為19和17。 最后的最優(yōu)解為：G1=20 G2=0 G3=11 G4=19 G1=20 G2=13 G3=0 G4=17每組方案的裝載量都是50，達到滿載，充分利用了貨車的裝載能力?？裳b重量實裝重量剩余容量第1階段的可裝容量W值對應(yīng)第2階段的剩余容量W-G第第5章章 物

22、流系統(tǒng)規(guī)劃物流系統(tǒng)規(guī)劃35三三. 物流服務(wù)系統(tǒng)中的配置問題物流服務(wù)系統(tǒng)中的配置問題q隨機服務(wù)系統(tǒng)v 物流服務(wù)系統(tǒng)由服務(wù)的機構(gòu)和顧客組成。v 物流服務(wù)系統(tǒng)是一個綜合服務(wù)系統(tǒng)，許多服務(wù)項目具有隨機性質(zhì)。如：裝卸系統(tǒng)、運輸系統(tǒng)。v 物流服務(wù)系統(tǒng)中的顧客（人、貨物等）到來的時間和服務(wù)時間隨不同的時機和條件而變化，這種變化具有隨機性質(zhì)，這類系統(tǒng)稱為隨機服務(wù)系統(tǒng)。v 隨機服務(wù)系統(tǒng)包含三個過程：顧客輸入、排隊、服務(wù)三個過程。v 排隊論是處理隨機服務(wù)系統(tǒng)的專門理論。q服務(wù)系統(tǒng)中的設(shè)備配置v 服務(wù)機構(gòu)越大，顧客越方便，但機構(gòu)過大，導(dǎo)致成本升高或浪費。v 服務(wù)機構(gòu)過小，便不能完全滿足顧客的需要，使服務(wù)質(zhì)量降低，導(dǎo)致信譽損失和顧客流失。v 合理配置服務(wù)系統(tǒng)，使他既能滿足顧客的需要，又能使系統(tǒng)的花費最為經(jīng)濟，是物流系統(tǒng)配置所關(guān)心的主要問題。q例題， (P110)，按某倉庫的統(tǒng)計數(shù)據(jù)表明，該倉庫必要的車輛數(shù)量有一定的分布規(guī)律，如表5-35和圖5-21所示。每臺車輛每天的費用如下：自備車輛使用費用：C1=500元；自備車輛閑置費用：C2=300元；租用車輛費用：C3=1000元。車輛(臺) 1010-1516-2021-2526-3031-3535-40頻率10%20%25%20%15%5%5%頻率累計10%30%55%75%90%95%100%表