貨物分配問(wèn)題.ppt

《貨物分配問(wèn)題.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、貨物裝配問(wèn)題貨物裝配的目的是在車(chē)輛載重量為額定值的情況下，合理進(jìn)行貨物的安排，使車(chē)輛裝載貨物的價(jià)值最大（如：重量最大、運(yùn)費(fèi)最低等）。11.運(yùn)用動(dòng)態(tài)規(guī)劃解裝貨問(wèn)題設(shè)貨車(chē)的載重量上限為G，用于運(yùn)送n種不同的貨物，貨物的重量分別為W1，W2，...，Wn，每一種貨物對(duì)應(yīng)于一個(gè)價(jià)值系數(shù)，分別用P1，P2，...，Pn表示，它表示價(jià)值、運(yùn)費(fèi)或重量等。設(shè)Xk表示第k種貨物的裝入數(shù)量，貨物裝配問(wèn)題的數(shù)學(xué)模型可以表示為：2可以把裝入一件貨物作為一個(gè)階段，把裝貨問(wèn)題看作動(dòng)態(tài)規(guī)劃問(wèn)題。由于裝入貨物的先后次序不影響裝貨問(wèn)題的最優(yōu)解,所以我們的求解過(guò)程可以從第一階段開(kāi)始，由前向后逐步進(jìn)行。求解

2、過(guò)程：（1）裝入第1種貨物X1件，其最大價(jià)值為其中：X1表示第1種貨物的裝載數(shù)量；其取值范圍：0

3、n種貨物Xn件，其最大價(jià)值為其中：Xn表示第n種貨物的裝載數(shù)量；其取值范圍：0

4、行。從價(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ù)字表示其余種類(lèi)貨物的裝載量。當(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í)，其余兩類(lèi)貨物裝入重量3；（3）在第2階段計(jì)算表中，查W=3，f2(W)=3對(duì)應(yīng)兩組數(shù)據(jù)：1）X2=0；2)

5、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)前面的尋找過(guò)程，可以得到兩組最優(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=891011前面的最優(yōu)方案是在第四階段取X4＝1時(shí)得出的方案。如果在第4階段計(jì)算表中取X4＝0，則其余種類(lèi)的貨物裝載量W-W4X4=8；在第3階段計(jì)算表中，查W=8一欄，f

6、3(w)=8對(duì)應(yīng)X3＝2，再仿照前面的方法，可以得到第3組最優(yōu)解：第三組：X1=0，X2=0，X3=2，X4=0；裝載量為：X3*2=2*4=8以上三組裝載方案，都最大限度地發(fā)揮了車(chē)輛的載重能力，都是最優(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；12132.品種混裝問(wèn)題在實(shí)際的物流過(guò)程中，儲(chǔ)運(yùn)倉(cāng)庫(kù)(或貨運(yùn)車(chē)站)要把客戶所需的貨物組成整車(chē)，運(yùn)往各地。不同客戶的貨物，要分別在一站或多站卸貨。在裝貨、運(yùn)輸和卸貨過(guò)程中，為了減少裝卸、運(yùn)輸過(guò)程中出現(xiàn)差

7、錯(cuò)，一般要按照品種、形狀、顏色、規(guī)格、到達(dá)地點(diǎn)，把貨物分為若干類(lèi)，在裝車(chē)時(shí)分別進(jìn)行處理。這就是品種混裝問(wèn)題。設(shè)裝車(chē)的貨物可以分為1類(lèi)，2類(lèi)，…，m類(lèi)。共有N件(捆)待運(yùn)貨物，其中1類(lèi)貨物有N1件(捆)，它們的重量分別G11，G12，……，G1N1；2類(lèi)貨物有N2件(捆)，它們的重量分別為G21，G22，……，G2N2；第s類(lèi)貨物共有Ns件，它們的重量分別為Gs1，Gs2，……，GsNs；以此類(lèi)推，可以看出：14貨物總的件數(shù)：其中，Ns：第s類(lèi)貨物的件數(shù)；m：貨物的種類(lèi)數(shù)；N：貨物的總件數(shù)；設(shè)：品種混裝問(wèn)題要求同一貨車(chē)內(nèi)每類(lèi)貨物至多裝入一件