3运输与分配问题.pptVIP

* 指派问题数学模型 * 7.2 The Management Scientist Software （MS 6.0） 见软件计算结果（7机器指派.ASN）。 其中机器3未分配任务。 阅读教材P184 海军陆战队的调遣 多少Job?多少军官？ 可能会有多少种分配方案？ 变量多少？如何解决？ * 7.3 转运问题 是运输问题的扩展，其中中间节点代表转运节点（例如仓库）。 三种节点为：起点节点、转运节点和终点节点。 出货发生在以上任意两个之间。 Case:分销系统设计（教材P192） * 例1 Part 2Network Model 例2 PG公司在北美的产品配送系统 （教材P176） * 下次课内容 第7章 整数规划 案例1 课本出版 第6章 网络模型 6.4最短路径问题、6.5最大流量问题、6.6 生产与库存应用 作业：用MS6.0计算 P16 3.1 3.2 * 1绪论 — Introduction 2线性规划 —Linear Programming 3运输与指派问题—Transportation Models 4整数规划 —Integer Programming 5图与网络 —Network Models 6项目计划 —PERT CPM 7排队论 —Queueing Models 8 模拟 —Simulation 9决策分析 — Decision Theory 10多目标决策 — Multi-objective Decision 《管理数量方法 》目录 * 授课内容（第6章） Question 6.1 运输问题(表上作业法) 6.2 指派问题(应用软件计算) 6.3 转运问题 Case:分销系统设计（教材P192） 6.4最短路径问题 6.5最大流量问题 6.6 生产与库存应用 * 运输问题举例 例 三个工厂B1、B2、B3，它们需要同一种原料，数量分别为72吨、102吨、41吨，另外有三个供应商A1、A2、A3可以供应上述原料56吨、82吨、77吨，由于工厂和供应商位置不同，单位运价也不同，具体数据如表。应如何安排运输方案，才能使总运费最小？ B1 B2 B3 供应量 A1 4 8 8 56 A2 16 24 16 82 A3 8 16 24 77 需求量 72 102 41 215 表 工厂B和供应商A之间单位运价 * 运输问题的提法 运输问题的提法:某物资有M个产地Ai, 产量分别是ai (I=1,2,…,m), 有N个销地Bj(j=1,2,…,n). 销量分别是bj (j=1,2,…,n). 若从Ai运到Bj的单位运价为cij (I=1,2,…,m; j=1,2,…,n), 又假设产销平衡, 即 问如何安排运输可使总运费最小? * 运输表格 销地 单价 产 地 B1 B2 … Bn 产量 A1 c11 c12 … c1n a1 A2 c21 c22 … c2n a2 … … … … … … Am cm1 cm2 … cmn am 销量 b1 b2 … bn x11 x12 x1n x21 x22 x2n xm1 xm2 xmn * 如何建立运输问题的LP模型 Xij:从Ai到Bj的运量. Z:总运输费用. 变量？ 约束方程？ 如何回答？ * 运输问题的解法及软件求解 线性规划问题：单纯形法 线性规划问题：表上作业法 最小费用流问题：对偶算法 如何回答？ * 运输问题举例 例 三个工厂B1、B2、B3，它们需要同一种原料，数量分别为72吨、102吨、41吨，另外有三个供应商A1、A2、A3可以供应上述原料56吨、82吨、77吨，由于工厂和供应商位置不同，单位运价也不同，具体数据如表。应如何安排运输方案，才能使总运费最小？ * min Z = 4X11 ＋ 8X12 ＋ 8X13 + 16X21 ＋ 24X22 ＋ 16X23 + 9X31 ＋ 16X32 ＋ 24X33 s.t. X11 ＋ X12 ＋ X13 ≤ 56 （供应量约束1） X21 ＋ X22 ＋ X23 ≤ 82 （供应量约束2） X31 ＋ X32 ＋ X33 ≤ 77 （供应量约束3） X11 ＋X21 ＋ X31 ≥ 72 （需求量约束1） X12 ＋X22 ＋ X32 ≥ 102 （需求量约束2） X13 ＋X23 ＋ X33 ≥ 41 （需求量约束3） Xij