货物分配问题.ppt

《货物分配问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、货物装配问题货物装配的目的是在车辆载重量为额定值的情况下，合理进行货物的安排，使车辆装载货物的价值最大（如：重量最大、运费最低等）。11.运用动态规划解装货问题设货车的载重量上限为G，用于运送n种不同的货物，货物的重量分别为W1，W2，...，Wn，每一种货物对应于一个价值系数，分别用P1，P2，...，Pn表示，它表示价值、运费或重量等。设Xk表示第k种货物的装入数量，货物装配问题的数学模型可以表示为：2可以把装入一件货物作为一个阶段，把装货问题看作动态规划问题。由于装入货物的先后次序不影响装货问题的最优解,所以我们的求解过程可以从第一阶段开始，由前向后逐步进行。求解

2、过程：（1）装入第1种货物X1件，其最大价值为其中：X1表示第1种货物的装载数量；其取值范围：0

3、n种货物Xn件，其最大价值为其中：Xn表示第n种货物的装载数量；其取值范围：0

4、行。从价值最大的装载情况，逐步向前寻找最优方案。（1）在第4阶段计算表中，在载重量为8时，价值(本例为载重量)最大值f4(W)＝8，对应两组数据(加*号的数据)：1）X4＝0；2）X4＝1；先看X4＝1时的情况：当X4＝1时，即第4种货物装入1件(5吨)，表中第3列数字表示其余种类货物的装载量。当X4＝1时，其他3种货物装载量为3吨；（2）按相反方向，在第3阶段计算表中，查W=3吨时，得到最大价值f3(W)＝3，对应的X3=0。查表中第3列数字，W=3，X3=0时，其余两类货物装入重量3；（3）在第2阶段计算表中，查W=3，f2(W)=3对应两组数据：1）X2=0；2)

5、X2=1；即当X2=1或0时，其他(第1种)货物装载量为3或0；（4）查第1阶段计算表，1）当W＝3时，对应X1=1；2）当W＝0时，对应X1=0；根据当前面的寻找过程，可以得到两组最优解：第一组：X1=1，X2=0，X3=0，X4=1；第二组：X1=0，X2=1，X3=0，X4=1；这两组最优解的实际载重量为：第一组：X1*3+X4*5=1*3+1*5=8第二组：X2*3+X4*5=1*3+1*5=891011前面的最优方案是在第四阶段取X4＝1时得出的方案。如果在第4阶段计算表中取X4＝0，则其余种类的货物装载量W-W4X4=8；在第3阶段计算表中，查W=8一栏，f

6、3(w)=8对应X3＝2，再仿照前面的方法，可以得到第3组最优解：第三组：X1=0，X2=0，X3=2，X4=0；装载量为：X3*2=2*4=8以上三组装载方案，都最大限度地发挥了车辆的载重能力，都是最优方案。最终的最优装载方案为：第一组：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.品种混装问题在实际的物流过程中，储运仓库(或货运车站)要把客户所需的货物组成整车，运往各地。不同客户的货物，要分别在一站或多站卸货。在装货、运输和卸货过程中，为了减少装卸、运输过程中出现差

7、错，一般要按照品种、形状、颜色、规格、到达地点，把货物分为若干类，在装车时分别进行处理。这就是品种混装问题。设装车的货物可以分为1类，2类，…，m类。共有N件(捆)待运货物，其中1类货物有N1件(捆)，它们的重量分别G11，G12，……，G1N1；2类货物有N2件(捆)，它们的重量分别为G21，G22，……，G2N2；第s类货物共有Ns件，它们的重量分别为Gs1，Gs2，……，GsNs；以此类推，可以看出：14货物总的件数：其中，Ns：第s类货物的件数；m：货物的种类数；N：货物的总件数；设：品种混装问题要求同一货车内每类货物至多装入一件