物流系統(tǒng)規(guī)劃課件

5.3物流分配規(guī)劃任務分配問題的數學模型用匈牙利法求解分配問題15.3物流分配規(guī)劃任務分配問題的數學模型1一.任務分配問題的數學模型在物流系統(tǒng)中或其它的管理工作中，管理人員經常面臨的一個問題是：如何根據有限的資源(人力、物力、財力等)，進行工作任務分配，以達到降低成本或提高經濟效益的目的。如：有A、B、C、D四門課程，上課的老師可以從甲、乙、丙、丁四名老師中選擇，不同的老師上不同的課程，其費用是不同的，并且規(guī)定，每人只講一門課程，每門課程只需要一人講授。問：如何安排，才能使總的上課費用最低？又如：運輸任務的分配問題。有n條航線的運輸任務指派給n艘船去完成，不同的船完成不同的航線其運輸成本不同。要求每條船完成一條航線，并且一條航線只能由一條船去完成。如何分配任務，才能使總的費用最??？這類問題是常見的任務分配問題，也叫指派問題，它的任務是如何進行合理的任務分配，使總的費用最小。2一.任務分配問題的數學模型在物流系統(tǒng)中或其它的管理工作中，一.任務分配問題的數學模型以運輸問題的n項任務由n個司機去完成的情況為例，有n個司機被分配完成n項運輸任務，不同的司機完成任務某一項任務的費用都不一樣。要求每個司機完成其中一項任務，每個任務只能由一名司機完成，如何分配任務，才能使總的費用最小？

令：

cij表示第i個司機完成第j項任務的運輸成本（工作成本或工作時間等價值系數）；

xij表示第i個司機去完成第j項任務，其值為1或0。當其值為1時表示第i個司機被分配去完成第j項任務；其值為0時，表示第i個司機不被分配去完成第j項任務。3一.任務分配問題的數學模型以運輸問題的n項任務由n個司機去一.任務分配問題的數學模型任務分配問題屬于整數規(guī)劃問題，其變量xij的取值為整數，（本例為0或1）。任務分配問題可以用一般的整數規(guī)劃求解方法進行求解。但是，整數規(guī)劃問題的求解也是非常困難的，到目前為止，還缺乏統(tǒng)一的求解方法。本書采用匈牙利法求解任務分配問題。4一.任務分配問題的數學模型任務分配問題屬于整數規(guī)劃問題，其二.匈牙利法求解分配問題可以證明，對于分配問題，在其費用矩陣Cij中，各行、各列均減去一個常數，Cij改變以后的最優(yōu)解，仍為原問題的最優(yōu)解。利用這個性質，通過對Cij的行、列進行加減常數的計算，把一些矩陣元素變?yōu)?，在Cij為0的元素上進行分解，就可得到原問題的最優(yōu)解。該方法應用了匈牙利數學家Konig矩陣性質定理，因此這種方法被稱為匈牙利法。5二.匈牙利法求解分配問題可以證明，對于分配問題，在其費用矩5.4其他規(guī)劃問題選址問題貨物裝配問題物流服務系統(tǒng)中的配置問題65.4其他規(guī)劃問題選址問題6一.選址問題物流調運規(guī)劃問題，是一種有固定發(fā)點、固定收點和固定道路的運輸規(guī)劃問題。還有一類運輸問題，他的收貨點和發(fā)貨點是待定的，這就是選址問題。這類問題在物流系統(tǒng)規(guī)劃中經常遇到。選址問題要考慮多種因素，本節(jié)只討論選址問題中的物流問題。分為兩個問題：單一地址選址方法；圖上作業(yè)法。7一.選址問題物流調運規(guī)劃問題，是一種有固定發(fā)點、固定收點1.單一地址選址方法

建立一個新工廠（或倉庫），應合理選擇廠址（或庫址）。所謂選址問題，就是從多個候選廠址中選取一個最優(yōu)地址建廠，使物流費用達到最低。

