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

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

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

xij表示第i個司機去完成第j項任務(wù)，其值為1或0。當其值為1時表示第i個司機被分配去完成第j項任務(wù)；其值為0時，表示第i個司機不被分配去完成第j項任務(wù)。32.任務(wù)分配問題的數(shù)學(xué)模型以運輸問題的n項任務(wù)由n個司機去3.任務(wù)分配問題數(shù)學(xué)模型的求解任務(wù)分配問題屬于整數(shù)規(guī)劃問題，其變量xij的取值為整數(shù)。（本例為0或1）。任務(wù)分配問題可以用一般的整數(shù)規(guī)劃求解方法進行求解。但是，整數(shù)規(guī)劃問題的求解也是非常困難的，到目前為止，還缺乏統(tǒng)一的求解方法。本書采用匈牙利法求解任務(wù)分配問題。43.任務(wù)分配問題數(shù)學(xué)模型的求解任務(wù)分配問題屬于整數(shù)規(guī)劃問題二.匈牙利法求解分配問題可以證明，對于分配問題，在其費用矩陣Cij中，各行、各列均減去一個常數(shù)，Cij改變以后的最優(yōu)解，仍為原問題的最優(yōu)解。利用這個性質(zhì)，通過對Cij的行、列進行加減常數(shù)的計算，把一些矩陣元素變?yōu)?，在Cij為0的元素上進行分配，就可得到原問題的最優(yōu)解。該方法應(yīng)用了匈牙利數(shù)學(xué)家Konig矩陣性質(zhì)定理，因此這種方法被稱為匈牙利法。5二.匈牙利法求解分配問題可以證明，對于分配問題，在其費用矩4其他規(guī)劃問題選址問題貨物配裝問題物流服務(wù)系統(tǒng)中的配置問題64其他規(guī)劃問題選址問題6一.選址問題簡介物流調(diào)運規(guī)劃問題，是一種有固定發(fā)點、固定收點和固定道路的運輸規(guī)劃問題。還有一類運輸問題，他的收貨點和發(fā)貨點是待定的，這就是選址問題。這類問題在物流系統(tǒng)規(guī)劃中經(jīng)常遇到。選址問題要考慮多種因素，本節(jié)只討論選址問題中的物流問題。分為兩個問題：單一地址選址方法；圖上作業(yè)法。7一.選址問題簡介71.單一地址選址方法單一選址問題：就是從多個候選地址中選取一個最優(yōu)地址。（1）問題描述假設(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表示。81.單一地址選址方法單一選址問題：就是從多個候選地址中選?。?）參數(shù)及變量說明設(shè)cij為供應(yīng)地Ai到候選廠址Dj的單位物資運輸成本；djk為候選廠址Dj到銷售地Bk的單位物資運輸成本；設(shè)：選址變量為x=(x1,x2,…,xs)，其中：xj=0或1，1表示在Dj點建廠，0表示不在Dj點建廠。9（2）參數(shù)及變量說明9（3）目標函數(shù)及約束條件10（3）目標函數(shù)及約束條件10單一選址問題是一種線性規(guī)劃問題,并且變量的取值為0或1，屬于整數(shù)規(guī)劃問題。單一地址的選址模型的求解方法比較簡單．從目標函數(shù)表達式的右邊可以看出：通過計算模型中括號內(nèi)的算式值，就能夠確定運輸成本最小的方案。當要選定的地址不是單一的，而是多個時，問題不再屬于線性規(guī)劃問題。（5）求解方法11單一選址問題是一種線性規(guī)劃問題,并且變量的取值為0或1，屬于2.圖上作業(yè)法

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

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

為了便于分析，用一個新的圖來代替原圖，新圖圈內(nèi)數(shù)字表示礦井編號，產(chǎn)量記在圈的旁邊，道路交叉點看作產(chǎn)量為零的礦井，把那些只有一條道路連接的礦井稱為端點。122.圖上作業(yè)法對于運輸路線不含回路的選址問題，可用圖上首先計算這些礦井的總產(chǎn)量，本例為27000噸。然后分析各端點，都沒有超過總產(chǎn)量的一半，因此把各端點的數(shù)量合并到前一站，即①和②的數(shù)量合并到③；把④的數(shù)量合并到⑤；把⑦的數(shù)量合并到⑥，如下圖所示。3561100090007000各端點都合并到前一站后，③和⑥變成了圖中的端點。對它們進行分析,其數(shù)量都不超過總產(chǎn)量的一半，所以他們也不是最佳點。再把它們合并到前一站，即把③和⑥的數(shù)量合并到⑤。則⑤的數(shù)量為27000，超過總量的一半，所以⑤是最佳點。結(jié)論：加工廠應(yīng)建在第5號礦井。13首先計算這些礦井的總產(chǎn)量，本例為27000噸。3561100二.貨物配裝貨物配裝的目的是在車輛載重量為額定值的情況下，合理進行貨物的安排，使車輛裝載貨物的價值最大（如：重量最大、運費最低等）。14二.貨物配裝貨物配裝的目的是在車輛載重量為額定值的情況1.裝貨問題的數(shù)學(xué)模型（1）問題描述

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

151.裝貨問題的數(shù)學(xué)模型（1）問題描述15（3）求解方法可以把裝入一件貨物作為一個階段，把裝貨問題看作動態(tài)規(guī)劃問題。一般情況下，動態(tài)規(guī)劃問題的求解過程是從最后一個階段開始由后向前進行的。由于裝入貨物的先后次序不影響裝貨問題的最優(yōu)解?？梢詮牡谝浑A段開始，由前向后逐步進行。（4）求解過程1）裝入第1種貨物X1件，其最大價值為其中：X1表示第1種貨物的裝載數(shù)量；其取值范圍：0<X1<[G/W1]，方括號表示取整；P1：第1種貨物的價值系數(shù)（重量、運費、價值等）；

f1(W)：第一種貨物的價值。16（3）求解方法其中：X1表示第1種貨物的裝載數(shù)量；其取值范圍2)裝入第2種貨物X2件，其最大價值為

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

