物流分配規(guī)劃課件

3物流分配規(guī)劃任務(wù)分配問題數(shù)學(xué)模型（重點(diǎn)）用匈牙利法求解分配問題（自學(xué)）1物流分配規(guī)劃課件第1頁一.任務(wù)分配問題1.介紹在物流系統(tǒng)中經(jīng)常面臨一個(gè)問題：怎樣依據(jù)有限資源(人力、物力、財(cái)力等)，進(jìn)行工作任務(wù)分配，以到達(dá)降低成本或提升經(jīng)濟(jì)效益目標(biāo)。如：運(yùn)輸任務(wù)分配問題。有n條航線運(yùn)輸任務(wù)指派給n艘船去完成，不一樣船完成不一樣航線其運(yùn)輸成本不一樣。要求每條船完成一條航線，而且一條航線只能由一條船去完成。怎樣分配任務(wù)，才能使總費(fèi)用最小？又如：有A、B、C、D四門課程，上課老師能夠從甲、乙、丙、丁四名老師中選擇，不一樣老師上不一樣課程，其費(fèi)用是不一樣，而且要求，每人只講一門課程，每門課程只需要一人講授。問：怎樣安排，才能使總上課費(fèi)用最低？這類問題是常見任務(wù)分配問題，也叫指派問題，它任務(wù)是怎樣進(jìn)行合理任務(wù)分配，使總費(fèi)用最小。2物流分配規(guī)劃課件第2頁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)用最?。苛睿?/p>

cij表示第i個(gè)司機(jī)完成第j項(xiàng)任務(wù)運(yùn)輸成本（工作成本或工作時(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物流分配規(guī)劃課件第3頁3.任務(wù)分配問題數(shù)學(xué)模型求解任務(wù)分配問題屬于整數(shù)規(guī)劃問題，其變量xij取值為整數(shù)。（本例為0或1）。任務(wù)分配問題能夠用普通整數(shù)規(guī)劃求解方法進(jìn)行求解。不過，整數(shù)規(guī)劃問題求解也是非常困難，到當(dāng)前為止，還缺乏統(tǒng)一求解方法。本書采取匈牙利法求解任務(wù)分配問題。4物流分配規(guī)劃課件第4頁二.匈牙利法求解分配問題能夠證實(shí)，對(duì)于分配問題，在其費(fèi)用矩陣Cij中，各行、各列均減去一個(gè)常數(shù)，Cij改變以后最優(yōu)解，仍為原問題最優(yōu)解。利用這個(gè)性質(zhì)，經(jīng)過對(duì)Cij行、列進(jìn)行加減常數(shù)計(jì)算，把一些矩陣元素變?yōu)?，在Cij為0元素上進(jìn)行分配，就可得到原問題最優(yōu)解。該方法應(yīng)用了匈牙利數(shù)學(xué)家Konig矩陣性質(zhì)定理，所以這種方法被稱為匈牙利法。5物流分配規(guī)劃課件第5頁4其它規(guī)劃問題選址問題貨物配裝問題物流服務(wù)系統(tǒng)中配置問題6物流分配規(guī)劃課件第6頁一.選址問題介紹物流調(diào)運(yùn)規(guī)劃問題，是一個(gè)有固定發(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è)法。7物流分配規(guī)劃課件第7頁1.單一地址選址方法單一選址問題：就是從多個(gè)候選地址中選取一個(gè)最優(yōu)地址。（1）問題描述假設(shè)地址候選地點(diǎn)有s個(gè)，分別用D1,D2,…,Ds表示；原材料、燃料、零配件供給地有m個(gè)，分別用A1,A2,…,Am表示，其供給量分別用P1,P2,…,Pm表示；產(chǎn)品銷售地有n個(gè)，分別用B1,B2,…,Bn表示，其銷售量分別為Q1,Q2,…,Qn表示。8物流分配規(guī)劃課件第8頁（2）參數(shù)及變量說明設(shè)cij為供給地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)建廠。9物流分配規(guī)劃課件第9頁（3）目標(biāo)函數(shù)及約束條件10物流分配規(guī)劃課件第10頁單一選址問題是一個(gè)線性規(guī)劃問題,而且變量取值為0或1，屬于整數(shù)規(guī)劃問題。單一地址選址模型求解方法比較簡(jiǎn)單．從目標(biāo)函數(shù)表示式右邊能夠看出：經(jīng)過計(jì)算模型中括號(hào)內(nèi)算式值，就能夠確定運(yùn)輸成本最小方案。當(dāng)要選定地址不是單一，而是多個(gè)時(shí)，問題不再屬于線性規(guī)劃問題。（5）求解方法11物流分配規(guī)劃課件第11頁2.圖上作業(yè)法

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

