【数模集】 图论常用算法 基础

浅夏110

【数模集】 图论常用算法 基础
8 G) f# ?  b6 Q) j; o
  ?/ P! P$ V# x$ _
1 t- F1 I9 R4 X1 o) M: ~图与网络优化概述
6 f! G; M2 l- ?3 c, q
; m- w" f; C3 B! N% m

         图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。

我们首先通过一些例子来了解网络优化问题。

例1  最短路问题（SPP－shortest path problem）

    一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。（最短路+迪杰斯特拉）

例2  公路连接问题

   某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？（最小代价生成树）

例3  指派问题（assignment problem）
8 V' `9 [1 d8 [. U2 O: k% u. a     一家公司经理准备安排几名员工去完成项任务， 每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。 如何分配工作方案可以使总回报最大？（基础目标规划lingo可解或最小费用最大流解或匈牙利算法）

# D+ L8 |6 w" q) L- q6 J5 g3 h5 @例4 中国邮递员问题（CPP－chinese postman  problem）
    一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国梅谷教授1960年首先提的，所以国际上称之为中国邮递员问题。（整数规划，最小代价生成树，复杂可用DNA算法等）

例5  运输问题（transportation problem）

   某种原材料有个产地，现在需要将原材料从产地运往个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？（lingo目标规划可解）

上述问题有两个共同的特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题；二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network）。与图和网络相关的最优化问题就是网络最优化或称网络优化 （netwok optimization）问题。

! a3 n6 L4 c1 }  e

4 `- b1 e, {3 t