北京交通大学：《管理运筹学》课程教学课件（讲稿）第10章 图与网络优化 Graph Theory and Network Optimization 第一节 图的基本概念 第二节 最小树问题

09.3某公司打算向它的三个营业区增设六个销售店.每个营业区至少增设一个。从各区赚取的利润（单位：万元）与增设的销售店个数有关，其数据如下。表9—6销售店增加数A区利润B区利润C区利润01002001501200210160228022017032251803304340230200试求各区应分配几个增设的销售店，才能使总利润最大，其值是多少？解将问题按营业区数分为3个阶段.阶段变量k=12.3，第1、2、3个阶段分别为A、B、C营业区分配增设的销售店。状态变量s表示给第k至第3个营业区增设销售店的数量：决策变量表示给第k个营业区增设销售店的数量：状态转移方程：S+1=S一阶段指标P（）表示给第k个营业区增设个销售店赚取的利润：最优值函数f（s）表示给第k至第3个营业区增设S个销售店赚取的最大利润：f（s）=max[p（x）+fh+1（s+1)].k=3.2.1TS递推公式：f4(s4)=0

kpe()f#+1(st+1)fa(se)akp(a)+fh+1(st+1)Skk11600160160112221700170170333031801801804402002002004212101603703701-21017038033801.2222016038012101803901,2422203901703902322516038512102004102220180400514103225170395423016039012004106102280390670167103.433303807104710340370由计算表格的结果可以看出，赚取的最大利润为710万元按计算表格的顺序反推算，可知最优增设方案有三个：(1)x*=3,x2=1,3=2;(2)x*=3,x2=2,3=1;二（3)x*=4,2=1,α3=1。北京父通大学

北京交通大学经济管理学院nics and ManagomentSchool of EcononBoijing Jiaotong UniversityA区利润B区利润C区利润销售店增加数0200210160128022017023301802253340200230北京交通大学

销售店增加数 A区利润 B区利润 C区利润 0 1 2 3 200 280 330 340 210 220 225 230 160 170 180 200

北京交通大学经济管理学院School of Ecorhics andManagomentBojing Jiaotong University第10章图与网络优化Graph Theory and Network Optimization北京交通大学

第 10 章图与网络优化 Graph Theory and Network Optimization

北京交通大学经济管理学院提纲School of Econics andManagomentBojing Jiaotong University1.图的基本概念2.最小树问题3.最短路问题4.最大流问题5.最小费用最大流问题北京交通大学

提 纲 1.图的基本概念 2.最小树问题 3.最短路问题 4.最大流问题 5.最小费用最大流问题

北京交通大学经济管理学院SchoollofEicsandManagomentBoijingJiaotong University图论是应用十分广泛的运筹学分支它已经广泛地应用在物理学、化学、控制论、信息论、经营管理、电子计算机等各个领域。北京交通大学

图论是应用十分广泛的运筹学分支, 它已经广泛地应用在物理学、化学、 控制论、信息论、经营管理、电子计 算机等各个领域

北京交通大学经济管理学院哥尼斯堡七桥问题SchoolIofEconnics andManagomentBoijingJiaotongUniversityB问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点题:能否从某一点开始一笔画出这个图形,最后回到原点.而不重复北京交通大学

哥尼斯堡七桥问题 问题:一个散步者能否从任一块陆地出发, 走过 七座桥, 且每座桥只走过一次, 最后回到出发 点? B A C D 问题:能否从某一点开始一笔画出这个图形, 最后回 到原点,而不重复

BB1736年，欧拉将这个问题抽象成一笔画问题，即能否从某一点开始不重复地一笔画出这个图形，最终回到原点欧拉在他的论文中证明了这是不可能的，这就是古典图论中的第一个著名问题为什么？怎样判断任意一个图形能否一笔画出？北京交通大学

1736年,欧拉将这个问题抽象成一笔画问题,即能否从某 一点开始不重复地一笔画出这个图形,最终回到原点. 欧拉在他的论文中证明了这是不可能的,这就是古典图 论中的第一个著名问题. 为什么?怎样判断任意一个图形能否一笔画出? B A C D A B C D

北京交通大学例：中国邮路问题经济管理学院SchoollofEoicsandMarsagementBoijing Jiaotong University一个邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。问题：他如何走？点：路口;边：两路口之间道路，第道路长e;。问题：求一个圈，过每边至少一次，并使圈的长度最短.北京交通大学

例：中国邮路问题 一个邮递员送信，要走完他所负责的全部街道分送 信件，最后返回邮局。邮递员都会本能地以尽可能少的 行程完成送信任务。 问题：他如何走？ 点：路口； 边：两路口之间道路，第i条道路长ei。 问题：求一个圈, 过每边至少一次, 并使圈的长度最 短

北京交通大学例：四色猜想经济管理学院SchoollofEoics and ManagomentBoijingJiaotongUniversity能否用四种颜色给地图染色，使相邻的国家有不同的颜色。点：国家;边：两个国家有公共边界。问题：能否用四种颜色给平面图的点染色，使有公共边的点有不同的颜色。北京交通大学

例：四色猜想 能否用四种颜色给地图染色，使相邻的国家有不 同的颜色。 点：国家； 边：两个国家有公共边界。 问题：能否用四种颜色给平面图的点染色，使有公共 边的点有不同的颜色