例題8假定有六個(gè)礦井．產(chǎn)量分別為5000噸、6000噸、7000噸、噸、4000噸和3000噸，運(yùn)輸路線如圖所表示，這些礦石要經(jīng)過加工后才能轉(zhuǎn)運(yùn)到其它地方。這些礦井之間道路不含回路，欲選擇一個(gè)礦井，在此礦井上建立一個(gè)加工廠，使各礦井到工廠運(yùn)輸總費(fèi)用最低。

為了便于分析，用一個(gè)新圖來代替原圖，新圖圈內(nèi)數(shù)字表示礦井編號(hào)，產(chǎn)量記在圈旁邊，道路交叉點(diǎn)看作產(chǎn)量為零礦井，把那些只有一條道路連接礦井稱為端點(diǎn)。12物流分配規(guī)劃課件第12頁首先計(jì)算這些礦井總產(chǎn)量，本例為27000噸。然后分析各端點(diǎn)，都沒有超出總產(chǎn)量二分之一，所以把各端點(diǎn)數(shù)量合并到前一站，即①和②數(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)礦井。13物流分配規(guī)劃課件第13頁二.貨物配裝貨物配裝目標(biāo)是在車輛載重量為額定值情況下，合理進(jìn)行貨物安排，使車輛裝載貨物價(jià)值最大（如：重量最大、運(yùn)費(fèi)最低等）。14物流分配規(guī)劃課件第14頁1.裝貨問題數(shù)學(xué)模型（1）問題描述

設(shè)貨車載重量上限為G，用于運(yùn)輸n種不一樣貨物，貨物重量分別為W1，W2，...，Wn，每一個(gè)貨物對(duì)應(yīng)于一個(gè)價(jià)值系數(shù)，分別用P1，P2，...，Pn表示，它表示價(jià)值、運(yùn)費(fèi)或重量等。（2）數(shù)學(xué)模型設(shè)Xk表示第k種貨物裝入數(shù)量，貨物配裝問題數(shù)學(xué)模型能夠表示為：

15物流分配規(guī)劃課件第15頁（3）求解方法能夠把裝入一件貨物作為一個(gè)階段，把裝貨問題看作動(dòng)態(tài)規(guī)劃問題。普通情況下，動(dòng)態(tài)規(guī)劃問題求解過程是從最終一個(gè)階段開始由后向前進(jìn)行。因?yàn)檠b入貨物先后次序不影響裝貨問題最優(yōu)解。能夠從第一階段開始，由前向后逐步進(jìn)行。（4）求解過程1）裝入第1種貨物X1件，其最大價(jià)值為其中：X1表示第1種貨物裝載數(shù)量；其取值范圍：0<X1<[G/W1]，方括號(hào)表示取整；P1：第1種貨物價(jià)值系數(shù)（重量、運(yùn)費(fèi)、價(jià)值等）；

f1(W)：第一個(gè)貨物價(jià)值。16物流分配規(guī)劃課件第16頁2)裝入第2種貨物X2件，其最大價(jià)值為

其中：X2表示第2種貨物裝載數(shù)量；其取值范圍：0<X2<[G/W2]；P2：第2種貨物價(jià)值系數(shù)（重量、運(yùn)費(fèi)、價(jià)值等）；：第一個(gè)貨物重量；：第一個(gè)貨物價(jià)值。3）裝入第3種貨物X3件，其最大價(jià)值為

其中：X3表示第3種貨物裝載數(shù)量；其取值范圍：0<X3<[G/W3]；P3：第3種貨物價(jià)值系數(shù)；：前兩種貨物重量；：前兩種貨物價(jià)值。17物流分配規(guī)劃課件第17頁……n)裝入第n種貨物Xn件，其最大價(jià)值為

其中：Xn表示第n種貨物裝載數(shù)量；其取值范圍：0<Xn<[G/Wn]；Pn：第n種貨物價(jià)值系數(shù)；18物流分配規(guī)劃課件第18頁例題9載重量為8t載重汽車，運(yùn)輸4種機(jī)電產(chǎn)品，產(chǎn)品重量分別為3噸、3噸、4噸、5噸，試問怎樣配裝才能充分利用貨車運(yùn)載能力?解：第一步，按照前面公式，分成四個(gè)階段計(jì)算每一階段價(jià)值。計(jì)算結(jié)果以表格表示以下：（5）貨物配裝例題求解19物流分配規(guī)劃課件第19頁載重量件數(shù)價(jià)值(重量)載重量第2種貨物件數(shù)第1種貨物重量價(jià)值計(jì)算價(jià)值Max20物流分配規(guī)劃課件第20頁載重量第3種貨物件數(shù)第1、2種貨物重量價(jià)值計(jì)算價(jià)值Max21物流分配規(guī)劃課件第21頁第二步：尋找最優(yōu)方案。尋找最優(yōu)解方案次序與計(jì)算次序相反，由第4階段向第1階段進(jìn)行。選擇最終一個(gè)階段價(jià)值最大裝載情況，逐步向前尋找最優(yōu)方案。22物流分配規(guī)劃課件第22頁第二步：尋找最優(yōu)方案。尋找最優(yōu)解方案次序與計(jì)算次序相反，由第4階段向第1階段進(jìn)行。從價(jià)值最大裝載情況，逐步向前尋找最優(yōu)方案。（1）在第4階段計(jì)算表中，在載重量為8時(shí)，價(jià)值(本例為載重量)最大值f4(W)＝8，對(duì)應(yīng)兩組數(shù)據(jù)(加*號(hào)數(shù)據(jù))：

