第3-2章物流系統(tǒng)規(guī)劃(二)ppt課件

1、3 物流分配規(guī)劃義務(wù)分配問題的數(shù)學(xué)模型重點用匈牙利法求解分配問題自學(xué)一. 義務(wù)分配問題1.簡介 在物流系統(tǒng)中經(jīng)常面臨的一個問題：如何根據(jù)有限的資源(人力、物力、財力等)，進展任務(wù)義務(wù)分配，以到達降低本錢或提高經(jīng)濟效益的目的。如：運輸義務(wù)的分配問題。有n條航線的運輸義務(wù)指派給n艘船去完成，不同的船完成不同的航線其運輸本錢不同。要求每條船完成一條航線，并且一條航線只能由一條船去完成。如何分配義務(wù)，才干使總的費用最小？又如：有A、B、C、D四門課程，上課的教師可以從甲、乙、丙、丁四名教師中選擇，不同的教師上不同的課程，其費用是不同的，并且規(guī)定，每人只講一門課程，每門課程只需求一人講授。問：如何安排，

2、才干使總的上課費用最低？這類問題是常見的義務(wù)分配問題，也叫指派問題，它的義務(wù)是如何進展合理的義務(wù)分配，使總的費用最小。2. 義務(wù)分配問題的數(shù)學(xué)模型以運輸問題的n項義務(wù)由n個司機去完成的情況為例：有n個司機被分配完成n項運輸義務(wù)，不同的司機完成某一項義務(wù)的費用都不一樣。要求每個司機完成其中一項義務(wù)，每個義務(wù)只能由一名司機完成，如何分配義務(wù)，才干使總的費用最?。?令： cij表示第i個司機完成第j項義務(wù)的運輸本錢任務(wù)本錢或任務(wù)時間等價值系數(shù)； xij表示第i個司機去完成第j項義務(wù)，其值為1或0。當其值為1時表示第i個司機被分配去完成第j項義務(wù)；其值為0時，表示第i個司機不被分配去完成第j項義務(wù)。3

3、. 義務(wù)分配問題數(shù)學(xué)模型的求解義務(wù)分配問題屬于整數(shù)規(guī)劃問題，其變量xij的取值為整數(shù)。本例為0或1。義務(wù)分配問題可以用普通的整數(shù)規(guī)劃求解方法進展求解。但是，整數(shù)規(guī)劃問題的求解也是非常困難的，到目前為止，還缺乏一致的求解方法。本書采用匈牙利法求解義務(wù)分配問題。二. 匈牙利法求解分配問題可以證明，對于分配問題，在其費用矩陣Cij中，各行、各列均減去一個常數(shù)，Cij改動以后的最優(yōu)解，仍為原問題的最優(yōu)解。利用這個性質(zhì)，經(jīng)過對Cij的行、列進展加減常數(shù)的計算，把一些矩陣元素變?yōu)?，在Cij為0的元素上進展分配，就可得到原問題的最優(yōu)解。該方法運用了匈牙利數(shù)學(xué)家Konig矩陣性質(zhì)定理，因此這種方法被稱為匈牙

4、利法。4 其他規(guī)劃問題選址問題貨物配裝問題物流效力系統(tǒng)中的配置問題一. 選址問題簡介物流調(diào)運規(guī)劃問題，是一種有固定發(fā)點、固定收點和固定道路的運輸規(guī)劃問題。還有一類運輸問題，他的收貨點和發(fā)貨點是待定的，這就是選址問題。這類問題在物流系統(tǒng)規(guī)劃中經(jīng)常遇到。選址問題要思索多種要素，本節(jié)只討論選址問題中的物流問題。分為兩個問題：單一地址選址方法；圖上作業(yè)法。1. 單一地址選址方法單一選址問題：就是從多個候選地址中選取一個最優(yōu)地址。1問題描畫 假設(shè)地址候選地點有s個，分別用D1,D2,Ds表示；原資料、燃料、零配件的供應(yīng)地有m個，分別用A1,A2,Am表示，其供應(yīng)量分別用P1,P2,Pm表示；產(chǎn)品銷售地有

5、n個，分別用B1,B2,Bn表示，其銷售量分別為Q1,Q2,Qn表示。2參數(shù)及變量闡明設(shè)cij為供應(yīng)地Ai到候選廠址Dj的單位物資運輸本錢；djk為候選廠址Dj到銷售地Bk的單位物資運輸本錢；設(shè)：選址變量為x=(x1,x2,xs)，其中：xj=0或1，1表示在Dj點建廠，0表示不在Dj點建廠。3目的函數(shù)及約束條件單一選址問題是一種線性規(guī)劃問題,并且變量的取值為0或1，屬于整數(shù)規(guī)劃問題。單一地址的選址模型的求解方法比較簡單從目的函數(shù)表達式的右邊可以看出：經(jīng)過計算模型中括號內(nèi)的算式值，就可以確定運輸本錢最小的方案。當要選定的地址不是單一的，而是多個時，問題不再屬于線性規(guī)劃問題。5求解方法2. 圖上