問題描述：假設廠址候選地點有s個，分別用D1,D2,…,Ds表示；原材料、燃料、零配件的供應地有m個，分別用A1,A2,…,Am表示，其供應量分別用P1,P2,…,Pm表示；產品銷售地有n個，分別用B1,B2,…,Bn表示，其銷售量分別為Q1,Q2,…,Qn表示。81.單一地址選址方法建立一個新工廠（或倉庫），應合設cij為供應地Ai到候選廠址Dj的單位運輸成本；djk為候選廠址Dj到銷售地Bk的單位運輸成本；設選址變量為xj(j=1,2,…,s)，其中：xj=0或1，1表示在Dj點建廠，0表示不在Dj點建廠。設cij為供應地Ai到候選廠址Dj的單位運輸成本；9物流系統(tǒng)規(guī)劃課件10單一選址問題是一種線性規(guī)劃問題,并且變量的取值為0或1，屬于整數規(guī)劃問題。單一地址的選址模型的求解方法比較簡單．從目標函數表達式的右邊可以看出：通過計算模型中括號內的算式值，就能夠確定運輸成本最小的方案。當要選定的地址不是單一的，而是多個時，問題不再屬于線性規(guī)劃問題。單一選址問題是一種線性規(guī)劃問題,并且變量的取值為0或1，屬于112.圖上作業(yè)法

對于運輸路線不含回路的選址問題，可用圖上作業(yè)法求解。

下面以一個實際例子來說明圖上作業(yè)法的選址問題：例題8假定有六個礦井．產量分別為5000噸、6000噸、7000噸、2000噸、4000噸和3000噸，運輸路線如圖所示，這些礦石要經過加工后才能轉運到其他地方。這些礦井之間道路不含回路，欲選擇一個礦井，在此礦井上建立一個加工廠，使各礦井到工廠的運輸總費用最低。為了便于分析，用一個新的圖來代替原圖，新圖圈內數字表示礦井編號，產量記在圈的旁邊，道路交叉點看作產量為零的礦井，把那些只有一條道路連接的礦井稱為端點。122.圖上作業(yè)法對于運輸路線不含回路的選址問題，可用圖上首先計算這些礦井的總產量，本例為27000噸。然后分析各端點，都沒有超過總產量的一半，因此把各端點的數量合并到前一站，即①和②的數量合并到③；把④的數量合并到⑤；把⑦的數量合并到⑥，如下圖所示。3561100090007000各端點都合并到前一站后，③和⑥變成了圖中的端點。對它們進行分析．其數量都不超過總產量的一半，所以他們不是最佳點。再把它們合并到前一站，即把②和⑥的數量合并到⑤。則⑤的數量為27000，超過總量的一半，所以⑤是最佳點。結論：加工廠應建在第5號礦井。首先計算這些礦井的總產量，本例為27000噸。356110013二.貨物裝配

貨物配裝的目的是在車輛載重量為額定值的情況下，合理進行貨物的安排，使車輛裝載貨物的價值最大（如：重量最大、運費最低等）。14二.貨物裝配貨物配裝的目的是在車輛載重量為額定值的情況1.運用動態(tài)規(guī)劃解裝貨問題

設貨車的載重量上限為G，用于運送n種不同的貨物，貨物的重量分別為W1，W2，...，Wn，每一種貨物對應于一個價值系數，分別用P1，P2，...，Pn表示，它表示價值、運費或重量等。設Xk表示第k種貨物的裝入數量，貨物配裝問題的數學模型可以表示為：

151.運用動態(tài)規(guī)劃解裝貨問題設貨車的載重量上限為G，可以把裝入一件貨物作為一個階段，把裝貨問題看作動態(tài)規(guī)劃問題。一般情況下，動態(tài)規(guī)劃問題的求解過程是從最后一個階段開始由后向前進行的。由于裝入貨物的先后次序不影響裝貨問題的最優(yōu)解。所以我們的求解過程可以從第一階段開始，由前向后逐步進行。求解過程：（1）裝入第1種貨物X1件，其最大價值為其中：X1表示第1種貨物的裝載數量；其取值范圍：0<X1<[G/W1]，方括號表示取整；

P1：第1種貨物的價值系數（重量、運費、價值等）；

f1(W)：第一種貨物的價值?？梢园蜒b入一件貨物作為一個階段，把裝貨問題看作動態(tài)規(guī)劃問題。16(2)裝入第2種貨物X2件，其最大價值為

其中：X2表示第2種貨物的裝載數量；其取值范圍：0<X2<[G/W2]；

P2：第2種貨物的價值系數（重量、運費、價值等）；：第一種貨物的重量；：第一種貨物的價值。（3）裝入第3種貨物X3件，其最大價值為

其中：X3表示第3種貨物的裝載數量；其取值范圍：0<X3<[G/W3]；

P3：第3種貨物的價值系數；(2)裝入第2種貨物X2件，其最大價值為17……(n)裝入第n種貨物Xn件，其最大價值為