其中：X3表示第3種貨物的裝載數(shù)量；其取值范圍：0<X3<[G/W3]；P3：第3種貨物的價值系數(shù)；：前兩種貨物的重量；：前兩種貨物的價值。172)裝入第2種貨物X2件，其最大價值為17……n)裝入第n種貨物Xn件，其最大價值為

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

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

當X2=1或0時，其他(第1種)貨物裝載量為3或0；（4）查第1階段計算表，1）當W＝3時，對應(yīng)X1=1；2）當W＝0時，對應(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=823第二步：尋找最優(yōu)方案。尋找最優(yōu)解方案的次序與計算順序相反，由載重量第3種貨物的件數(shù)第1、2種貨物的重量價值計算價值24載重量第3種貨物的件數(shù)第1、2種貨物的重量價值計算價值24載重量第2種貨物的件數(shù)第1種貨物的重量價值計算價值Max25載重量第2種貨物的件數(shù)第1種貨物的重量價值計算價值Max25前面的最優(yōu)方案是在第四階段取X4＝1時得出的方案。如果在第4階段計算表中取X4＝0，則其余種類的貨物裝載量W-W4X4=8；在第3階段計算表中，查W=8一欄，f3(w)=8對應(yīng)X3＝2，再仿照前面的方法，可以得到第3組最優(yōu)解：第三組：X1=0，X2=0，X3=2，X4=0；裝載量為：X3*2=2*4=8以上三組裝載方案，都最大限度地發(fā)揮了車輛的載重能力，都是最優(yōu)方案。26前面的最優(yōu)方案是在第四階段取X4＝1時得出的方案。262727最終的最優(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)方案。28282.品種混裝問題（1）品種混裝問題簡介在實際的物流過程中，儲運倉庫(或貨運車站)要把客戶所需的零擔(dān)貨物組成整車，運往各地。不同客戶的貨物，要分別在一站或多站卸貨。在裝貨、運輸和卸貨過程中，為了減少裝卸、運輸過程中出現(xiàn)差錯，一般要按照品種、形狀、顏色、規(guī)格、到達地點，把貨物分為若干類，在裝車時分別進行處理。這就是品種混裝問題。292.品種混裝問題（1）品種混裝問題簡介29（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ù)；30（2）品種混裝問題描述30（3）數(shù)學(xué)模型