6、作業(yè)法 對于運輸?shù)缆凡缓芈返倪x址問題，可用圖上作業(yè)法求解。 例題8 假定有六個礦井產(chǎn)量分別為5000噸、6000噸、7000噸、2000噸、4000噸和3000噸，運輸?shù)缆啡缦聢D，這些礦石要經(jīng)過加工后才干轉(zhuǎn)運到其他地方。這些礦井之間道路不含回路，欲選擇一個礦井，在此礦井上建立一個加工廠，使各礦井到工廠的運輸總費用最低。 為了便于分析，用一個新的圖來替代原圖，新圖圈內(nèi)數(shù)字表示礦井編號，產(chǎn)量記在圈的旁邊，道路交叉點看作產(chǎn)量為零的礦井，把那些只需一條道路銜接的礦井稱為端點。首先計算這些礦井的總產(chǎn)量，本例為27000噸。然后分析各端點，都沒有超越總產(chǎn)量的一半，因此把各端點的數(shù)量合并到前一站，即 和

7、的數(shù)量合并到；把的數(shù)量合并到 ；把 的數(shù)量合并到 ，如以下圖所示。3561100090007000各端點都合并到前一站后， 和變成了圖中的端點。對它們進展分析,其數(shù)量都不超越總產(chǎn)量的一半，所以他們也不是最正確點。再把它們合并到前一站，即把和的數(shù)量合并到 。那么 的數(shù)量為27000，超越總量的一半，所以是最正確點。結(jié)論：加工廠應(yīng)建在第5號礦井。 二. 貨物配裝 貨物配裝的目的是在車輛載分量為額定值的情況下，合理進展貨物的安排，使車輛裝載貨物的價值最大如：分量最大、運費最低等。1.裝貨問題的數(shù)學(xué)模型1問題描畫 設(shè)貨車的載分量上限為G，用于運送n種不同的貨物，貨物的分量分別為W1，W2，.，Wn，每

8、一種貨物對應(yīng)于一個價值系數(shù)，分別用P1，P2，.，Pn表示，它表示價值、運費或分量等。2數(shù)學(xué)模型 設(shè)Xk表示第k種貨物的裝入數(shù)量，貨物配裝問題的數(shù)學(xué)模型可以表示為： 3求解方法可以把裝入一件貨物作為一個階段，把裝貨問題看作動態(tài)規(guī)劃問題。普通情況下，動態(tài)規(guī)劃問題的求解過程是從最后一個階段開場由后向前進展的。由于裝入貨物的先后次序不影響裝貨問題的最優(yōu)解?？梢詮牡谝浑A段開場，由前向后逐漸進展。4求解過程1裝入第1種貨物X1件，其最大價值為 其中：X1表示第1種貨物的裝載數(shù)量；其取值范圍：0X1 G/W1 ，方括號表示取整； P1：第1種貨物的價值系數(shù)分量、運費、價值等； f1(W)：第一種貨物的價值

9、。 2)裝入第2種貨物X2件，其最大價值為 其中：X2表示第2種貨物的裝載數(shù)量；其取值范圍：0X2 G/W2 ； P2：第2種貨物的價值系數(shù)分量、運費、價值等； ：第一種貨物的分量； ：第一種貨物的價值。3裝入第3種貨物X3件，其最大價值為 其中：X3表示第3種貨物的裝載數(shù)量；其取值范圍：0X3 G/W3； P3：第3種貨物的價值系數(shù)； ： 前兩種貨物的分量； ：前兩種貨物的價值。n) 裝入第n種貨物Xn件，其最大價值為 其中：Xn表示第n種貨物的裝載數(shù)量； 其取值范圍：0Xn G/Wn ； Pn：第n種貨物的價值系數(shù)； 例題9 載分量為8t的載重汽車，運輸4種機電產(chǎn)品，產(chǎn)品分量分別為3噸、3

10、噸、4噸、5噸，試問如何配裝才干充分利用貨車的運載才干?解： 第一步，按照前面的公式，分成四個階段計算每一階段的價值。 計算結(jié)果以表格表示如下：5貨物配裝例題求解載分量件數(shù)價值(分量)載分量第2種貨物的件數(shù)第1種貨物的分量價值計算價值Max載分量第3種貨物的件數(shù)第1、2種貨物的分量價值計算價值Max第二步：尋覓最優(yōu)方案。尋覓最優(yōu)解方案的次序與計算順序相反，由第4階段向第1階段進展。選擇最后一個階段價值最大的裝載情況，逐漸向前尋覓最優(yōu)方案。第二步：尋覓最優(yōu)方案。尋覓最優(yōu)解方案的次序與計算順序相反，由第4階段向第1階段進展。從價值最大的裝載情況，逐漸向前尋覓最優(yōu)方案。1在第4階段計算表中，在載分量

