运输与指派问题ppt课件

Data ModelandDecisions数据 模型与决策 Session4TransportationandAssignmentProblems运输与指派问题 SessionTopics TheTransportationProblem运输问题TransportationProblemExample运输问题举例CharacteristicsofTransportationProblems运输问题的特征AnAward WinningApplication运输问题的一个获奖应用VariantsofTransportationProblems各种运输问题变体 SessionTopics TheAssignmentProblem指派问题TheModelforAssignmentProblem指派问题模型VariantsofAssignmentProblem指派问题的变形ApplicationsofAssignmentProblem指派问题的应用 物流中的一个普遍问题是如何以尽可能小的成本把货物从一系列起始地 sources 如工厂 仓库 运输到一系列终点地 destinations 如仓库 顾客 TheTransportationProblem运输问题 你怎么去分析这类问题呢 TheTransportationProblem运输问题 TransportationNetwork运输问题的网络表示 供应地约束 需求地约束 LPModelofTransportationProblem运输问题线性规划模型 P T公司是一家由家族经营的小公司 它收购生菜并在食品罐头厂中把它们加工成为罐头 然后再把这些罐头食品分销到各地卖出去 豌豆罐头在三个食品罐头厂 靠近华盛顿的贝林翰 俄勒冈州的尤基尼 明尼苏达州的艾尔贝 李 加工 然后用卡车把它们运送到美国西部的四个分销仓库 加利福尼亚州的萨克拉门托 犹他州盐湖城 南达科他州赖皮特城 新墨西哥州澳尔巴古 TransportationProblemExample运输问题举例 实际举例 TransportationProblemExample运输问题举例 实际举例 P T公司问题中的仓库和加工厂位置图 TransportationProblemExample运输问题举例 实际举例 作为一个运输问题的P T公司电子表格描述 每一个出发地都有一定的供应量 supply 配送到目的地 每一个目的地都有需要从一定的需求量 demand 接收从出发地发出的产品需求假设 TheRequirementsAssumption 可行解特性 TheFeasibleSolutionsProperty 成本假设 TheCostAssumption 整数解性质 IntegerSolutionsProperty CharacteristicsofTransportationProblems运输问题的特征 需求假设 TheRequirementsAssumption 每一个出发地都有一个固定的供应量 所有的供应量都必须配送到目的地 与之相类似 每一个目的地都有一个固定的需求量 整个需求量都必须由出发地满足 TheRequirementsAssumption需求假设 可行解特性 TheFeasibleSolutionsProperty 当且仅当供应量的总和等于需求量的总和时 运输问题才有可行解 TheFeasibleSolutionsProperty可行解特性 成本假设 TheCostAssumption 从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系 因此这个成本就等于配送的单位成本乘以所配送的数量 TheCostAssumption成本假设 整数解性质 IntegerSolutionsProperty 只要它的供应量和需求量都是整数 任何有可行解的运输问题必然有所有决策变量都是整数的最优解 因此 没有必要加上所有变量都是整数的约束条件 IntegerSolutionsProperty整数解性质 P G重新设计制造和配送体系 90 S成百上千个供应商50多个产品类别超过60个的工厂15个配送中心超过1000个的顾客群体 AnAward WinningApplication运输问题的一个获奖应用 为每个单独的产品种类设计并求解运输问题对于针对还在运行的工厂的每一个选择 为每一个产品种类解决相应的运输问题体现了从这些工厂运送产品到配送中心或顾客区所需要的配送成本是多少 在找出最好的新生产和配送系统的过程之中解决了许多这样的运输问题北美工厂数减少了20 并且公司每年节省了2亿美元的税前费用 AnAward WinningApplication运输问题的一个获奖应用 供应总量超出了需求总量供应总量小于需求总量一个目的地同时存在着最小需求和最大需求在配送中不能使用特定的出发地 目的地组合目标是与配送量有关的总利润最大不是成本最小 VariantsofTransportationProblems各种运输问题变体 TexagoCorp SiteLocation特塞格选址问题 实际举例 特塞格公司从油田运输原油到炼油厂运输问题的基本电子表格模型描述 TexagoCorp SiteLocation特塞格选址问题 实际举例 特塞格炼油厂每一个备选厂址所带来的年变动成本 现实生活之中 我们也经常遇到指派人员做某项工作的情况 指派问题的许多应用都用来帮助管理人员解决如何为一项将要开展进行的工作指派人员的问题 其他的一些应用如为一项任务指派机器 设备或者是工厂 TheAssignmentProblem指派问题 还有哪些这样的问题呢 指派问题的形式表述 给定了一系列所要完成的任务 tasks 以及一系列完成任务的被指派者 assignees 所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务 TheModelforAssignmentProblem指派问题模型 指派问题的假设 被指派者的数量和任务的数量是相同的每一个被指派者只完成一项任务每一项任务只能由一个被指派者来完成每个被指派者和每项任务的组合有一个相关成本目标是要确定怎样进行指派才能使得总成本最小 TheModelforAssignmentProblem指派问题模型 VariantsofAssignmentProblem指派问题的变形 指派问题的变形 有一些被指派者并不能进行某一些的任务任务比被指派者多被指派者比要完成的任务多每个被指派者可以同时被指派给多于一个的任务每一项任务都可以由多个被指派者共同完成 ApplicationsofAssignmentProblem指派问题的应用 在各个地点分派设备指派工厂生产产品设计学生入学区域 AssigningMachinestoLocations各个地点分派设备 为什么不需要0 1条件 AssigningPlantstoProducts指派工厂生产产品 求佳产品公司问题指派问题变形的电子表格模型 DesigningSchoolAttendanceZones设计学生入学区域 米德尔城学区问题指派问题变形的电子表格模型 SessionSummary本讲小结 小结 运输问题考虑 确实的或是比喻的 从出发地运送货物到目的地 每一个出发地都有一个固定的供应量 每一个目的地都有一个固定的需求量指派问就要处理应当将哪一项任务指派给哪一个被指派者 才能使完成这些任务的总达到最小把