品種混裝問題要求同一貨車內(nèi)每類貨物至多裝入一件，在此假設(shè)條件下，可以建立品種混裝問題的數(shù)學(xué)模型：設(shè)：其中m：貨物的類別數(shù)；Nr：第r類貨物的件數(shù)；Grs：第r類第s件貨物的重量；G0：貨車載重量的上限。31（3）數(shù)學(xué)模型其中31（4）求解方法品種混裝問題的數(shù)學(xué)模型屬于整數(shù)規(guī)劃問題，可以用單純形法進行求解動態(tài)規(guī)劃法圖5-20表示8件貨物分為4類的混裝網(wǎng)絡(luò)示意圖。在圖中同一列的方框表示同一類貨物，方框內(nèi)的數(shù)字(符號)表示貨物重量。上述品種混裝問題就是在網(wǎng)絡(luò)中自右向左尋找一條路線，使路線所經(jīng)過的方框中的重量之和達到最大，但又不超過貨車的載重量的上限Go。可以用窮舉法求解。如果將四類貨物看作4個階段，將上述問題化為動態(tài)規(guī)劃問題求解。32（4）求解方法32（5）求解實例例題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，分成四個階段進行。33（5）求解實例19176118132011計算過程見表可裝重量實裝重量剩余容量第1階段的可裝容量W值對應(yīng)第2階段的剩余容量W-G裝載情況計算表34可裝重量實裝重量剩余容量第1階段的可裝容量W值對應(yīng)第2階段的可裝重量實裝重量剩余容量第1階段的可裝容量W值對應(yīng)第2階段的剩余容量W-G最優(yōu)解的尋找過程35可裝重量實裝重量剩余容量第1階段的可裝容量W值對應(yīng)第2階段的尋找最優(yōu)解的次序與計算順序相反，從第一階段計算表開始，直到第四階段。

要使裝載量達到最大，對應(yīng)的剩余余量應(yīng)當最小。（1）在第一階段計算表中，余量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。