11、為8時，價值(本例為載分量)最大值f4(W)8，對應(yīng)兩組數(shù)據(jù)(加*號的數(shù)據(jù))： 1X40； 2X41； 先看X41時的情況： 當X41時，即第4種貨物裝入1件(5噸)，表中第3列數(shù)字表示其他種類貨物的裝載量。當X41時，其他3種貨物裝載量為3噸；2按相反方向，在第3階段計算表中，查W=3噸時，得到最大價值f3(W)3，對應(yīng)的X3=0。查表中第3列數(shù)字，W=3，X3=0時，其他兩類貨物裝入分量3；3在第2階段計算表中，查W=3，f2(W)=3對應(yīng)兩組數(shù)據(jù)： 1X2=0； 2) X2=1； 即 當X2 =1或0時，其他(第1種)貨物裝載量為3或0；4查第1階段計算表， 1當W3時，對應(yīng)X1=1；

12、2當W0時，對應(yīng)X1=0；根據(jù)當前面的尋覓過程，可以得到兩組最優(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載分量第3種貨物的件數(shù)第1、2種貨物的分量價值計算價值載分量第2種貨物的件數(shù)第1種貨物的分量價值計算價值Max 前面的最優(yōu)方案是在第四階段取X41時得出的方案。 假設(shè)在第4階段計算表中取X40，那么其他種類的貨物裝載量W - W4X4=8； 在第3階段計算表中，查W=

13、8一欄，f3(w)=8對應(yīng)X32，再仿照前面的方法，可以得到第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；以上三組裝載方案，都最大限制地發(fā)揚了車輛的載重才干，都是最優(yōu)方案。2. 種類混裝問題1種類混裝問題簡介在實踐的物流過程中，儲運倉庫(或貨運車站)要把客戶所需的零擔貨物組成整車，運往各地。不同客戶

14、的貨物，要分別在一站或多站卸貨。在裝貨、運輸和卸貨過程中，為了減少裝卸、運輸過程中出現(xiàn)過失，普通要按照種類、外形、顏色、規(guī)格、到達地點，把貨物分為假設(shè)干類，在裝車時分別進展處置。這就是種類混裝問題。2種類混裝問題描畫設(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ù)； 3數(shù)學(xué)模型 種類混

15、裝問題要求同一貨車內(nèi)每類貨物至多裝入一件，在此假設(shè)條件下，可以建立種類混裝問題的數(shù)學(xué)模型： 設(shè)：其中m：貨物的類別數(shù)；Nr：第r類貨物的件數(shù)；Grs：第r類第s件貨物的分量；G0：貨車載分量的上限。 4求解方法種類混裝問題的數(shù)學(xué)模型屬于整數(shù)規(guī)劃問題，可以用單純形法進展求解動態(tài)規(guī)劃法 圖5-20表示8件貨物分為4類的混裝網(wǎng)絡(luò)表示圖。在圖中同一列的方框表示同一類貨物，方框內(nèi)的數(shù)字(符號)表示貨物分量。 上述種類混裝問題就是在網(wǎng)絡(luò)中自右向左尋覓一條道路，使道路所經(jīng)過的方框中的分量之和到達最大，但又不超越貨車的載分量的上限Go?？梢杂酶F舉法求解。假設(shè)將四類貨物看作4個階段，將上述問題化為動態(tài)規(guī)劃問題求

16、解。5求解實例 例題10 貨車載分量上限Go50；第1類貨物2件，G11=20，G12=11；第2類貨物1件，G21=13；第3類貨物3件，G316，G3211，G338；第4類貨物2件，G4119，G4217。19176118132011 計算過程見表5-3134，分成四個階段進展?？裳b分量實裝分量剩余容量第1階段的可裝容量W值對應(yīng)第2階段的剩余容量W-G裝載情況計算表可裝分量實裝分量剩余容量第1階段的可裝容量W值對應(yīng)第2階段的剩余容量W-G最優(yōu)解的尋覓過程 尋覓最優(yōu)解的次序與計算順序相反，從第一階段計算表開場，直到第四階段。 要使裝載量到達最大，對應(yīng)的剩余余量該當最小。 1在第一階段計算表

17、中，余量W-G1的最小值為零，為最好的方案，此時，對應(yīng)的實踐裝載量G1為20，可裝載容量W值為20。 2第一階段的可裝載容量W=20為第二階段的剩余裝載容量，即W-G2的值為20，從表中可以看出第二階段的剩余裝載容量為20的實踐裝載方式有兩種，分別是： 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，到達滿載，充分利用了貨車的裝載才干。三. 物流效力系統(tǒng)中的配置問題隨機效力系統(tǒng)物流效力系統(tǒng)由效力的機構(gòu)和顧客組成。物流效力系統(tǒng)是一個綜合效力系統(tǒng)，許多效力工程具有隨機性質(zhì)。如：裝卸系統(tǒng)、運輸系統(tǒng)。物流效力系統(tǒng)中的顧客人、貨物等到來的時間和效力時間隨不同的