其中：Xn表示第n種貨物的裝載數量；其取值范圍：0<Xn<[G/Wn]；

Pn：第n種貨物的價值系數；……18例題9載重量為8t的載重汽車，運輸4種機電產品，產品重量分別為3噸、3噸、4噸、5噸，試問如何配裝才能充分利用貨車的運載能力?解：第一步，按照前面的公式，分成四個階段計算每一階段的價值。計算結果以表格表示如下：貨物裝配例題例題9載重量為8t的載重汽車，運輸4種機電產品，產品重量19載重量件數價值(重量)載重量第2種貨物的件數第1種貨物的重量價值計算價值Max載重量件數價值(重量)載重量第2種貨物的件數第1種貨物的重量20載重量第3種貨物的件數第1、2種貨物的重量價值計算價值Max載重量第3種貨物的件數第1、2種貨物的重量價值計算價值Max21第二步：尋找最優(yōu)方案。尋找最優(yōu)解方案的次序與計算順序相反，由第4階段向第1階段進行。從價值最大的裝載情況，逐步向前尋找最優(yōu)方案。（1）在第4階段計算表中，在載重量為8時，價值(本例為載重量)最大值f4(W)＝8，對應兩組數據(加*號的數據)：

1）X4＝0；2）X4＝1；先看X4＝1時的情況：當X4＝1時，即第4種貨物裝入1件(5噸)，表中第3列數字表示其余種類貨物的裝載量。當X4＝1時，其他3種貨物裝載量為3噸；（2）按相反方向，在第3階段計算表中，查W=3噸時，得到最大價值f3(W)＝3，對應的X3=0。查表中第3列數字，W=3，X3=0時，其余兩類貨物裝入重量3；（3）在第2階段計算表中，查W=3，f2(W)=3對應兩組數據：

1）X2=0；

2)X2=1；即

當X2=1或0時，其他(第1種)貨物裝載量為3或0；（4）查第1階段計算表，

1）當W＝3時，對應X1=1；

2）當W＝0時，對應X1=0；根據當前面的尋找過程，可以得到兩組最優(yōu)解：

第一組：X1=1，X2=0，X3=0，X4=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)方案。尋找最優(yōu)解方案的次序與計算順序相反，由22物流系統(tǒng)規(guī)劃課件23物流系統(tǒng)規(guī)劃課件24

前面的最優(yōu)方案是在第四階段取X4＝1時得出的方案。如果在第4階段計算表中取X4＝0，則其余種類的貨物裝載量W-W4X4=8；在第3階段計算表中，查W=8一欄，f3(w)=8對應X3＝2，再仿照前面的方法，可以得到第3組最優(yōu)解：第三組：X1=0，X2=0，X3=2，X4=0；裝載量為：X3*2=2*4=8以上三組裝載方案，都最大限度地發(fā)揮了車輛的載重能力，都是最優(yōu)方案。最終的最優(yōu)裝載方案為：

第一組：X1=1，X2=0，X3=0，X4=1；第二組：X1=0，X2=1，X3=0，X4=1；第三組：X1=0，X2=0，X3=2，X4=0；前面的最優(yōu)方案是在第四階段取X4＝1時得出的方案。25物流系統(tǒng)規(guī)劃課件262.品種混裝問題在實際的物流過程中，儲運倉庫(或貨運車站)要把客戶所需的貨物組成整車，運往各地。不同客戶的貨物，要分別在一站或多站卸貨。在裝貨、運輸和卸貨過程中，為了減少裝卸、運輸過程中出現(xiàn)差錯，一般要按照品種、形狀、顏色、規(guī)格、到達地點，把貨物分為若干類，在裝車時分別進行處理。這就是品種混裝問題。設裝車的貨物可以分為1類，2類，…，m類。共有N件(捆)待運貨物，其中1類貨物有N1件(捆)，它們的重量分別G11，G12，……，G1N1；2類貨物有N2件(捆)，它們的重量分別為G21，G22，……，G2N2；第s類貨物共有Ns件，它們的重量分別為Gs1，Gs2，……，GsNs；以此類推，可以看出：272.品種混裝問題在實際的物流過程中，儲運倉庫(或貨運車站)貨物總的件數：其中，Ns：第s類貨物的件數；

m：貨物的種類數；

