第六七次-session5网络最优化问题

Data,ModelandDecisions数据、模型与决策Session5NetworkOptimizationProblems网络最优化问题SessionTopicsPhillipsPetroleumVehicleReplacementPlanning

飞利浦石油公司运输工具替换计划

ApplicationsofNetworkOptimization

网络最优化模型的应用TypesofNetworkOptimizationProblem

网络最优化问题类型

MinimumCostNetworkFlowModel

最小费用流问题SessionTopicsMaximumFlowProblems

最大流问题

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）配送网络（Interfaces

1988年3/4）世界上最大的纸浆、纸和纸类产品的制造商以及木材和夹板的主要生产者。拥有两千万英亩的林区或其权益。分布在不同地方的林区是它配送网络的供应点,供应流必须经过一系列很长的转运点： 林区→木材堆积场→锯木厂→造纸厂 →纸制品加工厂→仓库→客户

实务经典SomeApplications一些实际应用马尔萨斯公司（Marshalls,Inc.）配送网络（Interfaces

1987年7/8）一家折扣连锁零售店，现在和以前是如何使用微型计算机去处理一个最小费用流问题。应用中公司力图使得从供应商到加工中心，再从加工中心到零售店的商流最优。其中的一些网络有超过20,000条弧。实务经典MaximumFlowProblems最大流问题最大流问题也与网络中的流有关，但目标不是使得流的成本最小化，而是寻找一个流的方案，使得通过网络的流量最大这种问题有哪些应用呢？想想看！BMZCaseStudyBMZ案例研究BMZ从德国斯图加特工厂到洛杉矶配送中心的配送网络案例研究BMZCaseStudyBMZ案例研究BMZ案例的网络描述案例研究BMZCaseStudyBMZ案例研究BMZ案例求解案例研究AssumptionsofMaximumFlowProblems最大流问题的假设

网络中所有流起源于一个叫做源的节点所有的流终止于一个叫做收点的节点其余所有的节点叫做转运点通过每一个弧的流只允许沿着弧的箭头方向流动目标是使得从源到收点的总流量最大ShortestPathProblem最短路问题最短路问题的最普遍的应用在两个点之间寻找最短路这种问题有哪些应用呢？LittletownFireStation里特城消防站实际举例里特城的消防站和某一农场社区间的道路系统LittletownFireStation里特城消防站实际举例里特城的消防站道路系统的网络表述LittletownFireStation里特城消防站实际举例AssumptionsofshortestPathProblem最短路问题的假设

网络中选择一条路,始于某源点终于目标地连接两个节点的连线叫做边（允许任一个方向行进），弧（只允许沿着一个方向行进）和每条边相关的一个非负数，叫做该边的长度目标是为了寻找从源到目标地的最短路MinimumSpanningTreeProblem最小支撑树问题给你网络中的节点，但没有给你边。或者，给你可供选择的边和如果把它插入到网络中后的每条边的正的成本（或者相似的度量）在设计网络时你希望通过插入足够的边，以满足每两个节点之间都存在一条路的需要目标是寻找一种方法，使得在满足要求的同时总成本最小TheSimpleAlgorithm简单的算法选择第一条边：选择成本最低的备选边选择下一条边：在一个已经有一条边连接的节点和另一个还没有边连接的节点之间选择成本最低的备选边重复第二个步骤，直到所有的节点都有一条边（可能会有多于一条边）与其相连此时就得到了最优解（最小支撑树）SomeApplications一些实际应用

电信网络（计算机网络、电话专用线网络、有线电视网络等等）的设计低负荷运输网络的设计，使得网络中提供链接的部分（如铁路、公路等等）的总成本最小高压输电线路网络的设计电器设备线路网络（如数字计算机系统）的设计，使得线路总长度最短连接多个场所的管道网络设计实务应用SessionSummary本讲小结小结网络表示在描绘网络系统中各部分之间关联上非常有用最小费用流问题的特殊类型包括运输问题和指派问题最大流问题的目标是使得从一个特定的起点（源）到一个特定的终点（收点）的总流量最大最短路问题也有始点（源）和终点（目标地），但是，它的目标是从源点到目标地寻找一条总长度最短的路最小支撑树问题的目标是使得为任意