运筹学chapter 5.pdf

Operations Research 第五章 图与网络分析 cmLiu@shufe Operations Research 第五章 图与网络分析 5.1 图的基本概念 5.2 树与最小树 5.3 最短路问题 5.4 网络最大流问题 5.5 最小费用最大流问题 5.6 电子表格的建模和求解 5.7 案例分析 救护车行程安排 cmLiu@shufe Operations Research 5.1 图的基本概念 在自然界和人类社会中，大量的事物以及事物间的关系都 可以用图来加以描述。一般来讲，图论中的图是由点以及 点与点之间的连线所构成的，通常用点代表所研究的对象， 用线代表两个对象之间的关系，至于图中点的相对位置如 何，点与点之间的连线是长还是短、是曲线还是直线，对 于反映对象之间的关系，并不十分重要。因此，图论中的 图与几何中的图形不是等价的。 cmLiu@shufe Operations Research 5.1.1 图的若干示例 例5.1 航线分布情况 下图描述的是我国上海到世界几个主要城市的航线示意图。用点代表 城市，点与点之间的连线代表两个城市之间的航班线路。类似的例子 还有铁路交通图、电话线分布图、煤气管道图、钻井平台与输油管道 的分布图。 大阪 新加坡 北京 纽约 巴黎 悉尼 cmLiu@shufe Operations Research 5.1.1 图的若干示例 例5.2 球队比赛问题 有甲、乙、丙、丁、戊五个球队，他们之间的比赛情况如下：甲队分 别和另外四只球队打过比赛，乙队和甲、丙、丁三个球队打过比赛， 丙队和甲、乙、丁、戊4个球队打过比赛，丁和甲、乙、丙、戊4个球 队打过比赛，戊和甲、丙、丁三个球队打过比赛。若将上述过程用图 加以表示，每一个球队用一个点表示，若两个球队之间比赛过，就用 一条线来表示，这条线不能通过其它的点，如下图。 甲 乙 戊 丙 丁 球队比赛示意图 cmLiu@shufe Operations Research 5.1.1 图的若干示例  上述两个例子中涉及到的对象具有“对称性”，即如果A对B具有某 种关系，B对A也具备同样的关系。  但是有些对象具有“非对称性”，如例5.2中我们考虑两队之间获胜 的关系。对于这种情况，我们就用有向线段表示球队之间的胜负关系。 箭头指向哪个队，意味着这个队在比赛中落败，如下图，我们很容易 的看出各队之间的比赛以及胜负情况。 甲 乙 戊 丙