《精编》物流分配规划课件

《《精编》物流分配规划课件》由会员分享，可在线阅读，更多相关《《精编》物流分配规划课件（36页珍藏版）》请在金锄头文库上搜索。

1、3物流分配规划 任务分配问题的数学模型 重点 用匈牙利法求解分配问题 自学 一 任务分配问题 1 简介在物流系统中经常面临的一个问题 如何根据有限的资源 人力 物力 财力等 进行工作任务分配 以达到降低成本或提高经济效益的目的 如 运输任务的分配问题 有n条航线的运输任务指派给n艘船去完成 不同的船完成不同的航线其运输成本不同 要求每条船完成一条航线 并且一条航线只能由一条船去完成 如何分配任务 才能使总的费用最小 又如 有A B C D四门课程 上课的老师可以从甲 乙 丙 丁四名老师中选择 不同的老师上不同的课程 其费用是不同的 并且规定 每人只讲一门课程 每门课程只需要一人讲授 问 如何安

2、排 才能使总的上课费用最低 这类问题是常见的任务分配问题 也叫指派问题 它的任务是如何进行合理的任务分配 使总的费用最小 2 任务分配问题的数学模型 以运输问题的n项任务由n个司机去完成的情况为例 有n个司机被分配完成n项运输任务 不同的司机完成某一项任务的费用都不一样 要求每个司机完成其中一项任务 每个任务只能由一名司机完成 如何分配任务 才能使总的费用最小 令 cij表示第i个司机完成第j项任务的运输成本 工作成本或工作时间等价值系数 xij表示第i个司机去完成第j项任务 其值为1或0 当其值为1时表示第i个司机被分配去完成第j项任务 其值为0时 表示第i个司机不被分配去完成第j项任务 3

3、 任务分配问题数学模型的求解 任务分配问题属于整数规划问题 其变量xij的取值为整数 本例为0或1 任务分配问题可以用一般的整数规划求解方法进行求解 但是 整数规划问题的求解也是非常困难的 到目前为止 还缺乏统一的求解方法 本书采用匈牙利法求解任务分配问题 二 匈牙利法求解分配问题 可以证明 对于分配问题 在其费用矩阵Cij中 各行 各列均减去一个常数 Cij改变以后的最优解 仍为原问题的最优解 利用这个性质 通过对Cij的行 列进行加减常数的计算 把一些矩阵元素变为0 在Cij为0的元素上进行分配 就可得到原问题的最优解 该方法应用了匈牙利数学家Konig矩阵性质定理 因此这种方法被称为匈牙

4、利法 4其他规划问题 选址问题货物配装问题物流服务系统中的配置问题 一 选址问题 简介物流调运规划问题 是一种有固定发点 固定收点和固定道路的运输规划问题 还有一类运输问题 他的收货点和发货点是待定的 这就是选址问题 这类问题在物流系统规划中经常遇到 选址问题要考虑多种因素 本节只讨论选址问题中的物流问题 分为两个问题 单一地址选址方法 图上作业法 1 单一地址选址方法 单一选址问题 就是从多个候选地址中选取一个最优地址 1 问题描述假设地址候选地点有s个 分别用D1 D2 Ds表示 原材料 燃料 零配件的供应地有m个 分别用A1 A2 Am表示 其供应量分别用P1 P2 Pm表示 产品销售地

5、有n个 分别用B1 B2 Bn表示 其销售量分别为Q1 Q2 Qn表示 2 参数及变量说明设cij为供应地Ai到候选厂址Dj的单位物资运输成本 djk为候选厂址Dj到销售地Bk的单位物资运输成本 设 选址变量为x x1 x2 xs 其中 xj 0或1 1表示在Dj点建厂 0表示不在Dj点建厂 3 目标函数及约束条件 单一选址问题是一种线性规划问题 并且变量的取值为0或1 属于整数规划问题 单一地址的选址模型的求解方法比较简单 从目标函数表达式的右边可以看出 通过计算模型中括号内的算式值 就能够确定运输成本最小的方案 当要选定的地址不是单一的 而是多个时 问题不再属于线性规划问题 5 求解方法

6、2 图上作业法 对于运输路线不含回路的选址问题 可用图上作业法求解 例题8假定有六个矿井 产量分别为5000吨 6000吨 7000吨 2000吨 4000吨和3000吨 运输路线如图所示 这些矿石要经过加工后才能转运到其他地方 这些矿井之间道路不含回路 欲选择一个矿井 在此矿井上建立一个加工厂 使各矿井到工厂的运输总费用最低 为了便于分析 用一个新的图来代替原图 新图圈内数字表示矿井编号 产量记在圈的旁边 道路交叉点看作产量为零的矿井 把那些只有一条道路连接的矿井称为端点 首先计算这些矿井的总产量 本例为27000吨 然后分析各端点 都没有超过总产量的一半 因此把各端点的数量合并到前一站 即

7、 和 的数量合并到 把 的数量合并到 把 的数量合并到 如下图所示 3 5 6 11000 9000 7000 各端点都合并到前一站后 和 变成了图中的端点 对它们进行分析 其数量都不超过总产量的一半 所以他们也不是最佳点 再把它们合并到前一站 即把 和 的数量合并到 则 的数量为27000 超过总量的一半 所以 是最佳点 结论 加工厂应建在第5号矿井 二 货物配装 货物配装的目的是在车辆载重量为额定值的情况下 合理进行货物的安排 使车辆装载货物的价值最大 如 重量最大 运费最低等 1 装货问题的数学模型 1 问题描述设货车的载重量上限为G 用于运送n种不同的货物 货物的重量分别为W1 W2