36尋找最優(yōu)解的次序與計算順序相反，從第一階段計算表開最后的最優(yōu)解為：G1=20G2=0G3=11G4=19G1=20G2=13G3=0G4=17每組方案的裝載量都是50，達到滿載，充分利用了貨車的裝載能力。37最后的最優(yōu)解為：G1=20G2=0G3=三.物流服務(wù)系統(tǒng)中的配置問題隨機服務(wù)系統(tǒng)物流服務(wù)系統(tǒng)由服務(wù)的機構(gòu)和顧客組成。物流服務(wù)系統(tǒng)是一個綜合服務(wù)系統(tǒng)，許多服務(wù)項目具有隨機性質(zhì)。如：裝卸系統(tǒng)、運輸系統(tǒng)。物流服務(wù)系統(tǒng)中的顧客（人、貨物等）到來的時間和服務(wù)時間隨不同的時機和條件而變化，這種變化具有隨機性質(zhì)，這類系統(tǒng)稱為隨機服務(wù)系統(tǒng)。隨機服務(wù)系統(tǒng)包含三個過程：顧客輸入、排隊、服務(wù)三個過程。排隊論是處理隨機服務(wù)系統(tǒng)的專門理論。服務(wù)系統(tǒng)中的設(shè)備配置服務(wù)機構(gòu)越大，顧客越方便，但機構(gòu)過大，導(dǎo)致成本升高或浪費。服務(wù)機構(gòu)過小，便不能完全滿足顧客的需要，使服務(wù)質(zhì)量降低，導(dǎo)致信譽損失和顧客流失。合理配置服務(wù)系統(tǒng)，使他既能滿足顧客的需要，又能使系統(tǒng)的花費最為經(jīng)濟，是物流系統(tǒng)配置所關(guān)心的主要問題。38三.物流服務(wù)系統(tǒng)中的配置問題隨機服務(wù)系統(tǒng)38本章重點物流調(diào)運規(guī)劃表上作業(yè)法確定產(chǎn)、銷地之間的供需聯(lián)系和數(shù)量最優(yōu)搭配圖上作業(yè)法進行運輸線路的選擇最短路徑與最大流量分配規(guī)劃選址問題貨物配裝39本章重點物流調(diào)運規(guī)劃393物流分配規(guī)劃任務(wù)分配問題的數(shù)學(xué)模型（重點）用匈牙利法求解分配問題（自學(xué)）403物流分配規(guī)劃任務(wù)分配問題的數(shù)學(xué)模型（重點）1一.任務(wù)分配問題1.簡介在物流系統(tǒng)中經(jīng)常面臨的一個問題：如何根據(jù)有限的資源(人力、物力、財力等)，進行工作任務(wù)分配，以達到降低成本或提高經(jīng)濟效益的目的。如：運輸任務(wù)的分配問題。有n條航線的運輸任務(wù)指派給n艘船去完成，不同的船完成不同的航線其運輸成本不同。要求每條船完成一條航線，并且一條航線只能由一條船去完成。如何分配任務(wù)，才能使總的費用最小？又如：有A、B、C、D四門課程，上課的老師可以從甲、乙、丙、丁四名老師中選擇，不同的老師上不同的課程，其費用是不同的，并且規(guī)定，每人只講一門課程，每門課程只需要一人講授。問：如何安排，才能使總的上課費用最低？這類問題是常見的任務(wù)分配問題，也叫指派問題，它的任務(wù)是如何進行合理的任務(wù)分配，使總的費用最小。41一.任務(wù)分配問題1.簡介22.任務(wù)分配問題的數(shù)學(xué)模型以運輸問題的n項任務(wù)由n個司機去完成的情況為例：有n個司機被分配完成n項運輸任務(wù)，不同的司機完成某一項任務(wù)的費用都不一樣。要求每個司機完成其中一項任務(wù)，每個任務(wù)只能由一名司機完成，如何分配任務(wù)，才能使總的費用最??？令：

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