N：貨物的總件數；設：品種混裝問題要求同一貨車內每類貨物至多裝入一件（捆），同一客戶的多件同類貨物可記作一件（捆）。在這樣的假設條件下，可以把品種混裝問題的數學模型表示如下：貨物總的件數：28該數學模型的目的是對合理進行分類后的貨物進行裝載，使實際載重量G的值最大。該數學模型屬于整數規(guī)劃的問題，可以用單純形法進行求解。其中m：貨物的類別數；Nr：第r類貨物的件數；Grs：第r類第s件貨物的重量；G0：貨車載重量的上限。該數學模型的目的是對合理進行分類后的貨物進行裝載，使實際載重29

圖5-20表示8件貨物分為4類，在圖中同一列的方框表示同一類貨物，方框內的數字(符號)表示貨物重量。上述品種混裝問題就是在網絡中自右向左尋找一條路線，使路線所經過的方框中的重量之和達到最大，但又不超過貨車的載重量的上限Go。這種問題可以用窮舉法求解，即比較各條路線的載重量從而求出不超過Go的最大裝載量的路線；也可以將四類貨物看作4個階段，將上述問題化為動態(tài)規(guī)劃問題求解。下面介紹動態(tài)規(guī)劃的解法。圖5-20表示8件貨物分為4類，在圖中同一列的方框表示30

例題10貨車載重量上限Go＝50；第1類貨物2件，G11=20，G12=11；第2類貨物1件，G21=13；第3類貨物3件，G31＝6，G32＝11，G33＝8；第4類貨物2件，G41＝19，G42＝17。19176118132011

計算過程見表5-31~34，分成四個階段進行。例題10貨車載重量上限Go＝50；第1類貨物2件，31可裝重量實裝重量剩余容量第1階段的可裝容量W值對應第2階段的剩余容量W-G可裝重量實裝重量剩余容量第1階段的可裝容量W值對應第2階段的32

尋找最優(yōu)解的次序與計算順序相反，從第一階段計算表開始，直到第四階段。要使裝載量達到最大，對應的剩余余量應當最小。（1）在第一階段計算表中，余量W-G1的最小值為零，為最好的方案，此時，對應的實際裝載量G1為20，可裝載容量W值為20。（2）第一階段的可裝載容量W=20為第二階段的剩余裝載容量，即W-G2的值為20，從表中可以看出第二階段的剩余裝載容量為20的實際裝載方式有兩種，分別是：

G2=0和G2=13

對應的可裝容量分別為W=20和33。（3）第二階段的可裝容量W=20和33為第三階段的剩余裝載容量，查表可得：對應于剩余可裝載容量為20的實際裝載量為G3=11,可裝載容量為W=31。對應于剩余可裝載容量為33的實際裝載量為G3=0,可裝載容量為W=33。（4）同理可得第四階段的G4為19和17。最后的最優(yōu)解為：G1=20G2=0G3=11G4=19G1=20G2=13G3=0G4=17每組方案的裝載量都是50，達到滿載，充分利用了貨車的裝載能力。尋找最優(yōu)解的次序與計算順序相反，從第一階段計算表開33可裝重量實裝重量剩余容量第1階段的可裝容量W值對應第2階段的剩余容量W-G可裝重量實裝重量剩余容量第1階段的可裝容量W值對應第2階段的34三.物流服務系統(tǒng)中的配置問題隨機服務系統(tǒng)物流服務系統(tǒng)由服務的機構和顧客組成。物流服務系統(tǒng)是一個綜合服務系統(tǒng)，許多服務項目具有隨機性質。如：裝卸系統(tǒng)、運輸系統(tǒng)。物流服務系統(tǒng)中的顧客（人、貨物等）到來的時間和服務時間隨不同的時機和條件而變化，這種變化具有隨機性質，這類系統(tǒng)稱為隨機服務系統(tǒng)。隨機服務系統(tǒng)包含三個過程：顧客輸入、排隊、服務三個過程。排隊論是處理隨機服務系統(tǒng)的專門理論。服務系統(tǒng)中的設備配置服務機構越大，顧客越方便，但機構過大，導致成本升高或浪費。服務機構過小，便不能完全滿足顧客的需要，使服務質量降低，導致信譽損失和顧客流失。合理配置服務系統(tǒng)，使他既能滿足顧客的需要，又能使系統(tǒng)的花費最為經濟，是物流系統(tǒng)配置所關心的主要問題。35三.物流服務系統(tǒng)中的配置問題隨機服務系統(tǒng)35例題，

(P110)，按某倉庫的統(tǒng)計數據表明，該倉庫必要的車輛數量有一定的分布規(guī)律，如表5-35和圖5-21所示。每臺車輛每天的費用如下：自備車