[货物分配问题.pptVIP

货物装配问题 货物装配的目的是在车辆载重量为额定值的情况下，合理进行货物的安排，使车辆装载货物的价值最大（如：重量最大、运费最低等）。 1. 运用动态规划解装货问题 设货车的载重量上限为G，用于运送n种不同的货物，货物的重量分别为W1，W2，...，Wn，每一种货物对应于一个价值系数，分别用P1，P2，...，Pn表示，它表示价值、运费或重量等。设Xk表示第k种货物的装入数量，货物装配问题的数学模型可以表示为： 可以把装入一件货物作为一个阶段，把装货问题看作动态规划问题。由于装入货物的先后次序不影响装货问题的最优解,所以我们的求解过程可以从第一阶段开始，由前向后逐步进行。 求解过程： （1）装入第1种货物X1件，其最大价值为 (2)装入第2种货物X2件，其最大价值为 ? ? 其中：X2表示第2种货物的装载数量； 其取值范围：0X2 [G/W2] ； P2：第2种货物的价值系数（重量、运费、价值等）； ：第一种货物的重量； ：第一种货物的价值。 （3）装入第3种货物X3件，其最大价值为 其中：X3表示第3种货物的装载数量； 其取值范围：0X3 [G/W3]； P3：第3种货物的价值系数； …… (n) 装入第n种货物Xn件，其最大价值为 ? ?  其中：Xn表示第n种货物的装载数量； 其取值范围：0Xn [G/Wn] ； Pn：第n种货物的价值系数； 货物装配例题 例题9 载重量为8t的载重汽车，运输4种机电产品，产品重量分别为3吨、3吨、4吨、5吨，试问如何配装才能充分利用货车的运载能力? 解： 第一步，按照前面的公式，分成四个阶段计算每一阶段的价值。 计算结果以表格表示如下： 第二步：寻找最优方案。寻找最优解方案的次序与计算顺序相反，由第4阶段向第1阶段进行。从价值最大的装载情况，逐步向前寻找最优方案。 （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) 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 = 8 前面的最优方案是在第四阶段取X4＝1时得出的方案。 如果在第4阶段计算表中取X4＝0，则其余种类的货物装载量W - W4X4=8； 在第3阶段计算表中，查W=8一栏，f3(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； 2. 品种混装问题 在实际的物流过程中，储运仓库(或货运车站)要把客户所需的货物组成整车，运往各地。不同客户的货物，要分别在一站或多站卸货。在装货、运输和卸货过程中，为了减少装卸、运输过程中出现差错，一般要按照品种、形状、颜