xij表示第i個司機去完成第j項任務(wù)，其值為1或0。當其值為1時表示第i個司機被分配去完成第j項任務(wù)；其值為0時，表示第i個司機不被分配去完成第j項任務(wù)。422.任務(wù)分配問題的數(shù)學(xué)模型以運輸問題的n項任務(wù)由n個司機去3.任務(wù)分配問題數(shù)學(xué)模型的求解任務(wù)分配問題屬于整數(shù)規(guī)劃問題，其變量xij的取值為整數(shù)。（本例為0或1）。任務(wù)分配問題可以用一般的整數(shù)規(guī)劃求解方法進行求解。但是，整數(shù)規(guī)劃問題的求解也是非常困難的，到目前為止，還缺乏統(tǒng)一的求解方法。本書采用匈牙利法求解任務(wù)分配問題。433.任務(wù)分配問題數(shù)學(xué)模型的求解任務(wù)分配問題屬于整數(shù)規(guī)劃問題二.匈牙利法求解分配問題可以證明，對于分配問題，在其費用矩陣Cij中，各行、各列均減去一個常數(shù)，Cij改變以后的最優(yōu)解，仍為原問題的最優(yōu)解。利用這個性質(zhì)，通過對Cij的行、列進行加減常數(shù)的計算，把一些矩陣元素變?yōu)?，在Cij為0的元素上進行分配，就可得到原問題的最優(yōu)解。該方法應(yīng)用了匈牙利數(shù)學(xué)家Konig矩陣性質(zhì)定理，因此這種方法被稱為匈牙利法。44二.匈牙利法求解分配問題可以證明，對于分配問題，在其費用矩4其他規(guī)劃問題選址問題貨物配裝問題物流服務(wù)系統(tǒng)中的配置問題454其他規(guī)劃問題選址問題6一.選址問題簡介物流調(diào)運規(guī)劃問題，是一種有固定發(fā)點、固定收點和固定道路的運輸規(guī)劃問題。還有一類運輸問題，他的收貨點和發(fā)貨點是待定的，這就是選址問題。這類問題在物流系統(tǒng)規(guī)劃中經(jīng)常遇到。選址問題要考慮多種因素，本節(jié)只討論選址問題中的物流問題。分為兩個問題：單一地址選址方法；圖上作業(yè)法。46一.選址問題簡介71.單一地址選址方法單一選址問題：就是從多個候選地址中選取一個最優(yōu)地址。（1）問題描述假設(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表示。471.單一地址選址方法單一選址問題：就是從多個候選地址中選?。?）參數(shù)及變量說明設(shè)cij為供應(yīng)地Ai到候選廠址Dj的單位物資運輸成本；djk為候選廠址Dj到銷售地Bk的單位物資運輸成本；設(shè)：選址變量為x=(x1,x2,…,xs)，其中：xj=0或1，1表示在Dj點建廠，0表示不在Dj點建廠。48（2）參數(shù)及變量說明9（3）目標函數(shù)及約束條件49（3）目標函數(shù)及約束條件10單一選址問題是一種線性規(guī)劃問題,并且變量的取值為0或1，屬于整數(shù)規(guī)劃問題。單一地址的選址模型的求解方法比較簡單．從目標函數(shù)表達式的右邊可以看出：通過計算模型中括號內(nèi)的算式值，就能夠確定運輸成本最小的方案。當要選定的地址不是單一的，而是多個時，問題不再屬于線性規(guī)劃問題。（5）求解方法50單一選址問題是一種線性規(guī)劃問題,并且變量的取值為0或1，屬于2.圖上作業(yè)法

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

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

為了便于分析，用一個新的圖來代替原圖，新圖圈內(nèi)數(shù)字表示礦井編號，產(chǎn)量記在圈的旁邊，道路交叉點看作產(chǎn)量為零的礦井，把那些只有一條道路連接的礦井稱為端點。512.圖上作業(yè)法對于運輸路線不含回路的選址問題，可用圖上首先計算這些礦井的總產(chǎn)量，本例為27000噸。然后分析各端點，都沒有超過總產(chǎn)量的一半，因此把各端點的數(shù)量合并到前一站，即①和②的數(shù)量合并到③；把④的數(shù)量合并到⑤；把⑦的數(shù)量合并到⑥，如下圖所示。3561100090007000各端點都合并到前一站后，③和⑥變成了圖中的端點。對它們進行分析,其數(shù)量都不超過總產(chǎn)量的一半，所以他們也不是最佳點。再把它們合并到前一站，即把③和⑥的數(shù)量合并到⑤。則⑤的數(shù)量為27000，超過總量的一半，所以⑤是最佳點。結(jié)論：加工廠應(yīng)建在第5號礦井。52首先計算這些礦井的總產(chǎn)量，本例為27000噸。3561100二.貨物配裝貨物配裝的目的是在車輛載重量為額定值的情況下，合理進行貨物的安排，使車輛裝載貨物的價值最大（如：重量最大、運費最低等）。53二.貨物配裝貨物配裝的目的是在車輛載重量為額定值的情況1.裝貨問題的數(shù)學(xué)模型（1）問題描述

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

541.裝貨問題的數(shù)學(xué)模型（1）問題描述15（3）求解方法可以把裝入一件貨物作為一個階段，把裝貨問題看作動態(tài)規(guī)劃問題。一般情況下，動態(tài)規(guī)劃問題的求解過程是從最后一個階段開始由后向前進行的。由于裝入貨物的先后次序不影響裝貨問題的最優(yōu)解?？梢詮牡谝浑A段開始，由前向后逐步進行。（4）求解過程1）裝入第1種貨物X1件，其最大價值為其中：X1表示第1種貨物的裝載數(shù)量；其取值范圍：0<X1<[G/W1]，方括號表示取整；P1：第1種貨物的價值系數(shù)（重量、運費、價值等）；

f1(W)：第一種貨物的價值。55（3）求解方法其中：X1表示第1種貨物的裝載數(shù)量；其取值范圍2)裝入第2種貨物X2件，其最大價值為

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