8、Wn 每一种货物对应于一个价值系数 分别用P1 P2 Pn表示 它表示价值 运费或重量等 2 数学模型设Xk表示第k种货物的装入数量 货物配装问题的数学模型可以表示为 3 求解方法可以把装入一件货物作为一个阶段 把装货问题看作动态规划问题 一般情况下 动态规划问题的求解过程是从最后一个阶段开始由后向前进行的 由于装入货物的先后次序不影响装货问题的最优解 可以从第一阶段开始 由前向后逐步进行 4 求解过程1 装入第1种货物X1件 其最大价值为 其中 X1表示第1种货物的装载数量 其取值范围 0 X1 G W1 方括号表示取整 P1 第1种货物的价值系数 重量 运费 价值等 f1 W 第一种货物的

9、价值 2 装入第2种货物X2件 其最大价值为其中 X2表示第2种货物的装载数量 其取值范围 0 X2 G W2 P2 第2种货物的价值系数 重量 运费 价值等 第一种货物的重量 第一种货物的价值 3 装入第3种货物X3件 其最大价值为其中 X3表示第3种货物的装载数量 其取值范围 0 X3 G W3 P3 第3种货物的价值系数 前两种货物的重量 前两种货物的价值 n 装入第n种货物Xn件 其最大价值为其中 Xn表示第n种货物的装载数量 其取值范围 0 Xn G Wn Pn 第n种货物的价值系数 例题9载重量为8t的载重汽车 运输4种机电产品 产品重量分别为3吨 3吨 4吨 5吨 试问如何配装才

10、能充分利用货车的运载能力 解 第一步 按照前面的公式 分成四个阶段计算每一阶段的价值 计算结果以表格表示如下 5 货物配装例题求解 载重量 件数 价值 重量 载重量 第2种货物的件数 第1种货物的重量 价值计算 价值 Max 载重量 第3种货物的件数 第1 2种货物的重量 价值计算 价值 Max 第二步 寻找最优方案 寻找最优解方案的次序与计算顺序相反 由第4阶段向第1阶段进行 选择最后一个阶段价值最大的装载情况 逐步向前寻找最优方案 第二步 寻找最优方案 寻找最优解方案的次序与计算顺序相反 由第4阶段向第1阶段进行 从价值最大的装载情况 逐步向前寻找最优方案 1 在第4阶段计算表中 在载重量

11、为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

12、当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 载重量 第3种货物的件数 第1 2种货物的重量 价值计算 价值 载重量 第2种货物的件数 第1种货物的重量 价值计算 价值 Max 前面的最优方案是在第四阶段取X4 1时得出的方案 如果在第4阶段计算表中取X4 0 则其余种类的货物装载量W W4X4 8 在第3阶段计算表中 查W 8一栏 f3 w 8对应X3 2

13、 再仿照前面的方法 可以得到第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 品种混装问题 1 品种混装问题简介在实际的物流过程中 储运仓库 或货运车站 要把客户所需的零担货物组成整车 运往各地 不同客户的货物 要分别在一站或多站卸货 在装货 运输和卸货过

14、程中 为了减少装卸 运输过程中出现差错 一般要按照品种 形状 颜色 规格 到达地点 把货物分为若干类 在装车时分别进行处理 这就是品种混装问题 2 品种混装问题描述设装车的货物可以分为1类 2类 m类 共有N件待运货物 其中 第1类货物有N1件 它们的重量分别G11 G12 G1N1 第2类货物有N2件 它们的重量分别为G21 G22 G2N2 第s类货物共有Ns件 它们的重量分别为Gs1 Gs2 GsNs 以此类推 可以看出 货物总的件数 其中 Ns 第s类货物的件数 m 货物的种类数 N 货物的总件数 3 数学模型品种混装问题要求同一货车内每类货物至多装入一件 在此假设条件下 可以建立品种

15、混装问题的数学模型 设 其中m 货物的类别数 Nr 第r类货物的件数 Grs 第r类第s件货物的重量 G0 货车载重量的上限 4 求解方法品种混装问题的数学模型属于整数规划问题 可以用单纯形法进行求解动态规划法图5 20表示8件货物分为4类的混装网络示意图 在图中同一列的方框表示同一类货物 方框内的数字 符号 表示货物重量 上述品种混装问题就是在网络中自右向左寻找一条路线 使路线所经过的方框中的重量之和达到最大 但又不超过货车的载重量的上限Go 可以用穷举法求解 如果将四类货物看作4个阶段 将上述问题化为动态规划问题求解 5 求解实例例题10货车载重量上限Go 50 第1类货物2件 G11 2

16、0 G12 11 第2类货物1件 G21 13 第3类货物3件 G31 6 G32 11 G33 8 第4类货物2件 G41 19 G42 17 19 17 6 11 8 13 20 11 计算过程见表5 31 34 分成四个阶段进行 可装重量 实装重量 剩余容量 第1阶段的可装容量W值对应第2阶段的剩余容量W G 装载情况计算表 可装重量 实装重量 剩余容量 第1阶段的可装容量W值对应第2阶段的剩余容量W G 最优解的寻找过程 寻找最优解的次序与计算顺序相反 从第一阶段计算表开始 直到第四阶段 要使装载量达到最大 对应的剩余余量应当最小 1 在第一阶段计算表中 余量W G1的最小值为零 为最好的方案 此时 对应的实际装载量G1为20 可装载容量W值为20 2 第一阶段的可装载容量W 20为第二阶段的剩余装载容量 即W G2的值为20 从表中可以看出第二阶段的剩余装载容量为20的实际装载方式有两种 分别是 G2 0和G2 13对应的可装容量分别为W 20和33 3 第二阶段的可装容量W 20和33为第三阶段的剩余装载容量 查表可得 对应于剩余可装载容量为20的实际装载量为G3 11 可