1）X4＝0；2）X4＝1；先看X4＝1時(shí)情況：當(dāng)X4＝1時(shí)，即第4種貨物裝入1件(5噸)，表中第3列數(shù)字表示其余種類貨物裝載量。當(dāng)X4＝1時(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ù)：1）X2=0；2)X2=1；即

當(dāng)X2=1或0時(shí)，其它(第1種)貨物裝載量為3或0；（4）查第1階段計(jì)算表，1）當(dāng)W＝3時(shí)，對(duì)應(yīng)X1=1；2）當(dāng)W＝0時(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=823物流分配規(guī)劃課件第23頁載重量第3種貨物件數(shù)第1、2種貨物重量價(jià)值計(jì)算價(jià)值24物流分配規(guī)劃課件第24頁載重量第2種貨物件數(shù)第1種貨物重量價(jià)值計(jì)算價(jià)值Max25物流分配規(guī)劃課件第25頁前面最優(yōu)方案是在第四階段取X4＝1時(shí)得出方案。假如在第4階段計(jì)算表中取X4＝0，則其余種類貨物裝載量W-W4X4=8；在第3階段計(jì)算表中，查W=8一欄，f3(w)=8對(duì)應(yīng)X3＝2，再仿照前面方法，能夠得到第3組最優(yōu)解：第三組：X1=0，X2=0，X3=2，X4=0；裝載量為：X3*2=2*4=8以上三組裝載方案，都最大程度地發(fā)揮了車輛載重能力，都是最優(yōu)方案。26物流分配規(guī)劃課件第26頁27物流分配規(guī)劃課件第27頁最終最優(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)方案。28物流分配規(guī)劃課件第28頁2.品種混裝問題（1）品種混裝問題介紹在實(shí)際物流過程中，儲(chǔ)運(yùn)倉庫(或貨運(yùn)車站)要把客戶所需零擔(dān)貨物組成整車，運(yùn)往各地。不一樣客戶貨物，要分別在一站或多站卸貨。在裝貨、運(yùn)輸和卸貨過程中，為了降低裝卸、運(yùn)輸過程中出現(xiàn)差錯(cuò)，普通要按照品種、形狀、顏色、規(guī)格、抵達(dá)地點(diǎn)，把貨物分為若干類，在裝車時(shí)分別進(jìn)行處理。這就是品種混裝問題。29物流分配規(guī)劃課件第29頁（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ù)；30物流分配規(guī)劃課件第30頁（3）數(shù)學(xué)模型

品種混裝問題要求同一貨車內(nèi)每類貨物至多裝入一件，在此假設(shè)條件下，能夠建立品種混裝問題數(shù)學(xué)模型：設(shè)：其中m：貨物類別數(shù)；Nr：第r類貨物件數(shù)；Grs：第r類第s件貨物重量；G0：貨車載重量上限。31物流分配規(guī)劃課件第31頁（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。能夠用窮舉法求解。假如將四類貨物看作4個(gè)階段，將上述問題化為動(dòng)態(tài)規(guī)劃問題求解。32物流分配規(guī)劃課件第32頁（5）求解實(shí)例例題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計(jì)算過程見表5-31~34，分成四個(gè)階段進(jìn)行。33物流分配規(guī)劃課件第33頁可裝重量實(shí)裝重量剩下容量第1階段可裝容量W值對(duì)應(yīng)第2階段剩下容量W-G裝載情況計(jì)算表34物流分配規(guī)劃課件第34頁可裝重量實(shí)裝重量剩下容量第1階段可裝容量W值對(duì)應(yīng)第2階段剩下容量W-G最優(yōu)解尋找過程35物流分配規(guī)劃課件第35頁尋找最優(yōu)解次序與計(jì)算次序相反，從第一階段計(jì)算表開始，直到第四階段。

要使裝載量到達(dá)最大，對(duì)應(yīng)剩下余量應(yīng)該最小。（1）在第一階段計(jì)算表中，余量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和3