Session05网络最优化问题.ppt

Data,ModelandDecisions数据、模型与决策,Session5NetworkOptimizationProblems网络最优化问题,SessionTopics,PhillipsPetroleumVehicleReplacementPlanning飞利浦石油公司运输工具替换计划ApplicationsofNetworkOptimization网络最优化模型的应用TypesofNetworkOptimizationProblem网络最优化问题类型MinimumCostNetworkFlowModel最小费用流问题,SessionTopics,MaximumFlowProblems最大流问题ShortestPathProblem最短路问题MinimumSpanningTreeProblem最小支撑树问题,飞利浦石油（PhillipsPetroleum）应用最短路问题模型对各种高速公路运输车、卡车和货车运输路线的优化来降低成本提高竞争力,PlanningVehicleReplacementatPhillipsPetroleum飞利浦石油的运输工具替换计划,经典应用,Waddell(1983)Jul-AugInterfacesarticle,“AModelforEquipmentReplacementDecisionsandPolicies”,有1500辆卡车和3800辆货车用最短路模型建立替换战略(20年时间跨度)每次为每一类运输工具求解模型考虑成本有维护和运营成本、租赁成本、购买成本、政府授权费用路税和其他税收（投资税、折旧）开始做lease-or-buy决策，然后做替换战略，目前扩展到了其他的设备（非运输工具）,PlanningVehicleReplacementatPhillipsPetroleum飞利浦石油的运输工具替换计划,经典应用,ApplicationsofNetworkOptimization网络最优化模型的应用,网络在交通、电子和通讯网络遍及我们日常生活的各个方面，网络规划也广泛用于解决不同领域中的各种问题，如生产、分配、项目计划、厂址选择、资源管理和财务策划等等。网络规划为描述系统各组成部分之间的关系提供了非常有效直观和概念上的帮助，广泛应用于科学、社会和经济活动的每个领域中,Networkrepresentation网络表述,这种描述还有其他应用吗？,TypesofNetworkOptimizationProblem网络最优化问题类型,MinimumCostNetworkFlowModel最小费用流问题MaximumFlowProblems最大流问题ShortestPathProblem最短路问题MinimumSpanningTreeProblem最小支撑树问题,MinimumCostNetworkFlowModel最小费用流问题,最小费用流问题的构成：节点(nodes)（供应点、需求点、转运点）弧（arcs）目标:通过网络满足需求提供供应，最小化流的总成本,AssumptionsofMinimumCostNetworkFlow最小费用流问题的假设,至少一个供应点一个需求点剩下都是转运点通过弧的流只允许沿着箭头方向流动，通过弧的最大流量取决于该弧的容量网络中有足够的弧提供足够容量，使得所有在供应点中产生的流都能够到达需求点在流的单位成本已知前提下，通过每一条弧的流的成本和流量成正比,CharacteristicofSolution解的特征,具有可行解的特征：在以上的假设下，当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时，最小费用流问题有可行解具有整数解的特征：只要其所有的供应、需求和弧的容量都是整数值，那么任何最小费用流问题的可行解就一定有所有流量都是整数的最优解,DistributionUnlimitedCo.无限配送公司,无限配送公司的最小成本流问题的电子表格模型,实际举例,NetworkSimplexMethod网络单纯形法,实际运用中解决比较大型问题时需要用不同的方法网络单纯形法可以用来解决那些对于单纯形法来说太大而无法解决的大型问题ExcelSolver软件中没有网络单纯形法，但是其他的线性规划的商业软件包通常都有这种方法,SomeApplications一些实际应用,国际纸业公司（InternationalPaperCompany）配送网络（Interfaces1988年3/4）世界上最大的纸浆、纸和纸类产品的制造商以及木材和夹板的主要生产者。拥有两千万英亩的林区或其权益。分布在不同地方的林区是它配送网络的供应点,供应流必须经过一系列很长的转运点：林区木材堆积场锯木厂造纸厂纸制品加工厂仓库客户,实务经典,SomeApplications一些实际应用,马尔萨斯公司（Marshalls,Inc.）配送网络（Interfaces1987年7/8）一家折扣连锁零售店，现在和以前是如何使用微型计算机去处理一个最小费用流问题。应用中公司力图使得从供应商到加工中心，再从加工中心到零售店的商流最优。其中的一些网络有超过20,000条弧。,实务经典,MaximumFlowProblems最大流问题,最大流问题也与网络中的流有关，但目标不是使得流的成本最小化，而是寻找一个流的方案，使得通过网络的流量最大,这种问题有哪些应用呢？,BMZCaseStudyBMZ案例研究,BMZ从德国斯图加特工厂到洛杉矶配送中心的配送网络,案例研究,BMZCaseStudyBMZ案例研究,BMZ案例的网络描述,案例研究,BMZCaseStudyBMZ案例研究,BMZ案例求解,案例研究,AssumptionsofMaximumFlowProblems最大流问题的假设,网络中所有流起源于一个叫做源的节点所有的流终止于一个叫做收点的节点其余所有的节点叫做转运点通过每一个弧的流只允许沿着弧的箭头方向流动目标是使得从源到收点的总流量最大,ShortestPathProblem最短路问题,最短路问题的最普遍的应用在两个点之间寻找最短路,这种问题有哪些应用呢？,LittletownFireStation里特城消防站,实际举例,里特城的消防站和某一农场社区间的道路系统,LittletownFireStation里特城消防站,实际举例,里特城的消防站道路系统的网络表述,LittletownFireStation里特城消防站,实际举例,AssumptionsofshortestPathProblem最短路问题的假设,网络中选择一条路,始于某源点终于目标地连接两个节点的连线叫做边（允许任一个方向行进），弧（只允许沿着一个方向行进）和每条边相关的一个非负数，叫做该边的长度目标是为了寻找从源到目标地的最短路,MinimumSpanningTreeProblem最小支撑树问题,给你网络中的节点，但没有给你边。或者，给你可供选择的边和如果把它插入到网络中后的每条边的正的成本（或者相似的度量）在设计网络时你希望通过插入足够的边，以满足每两个节点之间都存在一条路的需要目标是寻找一种方法，使得在满足要求的同时总成本最小,TheSimpleAlgorithm简单的算法,选择第一条边：选择成本最低的备选边选择下一条边：在一个已经有一条边连接的节点和另一个还没有边连接的节点之间选择成本最低的备选边重复第二个步骤，直到所有的节点都有一条边（可能会有多于一条边）与其相连此时就得到了最优解（最小支撑树）,SomeApplications一些实际应用,电信网络（计算机网络、电话专用线网络、有线电视网络等等）的设计低负荷运输网络的设计，使得网络中提供链接的部分（如铁路、公路等等）的总成本最小高压输电线路网络的设计电器设备线路网络（如数字计算机系统）的设计，使得线路总长度最短连接多个场所的管道网络设计,实务应用,SessionSummary本讲小结,小结,网络表示在描绘网络系统中各部分之间关联上非常有用最小费用流问题的特殊类型包括运输问题和指派问题最大流问题的目标是使得从一个特定的起点（源）到一个特定的终点（收点）的总流量最大最短路问题也有始点（源）和终点（目标地），但是，它的目标是从源点到目标