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

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

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

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

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

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

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

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

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

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

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

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

12、2當(dāng)W0時(shí)，對(duì)應(yīng)X1=0；根據(jù)當(dāng)前面的尋覓過程，可以得到兩組最優(yōu)解： 第一組：X1=1，X2=0，X3=0，X4=1； 第二組：X1=0，X2=1，X3=0，X4=1；這兩組最優(yōu)解的實(shí)踐載分量為： 第一組：X1 * 3 + X4 * 5 = 1*3+1*5 = 8 第二組：X2 * 3 + X4 * 5 = 1*3+1*5 = 8載分量第3種貨物的件數(shù)第1、2種貨物的分量?jī)r(jià)值計(jì)算價(jià)值載分量第2種貨物的件數(shù)第1種貨物的分量?jī)r(jià)值計(jì)算價(jià)值Max 前面的最優(yōu)方案是在第四階段取X41時(shí)得出的方案。 假設(shè)在第4階段計(jì)算表中取X40，那么其他種類的貨物裝載量W - W4X4=8； 在第3階段計(jì)算表中，查W=

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

14、的貨物，要分別在一站或多站卸貨。在裝貨、運(yùn)輸和卸貨過程中，為了減少裝卸、運(yùn)輸過程中出現(xiàn)過失，普通要按照種類、外形、顏色、規(guī)格、到達(dá)地點(diǎn)，把貨物分為假設(shè)干類，在裝車時(shí)分別進(jìn)展處置。這就是種類混裝問題。2種類混裝問題描畫設(shè)裝車的貨物可以分為1類，2類，m類。共有N件待運(yù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ī)劃問題，可以用單純形法進(jìn)展求解動(dòng)態(tài)規(guī)劃法 圖5-20表示8件貨物分為4類的混裝網(wǎng)絡(luò)表示圖。在圖中同一列的方框表示同一類貨物，方框內(nèi)的數(shù)字(符號(hào))表示貨物分量。 上述種類混裝問題就是在網(wǎng)絡(luò)中自右向左尋覓一條道路，使道路所經(jīng)過的方框中的分量之和到達(dá)最大，但又不超越貨車的載分量的上限Go。可以用窮舉法求解。假設(shè)將四類貨物看作4個(gè)階段，將上述問題化為動(dòng)態(tài)規(guī)劃問題求

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

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