其中：X3表示第3種貨物的裝載數(shù)量；其取值范圍：0<X3<[G/W3]；P3：第3種貨物的價值系數(shù)；：前兩種貨物的重量；：前兩種貨物的價值。562)裝入第2種貨物X2件，其最大價值為17……n)裝入第n種貨物Xn件，其最大價值為

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

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

當X2=1或0時，其他(第1種)貨物裝載量為3或0；（4）查第1階段計算表，1）當W＝3時，對應(yīng)X1=1；2）當W＝0時，對應(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=862第二步：尋找最優(yōu)方案。尋找最優(yōu)解方案的次序與計算順序相反，由載重量第3種貨物的件數(shù)第1、2種貨物的重量價值計算價值63載重量第3種貨物的件數(shù)第1、2種貨物的重量價值計算價值24載重量第2種貨物的件數(shù)第1種貨物的重量價值計算價值Max64載重量第2種貨物的件數(shù)第1種貨物的重量價值計算價值Max25前面的最優(yōu)方案是在第四階段取X4＝1時得出的方案。如果在第4階段計算表中取X4＝0，則其余種類的貨物裝載量W-W4X4=8；在第3階段計算表中，查W=8一欄，f3(w)=8對應(yīng)X3＝2，再仿照前面的方法，可以得到第3組最優(yōu)解：第三組：X1=0，X2=0，X3=2，X4=0；裝載量為：X3*2=2*4=8以上三組裝載方案，都最大限度地發(fā)揮了車輛的載重能力，都是最優(yōu)方案。65前面的最優(yōu)方案是在第四階段取X4＝1時得出的方案。266627最終的最優(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)方案。67282.品種混裝問題（1）品種混裝問題簡介在實際的物流過程中，儲運倉庫(或貨運車站)要把客戶所需的零擔(dān)貨物組成整車，運往各地。不同客戶的貨物，要分別在一站或多站卸貨。在裝貨、運輸和卸貨過程中，為了減少裝卸、運輸過程中出現(xiàn)差錯，一般要按照品種、形狀、顏色、規(guī)格、到達地點，把貨物分為若干類，在裝車時分別進行處理。這就是品種混裝問題。682.品種混裝問題（1）品種混裝問題簡介29（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ù)；69（2）品種混裝問題描述30（3）數(shù)學(xué)模型

品種混裝問題要求同一貨車內(nèi)每類貨物至多裝入一件，在此假設(shè)條件下，可以建立品種混裝問題的數(shù)學(xué)模型：設(shè)：其中m：貨物的類別數(shù)；Nr：第r類貨物的件數(shù)；Grs：第r類第s件貨物的重量；G0：貨車載重量的上限。70（3）數(shù)學(xué)模型其中31（4）求解方法品種混裝問題的數(shù)學(xué)模型屬于整數(shù)規(guī)劃問題，可以用單純形法進行求解動態(tài)規(guī)劃法圖5-20表示8件貨物分為4類的混裝網(wǎng)絡(luò)示意圖。在圖中同一列的方框表示同一類貨物，方框內(nèi)的數(shù)字(符號)表示貨物重量。上述品種混裝問題就是在