深圳大学管理学院：《运筹学》课程教学资源（PPT课件讲稿）图论（网络最优化问题）运筹学2类 网络最优化问题 Network Optimization Problems

e/Chapter 7 Network Optimization Problems 名七 四络最优化问题

Chapter 7. Network Optimization Problems 第七章. 网络最优化问题

e路奥彻 口法国国家铁路网每年运载约 5000万乘客 口通过网络最优化问题来适应乘 客的喜好,并且调整日运行量 来满足需求 口每年增加收入1500万美元,降 低成本的同时提高了服务质量 口获得了1997年度弗兰茨厄德曼 等奖 Copyright2007@深圳大学管理学院运筹学2

Copyright 2007 © 深圳大学管理学院 运筹学 2 获奖实例 ❑ 法国国家铁路网每年运载约 5000万乘客 ❑ 通过网络最优化问题来适应乘 客的喜好，并且调整日运行量 来满足需求 ❑ 每年增加收入1500万美元，降 低成本的同时提高了服务质量 ❑ 获得了1997年度弗兰茨.厄德曼 一等奖

Table of ontents(柱要内客) e Minimum-Cost Flow Problems(Section 71)(最小费用流问题) .A Case study: The bmz maximum Flow Problen( Section72)例究:Bm公 司的最大流问题) e Maximum Flow Problems(Section 3)最大流闻题 Copyright2007@深圳大学管理学院运筹学3

Copyright 2007 © 深圳大学管理学院 运筹学 3 Minimum-Cost Flow Problems (Section 7.1)(最小费用流问题) A Case Study: The BMZ Maximum Flow Problem (Section 7.2)(案例研究：BMZ公 司的最大流问题) Maximum Flow Problems (Section 7.3)(最大流问题) Table of Contents (主要内容)

Table of ontents(柱要内客) o Shortest path Problems: Littletown Fire Department( Section74)最路闷题 旦鲁城的消队问题) Shortest path problems: general Characteristics( Section74)最题 一特 Shortest Path Problems: Minimizing arah' s Total cost( Sectio7.4)最路间 最小化的总成本问题 Copyright2007@深圳大学管理学院运筹学4

Copyright 2007 © 深圳大学管理学院 运筹学 4 Shortest Path Problems: Littletown Fire Department (Section 7.4)(最短路问题： 里特城的消防队问题) Shortest Path Problems: General Characteristics (Section 7.4)(最短路问题： 一般特征) Shortest Path Problems: Minimizing Sarah’s Total Cost (Section 7.4)(最短路问 题：最小化莎拉的总成本问题) Table of Contents (主要内容)

Table of ontents(柱要内客) o Shortest Path Problems: Minimizing Quick’ s Total time( Section7.4)(最暗 问题:最小化克公司总时间问题 mInimum Spanning Trees: The Modern gorp. Problem( Section75)最小树 题:量公司问题) Copyright2007@深圳大学管理学院运筹学5

Copyright 2007 © 深圳大学管理学院 运筹学 5 Shortest Path Problems: Minimizing Quick’s Total Time (Section 7.4)(最短路 问题：最小化奎克公司总时间问题) Minimum Spanning Trees: The Modern Corp. Problem (Section 7.5)(最小支撑树 问题：摩登公司问题) Table of Contents (主要内容)

e Distribution unlimited co Problem eThe distribution unlimited co has two factories producing a product th at needs to be shipped to two warehouses (3 限公司有两个工厂生产产品,这 产品鲁要理到两个仓库里 喻 Factory1 produces80 units。(工 厂生产80个单健 e Factory 2 produces 70 units. 厂生产70个单位)最小费用流问题 Copyright2007@深圳大学管理学院运筹学6

Copyright 2007 © 深圳大学管理学院 运筹学 6 Distribution Unlimited Co. Problem The Distribution Unlimited Co. has two factories producing a product that needs to be shipped to two warehouses (无 限配送公司有两个工厂生产产品，这些 产品需要运到两个仓库里) Factory 1 produces 80 units. (工 厂1生产80个单位) Factory 2 produces 70 units. (工 厂2生产70个单位)

e Distribution unlimited co Problem Warehouse i needs 0 units 仓露要60个单位 Warehouse 2 needs 90 units 仓2要90个单包 There are rail links directly from Factory 1 to Warehouse 1 and Factory 2 to Warehouse 2.(在厂仓库间以录工厂和 仓之间各有一条铁暗输轨道 Copyright2007@深圳大学管理学院运筹学7

Copyright 2007 © 深圳大学管理学院 运筹学 7 Distribution Unlimited Co. Problem Warehouse 1 needs 60 units. (仓库1需要60个单位) Warehouse 2 needs 90 units. (仓库2需要90个单位) There are rail links directly from Factory 1 to Warehouse 1 and Factory 2 to Warehouse 2. (在工厂1和仓库1之间以及工厂2和 仓库2之间各有一条铁路运输轨道)

e Distribution unlimited co Problem iNdependent truckers are availlable to ship up to 50 units from each factory to the distribution center, and then 50 units from the distribution center to each wareh。use(卡司机至 以从工厂50个单位到己中 D,后可以从中心50 个单包到仓库 Copyright2007@深圳大学管理学院运筹学8

Copyright 2007 © 深圳大学管理学院 运筹学 8 Distribution Unlimited Co. Problem Independent truckers are available to ship up to 50 units from each factory to the distribution center, and then 50 units from the distribution center to each warehouse. (卡车司机至多可 以从工厂运输50个单位到配送中 心，然后可以从配送中心运输50 个单位到仓库)

e The Distribution network ■■■ 80 units F1 W1 60 units roduced needed DC 70 units F2 w2)90 units produced ■■■ needed Copyright2007@深圳大学管理学院运筹学9

Copyright 2007 © 深圳大学管理学院 运筹学 9 The Distribution Network

e Data for Distribution network 80 units Fl S700/unit 60 units pr oduce W1 needed S300/unit $200/ur [50TRits max I [50 units max J DC $400/unit. $400/unit [50 units max I [50 Units max I 70 units S900/unit 90 units produced F2 W2 needed Copyrigh2007c深圳大学管理学院运筹学10

Copyright 2007 © 深圳大学管理学院 运筹学 10 Data for Distribution Network