《数据、模型与决策》课件.ppt

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最短路问题的假设网络中选择一条路,始于某源点终于目标地连接两个节点的连线叫做边（允许任一个方向行